Home » Mathematics » Algebraic combinatorics » The RSK Correspondence

The RSK Correspondence

This is another tableau combinatorics post. The Robinson-Schensted-Knuth correspondence, or RSK for short, is another important theorem and algorithm in tableau combinatorics; I’ll discuss it here, though I won’t try to motivate it. For now, it will be something of a curiosity. As always, my reference is Fulton’s book Young Tableaux.

First, recall the definitions of partitions, Young diagrams and Young tableaux:

Definition. A partition is a finite, weakly decreasing sequence of positive integers, say $\lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0$). A Young diagram is a pictorial representation of a partition, as a grid of left-aligned boxes, with $\lambda_1$ boxes in the first row, $\lambda_2$ in the second, and so on.

Definition. A Young Tableau is a Young diagram with positive integers entered in the boxes, nondecreasing in both the rows and columns. A semi-standard or column-strict Young Tableau is one where the columns are strictly increasing.

For RSK, we’ll also be interested in the weight of our tableaux: if $T$ has $\mu_1$ 1s, $\mu_2$ 2s, and so on, the weight of $T$ is the sequence $w(T) = (\mu_1, \mu_2, \ldots).$

So, let’s let $SSYT(\lambda, \mu)$ denote the set of semi-standard Young tableaux of shape $\lambda$ and weight $\mu$. These sets show up elsewhere in algebraic combinatorics (coming soon!). Their cardinalities $K_{\lambda,\mu} = |SSYT(\lambda,\mu)|$ are known as the Kostka numbers. The RSK correspondence will be useful later on: it’ll show us that a certain pair of change-of-basis matrices coincide.

Theorem (RSK correspondence). There is a bijection between the following:

• Ordered pairs of tableaux $B,R$, of the same shape, with weights $\mu_B, \mu_R$, and
• Matrices with nonnegative integer entries, with column sums given by $\mu_B$ and row sums given by $\mu_R.$
• In this bijection, we refer to $B$ as the “bumping tableau” and $R$ as the “recording tableau”. We let $A(\mu_B,\mu_R)$ denote the corresponding set of matrices.

Notationally, we’re giving a bijection:

$\displaystyle{ \bigsqcup_{\lambda, \mu_B, \mu_R} SSYT(\lambda,\mu_B) \times SSYT(\lambda,\mu_R) \to \bigsqcup_{\mu_B,\mu_R} A(\mu_B,\mu_R) \subset \text{Mat}(\mathbb{Z}_{\geq 0})}.$

where $\text{Mat}(\mathbb{Z}_{\geq 0})$ is the set of matrices with nonnegative integer matrices.

Various consequences follow from the RSK correspondence, largely because integer matrices are easier to understand and picture than Young tableaux. For example: the transpose operation gives a bijection (an involution, in fact)

$K(\mu_B,\mu_R) \to K(\mu_R,\mu_B)$,

swapping the row and column sums. What does this correspond to on the tableau side? Hopefully it corresponds to swapping the bumping and recording tableau. This will be something of a surprise, as we’ll see, since the correspondence works by an algorithm that treats the two tableaux completely differently from each other.

The RSK Correspondence

Here’s how the algorithm works: we’ll make use of the row bumping algorithm from my last post. Given a matrix $A$ with nonnegative integer entries, we’ll use row-bumping to construct a tableau $T_B$. Simultaneously, we’ll “record” the algorithm step-by-step in another tableau $T_R$.

Here’s how it works: we read through the matrix, in standard English order (left to right, top to bottom). The entry $a_{ij}$ tells us to bump in $a_{ij}$ boxes into $T_B$, each containing the entry $j$. Each time we do this, the size of $T_B$ grows by one box, somewhere along its outer edge. We “record” this growth by adding one box to the recording tableau, $T_R$, in the same location, and the recording box gets the entry $i$.

Observation. By construction, $T_B$ and $T_R$ have the same shape. Moreover, the first row sum of $A$ tells us how many 1s are in $T_R$; the first column sum tells us how many 1s are in $T_B$. (Similarly for the other rows and columns.)

The only mysterious part of the process is that the recording tableau is, in fact, semistandard. Note that the recording tableau receives a bunch of 1s as we go along the first row of $A$, then a bunch of 2s, and so on, so its entries get filled in (weakly) increasingly. So, certainly the row condition is satisfied. The column-strictness condition is less obvious to check (relying on tracking what happens if we bump in a sequence of boxes with increasing, or decreasing, entries.)

As with other combinatorial theorems, a lot of the hard work went into correctly formulating the problem.

Some consequences

The general statement I gave above is certainly nice, and the algorithm is very clever! But there’s more: if we specialize it to various cases, we’ll get some cool combinatorial facts.

First, suppose we restrict the integer matrix to have row and column sums equal to 1. (This means our matrix is square, and that it should be a permutation matrix.) On the tableau side, this means we will end up with standard tableaux, where both the rows and columns are strictly increasing, and each number from $1$ to $n$ occurs exactly once. On the matrix side, there are exactly $n!$ permutation matrices, so RSK specializes to the formula:

$\displaystyle{ \sum_{\lambda: |\lambda|=n} |SYT(\lambda)|^2 = n!}$

The connection to the symmetric group $S_n$ is very strong here. Namely, we’ll later on use standard tableaux to construct irreducible representations of $S_n$, of dimension $|SYT(\lambda)|$, for each $\lambda$ with $n$ boxes. Then, the above sum becomes a combinatorial version of the statement that, for any finite group $G$ with irreducible representations $V_1, \ldots, V_n$,

$\displaystyle{ \sum_{i=1}^n \text{dim}(V_i)^2 = |G|.}$

In the same vein of thought, if we just restrict to having row sums equal to 1, and we restrict the matrix to be $m \times n$, then there are $n^m$ such matrices. On the tableau side, we’re getting a recording tableau of weight $(1, 1, \ldots, 1)$ (with $m 1$s), so the recording matrix is a standard tableau. The bumping tableau can be anything with $m$ boxes, but its entries can only range from $1$ to $n$. So, if we let $d_\lambda(n)$ be the set of SSYTs of shape $\lambda$ and entries ranging from $1$ to $n$, then

$\displaystyle{ \sum_{\lambda: |\lambda|=m} |SYT(\lambda)| \cdot d_\lambda(n) = n^m.}$

There are other identities and relationships we can find. For instance, since the transpose corresponds to swapping the recording and bumping tableaux, symmetric matrices correspond to individual tableaux, i.e. the set $SSYT(\lambda,\mu)$.

One last observation is that permuting the rows and columns of our integer matrix corresponds to reordering the weights. Since this clearly doesn’t change the number of admissible integer matrices, we get the following:

Theorem. For any permutation $\sigma$, the sets $SSYT(\lambda,\mu)$ and $SSYT(\lambda, \sigma \cdot \mu)$ have the same cardinality. That is, the number of semistandard tableaux of shape $\lambda$ and weight $\mu$ doesn’t depend on the ordering of $\mu$.

This is quite a surprise, since SSYTs are not “symmetric” in any obvious way with respect to reordering the alphabet. It’s certainly not clear that there are as many ways to fill a tableau with, say, $\mu = (1,3,5)$, (one 1, three 2s, five 3s) as $\mu = (5,1,3)$ (five 1s, one 2, three 3s). The 1s need to go in the top row, for example, while the 2s and 3s have other, different rules constraining their placement.

Still, it’s true, and there actually is a way to make this bijection clear, called the Bender-Knuth involution.