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:

Observation. $w(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