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. 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 .

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

:$\begin 0&0&1&0\\ 1&0&0&0\\ 0&1&-1&1\\ 0&0&1&0 \end.$

Alternating sign matrix theorem

The ''alternating sign matrix theorem'' states that the number of $n\times n$ alternating sign matrices is
:$\prod_^\frac = \frac.$
The first few terms in this sequence for ''n'' = 0, 1, 2, 3, … are
:1, 1, 2, 7, 42, 429, 7436, 218348, … .

This theorem was first proved by Doron Zeilberger in 1992. In 1995, Greg Kuperberg gave a short proof 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. In 2005, a third proof was given by Ilse Fischer using what is called the ''operator method''.

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.
This conjecture was proved in 2010 by Cantini and Sportiello.L. Cantini and A. Sportiello
Proof of the Razumov-Stroganov conjecture
'Journal of Combinatorial Theory, Series A'', 118 (5), (2011) 1549–1574,

References

Further reading

* Bressoud, David M., ''Proofs and Confirmations'', MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
* Bressoud, David M. and Propp, James
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
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.
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,
* Robbins, David P., The story of $1, 2, 7, 42, 429, 7436, \dots$, ''The Mathematical Intelligencer'', 13 (2), 12–19 (1991), .
* Doron Zeilberger, Zeilberger, Doron
Proof of the refined alternating sign matrix conjecture
''New York Journal of Mathematics'' 2 (1996), 59–68.

External links

entry in MathWorld

Alternating sign matrices
entry in th
FindStat
database

{{Matrix classes

Matrices
Enumerative combinatorics