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.

Advertisements

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

%d bloggers like this: