Group actions: Burnside’s lemma

Posted: May 12, 2022 in Basic Algebra, Groups
Tags: , , ,
0

Before stating and proving Burnside’s lemma, let me state and prove a very simple and yet useful fact from basic set theory.

Fact. Let X be a finite set and let \sim be an equivalence relation defined on X. For each x \in X, let \overline{x} be the equivalence class of x, i.e. \overline{x}=\{y \in X: \ y \sim x\}, and suppose that the number of distinct equivalence classes is n. Then

\displaystyle n=\sum_{x \in X} \frac{1}{|\overline{x}|}.

Proof. Let \{\overline{x}_1, \cdots , \overline{x}_n\} be the set of distinct equivalence classes. So \overline{x}_i \cap \overline{x}_j =\emptyset, for all i \ne j, and X=\bigcup_{i=1}^n \overline{x}_i. Also, for x \in X, \ 1 \le i \le n, we have \overline{x}=\overline{x}_i if and only if x \in \overline{x}_i. Thus

\displaystyle \sum_{x \in X} \frac{1}{|\overline{x}|}=\sum_{i=1}^n \sum_{x \in \overline{x_i}} \frac{1}{|\overline{x}|}=\sum_{i=1}^n\sum_{x \in \overline{x}_i} \frac{1}{|\overline{x}_i|}=\sum_{i=1}^n \frac{1}{|\overline{x}_i|}\sum_{x \in \overline{x}_i} 1=\sum_{i=1}^n 1=n. \ \Box

Notation. Let G be a group acting on a set X. For any g \in G, let \text{Fix}(g):=\{x \in X: \ g \cdot x=x\}.

Burnside’s Lemma. Let G be a finite group acting on a finite set X. Let n be the number of orbits of X. Then

\displaystyle n=\frac{1}{|G|}\sum_{g \in G} |\text{Fix}(g)|.

Proof. Let A:=\{(g,x) \in G \times X : \ g \cdot x = x\}. Then clearly

\displaystyle |A|=\sum_{g \in G}|\text{Fix}(g)|, \ \ \ \ |A|=\sum_{x \in X}|\text{stab}(x)|,

and so

\displaystyle \sum_{g \in G}|\text{Fix}(g)|=\sum_{x \in X}|\text{stab}(x)|=\sum_{x \in X}\frac{|G|}{|\text{orb}(x)|},

by the orbit-stabilizer theorem. Thus

\displaystyle \sum_{g \in G}|\text{Fix}(g)|=|G|\sum_{x \in X}\frac{1}{|\text{orb}(x)|}=|G|n, \ \ \ \ \ \ \text{by the above Fact},

and the result follows. \ \Box

Exercise. Use the above Fact to show that if G is a finite group, and C(g) is the centralizer of g \in G, then the number of conjugacy classes of G is \displaystyle \frac{1}{|G|}\sum_{g \in G}|C(g)|.

Leave a Reply