Alternating Sign Matrices¶

AUTHORS:

• Mike Hansen (2007): Initial version
• Pierre Cange, Luis Serrano (2012): Added monotone triangles
• Travis Scrimshaw (2013-28-03): Added element class for ASM’s and made MonotoneTriangles inherit from GelfandTsetlinPatterns
class sage.combinat.alternating_sign_matrix.AlternatingSignMatrices(n, use_monotone_triangles=True)

Class of all $$n \times n$$ alternating sign matrices.

An alternating sign matrix of size $$n$$ is an $$n \times n$$ matrix of $$0$$‘s, $$1$$‘s and $$-1$$‘s such that the sum of each row and column is $$1$$ and the non-zero entries in each row and column alternate in sign.

Alternating sign matrices of size $$n$$ are in bijection with monotone triangles with $$n$$ rows.

INPUT:

• $$n$$ – an integer, the size of the matrices.
• use_monotone_triangle – (Default: True) If True, the generation of the matrices uses monotone triangles, else it will use the earlier and now obsolete contre-tableaux implementation; must be True to generate a lattice (with the lattice method)

EXAMPLES:

This will create an instance to manipulate the alternating sign matrices of size 3:

sage: A = AlternatingSignMatrices(3)
sage: A
Alternating sign matrices of size 3
sage: A.cardinality()
7


Notably, this implementation allows to make a lattice of it:

sage: L = A.lattice()
sage: L
Finite lattice containing 7 elements
sage: L.category()
Join of Category of finite lattice posets
and Category of finite enumerated sets

Element

alias of AlternatingSignMatrix

cardinality()

Return the cardinality of self.

The number of $$n \times n$$ alternating sign matrices is equal to

$\prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!} = \frac{1! 4! 7! 10! \cdots (3n-2)!}{n! (n+1)! (n+2)! (n+3)! \cdots (2n-1)!}$

EXAMPLES:

sage: [AlternatingSignMatrices(n).cardinality() for n in range(0, 11)]
[1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700]

cover_relations()

Iterate on the cover relations between the alternating sign matrices.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: for (a,b) in A.cover_relations():
....:   eval('a, b')
(
[1 0 0]  [0 1 0]
[0 1 0]  [1 0 0]
[0 0 1], [0 0 1]
)
(
[1 0 0]  [1 0 0]
[0 1 0]  [0 0 1]
[0 0 1], [0 1 0]
)
(
[0 1 0]  [ 0  1  0]
[1 0 0]  [ 1 -1  1]
[0 0 1], [ 0  1  0]
)
(
[1 0 0]  [ 0  1  0]
[0 0 1]  [ 1 -1  1]
[0 1 0], [ 0  1  0]
)
(
[ 0  1  0]  [0 0 1]
[ 1 -1  1]  [1 0 0]
[ 0  1  0], [0 1 0]
)
(
[ 0  1  0]  [0 1 0]
[ 1 -1  1]  [0 0 1]
[ 0  1  0], [1 0 0]
)
(
[0 0 1]  [0 0 1]
[1 0 0]  [0 1 0]
[0 1 0], [1 0 0]
)
(
[0 1 0]  [0 0 1]
[0 0 1]  [0 1 0]
[1 0 0], [1 0 0]
)

from_corner_sum(corner)

Return an alternating sign matrix from a corner sum matrix.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A.from_corner_sum(matrix([[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,2,3]]))
[1 0 0]
[0 1 0]
[0 0 1]
sage: A.from_corner_sum(matrix([[0,0,0,0],[0,0,1,1],[0,1,1,2],[0,1,2,3]]))
[ 0  1  0]
[ 1 -1  1]
[ 0  1  0]

from_height_function(height)

Return an alternating sign matrix from a height function.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A.from_height_function(matrix([[0,1,2,3],[1,2,1,2],[2,3,2,1],[3,2,1,0]]))
[0 0 1]
[1 0 0]
[0 1 0]
sage: A.from_height_function(matrix([[0,1,2,3],[1,2,1,2],[2,1,2,1],[3,2,1,0]]))
[ 0  1  0]
[ 1 -1  1]
[ 0  1  0]

from_monotone_triangle(triangle)

Return an alternating sign matrix from a monotone triangle.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A.from_monotone_triangle([[3, 2, 1], [2, 1], [1]])
[1 0 0]
[0 1 0]
[0 0 1]
sage: A.from_monotone_triangle([[3, 2, 1], [3, 2], [3]])
[0 0 1]
[0 1 0]
[1 0 0]

lattice()

Return the lattice of the alternating sign matrices of size $$n$$, created by LatticePoset.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: L = A.lattice()
sage: L
Finite lattice containing 7 elements

matrix_space()

Return the underlying matrix space.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A.matrix_space()
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

size()

Return the size of the matrices in self.

TESTS:

sage: A = AlternatingSignMatrices(4)
sage: A.size()
4

sage.combinat.alternating_sign_matrix.AlternatingSignMatrices_n(n)

For old pickles of AlternatingSignMatrices_n.

EXAMPLES:

sage: sage.combinat.alternating_sign_matrix.AlternatingSignMatrices_n(3)
doctest:...: DeprecationWarning: this class is deprecated. Use sage.combinat.alternating_sign_matrix.AlternatingSignMatrices instead
See http://trac.sagemath.org/14301 for details.
Alternating sign matrices of size 3

class sage.combinat.alternating_sign_matrix.AlternatingSignMatrix(parent, asm)

An alternating sign matrix.

An alternating sign matrix is a square matrix of $$0$$‘s, $$1$$‘s and $$-1$$‘s such that the sum of each row and column is $$1$$ and the non-zero entries in each row and column alternate in sign.

ASM_compatible(B)

Return True if self and B are compatible alternating sign matrices in the sense of [EKLP92]. (If self is of size $$n$$, B must be of size $$n+1$$.)

In [EKLP92], there is a notion of a pair of ASM’s with sizes differing by 1 being compatible, in the sense that they can be combined to encode a tiling of the Aztec Diamond.

REFERENCES:

 [EKLP92] (1, 2, 3, 4) N. Elkies, G. Kuperberg, M. Larsen, J. Propp, Alternating-Sign Matrices and Domino Tilings, Journal of Algebraic Combinatorics, volume 1 (1992), p. 111-132.

EXAMPLES:

sage: A = AlternatingSignMatrix(matrix([[0,0,1,0],[0,1,-1,1],[1,0,0,0],[0,0,1,0]]))
sage: B = AlternatingSignMatrix(matrix([[0,0,1,0,0],[0,0,0,1,0],[1,0,0,-1,1],[0,1,0,0,0],[0,0,0,1,0]]))
sage: A.ASM_compatible(B)
True
sage: A = AlternatingSignMatrix(matrix([[0,1,0],[1,-1,1],[0,1,0]]))
sage: B = AlternatingSignMatrix(matrix([[0,0,1,0],[0,0,0,1],[1,0,0,0],[0,1,0,0]]))
sage: A.ASM_compatible(B)
False

ASM_compatible_bigger()

Return all ASM’s compatible with self that are of size one greater than self.

Given an $$n \times n$$ alternating sign matrix $$A$$, there are as many ASM’s of size $$n+1$$ compatible with $$A$$ as 2 raised to the power of the number of 1’s in $$A$$ [EKLP92].

EXAMPLES:

sage: A = AlternatingSignMatrix(matrix([[1,0],[0,1]]))
sage: A.ASM_compatible_bigger()
[
[ 0  1  0]  [1 0 0]  [0 1 0]  [1 0 0]
[ 1 -1  1]  [0 0 1]  [1 0 0]  [0 1 0]
[ 0  1  0], [0 1 0], [0 0 1], [0 0 1]
]
sage: B = AlternatingSignMatrix(matrix([[0,1],[1,0]]))
sage: B.ASM_compatible_bigger()
[
[0 0 1]  [0 0 1]  [0 1 0]  [ 0  1  0]
[0 1 0]  [1 0 0]  [0 0 1]  [ 1 -1  1]
[1 0 0], [0 1 0], [1 0 0], [ 0  1  0]
]

ASM_compatible_smaller()

Return the list of all ASMs compatible with self that are of size one smaller than self.

Given an alternating sign matrix $$A$$ of size $$n$$, there are as many ASM’s of size $$n-1$$ compatible with it as 2 raised to the power of the number of $$-1$$‘s in $$A$$ [EKLP92].

EXAMPLES:

sage: A = AlternatingSignMatrix(matrix([[0,0,1,0],[0,1,-1,1],[1,0,0,0],[0,0,1,0]]))
sage: A.ASM_compatible_smaller()
[
[0 0 1]  [ 0  1  0]
[1 0 0]  [ 1 -1  1]
[0 1 0], [ 0  1  0]
]
sage: B = AlternatingSignMatrix(matrix([[1,0,0],[0,0,1],[0,1,0]]))
sage: B.ASM_compatible_smaller()
[
[1 0]
[0 1]
]

corner_sum_matrix()

Return the corner sum matrix from self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).corner_sum_matrix()
[0 0 0 0]
[0 1 1 1]
[0 1 2 2]
[0 1 2 3]
sage: asm = A([[0, 1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.corner_sum_matrix()
[0 0 0 0]
[0 0 1 1]
[0 1 1 2]
[0 1 2 3]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.corner_sum_matrix()
[0 0 0 0]
[0 0 1 1]
[0 0 1 2]
[0 1 2 3]

gyration()

Return the alternating sign matrix obtained by applying the gyration action to the height function in bijection with self.

Gyration acts on height functions as follows. Go through the entries of the matrix, first those for which the sum of the row and column indices is even, then for those for which it is odd, and increment or decrement the squares by 2 wherever possible such that the resulting matrix is still a height function. Gyration was first defined in [Wieland00] as an action on fully-packed loops.

REFERENCES:

 [Wieland00] B. Wieland. A large dihedral symmetry of the set of alternating sign matrices. Electron. J. Combin. 7 (2000).

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).gyration()
[0 0 1]
[0 1 0]
[1 0 0]
sage: asm = A([[0, 1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.gyration()
[1 0 0]
[0 1 0]
[0 0 1]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.gyration()
[0 1 0]
[0 0 1]
[1 0 0]

height_function()

Return the height function from self. A height function corresponding to an $$n \times n$$ ASM is an $$(n+1) \times (n+1)$$ matrix such that the first row is $$0, 1, \ldots, n$$, the last row is $$n, n-1, \ldots, 1, 0$$, and the difference between adjacent entries is 1.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).height_function()
[0 1 2 3]
[1 0 1 2]
[2 1 0 1]
[3 2 1 0]
sage: asm = A([[0, 1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.height_function()
[0 1 2 3]
[1 2 1 2]
[2 1 2 1]
[3 2 1 0]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.height_function()
[0 1 2 3]
[1 2 1 2]
[2 3 2 1]
[3 2 1 0]

is_permutation()

Return True if self is a permutation matrix and False otherwise.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: asm = A([[0,1,0],[1,0,0],[0,0,1]])
sage: asm.is_permutation()
True
sage: asm = A([[0,1,0],[1,-1,1],[0,1,0]])
sage: asm.is_permutation()
False

left_key()

Return the left key of the alternating sign matrix self.

The left key of an alternating sign matrix was defined by Lascoux in [LascouxPreprint] and is obtained by successively removing all the $$-1$$‘suntil what remains is a permutation matrix. This notion corresponds to the notion of left key for semistandard tableaux. So our algorithm proceeds as follows: we map self to its corresponding monotone triangle, view that monotone triangle as a semistandard tableaux, take its left key, and then map back through monotone triangles to the permutation matrix which is the left key.

REFERENCES:

 [Aval07] J.-C. Aval. Keys and alternating sign matrices. Sem. Lothar. Combin. 59 (2007/10), Art. B59f, 13 pp.
 [LascouxPreprint] A. Lascoux. Chern and Yang through ice. Preprint.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[0,0,1],[1,0,0],[0,1,0]]).left_key()
[0 0 1]
[1 0 0]
[0 1 0]
sage: t = A([[0,1,0],[1,-1,1],[0,1,0]]).left_key(); t
[1 0 0]
[0 0 1]
[0 1 0]
sage: parent(t)
Alternating sign matrices of size 3

left_key_as_permutation()

Return the permutation of the left key of self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[0,0,1],[1,0,0],[0,1,0]]).left_key_as_permutation()
[3, 1, 2]
sage: t = A([[0,1,0],[1,-1,1],[0,1,0]]).left_key_as_permutation(); t
[1, 3, 2]
sage: parent(t)
Standard permutations

number_negative_ones()

Return the number of entries in self equal to -1.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: asm = A([[0,1,0],[1,0,0],[0,0,1]])
sage: asm.number_negative_ones()
0
sage: asm = A([[0,1,0],[1,-1,1],[0,1,0]])
sage: asm.number_negative_ones()
1

rotate_ccw()

Return the counterclockwise quarter turn rotation of self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).rotate_ccw()
[0 0 1]
[0 1 0]
[1 0 0]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.rotate_ccw()
[1 0 0]
[0 0 1]
[0 1 0]

rotate_cw()

Return the clockwise quarter turn rotation of self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).rotate_cw()
[0 0 1]
[0 1 0]
[1 0 0]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.rotate_cw()
[0 1 0]
[1 0 0]
[0 0 1]

to_dyck_word()

Return the Dyck word determined by the last diagonal of the monotone triangle corresponding to self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[0,1,0],[1,0,0],[0,0,1]]).to_dyck_word()
[1, 1, 0, 0, 1, 0]
sage: d = A([[0,1,0],[1,-1,1],[0,1,0]]).to_dyck_word(); d
[1, 1, 0, 1, 0, 0]
sage: parent(d)
Complete Dyck words

to_matrix()

Return self as a regular matrix.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: asm = A([[1, 0, 0],[0, 1, 0],[0, 0, 1]])
sage: m = asm.to_matrix(); m
[1 0 0]
[0 1 0]
[0 0 1]
sage: m.parent()
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

to_monotone_triangle()

Return a monotone triangle from self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).to_monotone_triangle()
[[3, 2, 1], [2, 1], [1]]
sage: asm = A([[0, 1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.to_monotone_triangle()
[[3, 2, 1], [3, 1], [2]]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.to_monotone_triangle()
[[3, 2, 1], [3, 1], [3]]
sage: A.from_monotone_triangle(asm.to_monotone_triangle()) == asm
True

to_permutation()

Return the corresponding permutation if self is a permutation matrix.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: asm = A([[0,1,0],[1,0,0],[0,0,1]])
sage: p = asm.to_permutation(); p
[2, 1, 3]
sage: parent(p)
Standard permutations
sage: asm = A([[0,1,0],[1,-1,1],[0,1,0]])
sage: asm.to_permutation()
Traceback (most recent call last):
...
ValueError: Not a permutation matrix

to_semistandard_tableau()

Return the semistandard tableau corresponding the monotone triangle corresponding to self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[0,0,1],[1,0,0],[0,1,0]]).to_semistandard_tableau()
[[1, 1, 3], [2, 3], [3]]
sage: t = A([[0,1,0],[1,-1,1],[0,1,0]]).to_semistandard_tableau(); t
[[1, 1, 2], [2, 3], [3]]
sage: parent(t)
Semistandard tableaux

transpose()

Return the counterclockwise quarter turn rotation of self.

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).transpose()
[1 0 0]
[0 1 0]
[0 0 1]
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.transpose()
[0 1 0]
[0 0 1]
[1 0 0]

class sage.combinat.alternating_sign_matrix.ContreTableaux

Factory class for the combinatorial class of contre tableaux of size $$n$$.

EXAMPLES:

sage: ct4 = ContreTableaux(4); ct4
Contre tableaux of size 4
sage: ct4.cardinality()
42

class sage.combinat.alternating_sign_matrix.ContreTableaux_n(n)

TESTS:

sage: ct2 = ContreTableaux(2); ct2
Contre tableaux of size 2
True

cardinality()

EXAMPLES:

sage: [ ContreTableaux(n).cardinality() for n in range(0, 11)]
[1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700]

class sage.combinat.alternating_sign_matrix.MonotoneTriangles(n)

Monotone triangles with $$n$$ rows.

A monotone triangle is a number triangle $$(a_{i,j})_{1 \leq i \leq n , 1 \leq j \leq i}$$ on $$\{1, \dots, n\}$$ such that:

• $$a_{i,j} < a_{i,j+1}$$
• $$a_{i+1,j} < a_{i,j} \leq a_{i+1,j+1}$$

This notably requires that the bottom column is [1,...,n].

Alternatively a monotone triangle is a strict Gelfand-Tsetlin pattern with top row $$(n, \ldots, 2, 1)$$.

INPUT:

• n – The number of rows in the monotone triangles

EXAMPLES:

This represents the monotone triangles with base [3,2,1]:

sage: M = MonotoneTriangles(3)
sage: M
Monotone triangles with 3 rows
sage: M.cardinality()
7


The monotone triangles are a lattice:

sage: M.lattice()
Finite lattice containing 7 elements


Monotone triangles can be converted to alternating sign matrices and back:

sage: M = MonotoneTriangles(5)
sage: A = AlternatingSignMatrices(5)
sage: all(A.from_monotone_triangle(m).to_monotone_triangle() == m for m in M)
True

cardinality()

Cardinality of self.

The number of monotone triangles with $$n$$ rows is equal to

$\prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!} = \frac{1! 4! 7! 10! \cdots (3n-2)!}{n! (n+1)! (n+2)! (n+3)! \cdots (2n-1)!}$

EXAMPLES:

sage: M = MonotoneTriangles(4)
sage: M.cardinality()
42

cover_relations()

Iterate on the cover relations in the set of monotone triangles with $$n$$ rows.

EXAMPLES:

sage: M = MonotoneTriangles(3)
sage: for (a,b) in M.cover_relations():
....:   eval('a, b')
([[3, 2, 1], [2, 1], [1]], [[3, 2, 1], [2, 1], [2]])
([[3, 2, 1], [2, 1], [1]], [[3, 2, 1], [3, 1], [1]])
([[3, 2, 1], [2, 1], [2]], [[3, 2, 1], [3, 1], [2]])
([[3, 2, 1], [3, 1], [1]], [[3, 2, 1], [3, 1], [2]])
([[3, 2, 1], [3, 1], [2]], [[3, 2, 1], [3, 1], [3]])
([[3, 2, 1], [3, 1], [2]], [[3, 2, 1], [3, 2], [2]])
([[3, 2, 1], [3, 1], [3]], [[3, 2, 1], [3, 2], [3]])
([[3, 2, 1], [3, 2], [2]], [[3, 2, 1], [3, 2], [3]])

lattice()

Return the lattice of the monotone triangles with $$n$$ rows.

EXAMPLES:

sage: M = MonotoneTriangles(3)
sage: P = M.lattice()
sage: P
Finite lattice containing 7 elements

sage.combinat.alternating_sign_matrix.MonotoneTriangles_n(n)

For old pickles of MonotoneTriangles_n.

EXAMPLES:

sage: sage.combinat.alternating_sign_matrix.MonotoneTriangles_n(3)
doctest:...: DeprecationWarning: this class is deprecated. Use sage.combinat.alternating_sign_matrix.MonotoneTriangles instead
See http://trac.sagemath.org/14301 for details.
Monotone triangles with 3 rows

class sage.combinat.alternating_sign_matrix.TruncatedStaircases

Factory class for the combinatorial class of truncated staircases of size n with last column last_column.

EXAMPLES:

sage: t4 = TruncatedStaircases(4, [2,3]); t4
Truncated staircases of size 4 with last column [2, 3]
sage: t4.cardinality()
4

class sage.combinat.alternating_sign_matrix.TruncatedStaircases_nlastcolumn(n, last_column)

TESTS:

sage: t4 = TruncatedStaircases(4, [2,3]); t4
Truncated staircases of size 4 with last column [2, 3]
True

cardinality()

EXAMPLES:

sage: T = TruncatedStaircases(4, [2,3])
sage: T.cardinality()
4

sage.combinat.alternating_sign_matrix.from_monotone_triangle(triangle)

EXAMPLES:

sage: sage.combinat.alternating_sign_matrix.from_monotone_triangle([[1, 2], [2]])
doctest:...: DeprecationWarning: from_monotone_triangle() is deprecated. Use AlternatingSignMatrix.from_monotone_triangle() instead
See http://trac.sagemath.org/14301 for details.
[0 1]
[1 0]

sage.combinat.alternating_sign_matrix.nw_corner_sum(M, i, j)

Return the sum of entries to the northwest of $$(i,j)$$ in matrix.

EXAMPLES:

sage: from sage.combinat.alternating_sign_matrix import nw_corner_sum
sage: A = matrix.ones(3,3)
sage: nw_corner_sum(A,2,2)
4

sage.combinat.alternating_sign_matrix.to_monotone_triangle(matrix)

EXAMPLES:

sage: sage.combinat.alternating_sign_matrix.to_monotone_triangle([[0,1],[1,0]])
doctest:...: DeprecationWarning: to_monotone_triangle() is deprecated. Use AlternatingSignMatrix.to_monotone_triangle() instead
See http://trac.sagemath.org/14301 for details.
[[2, 1], [2]]


Previous topic

Combinatorics features that are imported by default in the interpreter namespace

Backtracking