Alternating sign 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.^[1] 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

The permutation matrices are precisely the alternating sign matrices that don't contain $-1$ .

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

{\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.^[2] In 1995, Greg Kuperberg gave a short proof^[3] 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.^[4] In 2005, a third proof was given by Ilse Fischer using what is called the operator method.^[5]

Razumov–Stroganov problem

In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model and alternating sign matrices.^[6] This conjecture was proved in 2010 by Cantini and Sportiello.^[7]

Alternating sign matrix

Examples

Alternating sign matrix theorem

Razumov–Stroganov problem

References

Further reading

External links

Related Articles