Burnside's Lemma
Jump to navigation
Jump to search
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.