LINEAR ALGEBRA AND ITS APPLICATIONS (65219J0), 2002
Autori: Codenotti B., Resta G.
Tipo: Articoli su riviste ISIArea di disciplina: Computer Science and Engineering
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 3 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 4 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.