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:

|GX|=1|G|gG|Xg| Here, G is a finite group, X is a finite set that G acts on, GX={GxxX} is the set of orbits, and Xg={xXgx=x} is the set of fixed points for gG.

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 tr(AB)=tr(BA), which I thought was kind of neat.

Let CX denote the vector space over C with basis X (or, in other words, the set of all functions XC). Similarly, let CGX be the vector space with basis GX. The quotient map XGX induces a linear map

q:CXCGX with q(x)=Gx for each xX. (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

s:CGXCX by s(Gx)=1|G|gGgx 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(Gx) is a scale multiple of yGxy).

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

q(s(Gx))=q(1|G|gGgx)=1|G|gGGx=Gx Hence, qs is the identity on CGX. Second, s(q(x))=s(Gx)=1|G|gGgx

Now, consider the fact that the trace of the identity transformation for a vector space is the dimension of the vector space, which means tr(qs)=|GX|. Recall that trace is commutative, in the sense that tr(qs)=tr(sq). Hence, with square brackets denoting the Iverson bracket,

|GX|=tr(qs)=tr(sq)=xX1|G|gG[gx=x]=1|G|gGxX[gx=x]=1|G|gG|Xg| 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 CX. The inner product is equivalently dimhomG(CX,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 |GX|.