Let’s talk about Schur polynomials. These were defined as:
Here is a partition, is a semistandard Young tableau of shape , and is the monomial , where is the weight of (so is the number of ‘s in .)
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 as there are of weight , where is the transposition that swaps and . We’ll exhibit a bijection between these two sets, and 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 , and consider only the boxes containing . Our goal is to turn 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 , possibly with .
- within each column, there can be at most a single sequence .
Here’s what we do: ignore all the vertical pairs . What’s left is a bunch of vertically-disconnected horizontal strips . Then, change each strip to . By our vertical-disconnectedness assumptions, this does not break column-strictness — since there were no ‘s below the original ‘s, and no ‘s above the original ‘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:
Hopefully that communicates it.)
This process is obviously reversible, so it gives the desired bijection
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 .
Proof. Let’s expand in the monomial basis:
The coefficients are the Kostka numbers, the number of tableaux of shape and weight .
So, let be such a tableau. By column-strictness, all the 1s must be in the first row, so . Similarly, all the 1s and 2s must be in the first two rows, so . And so on: for each , we look at the first rows, and find that
In other words, in the dominance ordering. Moreover, if , then there’s only one such tableau, namely, the whose -th row consists only of ‘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
The monomial structure constants 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 is the number of matrices containing nonnegative integers, such that:
- the column sums are ,
- the first (resp. second) row contains the entries of (resp. ), in any order, with zeros interspersed anywhere.
There’s an obvious generalization of this to arbitrary products , with coefficients , using 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 , which is computationally convenient.
The Schur structure constants 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 be the “tableau ring”, the ring with additive basis given by all the SSYTs, and with (noncommutative) multiplication given by the tableau product. Let be the subring consisting of tableaux with entries coming from .
Proposition. There is a canonical homomorphism , given by .
This works because the tableau product just concatenates the weights, so .
Now we can think of a Schur polynomial as coming from an actual sum over SSYTs, where
where is the number of ways to factor the tableau as a product , where the shapes of are . The key point is the following:
Theorem. The number depends only on the shape of .
Corollary. The product above is in fact of the form
Hence (by passing to the ring of symmetric polynomials), the Littlewood-Richardson coefficient is the number of ways of factoring an arbitrary (fixed) tableau of shape into a product of tableaux of shape . 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 be a “bumping” and “recording” tableau pair of the same shape, corresponding (by RSK) to a unique matrix . Let be any tableau.
Perform the RSK algorithm using the matrix , but start with the tableau (instead of an empty tableau). That is, perform successive row insertions into , and separately record the locations of the new boxes, all according to the entries of . (The new boxes form a skew tableau, having the same contents as .)
Lemma. The rectification (by JDT) of the skew tableau formed by the recorded new boxes is .
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.