How fast can one compute the permanent of circulant matrices? Original Research Article

In this paper we address the problem of computing the permanent of (0,1)-circulant matrices. We investigate structural properties of circulant matrices, showing that (i) if they are dense enough, then they contain large arbitrary submatrices, and (ii) if they are very sparse, then they are not too “far” from convertible matrices. Building upon (ii), we then develop an efficient algorithm, which allows us to compute permanents of very sparse circulants of size up to 200.