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)

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

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()
Category of facade finite 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(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_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)

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.

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(*args, **kwds)

Return the permutation of the left key of self.

See also

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
to_dyck_word(*args, **kwds)

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)
<class 'sage.combinat.dyck_word.DyckWord_complete'>
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(*args, **kwds)

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(*args, **kwds)

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
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

TESTS:

sage: ct2 = ContreTableaux(2); ct2
Contre tableaux of size 2
sage: ct2 == loads(dumps(ct2))
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)

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
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

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

TESTS:

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

EXAMPLES:

sage: T = TruncatedStaircases(4, [2,3])
sage: T.cardinality()
4
sage.combinat.alternating_sign_matrix.from_contre_tableau(comps)

Returns an alternating sign matrix from a contre-tableau.

EXAMPLES:

sage: import sage.combinat.alternating_sign_matrix as asm
sage: asm.from_contre_tableau([[1, 2, 3], [1, 2], [1]])
doctest:...: DeprecationWarning: You can use from_monotone_triangle instead.
See http://trac.sagemath.org/12930 for details.
[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]
sage.combinat.alternating_sign_matrix.from_monotone_triangle(triangle)

Deprecated method, use AlternatingSignMatrices.from_monotone_triangle() instead.

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.to_monotone_triangle(matrix)

Deprecated method, use AlternatingSignMatrix.to_monotone_triangle() instead.

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

Compute Bell and Uppuluri-Carpenter numbers

Next topic

Cartesian Products

This Page