Smith normal form and combinatorics

-
Richard Stanley, MIT

Please note special day (Friday) and location (Fine 224).  If $A$ is an $m\times n$ matrix over a PID $R$ (and sometimes more general rings), then there exists an $m\times m$ matrix $P$ and an $n\times n$ matrix $Q$, both invertible over $R$, such that $PAQ$ is a matrix that vanishes off the main diagonal, and whose main diagonal elements $e_1,e_2,\dots,e_m$ satisfy $e_i|e_{i+1}$ in $R$. The matrix $PAQ$ is called a \emph{Smith normal form} (SNF) of $A$. The SNF is unique up to multiplication of the $e_i$'s by units in $R$. We will discuss some aspects of SNF related to combinatorics. In particular, we will give examples of SNF for some combinatorially interesting matrices. We also discuss a theory of SNF for random matrices over the integers recently developed by Yinghui Wang.