AUTHORS:
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
Class of all alternating sign matrices.
An alternating sign matrix of size is an
matrix of
‘s,
‘s and
‘s such that the sum of each row and column is
and the
non-zero entries in each row and column alternate in sign.
Alternating sign matrices of size are in bijection with
monotone triangles with
rows.
INPUT:
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
and Category of facade sets
alias of AlternatingSignMatrix
Return the cardinality of self.
The number of alternating sign matrices is equal to
EXAMPLES:
sage: [AlternatingSignMatrices(n).cardinality() for n in range(0, 11)]
[1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700]
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]
)
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]
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]
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]
Return the lattice of the alternating sign matrices of size
, created by LatticePoset.
EXAMPLES:
sage: A = AlternatingSignMatrices(3)
sage: L = A.lattice()
sage: L
Finite lattice containing 7 elements
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
Return the size of the matrices in self.
TESTS:
sage: A = AlternatingSignMatrices(4)
sage: A.size()
4
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
Bases: sage.structure.element.Element
An alternating sign matrix.
An alternating sign matrix is a square matrix of ‘s,
‘s and
‘s
such that the sum of each row and column is
and the non-zero
entries in each row and column alternate in sign.
Return True if self and B are compatible alternating sign
matrices in the sense of [EKLP92]. (If self is of size , B
must be of size
.)
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
Return all ASM’s compatible with self that are of size one greater than self.
Given an alternating sign matrix
, there are as many
ASM’s of size
compatible with
as 2 raised to the power of
the number of 1’s in
[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]
]
Return the list of all ASMs compatible with self that are of size one smaller than self.
Given an alternating sign matrix of size
, there are as many
ASM’s of size
compatible with it as 2 raised to the power of
the number of
‘s in
[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]
]
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]
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]
Return the height function from self. A height function
corresponding to an ASM is an
matrix
such that the first row is
, the last row is
, 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]
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
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
‘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
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
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
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]
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]
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
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
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
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
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
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]
Bases: sage.structure.parent.Parent
Factory class for the combinatorial class of contre tableaux of size .
EXAMPLES:
sage: ct4 = ContreTableaux(4); ct4
Contre tableaux of size 4
sage: ct4.cardinality()
42
Bases: sage.combinat.alternating_sign_matrix.ContreTableaux
TESTS:
sage: ct2 = ContreTableaux(2); ct2
Contre tableaux of size 2
sage: ct2 == loads(dumps(ct2))
True
EXAMPLES:
sage: [ ContreTableaux(n).cardinality() for n in range(0, 11)]
[1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700]
Bases: sage.combinat.gelfand_tsetlin_patterns.GelfandTsetlinPatternsTopRow
Monotone triangles with rows.
A monotone triangle is a number triangle on
such that:
This notably requires that the bottom column is [1,...,n].
Alternatively a monotone triangle is a strict Gelfand-Tsetlin pattern with
top row .
INPUT:
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 of self.
The number of monotone triangles with rows is equal to
EXAMPLES:
sage: M = MonotoneTriangles(4)
sage: M.cardinality()
42
Iterate on the cover relations in the set of monotone triangles
with 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]])
Return the lattice of the monotone triangles with rows.
EXAMPLES:
sage: M = MonotoneTriangles(3)
sage: P = M.lattice()
sage: P
Finite lattice containing 7 elements
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
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
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
EXAMPLES:
sage: T = TruncatedStaircases(4, [2,3])
sage: T.cardinality()
4
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]
Return the sum of entries to the northwest of 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
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]]