Alternating sign matrix

In mathematics, an alternating sign matrix is an square matrix made up of 0s, 1s, and −1s in such a manner than

• every row and column sums to 1,
• the nonzero entries of each row, read from left to right, begin with 1 and alternate in sign,
• the nonzero entries of each column, read from top to bottom, begin with 1 and alternate in sign.

These matrices arise naturally when using Dodgson condensation to compute a determinant, and were first defined by William Mills, David Robbins, and Howard Rumsey.

For example, the permutation matrices are alternating sign matrices, as is

<math>

\begin{bmatrix} 0&0&1&0\\ 1&0&0&0\\ 0&1&-1&1\\ 0&0&1&0 \end{bmatrix}. <math>

The alternating sign matrix conjecture states that the number of <math>n\times n<math> alternating sign matrices is

<math>

\frac{1! 4! 7! \cdots (3n-2)!}{n! (n+1)! \cdots (2n-1!)}. <math>

This was proved by Doron Zeilberger in 1992. In 1995, Greg Kuperberg gave another proof that using the square ice model from statistical mechanics.

References and further reading

• Bressoud, David M., Proofs and Confirmations, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
• Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637–646.
• Kuperberg, Greg, Another proof of the alternating sign matrix conjecture, International Mathematics Research Notes (1996), 139–150.
• Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73–87.
• Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340–359.
• Robbins, David P., The story of <math>1, 2, 7, 42, 429, 7436, \cdots<math>, The Mathematical Intelligencer, 13 (1991), 12–19.
• Zeilberger, Doron, Proof of the alternating sign matrix conjecture, Electronic Journal of Combinatorics 3 (1996), R13.
• Zeilberger, Doron, Proof of the refined alternating sign matrix conjecture, New York Journal of Mathematics 2 (1996), 59–68.

External links

• Alternating sign matrix entry in MathWorld