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

The alternating sign matrix conjecture states that the number of alternating sign matrices is

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 , 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