Alternating Sign Matrices

1. Definition

An alternating sign matrix (ASM) is a square matrix whose entries all belong to $\{-1,0,1\}$ such that the sum of each row and column is 1 and the non-zero entries in each row and column alternate in sign. We say an $n \times n$ alternating sign matrix is of order $n$.

2. Examples

Alternating sign matrices of order $3$:

$\begin{pmatrix} 0 &0 &1 \\0 &1 &0\\1 &0 &0\end{pmatrix} \; \; \begin{pmatrix} 0 &0 &1 \\1 &0 &0\\ 0 &1 &0\end{pmatrix} \; \; \begin{pmatrix} 0 &1 &0 \\0 &0 &1\\1 &0 &0\end{pmatrix} \; \; \begin{pmatrix} 0 &1 &0 \\1 &-1 &1\\0 &1 &0\end{pmatrix}\; \; $$\begin{pmatrix} 0 &1 &0 \\1 &0 &0\\0 &0 &1\end{pmatrix} \; \; \begin{pmatrix} 1 &0 &0 \\0 &0 &1\\0 &1 &0\end{pmatrix} \; \; \begin{pmatrix} 1 &0 &0 \\0 &1 &0\\0 &0 &1\end{pmatrix}$.

Alternating sign matrix of order $5$:

$\begin{pmatrix} 0& 0& 0 &1 &0 \\ 0& 1& 0 &-1 &1 \\ 1& -1& 0 &1 &0 \\ 0& 0& 1 &0 &0 \\ 0& 1& 0 &1 &0 \end{pmatrix}$

3. Properties

The number of alternating sign matrices of size $n$ is $$\prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!}.$$ This result was known as the alternating sign matrix conjecture before being proved in [Ze92].

4. Remarks

$\left(\begin{smallmatrix} 0 &0 &1 \\1 &0 &0\\ 0 &1 &0\end{smallmatrix}\right)\rightarrow\left(\begin{smallmatrix} 0 &0 &0 &0 \\0 &0 &0 &1\\ 0 &1 &1 &2 \\ 0 &1 &2 &3 \end{smallmatrix}\right)$

$\left(\begin{smallmatrix} 0 &0 &0 &0 \\0 &0 &0 &1\\ 0 &1 &1 &2 \\ 0 &1 &2 &3\end{smallmatrix}\right)\rightarrow\left(\begin{smallmatrix} 0 &1 &2 &3 \\1 &2 &3 &2\\ 2 &1 &2 &1 \\ 3 &2 &1 &0\end{smallmatrix}\right)$

[BCS].

5. Statistics

We have the following 21 statistics on Alternating sign matrices in the database:

The number of entries equal to $-1$ in the alternating sign matrix.
The column of the unique '1' in the first row of the alternating sign matrix.
The inversion number of the alternating sign matrix.
The rank of the alternating sign matrix in the alternating sign matrix poset.
The size of the orbit of an alternating sign matrix under gyration.
The determinant of an alternating sign matrix.
The row of the unique '1' in the first column of the alternating sign matrix.
The number of entries equal to positive one in the alternating sign matrix.
The column of the unique '1' in the last row of the alternating sign matrix.
The row of the unique '1' in the last column of the alternating sign matrix.
The osculating paths major index of an alternating sign matrix.
The positive inversions of an alternating sign matrix.
The maximal sum of entries on a diagonal of an alternating sign matrix.
The number of alternating sign matrices with the same antidiagonal sums.
The number of nonzero entries in an alternating sign matrix.
The maximal number of nonzero entries on a diagonal of an alternating sign matrix....
The number of distinct diagonal sums of an alternating sign matrix.
The trace of an alternating sign matrix.
The number of ones on the main diagonal of an alternating sign matrix.
The number of zeros on the main diagonal of an alternating sign matrix.
The number of maximal entries in the last diagonal of the monotone triangle.

6. Maps

We have the following 11 maps in the database:

to semistandard tableau
to left key permutation
rotate counterclockwise
rotate clockwise
transpose
gyration
to Dyck path
to alternating sign matrix
to alternating sign matrix
link pattern
to symmetric ASM

7. Monotone triangles

Define $\left(s_{ij}\right)_{i,j=1, \dots, n}$ to be the $n \times n$ matrix whose entries are the partial sums of the columns (top to bottom) of an $n \times n$ alternating sign matrix. The monotone triangle of an alternating sign matrix is a triangular array whose $i^{\text{th}}$ row consists of the values $j$ in which the entry $s_{ij}=1$.

$\left(\begin{smallmatrix} 0& 0& 0 &1 &0 \\ 0& 1& 0 &-1 &1 \\ 1& -1& 0 &1 &0 \\ 0& 0& 1 &0 &0 \\ 0& 1& 0 &1 &0 \end{smallmatrix}\right)\quad\quad\rightarrow\begin{smallmatrix}&&&&&&&&4&&&&&&&&\\&&&&&&&2&&5&&&&&&&\\&&&&&&1&&4&&5&&&&&&\\&&&&&1&&3&&4&&5&&&&&\\&&&&1&&2&&3&&4&&5&&&&\end{smallmatrix}$

8. Dyck Path Tuples

Applying Mp00007 to each row in an alternating sign matrix, you can construct a tuple of nested dyck paths.

DyckPathTuples.png

9. References

[BCS]   Phillip Biane, Luigi Cantini, and Andrea Sportiello, Doubly-refined enumeration of Alternating Sign Matrices and determinants of 2-staircase Schur functions, http://arxiv.org/pdf/1101.3427v1.pdf .

[Ze92]   D. Zeilberger, Proof of the alternating sign matrix conjecture, Electronic Journal of Combinatorics 3 (1996), R13.

10. Sage examples


CategoryCombinatorialCollection