Gelfand-Tsetlin Patterns

1. Definition

A Gelfand-Tsetlin pattern (or GT-pattern) is a triangular configuration of non-negative integers,

$$\begin{array}{cccccccccccccc} x_{n1} & & x_{n2} & & \cdots & & x_{nn} \\ & \ddots & & \ddots & & & & & \\ & & x_{21} & & x_{22} \\ & & & x_{11} &\end{array}$$

where the entries must satisfy the conditions $x_{i+1,j} \geq x_{ij}$ and $x_{ij} \geq x_{i+1,j+1}$ for all values of $i$, $j$ where the indexing is defined. The conditions ensure every row in the pattern defines an integer partition. Furthermore, any two adjacent rows define a skew shape.

There is a natural bijection between GT-patterns and semi-standard Young tableaux; The skew shape defined by row $j$ and $j+1$ in a GT-pattern describes which boxes in the corresponding tableau that have content $j$.

2. Gelfand-Tsetlin Polytopes

The inequalities above (with a fixed top row and fixed row sums) describe a polytope in $\mathbb{R}^{\frac{n(n+1)}{2}}$, and each GT-pattern therefore naturally corresponds to a lattice point inside this polytope. This type of polytope has integer vertices.

The usual definition of a Gelfand-Tsetlin polytope is to impose an additional restriction on the row sums. Thus, the GT-polytope $P_{\lambda,w}$ is defined as all real Gelfand-Tsetlin patterns $(x_{ij})$ such that $x_{ni}=\lambda_i$ and $\sum_i (x_{j,i}-x_{j-1,i}) = w_j$ where $x_{ij}=0$ whenever the indexing is outside the triangular array. Then, the lattice points in $P_{\lambda,w}$ are in bijection with semi-standard Young tableaux of shape $\lambda$ and type $w$, and the lattice points are counted by the Kostka numbers $K_{\lambda w}$.

The vertices of these polytopes are for small examples integral [KTT04], but there are families of GT-patterns where the GT-polytope has arbitrary large denominator, see [Lo04].

Hence, for each pair $(\lambda,w)$ the polytope can $P_{\lambda,w}$ either be

All non-empty $P_{\lambda,w}$ contain at least one integral vertex, (this is a consequence of Knutson and Tao's proof of the Saturation conjecture). All polytopes $P_{\lambda,\lambda}$ consist of exactly one lattice point.

Since $K_{\lambda w}$ is invariant under permutation of the entries in $w$ (proved by Bender and Knuth), most research has been focused on the case when $w$ is a partition. However, $P_{\lambda,w}$ might be integral for some $w$ but non-integral for some permutation of w.

3. Examples

The following GT-pattern has shape $(5,4,3,1)$ and weight (or type) $(4,4,3,1,1)$.

$$\begin{matrix}5 & & 4 & & 3 & & 1 & & 0\\ & 5 & & 4 & & 3 & & 0 \\ & & 5 & & 3 & & 3 & \\ & & & 5 & & 3 \\ & & & & 4\\ \end{matrix} \qquad \overset{bijection}{\longleftrightarrow} \qquad \begin{matrix}1 & 1 & 1 & 1 & 2\\2 & 2 & 2 & 4\\3 & 3 & 3\\5\\\end{matrix}.$$

See this video for an explanation of this bijection.

4. Properties

5. Remarks

For example, $\begin{matrix}5 & & 4 & & 3 & & 1\\ & 4 & & 4 & & 3 & & 1\\ & & 4 & & 4 & & 2 & & 1\\ & & & 4 & & 3 & & 2 & & 1\\ & & & & 3 & & 2 & & 2 & & 0\\ & & & & & 2 & & 2 & & 0 & & 0\\\end{matrix}$ corresponds to the skew semi-standard Young tableau $\begin{matrix} & & 1 & 2 & 5\\ & & 2 & 3\\1 & 1 & 4\\2\\\end{matrix}$.

Here is a fun video showing the bijection from a GT Pattern to a SSYT: Video

Here, the shape is a skew shape, $(5, 4, 3, 1)/(2, 2)$ and the weight is $(3, 3, 1, 1, 1)$.

Using the alternating sign matrix and its monotone triangle as above we have a map which gives the following Gelfand Tsetlin pattern:\begin{align*} 1 & &2 & &3 & &4 \\ &\; \; \; \; \; \; \;1 & &\; \; \; \; \; \; \;\;3 & &\; \; \; \; \; \; \;4 & \\ & & 1 & &3 & & \\ & & &\; \; \; \; \; \; \; \;2 & & & \end{align*} which has column partial sum matrix: $\begin{pmatrix}0 &1 &0 &0\\1 &0 &1 &0 \\1 &0 &1 &1 \\1 &1 &1 &1 \end{pmatrix}$ and maps to the Alternating Sign Matrix: $\begin{pmatrix}0 &1 &0 &0 \\1 &-1 &1 &0 \\0 &0 &0 &1 \\0 &1 &0 &0 \end{pmatrix}$

6. Tiles

In [Lo04], the notion of tiles is introduced as an important statistic on GT-patterns. The related statistic is linked to the dimension of faces of Gelfand-Tsetlin polytopes.

The tiling of a pattern is the finest partition of the entries in the pattern, such that adjacent (NW,NE,SW,SE) entries that are equal belong to the same part. These parts are called tiles, and each entry in a pattern belong to exactly one tile.

A tile is free if it do not intersect any of the first and the last row.

For example,

$$\begin{matrix}5 & & 4 & & 2 & & 1 & & 0\\ & 5 & & 3 & & 2 & & 0 \\ & & 5 & & 3 & & 2 & \\ & & & 5 & & 2 \\ & & & & 4\\ \end{matrix}$$

has 7 tiles, and the tile consisting of the two 3:s is the only free tile.

"The machinery of tilings allows us easily to find non-integral vertices of GT-polytopes by looking for a tiling with a tiling matrix satisfying certain properties. [See Lemma 2.2 in source] Then the tilings can be "filled" in a systematic way with the entries of a GT pattern that is a non-integral vertex." [Lo04]

7. Statistics

We have the following 11 statistics in the database:

The number of circled entries.
The number of boxed entries.
The number of special entries.
The number of boxed and circled entries.
The sum of the entries of the Gelfand-Tsetlin pattern.
The single entry in the last row.
The number of boxed plus the number of special entries.
The total number of tiles in the Gelfand-Tsetlin pattern.
The number of free tiles in the pattern.
Number of free entries.
The sum of the first row in a Gelfand-Tsetlin pattern.

8. Maps

We have the following 1 maps in the database:

to semistandard tableau

The following maps have not yet considered:

This map can be found by looking at the top row (or first partition) of a GT Pattern. Moving from left to right, each element corresponds to the amount of numbers (per row) in a Semi-standard Tableaux.

To find this map:

This map is given by the Sage command to_tableau(). See also this video.

9. Sage Reference & Example

Sage reference manual

10. References

[KTT04]   R.C. King, C. Tollu, and F. Toumazet, Stretched Littlewood-Richardson coefficients and Kostka coefficients, CRM Proceedings and Lecture Notes (2004), no. 24, 99–112..

[Lo04]   J. A. De Loera and T. B. McAllister, Vertices of Gelfand-Tsetlin polytopes, Discrete Comput. Geom. 32 (2004), no. 4, 459–470..

[Sta99]   R. Stanely, Enumerative Combinatorics II, Cambridge University Press (1999).

CategoryCombinatorialCollection

GelfandTsetlinPatterns (last edited 2016-05-30 11:20:57 by ChristianStump)