Polynomials and Representations XVII

Two Important Results

In this article and the next, we will find a combinatorial way of computing the Littlewood-Richardson coefficient.

The key result we have so far is that given any word w there is a unique SSYT T (called the rectification of w) such that its word w(T) is Knuth-equivalent to w. This is related to the RSK construction as follows: recall that we obtain a 2-row array \small \begin{pmatrix} i_1 & \ldots i_d \\ j_1 & \ldots j_d\end{pmatrix}, then define a pair of SSYT of the same shape via:

  • P_0 = Q_0 = \emptyset,
  • P_{r+1} = P_r \leftarrow j_{r+1} and Q_{r+1} is obtained from Q_r by appending i_{r+1} so that it has the same shape as P_{r+1},
  • let (P, Q) = (P_d, Q_d).

In particular P = ((\emptyset \leftarrow j_1) \leftarrow j_2) \leftarrow \ldots and since w(T\leftarrow m) \equiv w(T) * (m) we get:

Observationw(P) is Knuth-equivalent to the word (j_1, \ldots, j_d). In other words, P is the rectification of (j_1, \ldots, j_d).

blue-lin

First Theorem

Theorem 1. Suppose, in the RSK construction, the pair of SSYT (P, Q) of the same shape gives us the two-row matrix \small\begin{pmatrix} i_1 & \ldots & i_d \\ j_1 & \ldots & j_d \end{pmatrix}. Now let T be any SSYT and define the construction:

  • let P_0 = T and Q_0= \emptyset;
  • for each of r=0,\ldots,d-1, let P_{r+1} = P_{r} \leftarrow j_{r+1}, and Q_{r+1} be obtained from Q_r by attaching the new square of P_{i+1} to it, and filling in i_r.

The resulting Q_l is a skew SSYT whose rectification is Q.

Example

Suppose we have the matrix \small\begin{pmatrix} 1 & 1 & 1 & 2 & 2 \\ 1 & 2 & 2 & 1 & 3 \end{pmatrix} and the initial SSYT T = {\small \boxed{\begin{matrix} 1 & 2 \\ 2 \end{matrix}}}. This gives:

rsk_skew_tableau_version

The rectification of Q_5 is \small\boxed{\begin{matrix} 1 & 1 & 1 & 2 \\ 2\end{matrix}}, which is consistent with our claim.

Proof

Let w(T) = (t_1, t_2, \ldots, t_m). Add symbols s_1 < s_2 < \ldots < s_m which are strictly smaller than all i_r. (E.g. we can add a large constant to all existing labels). The RSK construction for 

\displaystyle \begin{pmatrix} s_1 & s_2 & \ldots & s_m \\ t_1 & t_2 & \ldots & t_m \end{pmatrix}

gives us a pair of SSYT. By the above observation, the first term of this pair is T; let the second term be U. Hence we get RSK correspondences:

rsk_skew_tableau_proofpic_new

The second correspondence is given in the conditions, while the third follows from

P_d = (T \leftarrow j_1) \leftarrow j_2 \leftarrow \ldots = ((\ldots ((\emptyset \leftarrow t_1) \leftarrow t_2) \leftarrow \ldots \leftarrow j_1) \leftarrow j_2) \ldots

and the definition of Q_d. By the symmetry theorem, swapping the two SSYT corresponds to swapping the two rows of the matrix and sorting the columns lexicographically so we get RSK correspondences:

rsk_skew_tableau_proofpic_2_new

Again by our observation above, the left matrix UQ_d satisfies

w(UQ_d) \equiv (s_1, \ldots, s_m) * some order of  (i_1, \ldots, i_d).

By the lemma here, dropping the m smallest terms still gives us Knuth-equivalent words. On the LHS, this gives the skew SSYT w(Q_d). On the RHS, this gives some order of (i_1, \ldots, i_d). From the first RSK correspondence, Q is the rectification of that same order of (i_1, \ldots, i_d). Hence w(Q_d) \equiv w(Q) and we are done. ♦

blue-lin

Second Theorem

Theorem 2. Let \lambda, \mu, \nu be partitions. Suppose T is an SSYT of shape \lambda and U is an SSYT of shape \nu. Then there is a bijection between:

  • pairs of SSYT (P, Q) of shapes \mu, \nu respectively, such that T = PQ;
  • skew SSYT U_1 of shape \lambda/\mu such that its rectification is U.

Recall that PQ is the rectification of the skew SSYT obtained by putting P below and Q above.

skew_tableau_and_double_tableaux_corr

Note

\lambda/\mu is well-defined only when \lambda_i \ge \mu_i for all i; otherwise, the second set is empty; it will follow from the proof that the first set is empty too.

Proof

Let (P,Q) be of shapes \mu,\nu respectively such that T=PQ. The RSK correspondence for (Q, U) gives us a two-row matrix:

\begin{pmatrix}i_1 & \ldots & i_d \\j_1 & \ldots & j_d\end{pmatrix}.

Let T_1 be the SSYT obtained from P by inserting j_1, \ldots, j_d and U_1 be the skew SSYT obtained by putting i_1, \ldots, i_d in the new empty boxes. By construction we have T_1 = PQ = T, so U_1 has shape \text{shape}(T) / \text{shape}(P) = \lambda/\mu. By theorem 1, the rectification of U_1 is U.

Conversely, suppose we are given skew U_1 of shape \lambda/\mu such that U_1 \equiv U. Let T_1 be the SSYT obtained from U_1 by attaching an SSYT V of shape \mu and entries smaller than those of U_1.

double_tableaux_proof

Then (T, T_1) corresponds via RSK to a two-row matrix:

\begin{pmatrix}x_1 & \ldots & x_m & i_1 & \ldots & i_d \\y_1 & \ldots & y_m & j_1 & \ldots & j_d\end{pmatrix}

where x_1, \ldots, x_m are from V and i_1, \ldots, i_d are from U_1. By RSK, the first m columns correspond to a pair of SSYT (P, V) of shape \mu. The remaining d columns correspond to a pair (Q, U) since U is the rectification of U_1. Hence Q has shape \nu. Finally we have T = P \leftarrow j_1 \leftarrow j_2 \leftarrow \ldots which gives T=PQ as desired. ♦

blue-lin

Our main interest is in the following.

Corollary. For each SSYT U of shape \nu, the number of skew SSYT U_1 of shape \lambda/\mu such that U_1 \equiv U is dependent only on \mu, \nu, \lambda, and independent of the choice of U.

Denote this number by d^\lambda_{\mu\nu}Recall that the skew Schur function

\displaystyle s_{\lambda/\mu} = \sum_T x^T over all skew SSYT T of shape \lambda/\mu.

Let T' be the rectification of T. By the corollary, if T' has shape \nu, there are exactly d^\lambda_{\mu\nu} possibilities for T. Hence,

\displaystyle s_{\lambda/\mu} = \sum_\nu d^\lambda_{\mu\nu}\sum_{T'} x^{T'}, over all partitions \nu and SSYT T' of shape \nu.

\displaystyle \implies s_{\lambda/\mu} = \sum_\nu d^{\lambda}_{\mu\nu} s_\nu.

So \displaystyle c_{\mu\nu}^\lambda = \left< s_{\lambda/\mu}, s_\nu\right> = d_{\mu\nu}^\lambda and our d_{\mu\nu}^\lambda is precisely the Littlewood-Richardson coefficient, and we get a combinatorial interpretation:

Summary. For any SSYT U_1 of shape \nu, c_{\mu\nu}^\lambda is the number of skew SSYT of shape \lambda/\mu whose rectification is U_1.

blue-lin

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