07 Jun The Remarkable Sequence 1, 2, 7, 42, 429, …: The story of Alternating Sign Matrices
The sequence in the title is given by the following ‘nice’ formula or, in product notation Here denotes the product . This formula was conjectured by Mills, Robbins and Rumsey to count what are called alternating sign matrices (ASMs), which is the subject of this post.
An alternating sign matrix (ASM) of size n is an matrix with entries in the set such that
(i) all row and column sums are equal to 1,
(ii) and the non-zero entries alternate in each row and column.
For instance, there are 7 ASMs of order 3, these are the six permutation matrices (which are matrices with entries either or such that only one appears in each row and each column) and the matrix
By the definition of an ASM it is clear that all permutation matrices are ASMs (why?).
An example of a bigger ASM is given below.
But, how were these matrices first defined? Let zs start with the determinants, that we all know. For example, for the matrix
the determinant is And similarly, for the matrix
the determinant is
We can keep on doing this and more generally, for an matrix, with entries , the determinant of is defined as
Given a matrix , we let denote the matrix that remains when the th row and th column of are deleted. If we remove more than one row or column, then the indices corresponding to those are added to the super- and sub- scripts.
Theorem 1 (Desnanot-Jacobi adjoint matrix theorem) If is an matrix, then
This gives us a way of evaluating determinants, in terms of smaller determinants. Reverend Charles L. Dodgson, better known by his pen name of Lewis Carroll used the Desnanot-Jacobi theorem to give an algorithm for evaluating determinants in terms of determinants.
For instance, we get
In the 1980s, Robbins and Rumsey looked at a generalization of the determinant, which they called the -determinant. They defined
Using the previous observations, they generalized it to an determinant. Their main result in this direction was
Theorem 2 (Robbins-Rumsey) Let be an matrix with entries , be the set of all ASMs, be the inversion number of and be the number of ‘s in . Then
This was the first appearance of an ASM in the literature.
What is the inversion number of an ASM? An easy way to calculate the inversion number is to take products of all pairs of entries for which one of them lies to the right and above the other, and then adding them all up.
In the matrix above, there are seven pairs here whose product is and two pairs whose product is . So the inversion number is .
Let us now make some observations, we look at an ASM below.
There can be only one in the top row (or, first column). Let be the number of ASMs with a at the top of top th column. Some thought will give us, (symmetry). Further, if is the number of ASMs, then . This allows one to check small values to get a formula. Mills, Robbins and Rumsey did exactly that. They first conjectured
This means that the ‘s are uniquely determined by the ‘s when and by . The above conjecture can be reformulated as
From here, knowing that allows one to conjecture the formula we had in the beginning.
But, what about a proof? Doron Zeilberger succeeded in proving the formula (called the ASM conjecture) in 1996 using constant term identities. The proof ran for 84 pages and involved a team of referees to check all the details. Shortly after, Greg Kuperberg gave an alternate proof by exploiting a connection between ASMs and statistical physics. It turned out that physicists have been studying ASMs under a different guise.
In the above picture, we see an ASM on the left and a model called the square ice model on the right. To each entry in an ASM we assign one of the six possibilities of arrangement of the water molecules on the right such that the angle between a bond is either or degrees. We leave it to the reader to see that this is indeed a bijection.
In the late 1980’s Richard Stanley suggested the study of various symmetry classes of ASMs; this let Robbins to conjecture formulas for many of these classes. It turned out to be as difficult as enumrating ASMs, and this study was only recently completed in 2016.
(i) Vertically Symmetric ASMs: , odd (Kuperberg 2002)
(ii) Half-turn Symmetric ASMs: , odd (Razumov-Stroganov 2005), even (Kuperberg 2002)
(iii) Diagonally Symmetric ASMs: , no ‘nice’ formula
(iv) Quarter-turn Symmetric ASMs: , odd (Razumov-Stroganov 2005), even (Kuperberg 2002)
(v) Horizontally and vertically Symmetric ASMs: , odd (Okada 2004)
(vi) Diagonally and Antidiagonally Symmetric ASMs: , odd (Behrend-Fischer-Konvalinka 2017)
(vii) All symmetries: , no ‘nice’ formula.
Here is an example of a vertically symmetric ASM.
Are ASMs worth studying only because they are difficult to enumerate? The answer is of course a big NO! They are intimately related to other objects that combinatorialists study. We give a few examples.
A plane partition in an box is a subset with if and . We usually denote them by a pictorial description, where each entry of the set corresponds to a box. An example is shown below.
A plane partition in an box is called cyclically symmetric if when . George Andrews in 1979 proved that the number of cyclically symmetric plane partitions in an box is An example is given below.
We state only two instances where plane partitions and ASMs appear together.
Theorem 3 (Ayyer-Behrend-FIscher) The number of diagonally and antidiagonally symmetric ASMs (DADSASMs) with occurences of ‘s in the diagonals and antidiagonals in their fundamental region is equal to the number of cyclically symmetric plane partitions in an box.
An example of a DADSASM is given below.
If a plane partition has all the symmetries and is its own complement, then it is called totally symmetric self-complementary plane partitions. For, instance the following is one.
This class of plane partitions inside a box are equinumerous with ASMs!
Another object which is related to ASMs is alternating sign triangles (ASTs), An AST of size is a triangular array such that
(i) the entries are either or ,
(ii) along the columns and rows the non-zero entries alternate,
(iii) the first non-zero entry from the top is a and the rowsums are equal to .
A recent theorem is the following.
Theorem 4 (Ayyer-Behrend-Fischer) The number of ASMs of size is equal to the number of ASTs of order .
There are other combinatorial objects which are equinumerous with ASMs, and one of the major open problems in enumerative combinatorics is to find bijections between such objects. The object of this post was to give a very brief introduction to ASMs, which are beautiful combinatorial objects that are studied by mathematicians in many different ways. A good place to start reading about them is the book Proofs and Confirmations by David Bressoud.
Managing Editor of the English Section, Gonit Sora and Research Fellow, Faculty of Mathematics, University of Vienna.