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.[1] 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.
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
The alternating sign matrix theorem states that the number of alternating sign matrices is
The first few terms in this sequence for n = 0, 1, 2, 3, … are
This theorem was first proved by Doron Zeilberger in 1992.[2] In 1995, Greg Kuperberg gave a short proof[3] 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.[4] In 2005, a third proof was given by Ilse Fischer using what is called the operator method.[5]
In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model (FPL) and ASMs.[6] This conjecture was proved in 2010 by Cantini and Sportiello.[7]