Gelfand-Tsetlin Patterns

Contents

# 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$ (counting from the bottom) in a GT-pattern describes which cells in the corresponding tableau contain $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

- Empty
- Integral
- Non-integral

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

See [Sta99] p. 313 for further references.

# 5. Remarks

- It is possible to extend this definition to a parallelogram GT-pattern, in which case the GT-pattern corresponds to a skew semi-standard Young tableau.

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

There also exists a correspondence from Gelfand Tsetlin Patterns to Alternating Sign Matrices. In this case we use a special type of Gelfand Tsetlin pattern called a

*monotone triangle*. Monotone triangles are Gelfand Tsetlin patterns with strict inequalities instead of weak, and the top row equals $1 2 \cdots n$.

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** on **Gelfand-Tsetlin patterns** in the database:

# 8. Maps

We have the following **3 maps** in the database:

# 9. Sage Reference & Example

# 10. References

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