Computation of sparse circulant permanents via determinants Original Research Article

We consider the problem of computing the permanent of circulant matrices. We apply some recent results on the computation of the number of perfect matchings of small genus graphs in order to show that the permanent of a circulant matrix with three nonzero entries per row is the linear combination of just four determinants (of circulant matrices with the same structure as the original matrix). We also show that the same result holds true for a class of circulant matrices with four nonzero entries per row related to the dimer problem with periodic boundary conditions. Conversely, we give hints at the fact that more general circulants do not share similar properties, and thus should be dealt with by means of radically different approaches.