Alternating sign matrix

From HandWiki
[math]\displaystyle{ \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} }[/math]
The seven alternating sign matrices of size 3

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.[citation needed] 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.

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
[math]\displaystyle{ \begin{bmatrix} 0&0&1&0\\ 1&0&0&0\\ 0&1&-1&1\\ 0&0&1&0 \end{bmatrix}. }[/math]

Alternating sign matrix theorem

The alternating sign matrix theorem states that the number of [math]\displaystyle{ n\times n }[/math] alternating sign matrices is

[math]\displaystyle{ \prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} = \frac{1!\, 4! \,7! \cdots (3n-2)!}{n!\, (n+1)! \cdots (2n-1)!}. }[/math]

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

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.[5] This conjecture was proved in 2010 by Cantini and Sportiello.[6]

References

  1. Zeilberger, Doron, "Proof of the alternating sign matrix conjecture", Electronic Journal of Combinatorics 3 (1996), R13.
  2. Kuperberg, Greg, "Another proof of the alternating sign matrix conjecture", International Mathematics Research Notes (1996), 139-150.
  3. "Determinant formula for the six-vertex model", A. G. Izergin et al. 1992 J. Phys. A: Math. Gen. 25 4315.
  4. Fischer, Ilse (2005). "A new proof of the refined alternating sign matrix theorem". Journal of Combinatorial Theory, Series A 114 (2): 253–264. doi:10.1016/j.jcta.2006.04.004. Bibcode2005math......7270F. 
  5. Razumov, A.V., Stroganov Yu.G., Spin chains and combinatorics, Journal of Physics A, 34 (2001), 3185-3190.
  6. L. Cantini and A. Sportiello, Proof of the Razumov-Stroganov conjectureJournal of Combinatorial Theory, Series A, 118 (5), (2011) 1549–1574,

Further reading

External links