Gelfand-Tsetlin Patterns#

AUTHORS:

  • Travis Scrimshaw (2013-15-03): Initial version

REFERENCES:

[BBF] (1,2,3)

B. Brubaker, D. Bump, and S. Friedberg. Weyl Group Multiple Dirichlet Series: Type A Combinatorial Theory. Ann. of Math. Stud., vol. 175, Princeton Univ. Press, New Jersey, 2011.

[GC50]

I. M. Gelfand and M. L. Cetlin. Finite-Dimensional Representations of the Group of Unimodular Matrices. Dokl. Akad. Nauk SSSR 71, pp. 825–828, 1950.

[Tok88]

T. Tokuyama. A Generating Function of Strict Gelfand Patterns and Some Formulas on Characters of General Linear Groups. J. Math. Soc. Japan 40 (4), pp. 671–685, 1988.

class sage.combinat.gelfand_tsetlin_patterns.GelfandTsetlinPattern[source]#

Bases: ClonableArray

A Gelfand-Tsetlin (sometimes written as Gelfand-Zetlin or Gelfand-Cetlin) pattern. They were originally defined in [GC50].

A Gelfand-Tsetlin pattern is a triangular array:

\[\begin{split}\begin{array}{ccccccccc} a_{1,1} & & a_{1,2} & & a_{1,3} & & \cdots & & a_{1,n} \\ & a_{2,2} & & a_{2,3} & & \cdots & & a_{2,n} \\ & & a_{3,3} & & \cdots & & a_{3,n} \\ & & & \ddots \\ & & & & a_{n,n} \end{array}\end{split}\]

such that \(a_{i,j} \geq a_{i+1,j+1} \geq a_{i,j+1}\).

Gelfand-Tsetlin patterns are in bijection with semistandard Young tableaux by the following algorithm. Let \(G\) be a Gelfand-Tsetlin pattern with \(\lambda^{(k)}\) being the \((n-k+1)\)-st row (note that this is a partition). The definition of \(G\) implies

\[\lambda^{(0)} \subseteq \lambda^{(1)} \subseteq \cdots \subseteq \lambda^{(n)},\]

where \(\lambda^{(0)}\) is the empty partition, and each skew shape \(\lambda^{(k)}/\lambda^{(k-1)}\) is a horizontal strip. Thus define \(T(G)\) by inserting \(k\) into the squares of the skew shape \(\lambda^{(k)}/ \lambda^{(k-1)}\), for \(k=1,\dots,n\).

To each entry in a Gelfand-Tsetlin pattern, one may attach a decoration of a circle or a box (or both or neither). These decorations appear in the study of Weyl group multiple Dirichlet series, and are implemented here following the exposition in [BBF].

Note

We use the “right-hand” rule for determining circled and boxed entries.

Warning

The entries in Sage are 0-based and are thought of as flushed to the left in a matrix. In other words, the coordinates of entries in the Gelfand-Tsetlin patterns are thought of as the matrix:

\[\begin{split}\begin{bmatrix} g_{0,0} & g_{0,1} & g_{0,2} & \cdots & g_{0,n-2} & g_{n-1,n-1} \\ g_{1,0} & g_{1,1} & g_{1,2} & \cdots & g_{1,n-2} \\ g_{2,0} & g_{2,1} & g_{2,2} & \cdots \\ \vdots & \vdots & \vdots \\ g_{n-2,0} & g_{n-2,1} \\ g_{n-1,0} \end{bmatrix}.\end{split}\]

However, in the discussions, we will be using the standard numbering system.

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3, 2, 1], [2, 1], [1]]); G
[[3, 2, 1], [2, 1], [1]]
sage: G.pp()
  3     2     1
     2     1
        1
sage: G = GelfandTsetlinPattern([[7, 7, 4, 0], [7, 7, 3], [7, 5], [5]]); G.pp()
  7     7     4     0
     7     7     3
        7     5
           5
sage: G.to_tableau().pp()
  1  1  1  1  1  2  2
  2  2  2  2  2  3  3
  3  3  3  4
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3), Integer(2), Integer(1)], [Integer(2), Integer(1)], [Integer(1)]]); G
[[3, 2, 1], [2, 1], [1]]
>>> G.pp()
  3     2     1
     2     1
        1
>>> G = GelfandTsetlinPattern([[Integer(7), Integer(7), Integer(4), Integer(0)], [Integer(7), Integer(7), Integer(3)], [Integer(7), Integer(5)], [Integer(5)]]); G.pp()
  7     7     4     0
     7     7     3
        7     5
           5
>>> G.to_tableau().pp()
  1  1  1  1  1  2  2
  2  2  2  2  2  3  3
  3  3  3  4
Tokuyama_coefficient(name='t')[source]#

Return the Tokuyama coefficient attached to self.

Following the exposition of [BBF], Tokuyama’s formula asserts

\[\sum_{G} (t+1)^{s(G)} t^{l(G)} z_1^{d_{n+1}} z_2^{d_{n}-d_{n+1}} \cdots z_{n+1}^{d_1-d_2} = s_{\lambda}(z_1,\dots,z_{n+1}) \prod_{i<j} (z_j+tz_i),\]

where the sum is over all strict Gelfand-Tsetlin patterns with fixed top row \(\lambda + \rho\), with \(\lambda\) a partition with at most \(n+1\) parts and \(\rho = (n, n-1, \ldots, 1, 0)\), and \(s_\lambda\) is a Schur function.

INPUT:

  • name – (Default: 't') An alternative name for the variable \(t\).

EXAMPLES:

sage: P = GelfandTsetlinPattern([[3,2,1],[2,2],[2]])
sage: P.Tokuyama_coefficient()
0
sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[2]])
sage: G.Tokuyama_coefficient()
t^2 + t
sage: G = GelfandTsetlinPattern([[2,1,0],[1,1],[1]])
sage: G.Tokuyama_coefficient()
0
sage: G = GelfandTsetlinPattern([[5,3,2,1,0],[4,3,2,0],[4,2,1],[3,2],[3]])
sage: G.Tokuyama_coefficient()
t^8 + 3*t^7 + 3*t^6 + t^5
>>> from sage.all import *
>>> P = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(2)],[Integer(2)]])
>>> P.Tokuyama_coefficient()
0
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(2)]])
>>> G.Tokuyama_coefficient()
t^2 + t
>>> G = GelfandTsetlinPattern([[Integer(2),Integer(1),Integer(0)],[Integer(1),Integer(1)],[Integer(1)]])
>>> G.Tokuyama_coefficient()
0
>>> G = GelfandTsetlinPattern([[Integer(5),Integer(3),Integer(2),Integer(1),Integer(0)],[Integer(4),Integer(3),Integer(2),Integer(0)],[Integer(4),Integer(2),Integer(1)],[Integer(3),Integer(2)],[Integer(3)]])
>>> G.Tokuyama_coefficient()
t^8 + 3*t^7 + 3*t^6 + t^5
bender_knuth_involution(i)[source]#

Return the image of self under the \(i\)-th Bender-Knuth involution.

If the triangle self has size \(n\) then this is defined for \(0 < i < n\).

The entries of self can take values in any ordered ring. Usually, this will be the integers but can also be the rationals or the real numbers.

This implements the construction of the Bender-Knuth involution using toggling due to Berenstein-Kirillov.

This agrees with the Bender-Knuth involution on semistandard tableaux.

EXAMPLES:

sage: G = GelfandTsetlinPattern([[5,3,2,1,0],[4,3,2,0],[4,2,1],[3,2],[3]])
sage: G.bender_knuth_involution(2)
[[5, 3, 2, 1, 0], [4, 3, 2, 0], [4, 2, 1], [4, 1], [3]]

sage: G = GelfandTsetlinPattern([[3,2,0],[2.2,0],[2]])
sage: G.bender_knuth_involution(2)
[[3, 2, 0], [2.80000000000000, 2], [2]]
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(5),Integer(3),Integer(2),Integer(1),Integer(0)],[Integer(4),Integer(3),Integer(2),Integer(0)],[Integer(4),Integer(2),Integer(1)],[Integer(3),Integer(2)],[Integer(3)]])
>>> G.bender_knuth_involution(Integer(2))
[[5, 3, 2, 1, 0], [4, 3, 2, 0], [4, 2, 1], [4, 1], [3]]

>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(0)],[RealNumber('2.2'),Integer(0)],[Integer(2)]])
>>> G.bender_knuth_involution(Integer(2))
[[3, 2, 0], [2.80000000000000, 2], [2]]
boxed_entries()[source]#

Return the position of the boxed entries of self.

Using the right-hand rule, an entry \(a_{i,j}\) is boxed if \(a_{i,j} = a_{i-1,j-1}\); i.e., \(a_{i,j}\) has the same value as its neighbor to the northwest.

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
sage: G.boxed_entries()
((1, 0),)
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]])
>>> G.boxed_entries()
((1, 0),)
check()[source]#

Check that this is a valid Gelfand-Tsetlin pattern.

EXAMPLES:

sage: G = GelfandTsetlinPatterns()
sage: G([[3,2,1],[2,1],[1]]).check()
>>> from sage.all import *
>>> G = GelfandTsetlinPatterns()
>>> G([[Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(1)]]).check()
circled_entries()[source]#

Return the circled entries of self.

Using the right-hand rule, an entry \(a_{i,j}\) is circled if \(a_{i,j} = a_{i-1,j}\); i.e., \(a_{i,j}\) has the same value as its neighbor to the northeast.

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
sage: G.circled_entries()
((1, 1), (2, 0))
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]])
>>> G.circled_entries()
((1, 1), (2, 0))
is_strict()[source]#

Return True if self is a strict Gelfand-Tsetlin pattern.

A Gelfand-Tsetlin pattern is said to be strict if every row is strictly decreasing.

EXAMPLES:

sage: GelfandTsetlinPattern([[7,3,1],[6,2],[4]]).is_strict()
True
sage: GelfandTsetlinPattern([[3,2,1],[3,1],[1]]).is_strict()
True
sage: GelfandTsetlinPattern([[6,0,0],[3,0],[2]]).is_strict()
False
>>> from sage.all import *
>>> GelfandTsetlinPattern([[Integer(7),Integer(3),Integer(1)],[Integer(6),Integer(2)],[Integer(4)]]).is_strict()
True
>>> GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]]).is_strict()
True
>>> GelfandTsetlinPattern([[Integer(6),Integer(0),Integer(0)],[Integer(3),Integer(0)],[Integer(2)]]).is_strict()
False
number_of_boxes()[source]#

Return the number of boxed entries. See boxed_entries().

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
sage: G.number_of_boxes()
1
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]])
>>> G.number_of_boxes()
1
number_of_circles()[source]#

Return the number of boxed entries. See circled_entries().

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
sage: G.number_of_circles()
2
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]])
>>> G.number_of_circles()
2
number_of_special_entries()[source]#

Return the number of special entries. See special_entries().

EXAMPLES:

sage: G = GelfandTsetlinPattern([[4,2,1],[4,1],[2]])
sage: G.number_of_special_entries()
1
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(4),Integer(2),Integer(1)],[Integer(4),Integer(1)],[Integer(2)]])
>>> G.number_of_special_entries()
1
pp()[source]#

Pretty print self.

EXAMPLES:

sage: G = GelfandTsetlinPatterns()
sage: G([[3,2,1],[2,1],[1]]).pp()
  3     2     1
     2     1
        1
>>> from sage.all import *
>>> G = GelfandTsetlinPatterns()
>>> G([[Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(1)]]).pp()
  3     2     1
     2     1
        1
row_sums()[source]#

Return the list of row sums.

For a Gelfand-Tsetlin pattern \(G\), the \(i\)-th row sum \(d_i\) is

\[d_i = d_i(G) = \sum_{j=i}^{n} a_{i,j}.\]

EXAMPLES:

sage: G = GelfandTsetlinPattern([[5,3,2,1,0],[4,3,2,0],[4,2,1],[3,2],[3]])
sage: G.row_sums()
[11, 9, 7, 5, 3]
sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[2]])
sage: G.row_sums()
[6, 4, 2]
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(5),Integer(3),Integer(2),Integer(1),Integer(0)],[Integer(4),Integer(3),Integer(2),Integer(0)],[Integer(4),Integer(2),Integer(1)],[Integer(3),Integer(2)],[Integer(3)]])
>>> G.row_sums()
[11, 9, 7, 5, 3]
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(2)]])
>>> G.row_sums()
[6, 4, 2]
special_entries()[source]#

Return the special entries.

An entry \(a_{i,j}\) is special if \(a_{i-1,j-1} > a_{i,j} > a_{i-1,j}\), that is to say, the entry is neither boxed nor circled and is not in the first row. The name was coined by [Tok88].

EXAMPLES:

sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
sage: G.special_entries()
()
sage: G = GelfandTsetlinPattern([[4,2,1],[4,1],[2]])
sage: G.special_entries()
((2, 0),)
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(1)]])
>>> G.special_entries()
()
>>> G = GelfandTsetlinPattern([[Integer(4),Integer(2),Integer(1)],[Integer(4),Integer(1)],[Integer(2)]])
>>> G.special_entries()
((2, 0),)
to_tableau()[source]#

Return self as a semistandard Young tableau.

The conversion from a Gelfand-Tsetlin pattern to a semistandard Young tableaux is as follows. Let \(G\) be a Gelfand-Tsetlin pattern with \(\lambda^{(k)}\) being the \((n-k+1)\)-st row (note that this is a partition). The definition of \(G\) implies

\[\lambda^{(0)} \subseteq \lambda^{(1)} \subseteq \cdots \subseteq \lambda^{(n)},\]

where \(\lambda^{(0)}\) is the empty partition, and each skew shape \(\lambda^{(k)} / \lambda^{(k-1)}\) is a horizontal strip. Thus define \(T(G)\) by inserting \(k\) into the squares of the skew shape \(\lambda^{(k)} / \lambda^{(k-1)}\), for \(k=1,\dots,n\).

EXAMPLES:

sage: G = GelfandTsetlinPatterns()
sage: elt = G([[3,2,1],[2,1],[1]])
sage: T = elt.to_tableau(); T
[[1, 2, 3], [2, 3], [3]]
sage: T.pp()
  1  2  3
  2  3
  3
sage: G(T) == elt
True
>>> from sage.all import *
>>> G = GelfandTsetlinPatterns()
>>> elt = G([[Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(1)]])
>>> T = elt.to_tableau(); T
[[1, 2, 3], [2, 3], [3]]
>>> T.pp()
  1  2  3
  2  3
  3
>>> G(T) == elt
True
weight()[source]#

Return the weight of self.

Define the weight of \(G\) to be the content of the tableau to which \(G\) corresponds under the bijection between Gelfand-Tsetlin patterns and semistandard tableaux. More precisely,

\[\mathrm{wt}(G) = (d_n, d_{n-1}-d_n, \dots, d_1-d_2),\]

where the \(d_i\) are the row sums.

EXAMPLES:

sage: G = GelfandTsetlinPattern([[2,1,0],[1,0],[1]])
sage: G.weight()
(1, 0, 2)
sage: G = GelfandTsetlinPattern([[4,2,1],[3,1],[2]])
sage: G.weight()
(2, 2, 3)
>>> from sage.all import *
>>> G = GelfandTsetlinPattern([[Integer(2),Integer(1),Integer(0)],[Integer(1),Integer(0)],[Integer(1)]])
>>> G.weight()
(1, 0, 2)
>>> G = GelfandTsetlinPattern([[Integer(4),Integer(2),Integer(1)],[Integer(3),Integer(1)],[Integer(2)]])
>>> G.weight()
(2, 2, 3)
class sage.combinat.gelfand_tsetlin_patterns.GelfandTsetlinPatterns(n, k, strict)[source]#

Bases: UniqueRepresentation, Parent

Gelfand-Tsetlin patterns.

INPUT:

  • n – The width or depth of the array, also known as the rank

  • k – (Default: None) If specified, this is the maximum value that can occur in the patterns

  • top_row – (Default: None) If specified, this is the fixed top row of all patterns

  • strict – (Default: False) Set to True if all patterns are strict patterns

Element[source]#

alias of GelfandTsetlinPattern

random_element()[source]#

Return a uniformly random Gelfand-Tsetlin pattern.

EXAMPLES:

sage: g = GelfandTsetlinPatterns(4, 5)
sage: x = g.random_element()
sage: x in g
True
sage: len(x)
4
sage: all(y in range(5+1) for z in x for y in z)
True
sage: x.check()
>>> from sage.all import *
>>> g = GelfandTsetlinPatterns(Integer(4), Integer(5))
>>> x = g.random_element()
>>> x in g
True
>>> len(x)
4
>>> all(y in range(Integer(5)+Integer(1)) for z in x for y in z)
True
>>> x.check()
sage: g = GelfandTsetlinPatterns(4, 5, strict=True)
sage: x = g.random_element()
sage: x in g
True
sage: len(x)
4
sage: all(y in range(5+1) for z in x for y in z)
True
sage: x.check()
sage: x.is_strict()
True
>>> from sage.all import *
>>> g = GelfandTsetlinPatterns(Integer(4), Integer(5), strict=True)
>>> x = g.random_element()
>>> x in g
True
>>> len(x)
4
>>> all(y in range(Integer(5)+Integer(1)) for z in x for y in z)
True
>>> x.check()
>>> x.is_strict()
True
class sage.combinat.gelfand_tsetlin_patterns.GelfandTsetlinPatternsTopRow(top_row, strict)[source]#

Bases: GelfandTsetlinPatterns

Gelfand-Tsetlin patterns with a fixed top row.

Tokuyama_formula(name='t')[source]#

Return the Tokuyama formula of self.

Following the exposition of [BBF], Tokuyama’s formula asserts

\[\sum_{G} (t+1)^{s(G)} t^{l(G)} z_1^{d_{n+1}} z_2^{d_{n}-d_{n+1}} \cdots z_{n+1}^{d_1-d_2} = s_{\lambda} (z_1, \ldots, z_{n+1}) \prod_{i<j} (z_j+tz_i),\]

where the sum is over all strict Gelfand-Tsetlin patterns with fixed top row \(\lambda+\rho\), with \(\lambda\) a partition with at most \(n+1\) parts and \(\rho = (n,n-1,\dots,1,0)\), and \(s_{\lambda}\) is a Schur function.

INPUT:

  • name – (Default: 't') An alternative name for the variable \(t\).

EXAMPLES:

sage: GT = GelfandTsetlinPatterns(top_row=[2,1,0],strict=True)
sage: GT.Tokuyama_formula()
t^3*x1^2*x2 + t^2*x1*x2^2 + t^2*x1^2*x3 + t^2*x1*x2*x3 + t*x1*x2*x3 + t*x2^2*x3 + t*x1*x3^2 + x2*x3^2
sage: GT = GelfandTsetlinPatterns(top_row=[3,2,1],strict=True)
sage: GT.Tokuyama_formula()
t^3*x1^3*x2^2*x3 + t^2*x1^2*x2^3*x3 + t^2*x1^3*x2*x3^2 + t^2*x1^2*x2^2*x3^2 + t*x1^2*x2^2*x3^2 + t*x1*x2^3*x3^2 + t*x1^2*x2*x3^3 + x1*x2^2*x3^3
sage: GT = GelfandTsetlinPatterns(top_row=[1,1,1],strict=True)
sage: GT.Tokuyama_formula()
0
>>> from sage.all import *
>>> GT = GelfandTsetlinPatterns(top_row=[Integer(2),Integer(1),Integer(0)],strict=True)
>>> GT.Tokuyama_formula()
t^3*x1^2*x2 + t^2*x1*x2^2 + t^2*x1^2*x3 + t^2*x1*x2*x3 + t*x1*x2*x3 + t*x2^2*x3 + t*x1*x3^2 + x2*x3^2
>>> GT = GelfandTsetlinPatterns(top_row=[Integer(3),Integer(2),Integer(1)],strict=True)
>>> GT.Tokuyama_formula()
t^3*x1^3*x2^2*x3 + t^2*x1^2*x2^3*x3 + t^2*x1^3*x2*x3^2 + t^2*x1^2*x2^2*x3^2 + t*x1^2*x2^2*x3^2 + t*x1*x2^3*x3^2 + t*x1^2*x2*x3^3 + x1*x2^2*x3^3
>>> GT = GelfandTsetlinPatterns(top_row=[Integer(1),Integer(1),Integer(1)],strict=True)
>>> GT.Tokuyama_formula()
0
random_element()[source]#

Return a uniformly random Gelfand-Tsetlin pattern with specified top row.

EXAMPLES:

sage: g = GelfandTsetlinPatterns(top_row = [4, 3, 1, 1])
sage: x = g.random_element()
sage: x in g
True
sage: x[0] == [4, 3, 1, 1]
True
sage: x.check()

sage: g = GelfandTsetlinPatterns(top_row=[4, 3, 2, 1], strict=True)
sage: x = g.random_element()
sage: x in g
True
sage: x[0] == [4, 3, 2, 1]
True
sage: x.is_strict()
True
sage: x.check()
>>> from sage.all import *
>>> g = GelfandTsetlinPatterns(top_row = [Integer(4), Integer(3), Integer(1), Integer(1)])
>>> x = g.random_element()
>>> x in g
True
>>> x[Integer(0)] == [Integer(4), Integer(3), Integer(1), Integer(1)]
True
>>> x.check()

>>> g = GelfandTsetlinPatterns(top_row=[Integer(4), Integer(3), Integer(2), Integer(1)], strict=True)
>>> x = g.random_element()
>>> x in g
True
>>> x[Integer(0)] == [Integer(4), Integer(3), Integer(2), Integer(1)]
True
>>> x.is_strict()
True
>>> x.check()
top_row()[source]#

Return the top row of self.

EXAMPLES:

sage: G = GelfandTsetlinPatterns(top_row=[4,4,3,1])
sage: G.top_row()
(4, 4, 3, 1)
>>> from sage.all import *
>>> G = GelfandTsetlinPatterns(top_row=[Integer(4),Integer(4),Integer(3),Integer(1)])
>>> G.top_row()
(4, 4, 3, 1)