Home » Mathematics » Algebraic combinatorics » Everything you wanted to know about symmetric polynomials, part III

Everything you wanted to know about symmetric polynomials, part III

Let’s talk about Schur polynomials. These were defined as:

$\displaystyle{ s_\lambda = \sum_{T \in SSYT(\lambda)} x^{w(T)}. }$

Here $\lambda$ is a partition, $T$ is a semistandard Young tableau of shape $\lambda$, and $x^{w(T)}$ is the monomial $x_1^{\mu_1} \cdots x_n^{\mu_n}$, where $\mu$ is the weight of $T$ (so $\mu_i$ is the number of $i$‘s in $T$.)

First things first: it’s not obvious from the definition that these are symmetric!

Claim. The Schur polynomials are symmetric polynomials.

Proof. It suffices to show that there as many tableaux of weight $\mu$ as there are of weight $s_i \cdot \mu$, where $s_i$ is the transposition that swaps $i$ and $i+1$. We’ll exhibit a bijection between these two sets, $SSYT(\lambda,\mu)$ and $SSYT(\lambda,s_i\cdot\mu)$ directly, called the Bender-Knuth involution.

(Personal note: this was one of the first proofs I ever learned in algebraic combinatorics, and remains one of my favourites, for its elegant use of the defining properties of SSYTs.)

So, let’s fix a tableau $T \in SSYT(\lambda,\mu)$, and consider only the boxes containing $i,i+1$. Our goal is to turn $T$ into a new tableau having a switched number of these boxes.

The rules of SSYTs tell us the following:

• each row has a sequence of the form $i^a,(i+1)^b$, possibly with $a,b = 0$.
• within each column, there can be at most a single sequence $i,i+1$.

Here’s what we do: ignore all the vertical pairs $i,i+1$. What’s left is a bunch of vertically-disconnected horizontal strips $i^a,(i+1)^b$. Then, change each strip to $i^b,(i+1)^a$. By our vertical-disconnectedness assumptions, this does not break column-strictness — since there were no $i+1$‘s below the original $i$‘s, and no $i$‘s above the original $i+1$‘s. So, the result is a valid SSYT.

(Really, the best way to show this is to draw a diagram, but the best I can do is this:

$\begin{array}{|c|c|c|c|c|c|c|} &&&&(no&i's&)\\ \hline i & i & \cdots & i & i+1 & \cdots & i+1 \\ \hline (&no&i+1's&) \end{array}$

Hopefully that communicates it.)

This process is obviously reversible, so it gives the desired bijection

$SSYT(\lambda,\mu) \to SSYT(\lambda,s_i\cdot\mu)$.

Great! Next, let’s show that they’re an additive basis for the ring of symmetric polynomials. This is surprisingly easy.

Claim. The Schur polynomials are a basis for $\Lambda$.
Proof. Let’s expand in the monomial basis:

$\displaystyle{ s_\lambda = \sum_{\mu} K_{\lambda \mu} m_\mu.}$

The coefficients $K_{\lambda \mu}$ are the Kostka numbers, the number of tableaux of shape $\lambda$ and weight $\mu$.

So, let $T$ be such a tableau. By column-strictness, all the 1s must be in the first row, so $\mu_1 \leq \lambda_1$. Similarly, all the 1s and 2s must be in the first two rows, so $\mu_1 + \mu_2 \leq \lambda_1 + \lambda_2$. And so on: for each $k$, we look at the first $k$ rows, and find that

$\mu_1 + \cdots + \mu_k \leq \lambda_1 + \cdots + \lambda_k$.

In other words, $\mu \unlhd \lambda$ in the dominance ordering. Moreover, if $\mu = \lambda$, then there’s only one such tableau, namely, the whose $k$-th row consists only of $k$‘s.

Thus, the Schur polynomials are “unitriangular” in the monomial basis, so they too are a basis. Done!

Multiplication and Structure Constants

In the elementary, complete homogeneous, and power bases, multiplying two basis elements gives another basis element, by definition. Both the monomial and Schur bases, by contrast, are distinctly “additive”: it’s not obvious how to expand a product of basis elements in the basis. Indeed, there are interesting structure constants to be found, defined by the equations

$\displaystyle{ m_\lambda \cdot m_\mu = \sum_{\nu} a_{\lambda \mu}^\nu m_\nu, \qquad s_\lambda \cdot s_\mu = \sum_{\nu} c_{\lambda \mu}^\nu s_\nu.}$

The monomial structure constants $a_{\lambda \mu}^\nu$ are not too hard to analyze. We can use the same approach we used last post to expand the elementary symmetric functions in the monomial basis, writing out a horizontally-infinite matrix. The result is:

Proposition. The coefficient $a_{\lambda \mu}^{\nu}$ is the number of $2 \times \infty$ matrices containing nonnegative integers, such that:

• the column sums are $\nu$,
• the first (resp. second) row contains the entries of $\lambda$ (resp. $\mu$), in any order, with zeros interspersed anywhere.

There’s an obvious generalization of this to arbitrary products $m_{\lambda_1} \cdots m_{\lambda_k}$, with coefficients $a_{\lambda_1, \ldots, \lambda_k}^\nu$, using $k \times \infty$ matrices.

In particular, it’s worth noting that all these coefficients are nonnegative (though this is obvious to see for the monomial basis without coming up with this explicit description). Our description is also “a nonnegative description” – it only involves counting up, without any subtraction steps. This is nice – for instance, if we can exhibit a single such matrix, we instantly have a lower bound on $a_{\lambda \mu}^\nu$, which is computationally convenient.

The Schur structure constants $c_{\lambda \mu}^\nu$ are called the Littlewood-Richardson coefficients, and are more subtle to define and compute. For one thing, it’s not at all obvious that they are nonnegative, though (it turns out) they are.

Fortunately, since I already defined tableau products in a previous post, we’re all set to analyze the Littlewood-Richardson numbers. Let $R$ be the “tableau ring”, the ring with additive basis given by all the SSYTs, and with (noncommutative) multiplication given by the tableau product. Let $R(m)$ be the subring consisting of tableaux with entries coming from $1, \ldots, m$.

Proposition. There is a canonical homomorphism $R(m) \to k[x_1, \ldots, x_m]$, given by $T \mapsto x^T$.

This works because the tableau product just concatenates the weights, so $x^{T \cdot U} = x^T \cdot x^U$.

Now we can think of a Schur polynomial as coming from an actual sum over SSYTs, where

$\displaystyle{ S_\lambda = \sum_{T \in SSYT(\lambda)} T,}$

and then

$\displaystyle{ S_\lambda \cdot S_\mu = \sum_{V} c_{\lambda\mu}^V V,}$

where $c_{\lambda \mu}^V$ is the number of ways to factor the tableau $V$ as a product $T \cdot U$, where the shapes of $T,U$ are $\lambda,\mu$. The key point is the following:

Theorem. The number $c_{\lambda \mu}^V$ depends only on the shape $\nu$ of $V$.

Corollary. The product above is in fact of the form

$\displaystyle{ S_\lambda \cdot S_\mu = \sum_{\nu} c_{\lambda\mu}^\nu S_\nu.}$

Hence (by passing to the ring of symmetric polynomials), the Littlewood-Richardson coefficient $c_{\lambda \mu}^\nu$ is the number of ways of factoring an arbitrary (fixed) tableau of shape $\nu$ into a product of tableaux of shape $\lambda, \mu$. In particular, these coefficients are nonnegative, and our description is subtraction-free.

The proof of this theorem uses the RSK correspondence, particularly the following computation:

Let $B,R$ be a “bumping” and “recording” tableau pair of the same shape, corresponding (by RSK) to a unique matrix $A$. Let $V$ be any tableau.

Perform the RSK algorithm using the matrix $A$, but start with the tableau $V$ (instead of an empty tableau). That is, perform successive row insertions into $V$, and separately record the locations of the new boxes, all according to the entries of $A$. (The new boxes form a skew tableau, having the same contents as $R$.)

Lemma. The rectification (by JDT) of the skew tableau formed by the recorded new boxes is $R$.

The proof also uses the Symmetry Theorem (for RSK), and the fact that deleting highest or lowest letters from a word preserves Knuth equivalence. That’s a lot of machinery for a big bijection, so I’ll stop here.