Alternating sign matrix

Not to be confused with Alternant matrix.

In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant. They are also closely related to the six-vertex model with domain wall boundary conditions from statistical mechanics. They were first defined by William Mills, David Robbins, and Howard Rumsey in the former context.

${\begin{matrix}{\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}\qquad {\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}}\\{\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}}\qquad {\begin{bmatrix}0&1&0\\1&-1&1\\0&1&0\end{bmatrix}}\qquad {\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}}\\{\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}}\qquad {\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}}\end{matrix}}$

The seven alternating sign matrices of size 3

Examples

A permutation matrix is an alternating sign matrix, and an alternating sign matrix is a permutation matrix if and only if no entry equals −1.

An example of an alternating sign matrix that is not a permutation matrix is

Puzzle picture

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

Alternating sign matrix theorem

The alternating sign matrix theorem states that the number of $n\times n$ alternating sign matrices is

$\prod _{k=0}^{n-1}{\frac {(3k+1)!}{(n+k)!}}={\frac {1!\,4!\,7!\cdots (3n-2)!}{n!\,(n+1)!\cdots (2n-1)!}}.$

The first few terms in this sequence for n = 0, 1, 2, 3, … are

1, 1, 2, 7, 42, 429, 7436, 218348, … (sequence A005130 in the OEIS).

This theorem was first proved by Doron Zeilberger in 1992. In 1995, Greg Kuperberg gave a short proof based on the Yang–Baxter equation for the six-vertex model with domain-wall boundary conditions, that uses a determinant calculation due to Anatoli Izergin. In 2005, a third proof was given by Ilse Fischer using what is called the operator method.

Razumov–Stroganov problem

In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model (FPL) and ASMs. This conjecture was proved in 2010 by Cantini and Sportiello.

Further reading

• Bressoud, David M., Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.ISBN 978-0521666466
• Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637–646.
• 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.
• Propp, James, The many faces of alternating-sign matrices, Discrete Mathematics and Theoretical Computer Science, Special issue on Discrete Models: Combinatorics, Computation, and Geometry (July 2001).
• Razumov, A. V., Stroganov Yu. G., Combinatorial nature of ground state vector of O(1) loop model, Theor. Math. Phys., 138 (2004), 333–337.
• Razumov, A. V., Stroganov Yu. G., O(1) loop model with different boundary conditions and symmetry classes of alternating-sign matrices], Theor. Math. Phys., 142 (2005), 237–243, arXiv:cond-mat/0108103
• Robbins, David P., The story of $1,2,7,42,429,7436,\dots$, The Mathematical Intelligencer, 13 (2), 12–19 (1991), doi:10.1007/BF03024081.
• 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
• Alternating sign matrices entry in the FindStat database