Burnside's Lemma

Theorem

Let $G$ be a finite group acting on a set $X$.

Let $X / G$ be the set of orbits under this action.

For $x \in X$, let $\Stab x$ be the stabilizer of $x$ by $G$.

For $g \in G$, let $X^g$ denotes the set of all elements in $X$ which is fixed by $g$, that is:

$X^g := \set {x \in X: g x = x}$

Then:

$\ds \size {X / G} = \frac 1 {\order G} \sum_{g \mathop \in G} \size {X^g}$

In words, the number of orbits equals the average number of fixed elements.

Proof

\(\ds \frac 1 {\order G} \sum_{g \mathop \in G} \size {X^g}\)

\(=\)

\(\ds \frac 1 {\order G} \sum_{g \mathop \in G} \size {\set {x \in X: g x = x} }\)

by definition

\(\ds \)

\(=\)

\(\ds \frac 1 {\order G} \sum_{x \mathop \in X} \size {\set {g \in G: g x = x} }\)

Same summation, different indexing

\(\ds \)

\(=\)

\(\ds \frac 1 {\order G} \sum_{x \mathop \in X} \order {\Stab x}\)

Definition of Stabilizer

\(\ds \)

\(=\)

\(\ds \frac 1 {\order G} \sum_{x \mathop \in X} \frac {\order G} {\order {\Orb x} }\)

Orbit-Stabilizer Theorem

\(\ds \)

\(=\)

\(\ds \sum_{x \mathop \in X} \frac 1 {\order {\Orb x} }\)

\(\ds \)

\(=\)

\(\ds \sum_{\Orb x \mathop \in X / G} \paren {\sum_{x \mathop \in \Orb x} \frac 1 {\order {\Orb x} } }\)

\(\ds \)

\(=\)

\(\ds \sum_{\Orb x \mathop \in X / G} 1\)

\(\ds \)

\(=\)

\(\ds \order {X / G}\)

$\blacksquare$

Also known as

This theorem is also known as Burnside's Counting Theorem.

Source of Name

This entry was named for William Burnside.