Polynomials and Representations VII

Our next task is as follows:

Given partition $\lambda$ and vector $\mu = (\mu_1, \mu_2, \ldots)$ , count the number of semistandard Young tableaux with shape $\lambda$ and type $\mu$ (i.e. $k$ occurs $\mu_k$ times).

Proposition. The number of SSYT with shape $\lambda$ and type $\mu$ remains invariant when we permute the $\mu_i$ ‘s around.

Proof

Since each permutation is a product of transpositions of the form $(i, i+1),$ it suffices to prove invariance under $(i, i+1).$ This is via the Bender-Knuth involution.

Given an SSYT with $\mu_i$ entries labelled $i$ and $\mu_{i+1}$ entries labelled $i+1$ , we first pair up vertical elements labelled $i$ and $i+1$ and leave them untouched. For the other elements, we consider each row which has $t\ge 0$ copies of $i$ followed by $u \ge 0$ copies of $i+1.$ Now replace them by $u$ copies of $i$ followed by $t$ copies of $i+1.$

ssyt_bender-knuth_v2

The rows remain weakly increasing, but are the columns still strictly increasing? The only problem which may occur is when an $i$ is replaced by $i+1$ (or vice versa) and this is equal to the entry below (or above). But we have already excluded all such cases by pairing $i$ and $i+1$ earlier. ♦

Hence we might as well sort the entries of $\mu$ and assume it is a partition.

Definition. Given partitions $\lambda, \mu$ , the Kostka number $K_{\lambda\mu}$ is the number of SSYT of the shape $\lambda$ and type $\mu.$

Clearly $K_{\lambda\mu} = 0$ if $|\lambda| \ne |\mu|$ .

blue-lin

More on Kostka Numbers

As an example, take $\lambda = (2, 1)$ and $\mu = (1, 1, 1)$ . Since $\mu_1 = \mu_2 = \mu_3 = 1$ , this is in fact an SYT and there are two possibilities.

young_tableau_2_examples

On the other hand, if $\l = (1, 1, 1)$ and $\mu = (2, 1)$ , no such tableau exists. Hence

$K_{21, 111} = 2, \qquad K_{111, 21} = 0.$

Lemma 1. If $K_{\lambda\mu} > 0$ , then $\lambda \trianglerighteq \mu$ , i.e. for each $r$ we have:

$\lambda_1 + \lambda_2 + \ldots + \lambda_r \ge \mu_1 + \mu_2 + \ldots + \mu_r.$

Also $K_{\lambda\lambda} = 1$ .

Proof

Consider a positive integer $r$ ; since each column is strictly increasing, each of $1, 2, \ldots, r$ must occur in the first $r$ rows, so the number of boxes $\lambda_1 + \ldots + \lambda_r$ is at least the number of these integers, i.e. $\mu_1 + \ldots + \mu_r.$ This proves the inequality. If equality holds for all $r$ , this constraint forces us to have all $i$ ‘s on the $i$ -th row. ♦

The rest of the article is dedicated to proving:

Main Theorem. For any partitions $\lambda, \mu$ , we have:

$\displaystyle M_{\lambda\mu}= \sum_\nu K_{\nu\lambda} K_{\nu\mu} = \sum_{\nu\trianglerighteq \lambda,\ \nu\trianglerighteq\mu} K_{\nu\lambda} K_{\nu\mu}.$

Written in matrix form, this gives $\mathbf M = \mathbf K^t \mathbf K.$

blue-lin

RSK Correspondence

The Robinson–Schensted–Knuth (RSK) correspondence works as follows; suppose we have a matrix $A=(A_{ij})$ of non-negative integers, with column sum $\sum_i A_{ij} = \lambda_j$ and row sum $\sum_j A_{ij} = \mu_i.$ We do not assume that $\lambda$ and $\mu$ are partitions. Now take

$w_A := \begin{pmatrix} i_1 & i_2 & i_3 & \ldots \\ j_1 & j_2 & j_3 & \ldots\end{pmatrix}$

satisfying the following:

$i_1 \le i_2\le \ldots$ ;
if $i_r = i_{r+1}$ , then $j_r \le j_{r+1}$ (together with the first condition, this means the sequence of $(i_r, j_r)$ is in lexicographical order);
$A_{ij}$ is exactly the number of $r$ for which $(i_r, j_r) = (i, j).$

For example,

$A=\begin{pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0\end{pmatrix}\ \implies\ w_A = \begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3\\ 1 & 3 & 3 & 2 & 2 & 1 & 2\end{pmatrix}.$

Now we construct a pair of SSYT $(P, Q)$ as follows:

Start with empty SSYT $P(0), Q(0)$ .
For each $r=0, 1, \ldots$ , let $P(r+1) := P_r \leftarrow j_{r+1}$ and $Q(r+1)$ be the SSYT with the same shape as $P(r+1)$ but with $i_{r+1}$ added to the extra box.

The above example for A gives us the following $P(r), Q(r)$ ; the coloured cells on the left refer to the bumped cells, while those on the right are the additional cells attached to maintain the same shape.

rsk_two_tableaux

Lemma 2. The resulting $Q(r)$ is an SSYT for each $r.$

Proof

Indeed if $i_{r+1} > i_r$ , then $i_{r+1}$ is larger than any other number in $Q(r)$ , so we still get an SSYT after placing it in the extra box. On the other hand if $i_{r+1} = i_r = \ldots = i_{r-j} > i_{r-j-1},$ then $j_{r+1} \ge j_r \ge\ldots\ge j_{r-j}$ so by lemma 3 here, the additional cell for $i_{r+1}$ lies strictly to the right of the bumped cells of $I(P(r-1), j_r), \ldots, I(P(r-j-1), j_{r-j}).$ Since these include all occurrences of $i_{r}$ in $Q(r)$ , it is safe to write $i_r$ in the new cell for $Q(r+1).$ ♦

Taking the final pair $(P(d), Q(d))$ , we have obtained (P, Q) of the same shape such that the type of P is $\lambda$ and that of Q is $\mu.$

Theorem. The correspondence $A\mapsto (P, Q)$ gives a bijection:

$\displaystyle\left\{\begin{array}{c}\text{non-negative integer matrix } A_{ij}\\ \sum_i A_{ij} = \lambda_j,\ \sum_j A_{ij} = \mu_i\end{array}\right\} \leftrightarrow \left\{ (P, Q): \begin{array}{c}\text{type}(P) = \lambda,\ \text{type}(Q) = \mu \\ \text{shape}(P) = \text{shape}(Q)\end{array}\right\}$

Proof

It remains to show how we can construct an A given (P, Q). Find the largest entry k of Q; if there are several of them, pick the rightmost one. Note that such a square must be a corner square (i.e. no square to its right or below). Now remove it from Q to obtain $i_d$ and perform reverse row-insertion from the corresponding square of P to obtain $j_d.$ This gives us $(P(d-1), Q(d-1))$ and a pair $(i_d, j_d).$

By construction we have $i_d \ge i_{d-1} \ge \ldots.$ Now suppose $i_r = i_{r-1}$ along the way. The box removed for $i_r$ in Q is strictly to the right of $i_{r-1}.$ Hence in P, the bumped entries for $j_r$ are strictly to the right of $j_{r-1}$ (by lemma 3 here and the exercise after it). In particular $j_r \ge j_{r-1}.$ ♦

Taking the cardinality of both sets, we obtain the desired equality:

$\displaystyle M_{\lambda\mu}= \sum_\nu K_{\nu\lambda} K_{\nu\mu}.$

Example

Suppose d=3. Labeling the columns and rows by partitions 3, 2+1 and 1+1+1, we get the following matrices. One easily checks that $\mathbf M = \mathbf K^t \mathbf K.$

$\mathbf M = \begin{pmatrix} 1&1&1 \\ 1&2&3 \\ 1&3&6 \end{pmatrix}, \qquad \mathbf K = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1\end{pmatrix}.$

Note

A is a permutation matrix if and only if P and Q are both standard Young tableaux.

Exercise

Find the matrix corresponding to the following tableaux:

rsk_exercise

Exercise

Let $f^\lambda$ be the number of SYT of shape $\lambda.$ Prove that we have $d! = \sum_{\lambda \vdash d} (f^\lambda)^2.$