View source for Alternating sign matrix

{{distinguish|Alternant matrix}}
{{Image frame|width=340|align=right|caption=The seven alternating sign matrices of size 3
|content=<math>\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>}}
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 matrix|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 P. Robbins|David Robbins]], and Howard Rumsey in the former context.

==Example==
An example of an alternating sign matrix (that is not also a permutation matrix) is

[[File:Matrice signes alternants 4x4.svg|thumbnail|Puzzle picture]]

:<math>
\begin{bmatrix} 
0&0&1&0\\
1&0&0&0\\
0&1&-1&1\\
0&0&1&0
\end{bmatrix}.
</math>

==Alternating sign matrix conjecture==
The ''alternating sign matrix conjecture'' states that the number of <math>n\times n</math> alternating sign matrices is
:<math>
\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 (number)|1]], 1, [[2 (number)|2]], [[7 (number)|7]], [[42 (number)|42]], 429, 7436, 218348, … {{OEIS|id=A005130}}.

This conjecture was first proved by [[Doron Zeilberger]] in 1992.<ref>Zeilberger, Doron, [http://www.combinatorics.org/Volume_3/Abstracts/v3i2r13.html Proof of the alternating sign matrix conjecture], ''[http://www.combinatorics.org/ Electronic Journal of Combinatorics]'' 3 (1996), R13.</ref>  In 1995, [[Greg Kuperberg]] gave a short proof<ref>[[Greg Kuperberg|Kuperberg, Greg]], [http://front.math.ucdavis.edu/math.CO/9712207 Another proof of the alternating sign matrix conjecture], ''International Mathematics Research Notes'' (1996), 139-150.</ref> 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.<ref>Determinant formula for the six-vertex model, A. G. Izergin et al. 1992 J. Phys. A: Math. Gen. 25 4315.</ref>

==Razumov–Stroganov conjecture==

In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model (FPL) and ASMs.<ref>Razumov, A.V., Stroganov Yu.G., [https://arxiv.org/abs/cond-mat/0012141 Spin chains and combinatorics], ''Journal of Physics A'', '''34''' (2001), 3185-3190.</ref>
This conjecture was proved in 2010 by Cantini and Sportiello.<ref>L. Cantini and A. Sportiello, [https://arxiv.org/abs/1003.3376 Proof of the Razumov-Stroganov conjecture]''Journal of Combinatorial Theory, Series A'', '''118 (5)''', (2011) 1549–1574,</ref>

==References==
{{reflist}}

==Further reading==
* [[David Bressoud|Bressoud, David M.]], ''Proofs and Confirmations'', MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
* [[David Bressoud|Bressoud, David M.]] and Propp, James, [http://www.ams.org/notices/199906/fea-bressoud.pdf How the alternating sign matrix conjecture was solved], ''Notices of the American Mathematical Society'', 46 (1999), 637–646.
* Mills, William H., [[David P. Robbins|Robbins, David P.]], and Rumsey, Howard Jr., Proof of the Macdonald conjecture, ''Inventiones Mathematicae'', 66 (1982), 73–87.
* Mills, William H., [[David P. Robbins|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, [https://arxiv.org/abs/math/0208125v1 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., [https://arxiv.org/abs/math/0104216 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}}
* [[David P. Robbins|Robbins, David P.]], The story of <math>1, 2, 7, 42, 429, 7436, \dots</math>, ''The Mathematical Intelligencer'', 13 (2), 12–19 (1991), {{doi|10.1007/BF03024081}}.
* [[Doron Zeilberger|Zeilberger, Doron]], [http://nyjm.albany.edu:8000/j/1996/2-4.pdf Proof of the refined alternating sign matrix conjecture], ''New York Journal of Mathematics'' 2 (1996), 59–68.

==External links==
* [http://mathworld.wolfram.com/AlternatingSignMatrix.html Alternating sign matrix] entry in [[MathWorld]]
* [http://www.findstat.org/AlternatingSignMatrices Alternating sign matrices] entry in the [http://www.findstat.org/ FindStat] database

[[Category:Matrices]]
[[Category:Enumerative combinatorics]]