Alternating sign matrix

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

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

File:Matrice signes alternants 4x4.svg

:$$

\begin{bmatrix}

0&0&1&0\\

1&0&0&0\\

0&1&-1&1\\

0&0&1&0

\end{bmatrix}.

The alternating sign matrix theorem states that the number of $n\backslash 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, … {{OEIS|id=A005130}}.

This theorem was first proved by Doron Zeilberger in 1992.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. In 1995, Greg Kuperberg gave a short proofKuperberg, Greg, [http://arxiv.org/abs/math.CO/9712207 "Another proof of the alternating sign matrix conjecture"], International Mathematics Research Notes (1996), 139-150. 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."Determinant formula for the six-vertex model", A. G. Izergin et al. 1992 J. Phys. A: Math. Gen. 25 4315. In 2005, a third proof was given by Ilse Fischer using what is called the operator method.{{Cite journal|last=Fischer|first=Ilse|title=A new proof of the refined alternating sign matrix theorem|journal=Journal of Combinatorial Theory, Series A|year=2005|volume=114|issue=2|pages=253–264|doi=10.1016/j.jcta.2006.04.004|arxiv=math/0507270|bibcode=2005math......7270F}}

In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model (FPL) and ASMs.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.

This conjecture was proved in 2010 by Cantini and Sportiello.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,

{{reflist}}

• 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, [https://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., 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, [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}}
• Robbins, David P., The story of $1,\; 2,\; 7,\; 42,\; 429,\; 7436,\; \backslash dots$, The Mathematical Intelligencer, 13 (2), 12–19 (1991), {{doi|10.1007/BF03024081}}.
• 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.

• [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

{{Matrix classes}}

Category:Matrices (mathematics)

Category:Enumerative combinatorics