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

Proof

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

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.

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