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…

The answer is rather involved, but here’s the general idea: we can define an inner product on the space of symmetric functions $\Lambda^n$ in such a way that the Schur functions form an orthonormal basis: \[\langle s_{\lambda},s_{\mu}\rangle=\begin{cases} 1 & \text{if }\lambda=\mu \\ 0 &\text{otherwise}\end{cases}\] This is known as the Hall inner product, and is well-defined for all symmetric functions since the Schur functions form a basis.

Furthermore, the Schur functions are also known to be a basis for the $\mathbb{Z}$-module consisting only of the symmetric functions having integer coefficients. And they are the unique such orthonormal basis up to sign and order, since any transition matrix to another basis must be integral and orthogonal with respect to the Hall inner product. But any integral orthogonal matrix must be a signed permutation matrix (this is another cute problem!)

It can be shown in a similar fashion that the irreducible characters of $S_n$ also are the unique (up to sign and order) integral basis of the space of virtual characters, that is, the integer linear combinations of characters.

Finally, the Frobenius map is known to be an isometry, in which the standard inner product on characters given by $\langle \chi,\psi\rangle=\frac{1}{n!}\sum_{\pi\in S_n} \chi(\pi)\psi(\pi)$ is used to define the norm on virtual characters. This implies that the two orthonormal bases - the irreducible characters and the Schur functions - must be sent to each other by the Frobenius map.

Let’s look at what this implies. By the original definition of the Frobenius map, we have \[F(\chi^{\lambda})=s_\lambda=\sum_{\mu}\frac{1}{z_\lambda}\chi^{\lambda}(\mu)p_\mu.\] So, to find a combinatorial rule for the entries $\chi^{\lambda}(\mu)$ of the character table, one only needs to find a combinatorial rule for expressing the Schur basis in terms of the power sum basis! And the Murnaghan-Nakayama rule comes about as a result.

This was just a general sketch of the proof; for full details see Enumerative Combinatorics, Vol. 2 by Richard Stanley, or The Symmetric Group, by Bruce Sagan. In any case, the use of the Frobenius map is the key step, turning an otherwise difficult problem in representation theory into a purely combinatorial problem about symmetric functions.