Smith Normal Form In Combinatorics
Let R be a commutative ring (with identity) and A an n × n matrix over R. Suppose there exist n × n matrices P, Q invertible over R for which PAQ is a diagonal matrix diag(α1, . . . , αr, 0, . . . , 0), where αi divides αi+1 in R. We then call PAQ a Smith normal form (SNF) of A. If R is a PID then an SNF always exists and is unique up to multiplication by units.
We will survey some connections between SNF and combinatorics. Topics will include (1) the general theory of SNF, (2) a close connection between SNF and chip firing in graphs, (3) the SNF of a random matrix of integers (joint work with Yinghui Wang), (4) SNF of special classes of matrices, including some arising in the theory of symmetric functions and the theory of hyperplane arrangements, and (5) some open problems dealing with SNF.