Polynomials and Representations XVIII

Littlewood-Richardson Coefficients

Recall that the Littlewood-Richardson coefficient satisfies:

$c^\lambda_{\mu\nu} = \left<s_\lambda, s_\mu s_\nu\right> = \left< s_{\lambda/\mu}, s_\nu\right>.$

By the previous article, for any SSYT $U_1$ of shape $\nu$ , $c^\lambda_{\mu\nu}$ is the number of skew SSYT of shape $\lambda/\mu$ whose rectification is $U_1.$ Since this number is independent of our choice of $U_1$ as long as its shape is $\nu,$ we take the most natural one.

Definition. An SSYT is said to be canonical if its $r$ -th row comprises of all $r.$ For example, the following is a canonical SSYT of shape (5, 4, 3).

canonical_tableau

Note that an SSYT is canonical if and only if its shape is the same as its type. Thus $c_{\mu\nu}^\lambda$ is the number of skew SSYT of shape $\lambda/\mu$ such that its rectification is canonical of shape $\nu.$

blue-lin

Condition for Canonical SSYT

Definition. A word $w = (w_1, w_2, \ldots, w_d)$ is a reverse lattice word if, for each $i$ , the substring $(w_i, w_{i+1}, \ldots, w_d)$ has at least as many 1’s as it has 2’s, at least as many 2’s as it has 3’s, etc.

A skew SSYT $T$ is called a Littlewood-Richardson tableau if $w(T)$ is a reverse lattice word.

For example, the following skew SSYT is a Littlewood-Richardson tableau since its word is (1,3,2,2,1,2,1,1).

littlewood_richardson_tableau

Lemma 1. An SSYT $T$ is a Littlewood-Richardson tableau if and only if it is canonical.

Proof

Indeed, $w(T)$ must end in 1, so the last entry of the first row is 1. Since each row is weakly increasing, the whole of first row is 1. Now the last entry of the second row is strictly greater than 1, but since $w(T)$ is a reverse lattice word, that entry can only be 2. Thus the whole of second row comprises of 2’s. And so on. ♦

Lemma 2. If $w$ and $w'$ are Knuth-equivalent words, then $w$ is a reverse lattice word if and only if $w'$ is.

Proof

We may assume $w'$ is obtained from $w$ via R1 or R2. For convenience, we say that a word is OK if it has at least as many $i$ as it has $(i+1)$ , for each $i.$

Consider R1; the other case is similar. We find a consecutive triplet $(a,b,c)$ in $w$ with $c < a \le b,$ then replace $(a,b,c) \mapsto (a, c, b)$ to form $w'.$ Let us show that, for any word $v,$ the four words on the left are OK if and only if the four words on the right are OK.

$\displaystyle\left.\begin{aligned}a,b,c,& v\\b,c,& v\\c,& v\\ & v \end{aligned}\right\} \text{ OK } \iff \left.\begin{aligned} a,c,b,& v\\ c,b,& v\\ b,& v\\ & v \end{aligned}\right\} \text{ OK }$

We only need to check the third word in each case. Suppose the LHS is OK.

If b,v is not OK, since v is OK there must be a d < b such that d and b occur an equal number of times in v.
Since b,c,v is OK, we must have d = c, and so any element between c and b (inclusive) occurs an equal number of times in v.
In particular, a, b, c each occurs an equal number of times in v.
Now if a < b, then b,c,v has more b‘s than a‘s, and if a = b, then a,b,c,v has more a‘s than c‘s, which contradicts the fact that the LHS is OK.

Now suppose the RHS is OK. If c,v is not OK, there is a d < c which occurs as many times in v as c. But now c,b,v is not OK, which gives a contradiction. ♦

For example, check that the rectification of the above Littlewood-Richardson tableau is:

littlewood_richardson_tableau_after_sliding

Exercise

Write out the proof for R2.

Now, putting the above two lemmas together, we have:

Corollary. A skew SSYT $T$ is a Littlewood-Richardson tableau if and only if its rectification is canonical.

Proof

Indeed if $T'$ is its rectification, then $T$ is Littlewood-Richardson if and only if $w(T)$ is a reverse lattice word; by lemma 2, this holds if and only if $w(T')$ is a reverse lattice word. By lemma 1, this holds if and only if $T'$ is canonical. ♦

We thus obtain:

Littlewood-Richardson Rule. $c_{\mu\nu}^\lambda$ is the number of Littlewood-Richardson skew SSYT of shape $\lambda/\mu$ and type $\nu.$

blue-lin

Example 1: Expanding Skew Schur Polynomials

Consider the skew Schur polynomial $s_{\lambda/\mu}$ where $\lambda = (4,3,2)$ and $\mu = (2,1).$ To express $s_{\lambda/\mu}$ as a linear sum of Schur polynomials, we only need to consider partitions $\nu$ of $|\lambda| - |\mu| = 6.$ Thus:

skew_schur_polynomial_example_2

We can also compute it directly by finding $K_{\lambda/\mu, \nu}$ for various $\nu$ , which gives:

$\begin{aligned}s_{432/21} &= m_{42} + 2m_{411} + 2m_{33} + 6m_{321} + 11m_{3111} + 10m_{222} + 18m_{2211} + 33m_{21111} + 61m_{111111}.\end{aligned}$

And the Schur polynomials give:

$\begin{aligned} s_{42} &= m_{42} + m_{411} + m_{33} + 2m_{321} + 3m_{3111} + 3m_{222} + 4m_{2211} + 6m_{21111} + 9m_{111111},\\ s_{411} &= m_{411} + m_{321} + 3m_{3111} + m_{222} + 3m_{2211} + 6m_{21111} + 10m_{111111},\\ s_{33} &= m_{33} + m_{321} + m_{3111} + m_{222} + 2m_{2211} + 3m_{21111} + 5m_{111111}, \\ s_{321} &= m_{321} + 2m_{3111} + 2m_{222} + 4m_{2211} + 8m_{21111} + 16m_{111111}, \\ s_{222} &= m_{222} + m_{2211} + 2m_{21111} + 5m_{111111}. \end{aligned}$

Example 2: Expanding Product of Schur Polynomials

Let us express $s_{3}s_{21}$ as a linear sum of Schur polynomials. For each partition $\lambda$ of 6, we have:

schur_polynomial_product_1

Swapping the two partitions (3) and (2,1) gives us an identical expansion, as expected.

schur_polynomial_product_2