edit this page

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 in the database:

St000065
Alternating sign matrices ⟶ ℤ
The number of entries equal to $-1$ in the alternating sign matrix.
St000066
Alternating sign matrices ⟶ ℤ
The column of the unique '1' in the first row of the alternating sign matrix.
St000067
Alternating sign matrices ⟶ ℤ
The inversion number of the alternating sign matrix.
St000076
Alternating sign matrices ⟶ ℤ
The rank of the alternating sign matrix in the alternating sign matrix poset.
St000134
Alternating sign matrices ⟶ ℤ
The size of the orbit of an alternating sign matrix under gyration.
St000187
Alternating sign matrices ⟶ ℤ
The determinant of an alternating sign matrix.
St000193
Alternating sign matrices ⟶ ℤ
The row of the unique '1' in the first column of the alternating sign matrix.
St000197
Alternating sign matrices ⟶ ℤ
The number of entries equal to positive one in the alternating sign matrix.
St000199
Alternating sign matrices ⟶ ℤ
The column of the unique '1' in the last row of the alternating sign matrix.
St000200
Alternating sign matrices ⟶ ℤ
The row of the unique '1' in the last column of the alternating sign matrix.
St000227
Alternating sign matrices ⟶ ℤ
The osculating paths major index of an alternating sign matrix.
St000332
Alternating sign matrices ⟶ ℤ
The positive inversions of an alternating sign matrix.
St000888
Alternating sign matrices ⟶ ℤ
The maximal sum of entries on a diagonal of an alternating sign matrix.
St000889
Alternating sign matrices ⟶ ℤ
The number of alternating sign matrices with the same antidiagonal sums.
St000890
Alternating sign matrices ⟶ ℤ
The number of nonzero entries in an alternating sign matrix.
St000892
Alternating sign matrices ⟶ ℤ
The maximal number of nonzero entries on a diagonal of an alternating sign matrix....
St000893
Alternating sign matrices ⟶ ℤ
The number of distinct diagonal sums of an alternating sign matrix.
St000894
Alternating sign matrices ⟶ ℤ
The trace of an alternating sign matrix.
St000895
Alternating sign matrices ⟶ ℤ
The number of ones on the main diagonal of an alternating sign matrix.
St000896
Alternating sign matrices ⟶ ℤ
The number of zeros on the main diagonal of an alternating sign matrix.
St000898
Alternating sign matrices ⟶ ℤ
The number of maximal entries in the last diagonal of the monotone triangle.

6. Maps

We have the following 11 maps in the database:

Mp00001
Alternating sign matrices ⟶ Semistandard tableaux
to semistandard tableau
Mp00002
Alternating sign matrices ⟶ Permutations
to left key permutation
Mp00003
Alternating sign matrices ⟶ Alternating sign matrices
rotate counterclockwise
Mp00004
Alternating sign matrices ⟶ Alternating sign matrices
rotate clockwise
Mp00005
Alternating sign matrices ⟶ Alternating sign matrices
transpose
Mp00006
Alternating sign matrices ⟶ Alternating sign matrices
gyration
Mp00007
Alternating sign matrices ⟶ Dyck paths
to Dyck path
Mp00035
Dyck paths ⟶ Alternating sign matrices
to alternating sign matrix
Mp00063
Permutations ⟶ Alternating sign matrices
to alternating sign matrix
Mp00098
Alternating sign matrices ⟶ Perfect matchings
link pattern
Mp00137
Dyck paths ⟶ Alternating sign matrices
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