Alternating sign matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Not to be confused with Alternant matrix.
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. 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.

Example[edit]

An example of an alternating sign matrix (that is not also 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 conjecture[edit]

The alternating sign matrix conjecture 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 OEIS).

This conjecture 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,[3] which solves recurrence relations due to Vladimir Korepin.[4]

Razumov–Stroganov conjecture[edit]

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[edit]

  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. ^ V. E. Korepin, Calculation of norms of Bethe wave functions, Comm. Math. Phys. Volume 86, Number 3 (1982), 391-418.
  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[edit]

External links[edit]