There is a reason I’ve been building up the theory of symmetric functions in the last few posts, one gemstone at a time: all this theory is needed for the proof of the beautiful Murnaghan-Nakayama rule for computing the characters of the symmetric group.

What do symmetric functions have to do with representation theory? The answer lies in the Frobenius map, the keystone that completes the bridge between these two worlds.

The Frobenius map essentially takes a character of a representation of the symmetric group and assigns it a symmetric function. To define it, recall that characters are constant across conjugacy classes, and in $S_n$, the conjugacy classes correspond to the partitions of $n$ by associating a permutation $\pi$ with its cycle type $c(\pi)$. For instance, the permutations $\pi=(12)(345)$ and $\sigma=(35)(142)$ both have cycle type $\lambda=(3,2)$. So, any character $\chi$ satisfies $\chi(\pi)=\chi(\sigma)$.

We can now define the Frobenius map $F$. For any character $\chi$ of a representation of $S_n$, define
$$F\left(\chi\right)=\frac{1}{n!}\sum_{\pi\in S_n}\chi(\pi)p_{c(\pi)}$$ where $p_\lambda=p_{\lambda_1}p_{\lambda_2}\cdots p_{\lambda_k}$ is the $\lambda$th power sum symmetric function. (Recall that $p_{\lambda_i}=x_1^{\lambda_i}+x_2^{\lambda_i}+\cdots+x_k^{\lambda_i}$.)

Then, combining the permutations with the same cycle type in the sum, we can rewrite the definition as a sum over partitions of size n:
$$F\left(\chi\right)=\sum_{|\lambda|=n}\frac{1}{z_\lambda}\chi(\lambda)p_{\lambda}$$ for some constants $z_\lambda$. (It’s a fun little combinatorial problem to show that if $\lambda$ has $m_1$ 1’s, $m_2$ 2’s, and so on, then $z_\lambda=1^{m_1}m_1!2^{m_2}m_2!\cdots.$)

As an example, let’s take a look at the character table of $S_3$:
$$
\begin{array}{c|ccc}
& [(1)(2)(3)] & [(12)(3)] & [(123)] \\\hline
\chi^{(3)} & 1 & 1 & 1 \\
\chi^{(1,1,1)} & 1 & -1 & 1 \\
\chi^{(2,1)} & 2 & 0 & -1
\end{array}
$$ Consider the third row, $\chi^{(2,1)}$, and let us work over three variables $x,y,z$. Then the Frobenius map sends $\chi^{(2,1)}$ to
$$F\chi^{(2,1)}=\frac{1}{6}(2p_{(1,1,1)}-2p_3)$$ by our definition above. This simplifies to:
$$\frac{1}{3}((x+y+z)^3-(x^3+y^3+z^3))=x^2y+y^2x+x^2z+z^2x+y^2z+z^2y+2xyz$$ which can be written as $m_{2,1}+2m_{1,1,1}$. Notice that, by the combinatorial definition of the Schur functions, this is precisely the Schur function $s_{2,1}$! In fact:

The Frobenius map sends the irreducible character $\chi^\lambda$ to the Schur function $s_\lambda$ for all $\lambda$.

And therein lies the bridge.

Why is this the case? Read on to find out…

In the last few posts (see here and here), I’ve been talking about various bases for the symmetric functions: the monomial symmetric functions $m_\lambda$, the elementary symmetric functions $e_\lambda$, the power sum symmetric functions $p_\lambda$, and the homogeneous symmetric functions $h_\lambda$. As some of you aptly pointed out in the comments, there is one more important basis to discuss: the Schur functions!

When I first came across the Schur functions, I had no idea why they were what they were, why every symmetric function can be expressed in terms of them, or why they were useful or interesting. I first saw them defined using a simple, but rather arbitrary-sounding, combinatorial approach:

First, define a semistandard Young tableau (SSYT) to be a way of filling in the squares of a partition diagram (Young diagram) with numbers such that they are nondecreasing across rows and strictly increasing down columns. For instance, the Young diagram of $(5,3,1,1)$ is:

and one possible SSYT of this shape is:

(Fun fact: The plural of tableau is tableaux, pronounced exactly the same as the singular, but with an x.)

Now, given a SSYT $T$ with numbers of size at most $n$, let $\alpha_i$ be the number of $i$`s written in the tableau. Given variables $x_1,\ldots,x_n$, we can define the monomial $x^T=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$. Then the Schur function $s_\lambda$ is defined to be the sum of all monomials $x^T$ where $T$ is a SSYT of shape $\lambda$.

For instance, if $\lambda=(2,1)$, then the possible SSYT’s of shape $\lambda$ with numbers of size at most $2$ are:

So the Schur function $s_{(2,1)}$ in $2$ variables $x$ and $y$ is $x^2y+y^2x$.

This combinatorial definition seemed rather out-of-the-blue when I first saw it. Even more astonishing is that the Schur functions have an abundance of nice properties. To name a few:

• The Schur functions are symmetric. Interchanging any two of the variables results in the same polynomial.
• The Schur functions form a basis for the symmetric functions, Like the elementary symmetric functions, every symmetric polynomial can be expressed uniquely as a linear combination of $s_\lambda$`s.
• The Schur functions arise as the characters of the irreducible polynomial representations of the general linear group. This was proven by Isaac Schur and was the first context in which the Schur functions were defined. Here, a polynomial representation is a matrix representation in which the entries are given by polynomials in the entries of the elements of $GL_n$.
• The transition matrix between the power sum symmetric functions and the Schur functions is precisely the character table of the symmetric group $S_n$. This fact is essential in proving the Murnaghan-Nakayama rule that I mentioned in a previous post.

All of this is quite remarkable – but why is it true? It is not even clear that they are symmetric, let alone a basis for the symmetric functions.

After studying the Schur functions for a few weeks, I realized that while this combinatorial definition is very useful for quickly writing down a given $s_\lambda$, there is an equivalent algebraic definition that is perhaps more natural in terms of understanding its role in symmetric function theory. (Turn to page 2!)

Last week, I sat down to compute the character table of $S_5$ for the first time in several years.

My first instinct, following what I learned five years ago, was to use the standard tricks for computing character tables: compute the characters of some easily constructed representations, use the fact that the sum of the squares of the dimensions of the irreducible characters is $|S_5|=120$, and use the orthogonality of the rows and columns of the character table to finish it off.

This, however, is rather tedious for a group as large as $S_5$. But I had recently learned that the irreducible representations of the symmetric group are completely classified, and can be constructed using group actions on standard Young tableaux. Was there a way to use this theory to compute each entry of the character table directly?

It turned out that it was possible to laboriously use this theory to compute the characters one at a time, by finding an explicit matrix representation for each irreducible representation. However, I still had a nagging feeling that there should be a faster way to compute the characters.

I dug through the standard references in search of an answer, and I found it: the Murnaghan-Nakayama Rule (thanks to Enumerative Combinatorics, Vol. 2, by Richard Stanley). This concise and elegant method gives a simple combinatorial way of computing the character table of any symmetric group $S_n$. And it goes like this:

Step 1. The conjugacy classes of $S_n$ are the permutations having a fixed number of cycles of each length, corresponding to a partition of $n$ called the shape of the permutation. For instance, the conjugacy classes for $S_5$ have representative elements $\mathbf{1}, (12), (12)(34), (123), (123)(45), (1234), (12345),$ corresponding to the seven partitions $11111, 2111, 221, 311, 32, 41, 5$ of $5$. Since the characters of a group are constant on its conjugacy classes, we index the columns of our character table by these partitions:

Step 2. There are precisely as many irreducible characters as conjugacy classes, so we can also index the irreducible characters by the partitions of $n$. We represent each partition as a Young diagram and write these down the left of the table:

Step 3: The Murnaghan-Nakayama Rule. We can now calculate the entry in row $\lambda$ and column $\mu$. Let $\mu_1,\mu_2,\ldots$ be the parts of $\mu$ in decreasing order. Drawing $\lambda$ as a Young diagram, define a filling of $\lambda$ with content $\mu$ to be a way of writing a number in each square of $\lambda$ such that the numbers are weakly increasing along each row and column and there are exactly $\mu_i$ squares labeled $i$ for each $i$.

Consider all fillings of $\lambda$ with content $\mu$ such that for each label $i$, the squares labeled $i$ form a connected skew tableaux that does not contain a $2\times 2$ square. (A skew tableau is connected if the graph formed by connecting horizontally or vertically adjacent squares is connected.) Such a tableaux is called a border-strip tableaux, with each label coloring a border strip. For instance, the following is a border-strip tableaux:

For each label in the tableau, define the height of the corresponding border strip to be one less than the number of rows of the border strip. We then weight the tableau by $(-1)^s$ where $s$ is the sum of the heights of the border strips that compose the tableau. (For instance, the heights of the border strips in the above tableaux are $1$, $2$, $1$, and $0$, and so the weight of the tableau is $(-1)^{1+2+1}=1$.) Then, the entry in the character table is simply the sum of these weights.

For example, in the case $n=5$, suppose we are trying to calculate the entry for $\lambda=(3,2)$ and $\mu = 221$. Then the three possible border-strip tableaux are drawn below:

They have weights $1$, $1$, and $-1$, for a total weight of $1+1-1=1$. So, the corresponding entry of the character table is $1$.

That’s all! This gives a quick way to churn out all the entries in the character table:

Using the Murnaghan-Nakayama rule, I was able to compute this table by hand in about 30 minutes. What a gemstone!