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.

Without further ado:

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 1s), 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.

Advertisements

2 Comments

  1. […] already shown this (I hinted at it in the second post): this equality is none other than the the RSK correspondence. More specifically, the RSK correspondence is the above equality when written in the basis. To see […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: