The Number of Terms in the Permanent and the Determinant of a Generic Circulant Matrix
Hugh Thomas
DOI: 10.1023/B:JACO.0000047292.01630.a6
Abstract
Let A = ( a ij) be the generic n \times n circulant matrix given by a ij = x i + j , with subscripts on x interpreted mod n. Define d( n) (resp. p( n)) to be the number of terms in the determinant (resp. permanent) of A. The function p( n) is well-known and has several combinatorial interpretations. The function d( n), on the other hand, has not been studied previously. We show that when n is a prime power, d( n) = p( n).
Pages: 55–60
Keywords: generic circulant matrix; determinant; permanent
Full Text: PDF
References
1. R. Brualdi and M. Newman, “An enumeration problem for a congruence equation,” J. Res. Nat. Bur. Standards Sect. B 74B (1970), 37-40.
2. \ddot O. E\?gecio\?glu and J. Remmel, “Brick tabloids and the connection matrices between bases of symmetric functions,” Discrete Appl. Math. 34 (1991), 107-120.
3. M. Hall, Jr., “A combinatorial problem on abelian groups,” Proc. Amer. Math. Soc. 3 (1952), 584-587.
4. D. Lehmer, “Some properties of circulants,” J. Number Theory 5 (1973), 43-54.
5. R. Stanley, Enumerative Combinatorics, Volume 2 Cambridge University Press, Cambridge, 1999.
2. \ddot O. E\?gecio\?glu and J. Remmel, “Brick tabloids and the connection matrices between bases of symmetric functions,” Discrete Appl. Math. 34 (1991), 107-120.
3. M. Hall, Jr., “A combinatorial problem on abelian groups,” Proc. Amer. Math. Soc. 3 (1952), 584-587.
4. D. Lehmer, “Some properties of circulants,” J. Number Theory 5 (1973), 43-54.
5. R. Stanley, Enumerative Combinatorics, Volume 2 Cambridge University Press, Cambridge, 1999.