# The Springer Correspondence, Part II: The Resolution

This is a continuation of The Springer Correspondence, Part I. Here we will work with unipotent matrices to construct the Springer resolution and the cohomology of its fibers.

# Unipotent Matrices and Partitions

A unipotent element of a linear algebraic group $G$ is any element $u\in G$ such that $1-u$ is nilpotent. That is, $u=1+n$ where $n^k=0$ for some $k$.

To get a sense of what unipotent matrices look like, consider the type A situation in which $\DeclareMathOperator{\GL}{GL}\newcommand{\CC}{\mathbb{C}} G=\GL_n(\CC)$. Given a unipotent element $u$, we can conjugate it by some matrix to put it in Jordan normal form. It will look something like this:
$$gug^{-1}=\left(\begin{array}{ccccccc} \lambda_1 & 1 & & & & & \\ & \lambda_1 & 1 & & & & \\ & & \lambda_1 & & & & \\ & & & \lambda_2 & 1 & & \\ & & & & \lambda_2 & & \\ & & & & & \ddots & \\ & & & & & & \lambda_k \end{array}\right)$$

It turns out that the matrix above is particularly simple in this case:

The eigenvalues $\lambda_i$ of a unipotent matrix are all $1$.

To see this, suppose $\lambda$ is an eigenvalue of $u$. We have $uv=\lambda v$ for some vector $v$, and so $$(1-u)v=(1-\lambda)v.$$ Since $1-u=n$ is nilpotent, say with $n^k=0$, we have $$(1-u)^kv=(1-\lambda)^kv=0,$$ so $(1-\lambda)^k=0$. Since $\lambda\in\CC$ and $\CC$ is a field, it follows that $\lambda=1$, as claimed.

Therefore, every unipotent matrix is conjugate to a matrix havnig all $1$’s on the diagonal, $0$’s or $1$’s on the off-diagonal, and $0$’s everywhere else. The blocks of $1$’s on the off-diagonal split the matrix into Jordan blocks, which we can order by size from greatest to least. Let the sizes of the Jordan blocks be $\mu_1,\mu_2,\ldots,\mu_k$. Then $\mu=(\mu_1,\ldots,\mu_k)$ is a partition of $n$, and determines the conjugacy class of a given unipotent matrix.

For instance, the partition $\mu=(3,2,2)$ corresponds to the conjugacy class of unipotent matrices with the Jordan canonical form below.

This can all be summed up in the following fact:

The unipotent conjugacy classes in $\GL_n$ are in one-to-one correspondence with the partitions of $n$.

Now, I know what you are thinking:

“Maria, if the unipotent conjugacy classes of $\GL_n$ and the irreducible representations of $S_n$ are both indexed by the partitions of $n$, shouldn’t there be some nice geometric construction that relates them directly?”

Indeed there is! The Springer correspondence gives just that – and furthermore relates the unipotent conjgacy classes of any Lie group $G$ to the representations of its Weyl group.

# The Springer Resolution

In what follows, let $G$ be a Lie group, and let $U$ be the subvariety of $G$ consisting of all unipotent elements. The variety $U$ is not smooth in general, and to resolve the singularities we construct the variety $\widetilde{U}\subset U\times \mathcal{B}$ by $$\widetilde{U}=\{(u,B):u\in B\}.$$ Recall from the previous post that $\mathcal{B}$ is the variety of all Borel subgroups of $G$ and is isomorphic to the Flag variety $G/B$ for any Borel $B$. If we interpret $\mathcal{B}$ as the Flag variety in the case $G=\GL_n$, we can alternatively define $\widetilde{U}$ as the set of all pairs $(u,F)$ where $F$ is a flag and $u$ fixes $F$, that is, $uF_i=F_i$ for each $i$.

It turns out that $\widetilde{U}$ is smooth and the projection map $$\pi:\widetilde{U}\to U$$ is proper, so it resolves the singularities in $U$. This map is known as the Springer resolution.

The theory gets rather deep at this point, so in what follows I will state the main facts without proof. For full details I refer the interested reader to the exposition in Chapter 3 of Representation Theory and Complex Geometry by Chriss and Ginzburg.

## Springer Fibers and Weyl Group Action

For any $x\in U$, define the Springer fiber $\mathcal{B}_x$ to be the fiber $\pi^{-1}(x)$ of the Springer resolution over $x$, that is, the set of all Borel subgroups of $G$ that contain $x$. Now, consider the cohomology ring $H^\ast(\mathcal{B}_x)$ over $\CC$. It turns out that there is an action of the Weyl group $W$ on this cohomology ring, called the Springer action.

There is unfortunately no direct way of defining this action. To get some intuition for where the action comes from, notice that the Springer resolution above can be lifted to the entire group: one can define $\widetilde{G}$ to be the subvariety of $G\times \mathcal{B}$ consisting of all pairs $(g,B)$ such that $g\in B$. Now, let $x$ be a regular semisimple element of $G$.

In the case $G=\GL_n$, a regular semisimple element is simply a diagonalizable element $x$ with $n$ distinct nonzero eigenvalues. If $x$ is of this form, any subspace of $\CC^n$ fixed by $x$ is a direct sum of its (linear) eigenspaces. So, if $V_1,\ldots,V_n$ are the eigenspaces corresponding to the distinct eigenvalues of $x$, any flag fixed by $x$ is of the form $$V_{\sigma(1)}\subset V_{\sigma(1)}\oplus V_{\sigma(2)}\subset \cdots \subset V_{\sigma(1)}\oplus \cdots \oplus V_{\sigma(n)}$$ for some permutation $\sigma$ of $\{1,2,\ldots,n\}$. It follows that $\mathcal{B}_x$ consists of exactly $n!$ flags, and has a natural action of $S_n$ via permuting the eigenspaces $V_i$. Therefore, $S_n$ acts on $\mathcal{B}_x$ and therefore on $H^\ast(\mathcal{B}_x)$.

In general, if $x$ is regular and semisimple, the fiber $\mathcal{B}_x$ is a finite set of size $|W|$ where $W$ is the Weyl group of $G$. The regular semisimple elements form a dense subset of $G$, and one can use this to extend the action to all cohomology rings $H^\ast(\mathcal{B}_x)$ for any $x\in G$. This is the tricky part, and involves many more constructions than fit in a reasonable-length blog post, so again I refer the reader to this awesome book.

## The Springer Correspondence

We’re finally ready to state the Springer correspodence. For $x\in G$, let $d(x)$ be the dimension of the Springer fiber $\mathcal{B}_x$.

In the case $G=\GL_n$, the top cohomology groups $H^{d(x)}(\mathcal{B}_x)$ are $S_n$-modules due to the Springer action described above. Notice also that $\mathcal{B}_x$ depends only on the conjugacy class of $x$, so for $x$ in the unipotent conjugacy class with shape $\mu$, we write $\mathcal{B}_\mu$ to denote this Springer fiber, with $d(\mu)$ its dimension. It turns out that these $S_n$-modules are precisely the irreducible representations of $S_n$.

The $S_n$-module $H^{d(\mu)}(\mathcal{B}_\mu)$ is isomoprhic to the irreducible representation $V_\mu$ of $S_n$ corresponding to $\mu$.

And there you have it.

For general Lie groups $G$, the Springer correspondence is not quite as nice; the top cohomology groups $H^d(\mathcal{B}_u)$ (where $u$ is a unipotent conjugacy class) are not in general irreducible $W$-modules. However, all of the irreducible $W$-modules occur exactly once as a summand among the modules $H^d(\mathcal{B}_u)$, and there is a correspondence between the irreducible representations of $W$ and pairs $(u,\xi)$ where $u$ is a unipotent conjugacy class in $G$ and $\xi$ is an irreducible $G$-equivariant local system on $u$.

# Hall-Littlewood Polynomials

The fact that the top cohomology groups $H^{d(\mu)}(\mathcal{B}_\mu)$ are so nice naturally raises the question: what about the other cohomology groups? What $S_n$-modules do we get in each degree?

In particular, let $R_\mu=H^\ast(\mathcal{B}_\mu)$. Then $R_\mu$ is a graded $S_n$-module with grading $$R_\mu=\bigoplus (R_\mu)_i=\bigoplus H^i(\mathcal{B}_\mu),$$ and so we can construct the Frobenius series
$$F_t(R_\mu)=\sum_{i=0}^{d(\mu)}F((R_{\mu})_i)t^i$$
where $F$ is the Frobenius map that sends $S_n$-modules to symmetric functions.

The Hall-Littlewood polynomials $\widetilde{H}_\mu(\mathbf{x};t)$ are defined to be the Frobenius characteristics $F_t(R_\mu)$, and are therefore a class of symmetric polynomials in the variables $\mathbf{x}=x_1,x_2,\ldots$ with coefficients in $\mathbb{Q}[t]$. They have incredibly rich combinatorial structure which reveals the decomposition of $R_\mu$ into irreducible $S_n$-modules… structure that I will save for a later post. Stay tuned!

# The Springer Correspondence, Part I: The Flag Variety

In prior posts, we’ve seen that the irreducible representations of the symmetric group $S_n$ are in one-to-one correspondence with the partitions of $n$, and the Schur functions give an elegant encoding of their characters as symmetric polynomials. Now we can dive a bit deeper: a geometric construction known as the Springer resolution allows us to obtain all the irreducible representations of $S_n$ geometrically, and as a side bonus give natural graded representations that will allow us to define a $q$-analog of the Schur functions known as the Hall-Littlewood polynomials.

Quite a mouthful of terminology. Let’s start at the beginning.

# The Classical Flag Variety

When you think of a flag, you might imagine something like this:

Roughly speaking, a flag on a flagpole consists of:

• a point (the bulbous part at the top of the pole),
• a line passing through that point (the pole),
• a plane passing through that line (the plane containing the flag), and
• space to put it in.

Mathematically, this is the data of a complete flag in three dimensions. However, higher-dimensional beings would require more complicated flags. So in general, a complete flag in $n$-dimensional space $\mathbb{C}^n$ is a chain of vector spaces of each dimension from $0$ to $n$, each containing the previous:

$$0=V_0\subset V_1 \subset V_2 \subset \cdots \subset V_n=\mathbb{C}^n$$

with $\dim V_i=i$ for all $i$.

(Our higher-dimensional flag-waving imaginary friends are living in a world of complex numbers because $\mathbb{C}$ is algebraically closed and therefore easier to work with. However, one could define the flag variety similarly over any field $k$.)

## Variety Structure

Now that we’ve defined our flags, let’s see what happens when we wave them around continuously in space. It turns out we get a smooth algebraic variety!

Indeed, the set of all possible flags in $\mathbb{C}^n$ forms an algebraic variety of dimension $n(n-1)$ (over $\mathbb{R}$), covered by open sets similar to the Schubert cells of the Grassmannian. In particular, given a flag $\{V_i\}_{i=1}^n$, we can choose $n$ vectors $v_1,\ldots,v_n$ such that the span of $v_1,\ldots,v_i$ is $V_i$ for each $i$, and list the vectors $v_i$ as row vectors of an $n\times n$ matrix. We can then perform certain row reduction operations to form a different basis $v_1^\prime,\ldots,v_n^\prime$ that also span the subspaces of the flag, but whose matrix is in the following canonical form: it has $1$’s in a permutation matrix shape, $0$’s to the left and below each $1$, and arbitrary complex numbers in all other entries.


$$\left(\begin{array}{ccc} 0 & 2 & 3 \\ 1 & 1 & 4 \\ 1 & 2 & -3\end{array}\right) \to \left(\begin{array}{ccc} 0 & 1 & 1.5 \\ 1 & 0 & 2.5 \\ 1 & 0 & -6\end{array}\right)\to \left(\begin{array}{ccc} 0 & 1 & 1.5 \\ 1 & 0 & 2.5 \\ 0 & 0 & 1\end{array}\right)$$

It is easy to see that this process does not change the flag formed by the partial row spans, and that any two matrices in canonical form define different flags. So, the flag variety is covered by $n!$ open sets given by choosing a permutation and forming the corresponding canonical form. For instance, one such open set in the $5$-dimensional flag variety is the open set given by all matrices of the form
$$\left(\begin{array}{ccccc} 0 & 1 & \ast & \ast & \ast \\ 1 & 0 & \ast & \ast & \ast \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & \ast & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right)$$

We call this open set $X_{45132}$ because it corresponds to the permutation matrix formed by placing a $1$ in the $4$th column from the right in the first row, in the $5$th from the right in the second row, and so on. The maximum number of $\ast$’s we can have in such a matrix is when the permutation is $w_0=n(n-1)\cdots 3 2 1$, in which case the dimension of the open set $X_{12\cdots n}$ is $n(n-1)/2$ over $\CC$ — or $n(n-1)$ over $\RR$, since $\CC$ is two-dimensional over $\RR$. In general, the number of $\ast$’s in the set $X_w$ is the inversion number $\inv(w)$, the number of pairs of entries of $w$ which are out of order.

Finally, in order to paste these disjoint open sets together to form a smooth manifold, we consider the closures of the sets $X_w$ as a disjoint union of other $X_w$’s. The partial ordering in which $\overline{X_w}=\sqcup_{v\le w} X_v$ is called the Bruhat order, a famous partial ordering on permutations. (For a nice introduction to Bruhat order, one place to start is Yufei Zhao’s expository paper on the subject.)

## Intersection Cohomology

Now suppose we wish to answer incidence questions about our flags: which flags satisfy certain given constraints? As in the case of the Grassmannians, this boils down to understanding how the Schubert cells $X_w$ intersect. This question is equaivalent to studying the cohomology ring of the flag variety $\Fl_n$ over $\mathbb{Z}$, where we consider the Schubert cells as forming a cell complex structure on the flag variety.

The cohomology ring $H^\ast(\Fl_n)$, as it turns out, is the coinvariant ring that we discussed in the last post! For full details I will refer the interested reader to Fulton’s book on Young tableaux. To give the reader the general idea here, the Schubert cell $X_w$ can be thought of as a cohomology class in $H^{2i}(\Fl_n)$ where $i=\inv(w)$. We call this cohomology class $\sigma_w$, and note that for the transpositions $s_i$ formed by swapping $i$ and $i+1$, we have $\sigma_{s_i}\in H^2(\Fl_n)$. It turns out that setting $x_i=\sigma_i-\sigma_{i+1}$ for $i\le n-1$ and $x_n=-\sigma_{s_{n-1}}$ gives a set of generators for the cohomology ring, and in fact $$H^\ast(\Fl_n)=\mathbb{Z}[x_1,\ldots,x_n]/(e_1,\ldots,e_n)$$ where $e_1,\ldots,e_n$ are the elementary symmetric polynomials in $x_1,\ldots,x_n$.

# Digging deeper: The isotypic components

In last week’s post, we made use of the coinvariant ring $$\mathbb{C}[x_1,\ldots,x_n]/I$$ where $I=(p_1,\ldots,p_n)$ is the ideal generated by the positive-degree homogeneous $S_n$-invariants (symmetric polynomials). We saw that this was an $S_n$-module with Hilbert series $(n)_q!$, and claimed that it was the regular representation.

Let’s see why that is, and see if we can understand where the irreducible components occur.

More precisely, our goal is to understand the series $$\sum_{d} H_{\chi^\mu}(d)q^d$$ where $H_{\chi^\mu}(d)$ is the number of copies of the $\mu$th irreducible representation of $S_n$ occurring in the $d$th degree component of $\mathbb{C}[x_1,\ldots,x_n]/I$. In Stanley’s paper on invariants of finite groups, he states without proof the answer as the following “unpublished result of Lusztig”:

Let $G$ be the group of all $m \times m$ permutation matrices, and let $\chi$ be the irreducible character of $G$ corresponding to the partition $\mu$ of $m$. Then $H_{\chi}(n)$ is equal to the number of standard Young tableaux $T$ of shape $\mu$ such that $n$ is equal to the sum of those entries $i$ of $T$ for which $i$ appears in a column to the left of $i+1$.

To prove this, let’s start with the identity we showed last time, using boldface $\mathbf{x}$ to denote $x_1,\ldots,x_n$ as a shorthand:
$$\mathbb{C}[\mathbf{x}]=\Lambda_{\mathbb{C}}(\mathbf{x})\otimes_{\mathbb{C}[S_n]}\mathbb{C}[\mathbf{x}]/I$$

Since $\Lambda_{\mathbb{C}}(\mathbf{x})$, the ring of symmetric functions, consists entirely of copies of the trivial representation of $S_n$, we see that the irreducible components of type $\chi^\mu$ in degree $d$ on the right hand side come from those of that type in $\mathbb{C}[\mathbf{x}]/I$ of degree $d-k$, tensored with the trivial representations in degree $k$ in $\Lambda$, for some $k$. Moreover, there are $p_n(d)$ copies of the trivial representation in the $d$th degree in $\Lambda$ for all $d$, where $p_n(d)$ is the number of partitions of $d$ into parts of size at most $n$. (One can use the elementary or power sum symmetric function bases to see this.) From this we obtain the following series identity:

$$\left(\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d\right)= \left(\sum p_n(d)q^d\right)\cdot \left(\sum H_{\chi^\mu}(d) q^d\right)$$

To simplify the left hand side, we can use the generalized version of Molien’s theorem for isotypic components (see here.) This gives us
$$\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d=\frac{1}{n!}\sum_{\pi\in S_n}\frac{\overline{\chi^\mu}(\pi)}{\prod (1-q^{c_i(\pi)})}$$ where the $c_i(\pi)$’s are the cycle lengths of $\pi$.

(See this post for details on the above simplification in the case of the trivial character. The case of a general $\chi^\mu$ is analogous.)

If we group the permutations $\pi$ in the sum above according to cycle type (i.e. by conjugacy class), and use the fact that characters of $S_n$ are integers and hence $\overline{\chi^\mu}=\chi^\mu$, we have $$\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d=\frac{1}{n!}\sum_{\lambda\vdash n} \frac{n!}{z_\lambda}\frac{\chi^\mu(\lambda)}{\prod_i (1-q^{\lambda_i})}.$$ Here $z_\lambda$ are the numbers such that $n!/z_\lambda$ is the size of the conjugacy class corresponding to the partition $\lambda$. It is not hard to see that this simplifies to a specialization of the power sum symmetric functions: $$\sum \frac{\chi^\mu(\lambda)}{z_\lambda} p_\lambda(1,q,q^2,\ldots)$$

Finally, by the representation-theoretic definition of the Schur functions, we see that this is simply $$s_\mu(1,q,q^2,\ldots).$$

Substituting for the left hand side of our original equation, we now have $$s_\lambda(1,q,q^2,\ldots)=\left(\sum p_n(d) q^d\right)\cdot \left(\sum H_{\chi^\mu}(d) q^d\right).$$ We can simplify this further by using the series identity $$\sum p_n(d) q^d=\frac{1}{(1-q)(1-q^2)\cdots(1-q^n)}.$$ In addition, there is a well-known identity (see also Enumerative Combinatorics vol. 2, Proposition 7.19.11) $$s_\mu(1,q,q^2,\ldots)=\frac{\sum_T q^{\operatorname{maj} T}}{(1-q)(1-q^2)\cdots (1-q^n)}$$ where the sum ranges over all standard Young tableaux $T$ of shape $\mu$, and where $\operatorname{maj} T$ denotes the sum of all entries $i$ of $T$ that occur in a higher row than $i+1$ (written in English notation).

This does it: putting everything together and solving for $\sum H_{\chi^\mu}(d) q^d$, we obtain $$\sum H_{\chi^\mu}(d) q^d=\sum_{T}q^{\operatorname{maj} T},$$ which is just about equivalent to Lusztig’s claim. (The only difference is whether we are looking at the rows or the columns that $i$ and $i+1$ are in. There must have been a typo, because the two are not the same $q$-series for the shape $(3,1)$. Replacing “column to the left of” by “row above” or replacing $\mu$ by its conjugate would fix the theorem statement above.)

One final consequence of the formulas above is that it is easy to deduce that the ring of coinvariants, $\mathbb{C}[\mathbf{x}]/I$, is isomorphic to the regular representation of $S_n$. Indeed, setting $q=1$ we see that the total number of copies of the irreducible representation corresponding to $\mu$ is equal to the number of standard Young tableaux of shape $\mu$, giving us the regular representation.

Acknowledgments: The above techniques were shown to me by Vic Reiner at a recent conference. Thanks also to Federico Castillo for many discussions about the ring of coinvariants.

# Molien’s Theorem and symmetric functions

My colleague David Harden recently pointed me to Molien’s theorem, a neat little fact about the invariant polynomials under the action by a finite group. It turns out that this has a nice interpretation in the case of the symmetric group $S_n$ that brings in some nice combinatorial and group-theoretic arguments.

The general version of Molien’s theorem can be stated thus: Suppose we have a finite subgroup $G$ of the general linear group $GL_n(\mathbb{C})$. Then $G$ acts on the polynomial ring $R=\mathbb{C}[x_1,\ldots,x_n]$ in the natural way, that is, by replacing the column vector of variables $(x_1,\ldots,x_n)$ with their image under left matrix multiplication by $G$.

Let $R^G$ be the invariant space under this action. Then $R$ is graded by degree; that is, for each nonnegative integer $k$, the space $R_k^G$ of $G$-invariant homogeneous polynomials of degree $k$ are a finite dimensional subspace of $R^G$, and $R^G$ is the direct sum of these homogeneous components. What is the size (dimension) of these homogeneous components?

If $d_k$ denotes the dimension of the $k$th piece, then Molien’s theorem states that the generating function for the $d_k$’s is given by
$$\sum_{k\ge 0} d_k t^k=\frac{1}{|G|}\sum_{M\in G} \frac{1}{\det(I-tM)}$$ where $I$ is the $n\times n$ identity matrix.

There is a nice exposition of the proof (in slightly more generality) in this paper of Richard Stanley, which makes use of some basic facts from representation theory. Rather than go into the proof, let’s look at the special case $G=S_n$, namely the set of all permutation matrices in $GL_n$.

Specialization at $G=S_n$

In this case, the invariant space $R^{S_n}$ is simply the space of symmetric polynomials in $x_1,\ldots,x_n$, and the $k$th graded piece consists of the degree-$k$ homogeneous symmetric polynomials. But we know exactly how many linearly independent homogeneous symmetric polynomials of degree $k$ there can be – as shown in my previous post, the monomial symmetric polynomials $m_\lambda$, where $\lambda$ is any partition of $k$, form a basis of this space in the case that we have infinitely many variables. Since we only have $n$ variables, however, some of these are now zero, namely those for which $\lambda$ has more than $n$ parts. The nonzero $m_\lambda$’s are still linearly independent, so the dimension of the $k$th graded piece in this case is $p(k,n)$, the number of partitions of $k$ into at most $n$ parts.

Notice that by considering the conjugate of each partition, we see that the number of partitions of $k$ into at most $n$ parts is equal to the number of partitions of $k$ that use parts of size at most $n$. It is not hard to see that the generating function for $p(k,n)$ is therefore
$$\sum_{k\ge 0}p(k,n)t^k=\frac{1}{(1-t)(1-t^2)\cdots (1-t^n)}.$$

Molien’s theorem says that this generating function should also be equal to $$\frac{1}{n!}\sum_{M\in S_n}\frac{1}{\det(I-tM)}$$ where we use the somewhat sloppy notation $M\in S_n$ to indicate that $M$ is an $n\times n$ permutation matrix. What are these determinants? Well, suppose $M$ corresponds to a permutation with cycle type $\lambda$, that is, when we decompose the permutation into cycles the lengths of the cycles are $\lambda_1,\ldots,\lambda_r$ in nonincreasing order. Then notice that, up to simultaneous reordering of the rows and columns, $I-tM$ is a block matrix with blocks of sizes $\lambda_1,\ldots,\lambda_r$. The determinant of a block of size $\lambda_i$ is easily seen to be $1-t^{\lambda_i}$. For instance
$$\det \left(\begin{array}{ccc} 1 & -t & 0 \\ 0& 1 & -t \\ -t & 0 & 1\end{array}\right)=1-t^3,$$ and in general, the determinant of such a block will have contributions only from the product of the 1’s down the diagonal and from the product of the off-diagonal $-t$’s; all other permutations have a $0$ among the corresponding matrix entries. The sign on the product of $t$’s is always negative since either $\lambda_i$ is odd, in which case the cyclic permutation of length $\lambda_i$ is even, or $\lambda_i$ is even, in which case the permutation is odd. Hence, the determinant of each block is $1-t^{\lambda_i}$, and the entire determinant is
$$\det (I-tM)=\prod_i (1-t^{\lambda_i}).$$

So, our summation becomes
$$\frac{1}{n!}\sum_{\pi\in S_n} \frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}$$ where $c(\pi)$ denotes the cycle type of a permutation $\pi$. Already we have an interesting identity; we now know this series is equal to
$$\frac{1}{(1-t)(1-t^2)\cdots (1-t^n)}.$$ But can we prove it directly?

It turns out that the equality of these two series can be viewed as a consequence of Burnside’s Lemma. In particular, consider the action of the symmetric group on the set $X$ of weak compositions of $k$ having $n$ parts, that is, an ordered $n$-tuple of nonnegative integers (possibly $0$) that add up to $k$. Then Burnside’s lemma states that the number of orbits under this action, which correspond to the partitions of $k$ having at most $n$ parts, is equal to
$$\frac{1}{n!}\sum_{\pi \in S_n} |X^\pi|$$ where $X^\pi$ is the collection of weak compositions which are fixed under permuting the entries by $\pi$. We claim that this is the coefficient of $t^k$ in
$$\frac{1}{n!}\sum_{\pi\in S_n} \frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}$$ hence showing that the two generating functions are equal.

To see this, note that if $\pi\in S_n$ has cycle type $\lambda$, then $X^\pi$ consists of the weak compositions which have $\lambda_1$ of their parts equal to each other, $\lambda_2$ other parts equal to each other, and so on. Say WLOG that the first $\lambda_1$ parts are all equal, and the second $\lambda_2$ are equal, and so on. Then the first $\lambda_1$ parts total to some multiple of $\lambda_1$, and the next $\lambda_2$ total to some multiple of $\lambda_2$, and so on, and so the total number of such compositions of $k$ is the coefficient of $t^k$ in the product $$\frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}.$$ Averaging over all $\pi\in S_n$ yields the result.

# A q-analog of the decomposition of the regular representation of the symmetric group

It is a well-known fact of representation theory that, if the irreducible representations of a finite group $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\sh}{sh} G$ are $V_1,\ldots,V_m$, and $R$ is the regular representation formed by $G$ acting on itself by left multiplication, then
$$R=\bigoplus_{i=1}^{m} (\dim V_i) \cdot V_i$$ is its decomposition into irreducibles.

I’ve recently discovered a $q$-analog of this fact for $G=S_n$ that is a simple consequence of some known results in symmetric function theory.

In Enumerative Combinatorics, Stanley defines a generalization of the major index on permutations to standard tableaux. For a permutation $$w=w_1,\ldots,w_n$$ of $1,\ldots,n$, a descent is a position $i$ such that $w_i>w_{i+1}$. For instance, $52413$ has two descents, in positions $1$ and $3$. The major index of $w$, denoted $\maj(w)$, is the sum of the positions of the descents, in this case $$\maj(52413)=1+3=4.$$

To generalize this to standard Young tableaux, notice that $i$ is a descent of $w$ if and only if the location of $i$ occurs after $i+1$ in the inverse permutation $w^{-1}$. With this as an alternative notion of descent, we define a descent of a tableau $T$ to be a number $i$ for which $i+1$ occurs in a lower row than $i$. In fact, this is precisely a descent of the inverse of the reading word of $T$, the word formed by reading the rows of $T$ from left to right, starting from the bottom row.

As an example, the tableau $T$ below has two descents, $2$ and $4$, since $3$ and $5$ occur in lower rows than $2$ and $4$ respectively:

So $\maj(T)=2+4=6$. Note that its reading word $5367124$, and the inverse permutation is $5627134$, which correspondingly has descents in positions $2$ and $4$.

(This is a slightly different approach to the major index than taken by Stanley, who used a reading word that read the columns from bottom to top, starting at the leftmost column. The descents remain the same in either case, since both reading words Schensted insert to give the same standard Young tableau.)

Now, the major index for tableaux gives a remarkable specialization of the Schur functions $s_\lambda$. As shown in Stanley’s book, we have $$s_\lambda(1,q,q^2,q^3,\ldots)=\frac{\sum_{T} q^{\maj(T)}}{(1-q)(1-q^2)\cdots(1-q^n)}$$ where the sum is over all standard Young tableaux $T$ of shape $\lambda$. When I came across this fact, I was reminded of a similar specialization of the power sum symmetric functions. It is easy to see that
$$p_\lambda(1,q,q^2,q^3,\ldots)=\prod_{i}\frac{1}{1-q^{\lambda_i}},$$ an identity that comes up in defining a $q$-analog of the Hall inner product in the theory of Hall-Littlewood symmetric functions. In any case, the power sum symmetric functions are related to the Schur functions via the irreducible characters $\chi_\mu$ of the symmetric group $S_n$, and so we get

\begin{eqnarray*}
p_\lambda(1,q,q^2,\ldots) &=& \sum_{|\mu|=n} \chi_{\mu}(\lambda) s_{\mu}(1,q,q^2,\ldots) \\
\prod_{i} \frac{1}{1-q^{\lambda_i}} &=& \sum_{\mu} \chi_{\mu}(\lambda) \frac{\sum_{T\text{ shape }\mu} q^{\maj(T)}}{(1-q)(1-q^2)\cdots(1-q^n)} \\
\end{eqnarray*}

This can be simplified to the equation:
\sum_{|T|=n} \chi_{\sh(T)}(\lambda)q^{\maj(T)} = \frac{(1-q)(1-q^2)\cdots (1-q^n)}{(1-q^{\lambda_1})(1-q^{\lambda_2})\cdots(1-q^{\lambda_k})}
where $\sh(T)$ denotes the shape of the tableau $T$.

Notice that when we take $q\to 1$ above, the right hand side is $0$ unless $\lambda=(1^n)$ is the partition of $n$ into all $1$’s. If $\lambda$ is not this partition, setting $q=1$ yields $$\sum \chi_\mu(\lambda)\cdot f^{\mu}=0$$ where $f^\mu$ is the number of standard Young tableaux of shape $\mu$. Otherwise if $\lambda=(1^n)$, we obtain $$\sum \chi_\mu(\lambda)\cdot f^{\mu}=n!.$$ Recall also that $f^\mu$ (see e.g. Stanley or Sagan) is equal to the dimension of the irreducible representation $V_\mu$ of $S_n$. Thus, these two equations together are equivalent to the fact that, if $R$ is the regular representation,
$$\chi_R=\sum_\mu (\dim V_\mu) \cdot \chi_{\mu}$$ which is in turn equivalent to the decomposition of $R$ into irreducibles.

Therefore, Equation (1) is a $q$-analog of the decomposition of the regular representation. I’m not sure this is known, and I find it’s a rather pretty consequence of the Schur function specialization at powers of $q$.

EDIT: It is known, as Steven Sam pointed out in the comments below, and it gives a formula for a graded character of a graded version of the regular representation.

# Summary: Symmetric functions transition table

Over the last few weeks I’ve been writing about several little gemstones that I have seen in symmetric function theory. But one of the main overarching beauties of the entire area is that there are at least five natural bases with which to express any symmetric functions: the monomial ($m_\lambda$), elementary ($e_\lambda$), power sum ($p_\lambda$), complete homogeneous ($h_\lambda$), and Schur ($s_\lambda$) bases. As a quick reminder, here is an example of each, in three variables $x,y,z$:

$m_{(3,2,2)}=x^3y^2z^2+y^3x^2z^2+z^3y^2x^2$

$e_{(3,2,2)}=e_3e_2e_2=xyz(xy+yz+zx)^2$

$p_{(3,2,2)}=p_3p_2p_2=(x^3+y^3+z^3)(x^2+y^2+z^2)^2$

$h_{(2,1)}=h_2h_1=(x^2+y^2+z^2+xy+yz+zx)(x+y+z)$

$s_{(3,1)}=m_{(3,1)}+m_{(2,2)}+2m_{(2,1,1)}$

Since we can usually transition between the bases fairly easily, this gives us lots of flexibility in attacking problems involving symmetric functions; it’s sometimes just a matter of picking the right basis.

So, to wrap up my recent streak on symmetric function theory, I’ve posted below a list of rules for transitioning between the bases. (The only ones I have not mentioned is how to take a polynomial expressed in the monomial symmetric functions $m_\lambda$ in terms of the others; this is rarely needed and also rather difficult.)

Elementary to monomial:
$$e_\lambda=\sum M_{\lambda\mu} m_\mu$$
where $M_{\lambda\mu}$ is the number of $0,1$-matrices with row sums $\lambda_i$ and column sums $\mu_j$.

Elementary to homogeneous:
$$e_n=\det \left(\begin{array}{cccccc} h_1 & 1 & 0 & 0 &\cdots & 0 \\ h_2 & h_1 & 1 & 0 & \cdots & 0 \\ h_3 & h_2 & h_1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ h_{n-1} & h_{n-2} & h_{n-3} & h_{n-4} & \ddots & 1 \\ h_n & h_{n-1} & h_{n-2} & h_{n-3} & \cdots & h_1 \end{array}\right)$$

Elementary to power sum:
$$e_n=\frac{1}{n!}\det\left(\begin{array}{cccccc} p_1 & 1 & 0 & 0 &\cdots & 0 \\ p_2 & p_1 & 2 & 0 & \cdots & 0 \\ p_3 & p_2 & p_1 & 3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ p_{n-1} & p_{n-2} & p_{n-3} & p_{n-4} & \ddots & n-1 \\ p_n & p_{n-1} & p_{n-2} & p_{n-3} & \cdots & p_1 \end{array}\right)$$

Elementary to Schur:
$$e_\lambda=\sum_{\mu} K_{\mu’\lambda}s_\mu$$
where $K_{\lambda\mu}$ is the number of semistandard Young tableau of shape $\lambda$ and content $\mu$.

Homogeneous to monomial:
$$h_\lambda=\sum N_{\lambda\mu} m_\mu$$

where $N_{\lambda\mu}$ is the number of matrices with nonnegative integer entries with row sums $\lambda_i$ and column sums $\mu_j$.

Homogeneous to elementary:
$$h_n=\det\left(\begin{array}{cccccc} e_1 & 1 & 0 & 0 &\cdots & 0 \\ e_2 & e_1 & 1 & 0 & \cdots & 0 \\ e_3 & e_2 & e_1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ e_{n-1} & e_{n-2} & e_{n-3} & e_{n-4} & \ddots & 1 \\ e_n & e_{n-1} & e_{n-2} & e_{n-3} & \cdots & e_1 \end{array}\right)$$

Homogeneous to power sum:
$$h_n=\frac{1}{n!}\det\left(\begin{array}{cccccc} p_1 & -1 & 0 & 0 &\cdots & 0 \\ p_2 & p_1 & -2 & 0 & \cdots & 0 \\ p_3 & p_2 & p_1 & -3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ p_{n-1} & p_{n-2} & p_{n-3} & p_{n-4} & \ddots & -(n-1) \\ p_n & p_{n-1} & p_{n-2} & p_{n-3} & \cdots & p_1 \end{array}\right)$$

Homogeneous to Schur:
$$h_{\lambda}=\sum_\mu K_{\mu\lambda}s_\mu$$

Power sum to monomial:
$$p_\lambda=\sum_{\mu} R_{\lambda\mu}m_\mu$$
where $R_{\lambda\mu}$ is the number of ways of sorting the parts of $\lambda$ into a number of ordered blocks in such a way that the sum of the parts in the $j$th block is $\mu_j$.

Power sum to elementary:
Newton-Gerard identities:
$$p_n=\det\left(\begin{array}{cccccc} e_1 & 1 & 0 & 0 &\cdots & 0 \\ 2e_2 & e_1 & 1 & 0 & \cdots & 0 \\ 3e_3 & e_2 & e_1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ (n-1)e_{n-1} & e_{n-2} & e_{n-3} & e_{n-4} & \ddots & 1 \\ ne_n & e_{n-1} & e_{n-2} & e_{n-3} & \cdots & e_1 \end{array}\right)$$

Power sum to homogeneous:
$$p_n=(-1)^{n-1}\det\left(\begin{array}{cccccc} h_1 & 1 & 0 & 0 &\cdots & 0 \\ 2h_2 & h_1 & 1 & 0 & \cdots & 0 \\ 3h_3 & h_2 & h_1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ (n-1)h_{n-1} & h_{n-2} & h_{n-3} & h_{n-4} & \ddots & 1 \\ nh_n & h_{n-1} & h_{n-2} & h_{n-3} & \cdots & h_1 \end{array}\right)$$

Power sum to Schur:
Let $\chi^\lambda$ be the $\lambda$th character of the symmetric group $S_n$ where $n=|\lambda|$, and write $\chi^\lambda(\mu)$ to denote the value of $\chi^{\lambda}$ at any permutation with cycle type $\mu$. Then for any partition $\mu\vdash n$, we have:
$$p_\mu=\sum_{\lambda\vdash n} \chi^\lambda(\mu) s_\lambda$$ Alternatively: $$p_n=s_{(n)}-s_{(n-1,1)}+s_{(n-2,1,1)}-s_{(n-3,1,1,1)}+\cdots+(-1)^{n}s_{(1,1,\ldots,1)}$$

Schur to monomial:
$$s_{\lambda}=\sum_{\mu\vdash |\lambda|} K_{\lambda \mu}m_\mu$$

Schur to elementary:
(Dual Jacobi-Trudi Identity.)
$$s_{\lambda/\mu} = \det \left(e_{\lambda’_i-\mu’_j-i+j}\right)_{i,j=1}^n$$

Schur to homogeneous:
(Jacobi-Trudi Identity.)
$$s_{\lambda/\mu} = \det \left(h_{\lambda_i-\mu_j-i+j}\right)_{i,j=1}^n$$

Schur to power sum:
$$s_\lambda=\sum_{\nu\vdash |\lambda|} z_\nu^{-1} \chi^{\lambda}(\nu) p_\nu$$