The Fundamental Theorem of Symmetric Function Theory

A proof of the Fundamental Theorem, for the curious:

We start by expressing $e_\lambda$ in terms of monomial symmetric functions.

Notice that, in the expansion of the product $e_{\lambda_1} e_{\lambda_2} \cdots e_{\lambda_k}$, the coefficient of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_l^{\alpha_l}$ is the number of ways of choosing one monomial from each $e_{\lambda_i}$ so that there are a total of $\alpha_j$ occurrences of $x_j$ for each $j$. Writing the exponents of these monomials as the rows of a matrix, it is simply the number of matrices of zeroes and ones with row sums $\lambda_i$ and column sums $\alpha_j$.

Grouping these monomials into $m_\lambda$`s, we now have
$$e_\lambda=\sum_{\mu} M_{\lambda\mu} m_\mu$$ where $M_{\lambda\mu}$ is the number of matrices of $0$`s and $1$`s with row sums $\lambda_i$ and column sums $\mu_j$.

We now only need to show that the matrix of coefficients $M_{\lambda\mu}$, for a given size of partition $n$, is invertible.

We say a partition $\lambda$ dominates $\mu$, written $\lambda\ge \mu$, if the partial sums of $\lambda$ are never less than those of $\mu$: $\lambda_1+\cdots+\lambda_i\ge \mu_1+\cdots \mu_i$ for all $i$. Dominance is a partial ordering on the partitions of $n$, and so we can extend it to some total ordering of the partitions, say $\lambda^{1}, \lambda^{2},\ldots$.

For a partition $\lambda$, let its conjugate, $\lambda^\ast$, be the partition formed by transposing its Young diagram. We will show that if we arrange the matrix of coefficients $M_{\lambda\mu}$ so that its rows are indexed by $\lambda^1,\lambda^2,\ldots$ and its columns by $(\lambda^1)^\ast, (\lambda^2)^\ast,\ldots$, then the matrix is upper triangular with $1$`s on the diagonal.

Indeed, we have $M_{\lambda\lambda^\ast}=1$, since the only matrix of $0$`s and $1$`s with row sums $\lambda_i$ and column sums $\lambda_j^\ast$ is the matrix with the $\lambda_i$ $1$`s in each row aligned all the way to the left, forming the Young diagram of $\lambda$ with the $1$’s.

It only remains to show that $M_{\lambda\mu}$ is $0$ for $\mu\not\le \lambda^\ast$. Suppose $M_{\lambda\mu}$ is nonzero. Then there is a matrix $A$ of $0$`s and $1$`s with row sums $\lambda_i$ and column sums $\mu_j$, which are clearly dominated by the column sums of the matrix formed by shifting all the $1$`s in $A$ to the left. But these new column sums are the parts of $\lambda^\ast$, and so $\mu\le\lambda^{\ast}$.

This completes the proof! Stay tuned – there are more symmetric function gemstones to be uncovered in future posts.

8 thoughts on “The Fundamental Theorem of Symmetric Function Theory

  1. Thanks, Maria, for an interesting look into some mathematics I probably wouldn’t have otherwise encountered!

    I noticed a one error though, at the end of the first page, you state that we’re going to write x^2 + y^2 + z^2 in terms of elementary symmetric functions, then proceed to write x^3 + y^3 + z^3 in terms of its elementary symmetric functions.

    Also, I was confused when you said, “We can then write the term x^2 y + y^2 x + … as e1e2 – 3e3”, wherein I took the term to be x^2 y + y^2 x + … + z^2 y rather than x^2 y + y^2 x + … + 6xyz, which rather confused me until I worked it out, so that may merit some clarification.

  2. Thanks for your comments, Zach! I edited the error you found.

    As for the paragraph you were confused about, I’m pretty sure the mathematics was correct as stated (I didn’t mean to include the 6xyz term) but you are right that the paragraph was badly worded. I re-worded it above and included more detail – does it make more sense now?

    Glad you enjoyed it!

  3. Hi Maria,

    This is a nice introduction to symmetric functions. However, do you think this theorem deserves to be called the “fundamental theorem” of symmetric functions? I don’t see any particularly strong reason to favour the e’s over the h’s or p’s, and if I were to call any symmetric functions “fundamental” it would be the Schur functions.

    Also, I didn’t know this argument was due to Mark Haiman! It appears without attribution in section 7.4 of Volume 2 of Stanley’s Enumerative Combinatorics.

    • Hi Steven,

      First, you are right that the same proof appears in Stanley’s book – I probably should have been more clear about my attribution. I didn’t mean that it is due to Mark Haiman; I meant that he was the first to teach that proof to me. I will edit my post to make that more clear.

      Now, about the Fundamental Theorem… while you’re right that the Schur functions are the more “important” basis for the applications in representation theory, I do think that the elementary symmetric functions are called “elementary” or “fundamental” for good reason.

      First, they are, up to sign, the coefficients of a polynomial in terms of its roots. This is a rather elementary fact, but I think it comes up often enough to make them stand out amongst the other symmetric functions.

      Now, the p’s also often come up when studying polynomials or looking for a simple basis, but there is a second, deeper reason why the e’s are more fundamental than the p’s. Suppose we are working over a ring R that does not contain $mathbb{Q}$, such as $mathbb{Z}$. So, we are considering the R-module of symmetric functions $Lambda_R(x_1,ldots,x_n)$. Then the p’s actually don’t form a basis for these symmetric functions! The reason is that when you express the p’s in terms of the m’s, the matrix is upper triangular, but the diagonal entries are not all $pm 1$, and so you would need fractions in order to express the m’s in terms of the p’s.

      One could argue that the h’s are exactly as fundamental as the e’s in this sense, but from an algebraic standpoint the h’s are essentially equivalent to the e’s, since the involution $omega$ sends one to the other. So, I’d say that it would be a restatement of the Fundamental Theorem to say that the h’s form a basis.

      I can see why you’d think the Schur functions are more fundamental, but to me that seems like saying that the fact that every positive integer can be written as a sum of four squares should be called the Fundamental Theorem of Arithmetic. The Schur functions are important for certain deeper areas of mathematics, but aren’t so easy to deal with or understand as the elementary symmetric functions.

      That being said, I wasn’t the one to name it the Fundamental Theorem – those are just my thoughts on the matter. I’d be interested to hear if anyone else has a better, or more historically accurate, reason for the name.

      -Maria

  4. Pingback: Theme and variations: the Newton-Girard identities | Finding Gemstones

  5. Pingback: The hidden basis | Finding Gemstones

  6. Pingback: Addicted to Crystal Math | Mathematical Gemstones

Leave a Reply

Your email address will not be published. Required fields are marked *