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
sage.combinat.alternating_sign_matrix.AlternatingSignMatrices

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
sage.combinat.alternating_sign_matrix.AlternatingSignMatrix

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

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)

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]
sage.combinat.alternating_sign_matrix.MonotoneTriangles

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

Bases: sage.combinat.alternating_sign_matrix.TruncatedStaircases

cardinality()

EXAMPLES:

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