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.


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.


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


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.


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.


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.


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.


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


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 (PQ) 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\}


It remains to show how we can construct an A given (PQ). 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}.


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}.


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


Find the matrix corresponding to the following tableaux:



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

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

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