Burnside’s lemma by traces

Burnside’s lemma relates the number of orbits of a group action to the average number of fixed points for each group element:

$$\begin{array}{c}\left|G\setminus X\right|=\frac{1}{\left|G\right|}\sum _{g\in G}\left|X^g\right|\end{array}$$ Here, $G$ is a finite group, $X$ is a finite set that $G$ acts on, $G\setminus X=\{Gx\mid x\in X\}$ is the set of orbits, and $X^g=\{x\in X\mid gx=x\}$ is the set of fixed points for $g\in G$.

Today I noticed that there is an interesting elementary proof of this using linear algebra. It takes a little work to define a few things (which are sort of standard in representation theory), but then the core of the argument reduces to the observation that the trace satisfies $\mathrm{tr}\left(AB\right)=\mathrm{tr}\left(BA\right)$, which I thought was kind of neat.

Let $C\cdot X$ denote the vector space over $C$ with basis $X$ (or, in other words, the set of all functions $X\to C$). Similarly, let $C\cdot G\setminus X$ be the vector space with basis $G\setminus X$. The quotient map $X\to G\setminus X$ induces a linear map

$$\begin{array}{c}q:C\cdot X\to C\cdot G\setminus X\end{array}$$ with $q\left(x\right)=Gx$ for each $x\in X$. (To clarify this: $Gx$ is the orbit for $x$, and it is considered to be one of the basis vectors of the codomain.)

So far, no real use of linearity, but we will make use of it for the next map. We define

$$\begin{array}{c}s:C\cdot G\setminus X\to C\cdot X\end{array}$$ by $$\begin{array}{c}s\left(Gx\right)=\frac{1}{\left|G\right|}\sum _{g\in G}gx\end{array}$$ That is, $s$ averages over the action of $G$ on a representative $x$ in an orbit. This does not depend on the choice of representative (and indeed $s\left(Gx\right)$ is a scale multiple of ${\sum }_{y\in Gx}y$).

We calculate the two compositions of $q$ with $s$. First,

$$\begin{array}{cc}q\left(s\right(Gx\left)\right)& =q\left(\frac{1}{\left|G\right|}\sum _{g\in G}gx\right)\\ & =\frac{1}{\left|G\right|}\sum _{g\in G}Gx\\ & =Gx\end{array}$$ Hence, $q\circ s$ is the identity on $C\cdot G\setminus X$. Second, $$\begin{array}{cc}s\left(q\right(x\left)\right)& =s\left(Gx\right)\\ & =\frac{1}{\left|G\right|}\sum _{g\in G}gx\end{array}$$

Now, consider the fact that the trace of the identity transformation for a vector space is the dimension of the vector space, which means $\mathrm{tr}(q\circ s)=\left|G\setminus X\right|$. Recall that trace is commutative, in the sense that $\mathrm{tr}(q\circ s)=\mathrm{tr}(s\circ q)$. Hence, with square brackets denoting the Iverson bracket,

$$\begin{array}{cc}\left|G\setminus X\right|& =\mathrm{tr}(q\circ s)\\ & =\mathrm{tr}(s\circ q)\\ & =\sum _{x\in X}\frac{1}{\left|G\right|}\sum _{g\in G}[gx=x]\\ & =\frac{1}{\left|G\right|}\sum _{g\in G}\sum _{x\in X}[gx=x]\\ & =\frac{1}{\left|G\right|}\sum _{g\in G}\left|X^g\right|\end{array}$$ And that’s Burnside’s lemma!

There’s a more representation-theoretic reason for the theorem, too, and the above came from thinking about it, trying to remove the representation theory to make it more accessible. What we can recognize is that the right-hand side of the equality is the inner product of the characters for the trivial representation and for the permutation representation $C\cdot X$. The inner product is equivalently $\dim {\mathrm{hom}}_G(C\cdot X,C)$, which is the same as the vector space of functions on $X$ that are constant on orbits — and the dimension of this space is $\left|G\setminus X\right|$.