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 $1$s 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.