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
• Jessica Striker (2013): Added additional methods
• Vincent Delecroix (2017): cleaning

class sage.combinat.alternating_sign_matrix.AlternatingSignMatrices(n)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

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.

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()
Category of facade finite enumerated lattice posets

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(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]
)

first()

Return the first alternating sign matrix.

EXAMPLES:

sage: AlternatingSignMatrices(5).first()
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

from_contre_tableau(comps)

Return an alternating sign matrix from a contre-tableau.

EXAMPLES:

sage: ASM = AlternatingSignMatrices(3)
sage: ASM.from_contre_tableau([[1, 2, 3], [1, 2], [1]])
[0 0 1]
[0 1 0]
[1 0 0]
sage: ASM.from_contre_tableau([[1, 2, 3], [2, 3], [3]])
[1 0 0]
[0 1 0]
[0 0 1]

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, check=True)

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]


sage: A.from_monotone_triangle([[3, 2, 1], [2, 2], [1]])
Traceback (most recent call last):
...
ValueError: not a valid triangle

gyration_orbit_sizes()

Return the sizes of gyration orbits of self.

EXAMPLES:

sage: AlternatingSignMatrices(3).gyration_orbit_sizes()
[3, 2, 2]
sage: AlternatingSignMatrices(4).gyration_orbit_sizes()
[4, 8, 2, 8, 8, 8, 2, 2]

sage: A = AlternatingSignMatrices(5)
sage: li = [5,10,10,10,10,10,2,5,10,10,10,10,10,10,10,10,10,10,10,10,
....: 4,10,10,10,10,10,10,4,5,10,10,10,10,10,10,10,2,4,5,10,10,10,10,10,10,
....: 4,5,10,10,2,2]
sage: A.gyration_orbit_sizes() == li
True

gyration_orbits()

Return the list of gyration orbits of self.

EXAMPLES:

sage: AlternatingSignMatrices(3).gyration_orbits()
((
  [1 0 0]  [0 0 1]  [ 0  1  0]
  [0 1 0]  [0 1 0]  [ 1 -1  1]
  [0 0 1], [1 0 0], [ 0  1  0]
 ),
 (
  [0 1 0]  [1 0 0]
  [1 0 0]  [0 0 1]
  [0 0 1], [0 1 0]
 ),
 (
  [0 0 1]  [0 1 0]
  [1 0 0]  [0 0 1]
  [0 1 0], [1 0 0]
 ))

last()

Return the last alternating sign matrix.

EXAMPLES:

sage: AlternatingSignMatrices(5).last()
[0 0 0 0 1]
[0 0 0 1 0]
[0 0 1 0 0]
[0 1 0 0 0]
[1 0 0 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

random_element()

Return a uniformly random alternating sign matrix.

EXAMPLES:

sage: AlternatingSignMatrices(7).random_element()  # random
[ 0  0  0  0  1  0  0]
[ 0  0  1  0 -1  0  1]
[ 0  0  0  0  1  0  0]
[ 0  1 -1  0  0  1  0]
[ 1 -1  1  0  0  0  0]
[ 0  0  0  1  0  0  0]
[ 0  1  0  0  0  0  0]
sage: a = AlternatingSignMatrices(5).random_element()
sage: bool(a.number_negative_ones()) or a.is_permutation()
True

This is done using a modified version of Propp and Wilson’s “coupling from the past” algorithm. It creates a uniformly random Gelfand-Tsetlin triangle with top row \([n, n-1, \ldots 2, 1]\), and then converts it to an alternating sign matrix.

size()

Return the size of the matrices in self.

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

Bases: sage.structure.element.Element

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.

These were introduced in [MRR1983].

ASM_compatible(B)

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

In [EKLP1992], 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.

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\) [EKLP1992].

EXAMPLES:

sage: A = AlternatingSignMatrix([[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([[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]
]

sage: B = AlternatingSignMatrix([[0,1,0],[1,-1,1],[0,1,0]])
sage: len(B.ASM_compatible_bigger()) == 2**4
True

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\) [EKLP1992].

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 of 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 0 1]
[0 1 1 2]
[0 1 2 3]

gyration()

Return the alternating sign matrix obtained by applying gyration 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 [Wie2000] as an action on fully-packed loops.

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]
sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).gyration().gyration()
[ 0  1  0]
[ 1 -1  1]
[ 0  1  0]
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).gyration().gyration().gyration()
[1 0 0]
[0 1 0]
[0 0 1]

sage: A = AlternatingSignMatrices(4)
sage: M = A([[0,0,1,0],[1,0,0,0],[0,1,-1,1],[0,0,1,0]])
sage: for i in range(5):
....:     M = M.gyration()
sage: M
[1 0 0 0]
[0 0 0 1]
[0 1 0 0]
[0 0 1 0]

sage: a0 = a = AlternatingSignMatrices(5).random_element()
sage: for i in range(10):
....:     a = a.gyration()
sage: a == a0
True

gyration_orbit()

Return the gyration orbit of self (including self).

EXAMPLES:

sage: AlternatingSignMatrix([[0,1,0],[1,-1,1],[0,1,0]]).gyration_orbit()
[
[ 0  1  0]  [1 0 0]  [0 0 1]
[ 1 -1  1]  [0 1 0]  [0 1 0]
[ 0  1  0], [0 0 1], [1 0 0]
]

sage: AlternatingSignMatrix([[0,1,0,0],[1,-1,1,0],[0,1,-1,1],[0,0,1,0]]).gyration_orbit()
[
[ 0  1  0  0]  [1 0 0 0]  [ 0  0  1  0]  [0 0 0 1]
[ 1 -1  1  0]  [0 1 0 0]  [ 0  1 -1  1]  [0 0 1 0]
[ 0  1 -1  1]  [0 0 1 0]  [ 1 -1  1  0]  [0 1 0 0]
[ 0  0  1  0], [0 0 0 1], [ 0  1  0  0], [1 0 0 0]
]

sage: len(AlternatingSignMatrix([[0,1,0,0,0,0],[0,0,1,0,0,0],[1,-1,0,0,0,1],
....: [0,1,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,1,0]]).gyration_orbit())
12

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]

sage: A = AlternatingSignMatrices(4)
sage: all(A.from_height_function(a.height_function()) == a for a in A)
True

inversion_number()

Return the inversion number of self.

If we denote the entries of the alternating sign matrix as \(a_{i,j}\), the inversion number is defined as \(\sum_{i>k}\sum_{j<l}a_{i,j}a_{k,l}\). When restricted to permutation matrices, this gives the usual inversion number of the permutation.

This definition is equivalent to the one given in [MRR1983].

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[1, 0, 0],[0, 1, 0],[0, 0, 1]]).inversion_number()
0
sage: asm = A([[0, 0, 1],[1, 0, 0],[0, 1, 0]])
sage: asm.inversion_number()
2
sage: asm = A([[0, 1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.inversion_number()
2
sage: P=Permutations(5)
sage: all(p.number_of_inversions()==AlternatingSignMatrix(p.to_matrix()).inversion_number() for p in P)
True

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 [Lasc] and is obtained by successively removing all the \(-1\)’s until 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 tableau, take its left key, and then map back through monotone triangles to the permutation matrix which is the left key.

See also [Ava2007].

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.

See also

• left_key()

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

link_pattern()

Return the link pattern corresponding to the fully packed loop corresponding to self.

EXAMPLES:

We can extract the underlying link pattern (a non-crossing partition) from a fully packed loop:

sage: A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]])
sage: A.link_pattern()
[(1, 2), (3, 6), (4, 5)]

sage: B = AlternatingSignMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
sage: B.link_pattern()
[(1, 6), (2, 5), (3, 4)]

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(algorithm)

Return a Dyck word determined by the specified algorithm.

The algorithm ‘last_diagonal’ uses the last diagonal of the monotone triangle corresponding to self. The algorithm ‘link_pattern’ returns the Dyck word in bijection with the link pattern of the fully packed loop.

Note that these two algorithms in general yield different Dyck words for a given alternating sign matrix.

INPUT:

• algorithm - either 'last_diagonal' or 'link_pattern'

EXAMPLES:

sage: A = AlternatingSignMatrices(3)
sage: A([[0,1,0],[1,0,0],[0,0,1]]).to_dyck_word(algorithm = 'last_diagonal')
[1, 1, 0, 0, 1, 0]
sage: d = A([[0,1,0],[1,-1,1],[0,1,0]]).to_dyck_word(algorithm = 'last_diagonal'); d
[1, 1, 0, 1, 0, 0]
sage: parent(d)
Complete Dyck words
sage: A = AlternatingSignMatrices(3)
sage: asm = A([[0,1,0],[1,0,0],[0,0,1]])
sage: asm.to_dyck_word(algorithm = 'link_pattern')
[1, 0, 1, 0, 1, 0]
sage: asm = A([[0,1,0],[1,-1,1],[0,1,0]])
sage: asm.to_dyck_word(algorithm = 'link_pattern')
[1, 0, 1, 1, 0, 0]
sage: A = AlternatingSignMatrices(4)
sage: asm = A([[0,0,1,0],[1,0,0,0],[0,1,-1,1],[0,0,1,0]])
sage: asm.to_dyck_word(algorithm = 'link_pattern')
[1, 1, 1, 0, 1, 0, 0, 0]
sage: asm.to_dyck_word()
Traceback (most recent call last):
...
TypeError: to_dyck_word() ...argument...
sage: asm.to_dyck_word(algorithm = 'notamethod')
Traceback (most recent call last):
...
ValueError: unknown algorithm 'notamethod'

to_fully_packed_loop()

Return the fully packed loop configuration from self.

See also

FullyPackedLoop

EXAMPLES:

sage: asm = AlternatingSignMatrix([[1,0,0],[0,1,0],[0,0,1]])
sage: fpl = asm.to_fully_packed_loop()
sage: fpl
    |         |
    |         |
    +    + -- +
    |    |
    |    |
 -- +    +    + --
         |    |
         |    |
    + -- +    +
    |         |
    |         |

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

to_six_vertex_model()

Return the six vertex model configuration from self.

This method calls sage.combinat.six_vertex_model.from_alternating_sign_matrix().

EXAMPLES:

sage: asm = AlternatingSignMatrix([[0,1,0],[1,-1,1],[0,1,0]])
sage: asm.to_six_vertex_model()
    ^    ^    ^
    |    |    |
--> # -> # <- # <--
    ^    |    ^
    |    V    |
--> # <- # -> # <--
    |    ^    |
    V    |    V
--> # -> # <- # <--
    |    |    |
    V    V    V

transpose()

Return self transposed.

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

Bases: sage.structure.parent.Parent

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)

Bases: sage.combinat.alternating_sign_matrix.ContreTableaux

cardinality()

EXAMPLES:

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

class sage.combinat.alternating_sign_matrix.MonotoneTriangles(n)

Bases: sage.combinat.gelfand_tsetlin_patterns.GelfandTsetlinPatternsTopRow

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

class sage.combinat.alternating_sign_matrix.TruncatedStaircases

Bases: sage.structure.parent.Parent

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)

Bases: sage.combinat.alternating_sign_matrix.TruncatedStaircases

cardinality()

EXAMPLES:

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