Alternating Sign Matrices

class sage.combinat.alternating_sign_matrix.AlternatingSignMatrices

Bases: sage.structure.parent.Parent

Factory class for the combinatorial structure of alternating sign matrices of size n.

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

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
class sage.combinat.alternating_sign_matrix.AlternatingSignMatrices_n(n, use_monotone_triangles=True)

Bases: sage.combinat.alternating_sign_matrix.AlternatingSignMatrices

Specialization class for alternating sign matrices of size n when n is an integer.

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

Return the cardinality of self.

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

Return the size of the matrices in self.

TESTS:

sage: A = AlternatingSignMatrices(4)
sage: A.size()
4
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

Bases: sage.structure.parent.Parent

Factory class for the combinatorial structure of 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].

EXAMPLES:

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

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
class sage.combinat.alternating_sign_matrix.MonotoneTriangles_n(n)

Bases: sage.combinat.alternating_sign_matrix.MonotoneTriangles

Specialization class for monotone triangles with n rows when n is an integer.

INPUT:

  • n – integer of type int or Integer, the number of rows of the monotone triangles in self.
cardinality()

Cardinality of self.

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')
...
([[1, 2, 3], [1, 2], [1]], [[1, 2, 3], [1, 2], [2]])
([[1, 2, 3], [1, 2], [1]], [[1, 2, 3], [1, 3], [1]])
([[1, 2, 3], [1, 2], [2]], [[1, 2, 3], [1, 3], [2]])
([[1, 2, 3], [1, 3], [1]], [[1, 2, 3], [1, 3], [2]])
([[1, 2, 3], [1, 3], [2]], [[1, 2, 3], [1, 3], [3]])
([[1, 2, 3], [1, 3], [2]], [[1, 2, 3], [2, 3], [2]])
([[1, 2, 3], [1, 3], [3]], [[1, 2, 3], [2, 3], [3]])
([[1, 2, 3], [2, 3], [2]], [[1, 2, 3], [2, 3], [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

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)

Return an alternating sign matrix from a monotone triangle.

EXAMPLES:

sage: import sage.combinat.alternating_sign_matrix as asm
sage: asm.from_monotone_triangle([[1, 2, 3], [1, 2], [1]])
[1 0 0]
[0 1 0]
[0 0 1]
sage: asm.from_monotone_triangle([[1, 2, 3], [2, 3], [3]])
[0 0 1]
[0 1 0]
[1 0 0]
sage.combinat.alternating_sign_matrix.to_monotone_triangle(matrix)

Return a monotone triangle from an alternating sign matrix.

EXAMPLES:

sage: import sage.combinat.alternating_sign_matrix as asm
sage: asm.to_monotone_triangle(Matrix(3,[[1, 0, 0],[0, 1, 0],[0, 0, 1]]))
[[1, 2, 3], [1, 2], [1]]
sage: M = Matrix(3,[[0,1, 0],[1, -1, 1],[0, 1, 0]])
sage: asm.to_monotone_triangle(M)
[[1, 2, 3], [1, 3], [2]]
sage: asm.from_monotone_triangle(asm.to_monotone_triangle(M)) == M
True

Previous topic

Compute Bell and Uppuluri-Carpenter numbers

Next topic

Cartesian Products

This Page