An algorithm for the permanent of circulant matrices

The permanent of an n x n matrix A = (a;j) is the matrix function ( 1) per A = ∑ al1r(1)••• a .. ",( .. )".C~" where the summation is over all permutations in the symmetric group, S ... An n x n matrix A is a circulant if there are scalars ab ... ,a,. such that (2) A= ∑ a;pi-l where P is the n x n permutation matrix corresponding to the cycle (12• .. n) in s". In general the computation of the permanent function is quite difficult chiefly because it is not invariant under addition of a multiple of one row to another. Using the principle of "inclusion and exclusion", Ryser [6, p. 27J gave an expansion for the permanent. Also the Laplace expansion is available for the permanent [2, p. 20]. Neither of these methods are particularly efficient. In [4J Mine considered the permanents of matrices with entires either 0 or 1. Mine also studied tridiagonal circulants in [5J]. Metropolis, Stein, and Stein [3] have given recurrence relations for evaluating the permanents of circulant matrices (2) where the first k scalars are 1 and the remaining ones are O. Permanents of circulant matrices were also studied by Tinsley [7].