Burnside's lemma (FGT 1A.6)

Let \(\chi\) be the permutation character associated with the action of a group \(G\) on a set \(A\). Prove that \(\sum_{g \in G} \chi(g) = \sum_{a \in A} \left|G_a\right| = n\left|G\right|\), where \(n\) is the number of orbits.

The action of \(G\) on \(A\) can be represented by a table where the rows are elements of \(G\) and the columns are elements of \(A\). For example, here is the action of \(D_6\) on the three vertices of a triangle:

	1	2	3
1	1	2	3
\(r\)	3	1	2
\(r^2\)	2	3	1
\(s\)	3	2	1
\(rs\)	1	3	2
\(r^2s\)	2	1	3

If we highlight all cells \((g,a)\) where \(g \cdot a = a\), then we get the following table:

	1	2	3
1	1	2	3
\(r\)	3	1	2
\(r^2\)	2	3	1
\(s\)	3	2	1
\(rs\)	1	3	2
\(r^2s\)	2	1	3

Notice that the sum \(\sum_{g \in G} \chi(g)\) corresponds to be a horizontal summation of the highlighted squares, while \(\sum_{a \in A} \left|G_a\right|\) corresponds to a vertical summation.

Lastly, \(\sum_{a \in A} \left|G_a\right| = \sum_{\mathcal{O}} \sum_{a \in \mathcal{O}} \left|G_a\right| = \sum_{\mathcal{O}} \sum_{a \in \mathcal{O}} \frac{\left|G\right|}{\left|\mathcal{O}\right|} = n\left|G\right|\).