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

6. Maps

We have the following 8 maps in the database:

to semistandard tableau
to left key permutation
rotate counterclockwise
rotate clockwise
transpose
gyration
to Dyck path
link pattern

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

AlternatingSignMatrices (last edited 2015-12-17 22:06:01 by AaronCrenshaw)