Burnside's Lemma

From ProofWiki
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:

$\displaystyle \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.