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.