Alternating sign matrix

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

${\begin{bmatrix}0&0&1&0\\1&0&0&0\\0&1&-1&1\\0&0&1&0\end{bmatrix}}.$

The Alternating Sign Matrix Conjecture states that the number of $n\times n$ alternating sign matrices is

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

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 &amph; 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 $1,2,7,42,429,7436,\cdots$, 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