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

Everything you wanted to know about symmetric polynomials, part II

Last post, I introduced the ring \Lambda of symmetric polynomials in infinitely-many variables. Its elements are infinite sums of monomials (of bounded degree), symmetric in all the variables. I also defined the five most common bases for it: the monomial, elementary, (complete) homogeneous, power and Schur polynomials, m,e,h,p,s for short. All of them are indexed by partitions \lambda, and in each case the basis element is homogeneous of (total) degree |\lambda|.

Now, I’m going to prove that each of these is a basis for \Lambda.

As I noted last post, the monomial symmetric polynomials are obviously a basis – if a symmetric polynomial f \in \Lambda includes some monomial term, then it must include the entire corresponding m_\lambda. Thus f is a linear combination of monomial symmetric polynomials; and it’s again obvious that there are no relations between the m_\lambda.

Throughout this post, we’ll use the following key idea: let \{b_i\}_{i \in I} be a basis for a vector space, and \{a_i\}_{i \in I} a set of vectors indexed by the same set I. Suppose that I is partially ordered, and that we can express the a‘s in terms of the b‘s in the form

\displaystyle{ a_i = c_{ii} b_i + \sum_{j \prec i} c_{ij} b_j, \qquad c_{ii} \text{ a unit}.}

Then the a‘s are also a basis. In fact, this means the change-of-basis matrix is upper-triangular (or maybe lower-triangular), with units down the diagonal, so it must be invertible. This is one of the nicest ways to establish (discover?) that something is a basis, since determinants are, in general, not always easy to compute.

The Elementary Symmetric Polynomials

Let’s express the elementary symmetric polynomials in the m basis. The result will be “upper-triangular”, as described above. To begin, let’s write out the product e_\lambda = e_{\lambda_1} e_{\lambda_2} \cdots e_{\lambda_k}. For a set of indices A, let x^A denote the corresponding (squarefree) monomial.

\displaystyle{ e_\lambda = e_{\lambda_1} e_{\lambda_2} \cdots e_{\lambda_k} = \bigg(\sum_{A_1 : |A_1| =\lambda_1} x^{A_1} \bigg) \cdots \bigg(\sum_{A_k : |A_k| =\lambda_k} x^{A_k} \bigg) }.

To expand this out, we need to select, for each i=1, \ldots, k, a set A_i of size \lambda_i. We can visualize the result as a horizontally-infinite k \times \infty matrix of zeros and ones, where the rows correspond to the A_i‘s and the columns to the x_j variables, and we fill in 1‘s to indicate the contents of the A_i‘s:

\begin{array}{r|ccccc}   & x_1 & x_2 & x_3 & x_4 & \cdots \\ \hline  A_1 & 1 & 1 & 0 & 1 & \cdots \\  A_2 & 1 & 1 & 1 & 0 & \cdots \\  A_3 & 0 & 0 & 1 & 1 & \cdots  \end{array}

This matrix corresponds to A_1 = \{1,2,4\}, A_2 = \{1,2,3\}, A_3 = \{3,4\}. (It comes from expanding out the product e_{3,3,2}.) We see the following:

  • The row sums are the sizes of the A_i, that is, the row sums are given by \lambda.
  • The column sums are the multiplicities of the x_j, that is, they give the exponents of a monomial.

In particular, by rearranging the columns, let’s assume that the column sums are nondecreasing, so they form a partition \mu, giving rise to a monomial x_1^{\mu_1} \cdots x_n^{\mu_n}. The coefficient of this monomial, and by extension the coefficient of m_\mu in e_\lambda, is the number of 0-1 matrices with row sums \lambda and column sums \mu. Call this number N_{\lambda \mu}, so:

\displaystyle{ e_\lambda = \sum_{\mu} N_{\lambda \mu} m_\mu.}

But not every \mu occurs in this sum.

Claim. If \mu occurs with a nonzero coefficient, then \mu \unlhd \tilde\lambda in the dominance ordering, that is, for each i,

\mu_1 + \cdots + \mu_i \leq \tilde\lambda_1 + \cdots + \tilde\lambda_i.

Here \tilde\lambda is the transpose of \lambda, obtained by flipping its Young diagram diagonally. (This is a partial ordering, but not a total ordering.)

To see this, consider a matrix as above, with row sums \lambda and column sums \mu. Within each row, rearranging the 1s doesn’t change the row sum. So let’s move all the 1s as far left as possible – so that each row consists of \lambda_i ones, followed by zeros.

What does this do? Well, we’ve made the first few column sums larger, so the new column sums \mu' dominate the old ones: \mu \unlhd \mu'. But, by our setup, \mu' is the transpose of \lambda! So this says that \mu \unlhd \tilde \lambda.

And, we also see that if \mu = \tilde\lambda, then there’s only one possible matrix to get – namely, the one we just reduced to.

So, by our discussion about upper-triangular changes of bases, this shows that the e_\lambda‘s are upper-triangular in the m_\lambda‘s.

Final Remark. This also shows that \Lambda is generated as a ring by the e_k‘s, since the e_\lambda‘s are products in the e_k‘s. Moreover, there can be no polynomial relations among the e_k‘s either, since these would yield linear relations among the e_\lambda‘s!

This shows:

Theorem. As rings, \Lambda \cong k[e_1, e_2, e_3, \ldots], where the latter is a polynomial ring on the generators e_k, with no relations.

Cool.

The Homogeneous Symmetric Polynomials

This will be much easier!

We’ll say goodbye to the m‘s. Instead, we’ll relate the h‘s to the e‘s. Consider the following formal power series (from the ring \Lambda[[t]]):

\begin{array}{rl}  \displaystyle{ \prod_{i=1}^\infty (1 + x_i t)}&= 1 + e_1 t + e_2 t^2 + e_3 t^3 + \cdots,\\  \displaystyle{ \prod_{i=1}^\infty \frac{1}{1 + x_i t} = \prod_{i=1}^\infty \bigg( \sum_{n=0}^\infty (-1)^n x_i^n t^n \bigg)}&= 1 - h_1 t + h_2 t^2 - h_3 t^3 + \cdots.  \end{array}

Here we’re cleverly using the variable t to index the total degree of each monomial.

Since these series are inverse to each other, we multiply them out to get

\displaystyle{ \prod_{i=1}^\infty (1 + x_i t) \cdot \prod_{i=1}^\infty \frac{1}{1 + x_i t} = 1}.

Then we compare term-by-term in the t variable, and we find:

\begin{array}{ll}  e_1 - h_1 &=0,\\  e_2 - e_1h_1 + h_2 &= 0,\\  e_3 - e_2 h_1 + e_1 h_2 - h_3 &= 0,\\  \qquad \vdots \\  e_k + \sum_{i=1}^{k-1} (-1)^i e_{k-i}h_i + (-1)^k h_k &= 0.  \end{array}

This is sort of ring-theoretic version of being upper-triangular, since the equation is of the form

e_k = \pm h_k + lower terms.

In particular, any polynomial expression in the e‘s can be converted into one in the h‘s, and vice versa. This shows:

Theorem. The h_k‘s generate \Lambda as a ring.

Again by dimension counting in each degree, we get:

Theorem. The h_\lambda‘s are a basis for \Lambda as a vector space. In particular, \Lambda is free (i.e. a polynomial ring) on the h_k‘s.

Done! That was easier. For fun and while it’s on my mind, I’ll remark the following:

Proposition (The \omega involution). Let \omega : \Lambda \to \Lambda be defined by sending e_k \mapsto h_k. (This is allowed because \Lambda is a polynomial ring on the e_k‘s. Then \omega also sends h_k \mapsto e_k. In particular, it is an involution.

Proof. The relations we found above are symmetric in the h_k‘s and the e_k‘s. That is, \omega(h_k) satisfies the same relations (relative to h_k) as e_k does. Hence, working inductively, we must have \omega(h_k) = e_k.

The \omega involution (as it’s called) is a fairly deep operation: we’ll see later that it sends the Schur polynomial s_\lambda to s_{\tilde \lambda}, the transpose. It will have interesting properties in the representation theory of the symmetric group (where it corresponds to tensoring with the alternating representation) and of GL_n (where it’s much stranger, and corresponds to switching between exterior powers and symmetric powers… somehow it switches between ‘symmetry’ and ‘alternation’. If anyone reads this and has thoughts on it, I’d love to hear them).

Moving on…

The Power Symmetric Polynomials

This will be like the previous approach (via generating functions), only… powered-up.

First, let’s take

\displaystyle{f = p_1 - p_2 t + p_3 t^2 - p_4 t^3 + \cdots = \sum_{i=1}^\infty (x_i - x_i^2 t + x_i^3 t^2 - \cdots)\cdots.}

(The reason for the off-by-one exponents will be clear in a moment.) The summand at the end is an (alternating) geometric series, so

\displaystyle{ f = \sum_{i=1}^\infty \frac{x_i}{1 + x_i t}.}

This is looking similar to the generating function for the h‘s above, but the latter is a product, not a sum. So, let’s integrate! (The extra x_i factor lets us use the chain rule.) Let F be the antiderivative of f (with constant term 0), so

\displaystyle{ F = \sum_{i=1}^\infty \log(1+x_i t) = \log \prod_{i=1}^\infty(1+x_i t).}

Well, good enough anyways – we got the generating function for the e‘s. In particular,

\displaystyle{ \exp(F) = \prod_{i=1}^\infty(1+x_i t) = \sum_{k=0}^\infty e_k t^k.}

Expanding out \exp(F) is a bit of a pain, but we don’t have to. Let’s differentiate both sides with respect to t. We get:

\displaystyle{ \exp(F) \cdot f = \sum_{n=1}^\infty k e_k t^{k-1}.}

Now, we combine the last two equations to get:

\displaystyle{ \bigg(\sum_{k=0}^\infty e_k t^k\bigg) \bigg(\sum_{i=0}^\infty (-1)^i p_{i+1} t^i \bigg) = \sum_{k=1}^\infty k e_k t^{k-1}.}

Now we equate t coefficients, and we’re done. The punch line is:

Claim (Newton’s Identities). The p_k‘s and e_k‘s satisfy:

\displaystyle{ k e_k + \sum_{i=1}^k (-1)^{i-1} e_{k-i} p_i = 0.}

Since the coefficient of k shows up, the p_k‘s are not quite as nice. We have:

Theorem. The p_k‘s freely generate \Lambda as a polynomial ring over a characteristic zero field (but not over \mathbb{Z} or in positive characteristic). The p_\lambda‘s generate \Lambda additively, under the same circumstances.

As a bonus, we can understand their properties under the \omega involution:

Theorem. The \omega involution sends p_k \mapsto \pm p_k.

This follows from the symmetry between the h‘s and e‘s, and Newton’s identity above.

Conclusions

I still have to deal with the Schur polynomials, but they deserve their own post – showing that they are symmetric, that they are a basis (not too hard actually – but it’s similar to the matrix-based argument for the first proof above), and that they have other neat properties. So, I’ll stop here for now.

Advertisements

1 Comment

  1. […] Everything you wanted to know about symmetric polynomials, part II […]

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: