Group Actions

Study Sheet

Group Actions

Groups acting on sets, orbits and stabilizers, and counting with Burnside's lemma

Group Actions

Concept
Group action

A (left) group action of GG on a set XX is a function G×X→XG\times X\to X, written (g,x)↦g⋅x(g,x)\mapsto g\cdot x, satisfying e⋅x=xe\cdot x=x and (gh)⋅x=g⋅(h⋅x)(gh)\cdot x=g\cdot(h\cdot x) for all g,h∈Gg,h\in G and x∈Xx\in X.

An action lets an abstract group become literal motion: GG does not just sit beside XX, every g∈Gg\in G moves every point of XX somewhere, and the compatibility axiom says doing hh then gg always lands in the same place as doing the single combined motion ghgh the action faithfully tracks the group's own multiplication, not just a loose pile of functions. Cayley's theorem (Topic 4) already used one action without the name: GG acting on itself by left multiplication, g⋅x=gxg\cdot x=gx. This topic studies actions on sets XX other than GG itself vertices of a polygon, colorings, subsets where the geometry becomes the real subject.

Example
D4D_4 acting on the vertices of a square
1234The square's 4 vertices; D_4 acts by its 8 symmetries.

Label the square's vertices 1,2,3,41,2,3,4 clockwise from the top. D4={e,r,r2,r3,s,rs,r2s,r3s}D_4=\{e,r,r^2,r^3,s,rs,r^2s,r^3s\} (Topic 6) acts on {1,2,3,4}\{1,2,3,4\}: rr sends 1↦2↦3↦4↦11\mapsto2\mapsto3\mapsto4\mapsto1, and ss fixes 1,31,3 while swapping 2,42,4. Check compatibility at x=1x=1: s⋅1=1s\cdot1=1, so r⋅(s⋅1)=r⋅1=2r\cdot(s\cdot1)=r\cdot1=2. Directly, rsrs (apply ss, then rr) sends 1↦1↦21\mapsto1\mapsto2, so (rs)⋅1=2(rs)\cdot1=2 as well the two routes agree.

Example
Multiplication mod 77 is a group action

U(7)={1,…,6}U(7)=\{1,\ldots,6\} acts on X=Z7X=\mathbb Z_7 by a⋅x=ax mod 7a\cdot x=ax\bmod7. Check compatibility at a=3,b=5,x=4a=3,b=5,x=4: first b⋅x=5⋅4=20≡6(mod7)b\cdot x=5\cdot4=20\equiv6\pmod7, so a⋅(b⋅x)=3⋅6=18≡4(mod7)a\cdot(b\cdot x)=3\cdot6=18\equiv4\pmod7. Directly, ab=15≡1(mod7)ab=15\equiv1\pmod7, so (ab)⋅x=1⋅4=4(mod7)(ab)\cdot x=1\cdot4=4\pmod7 the same value 44 either way, as associativity of multiplication mod 77 guarantees for every triple.

Example
Is this a group action?

S4S_4 acts on the 66 two-element subsets of {1,2,3,4}\{1,2,3,4\} by σ⋅{a,b}={σ(a),σ(b)}\sigma\cdot\{a,b\}=\{\sigma(a),\sigma(b)\}. Check compatibility for σ=(1 2 3)\sigma=(1\,2\,3), τ=(1 2)(3 4)\tau=(1\,2)(3\,4), acting on {1,2}\{1,2\}. First τ⋅{1,2}={τ(1),τ(2)}={2,1}={1,2}\tau\cdot\{1,2\}=\{\tau(1),\tau(2)\}=\{2,1\}=\{1,2\}, so σ⋅(τ⋅{1,2})=σ⋅{1,2}={2,3}\sigma\cdot(\tau\cdot\{1,2\})=\sigma\cdot\{1,2\}=\{2,3\}. Directly, στ\sigma\tau sends 1↦σ(τ(1))=σ(2)=31\mapsto\sigma(\tau(1))=\sigma(2)=3 and 2↦σ(τ(2))=σ(1)=22\mapsto\sigma(\tau(2))=\sigma(1)=2, so (στ)⋅{1,2}={3,2}={2,3}(\sigma\tau)\cdot\{1,2\}=\{3,2\}=\{2,3\} matching. Since every σ\sigma is a bijection, {σ(a),σ(b)}\{\sigma(a),\sigma(b)\} is always a genuine 22-element subset: this is a group action, on a set of size ∣X∣=(42)=6|X|=\binom{4}{2}=6.

Side note
Where it goes wrong

A plausible-looking rule can still fail the compatibility axiom. Try g⋅x:=g−1(x)g\cdot x:=g^{-1}(x) for S3S_3 acting on {1,2,3}\{1,2,3\}, with σ=(1 2)\sigma=(1\,2), τ=(1 3)\tau=(1\,3). Then τ⋅1=τ−1(1)=τ(1)=3\tau\cdot1=\tau^{-1}(1)=\tau(1)=3 (transpositions are self-inverse), so σ⋅(τ⋅1)=σ⋅3=σ−1(3)=3\sigma\cdot(\tau\cdot1)=\sigma\cdot3=\sigma^{-1}(3)=3. But στ\sigma\tau sends 1↦σ(τ(1))=σ(3)=31\mapsto\sigma(\tau(1))=\sigma(3)=3, 2↦σ(τ(2))=σ(2)=12\mapsto\sigma(\tau(2))=\sigma(2)=1, 3↦σ(τ(3))=σ(1)=23\mapsto\sigma(\tau(3))=\sigma(1)=2, so (στ)−1(\sigma\tau)^{-1} sends 1↦21\mapsto2, giving (στ)⋅1=(στ)−1(1)=2(\sigma\tau)\cdot1=(\sigma\tau)^{-1}(1)=2. Since 3≠23\ne2, the axiom fails: g⋅x=g−1(x)g\cdot x=g^{-1}(x) is not a group action on a non-abelian group, even though e⋅x=xe\cdot x=x holds.

Try it
Try it: check the axiom

Using the D4D_4 action on the square's vertices above, check that (rs)⋅2=r⋅(s⋅2)(rs)\cdot2=r\cdot(s\cdot2).

Show the answer

s⋅2=4s\cdot2=4 (the reflection swaps 22 and 44), so r⋅(s⋅2)=r⋅4=1r\cdot(s\cdot2)=r\cdot4=1. Directly, rsrs sends 2↦4↦12\mapsto4\mapsto1 (apply ss, then rr), so (rs)⋅2=1(rs)\cdot2=1 too. Both routes give 1\mathbf{1}.

Orbits and Stabilizers

Concept
Orbit and stabilizer

For x∈Xx\in X, the orbit of xx is Orb⁡(x)={g⋅x:g∈G}⊆X\operatorname{Orb}(x)=\{g\cdot x:g\in G\}\subseteq X, the set of everywhere xx can be moved to. The stabilizer of xx is Stab⁡(x)={g∈G:g⋅x=x}⊆G\operatorname{Stab}(x)=\{g\in G:g\cdot x=x\}\subseteq G, the symmetries that leave xx exactly where it is; Stab⁡(x)\operatorname{Stab}(x) is always a subgroup of GG (Why It Works). The orbits partition XX into disjoint pieces, the same way cosets partition a group (Topic 5).

Orbit and stabilizer answer two different questions about the same point: the orbit lives inside XX and asks "where can xx go?", while the stabilizer lives inside GG and asks "which symmetries don't move xx at all?" An action is transitive when XX itself is a single orbit every point reachable from every other which is exactly the situation for D4D_4 turning a square's vertices into one another. The stabilizer is never empty, since ee always fixes xx, and checking it is a subgroup costs nothing new: it is a direct instance of the subgroup test from Topic 3, run on the condition "g⋅x=xg\cdot x=x" instead of a formula in gg alone.

Example
The orbit of a vertex

Find Orb⁡(2)\operatorname{Orb}(2) for D4D_4 acting on the square's vertices. Applying all 88 elements to 22: e⋅2=2e\cdot2=2, r⋅2=3r\cdot2=3, r2⋅2=4r^2\cdot2=4, r3⋅2=1r^3\cdot2=1, s⋅2=4s\cdot2=4, rs⋅2=1rs\cdot2=1, r2s⋅2=2r^2s\cdot2=2, r3s⋅2=3r^3s\cdot2=3. The distinct values are {1,2,3,4}\{1,2,3,4\}: Orb⁡(2)\operatorname{Orb}(2) is the whole vertex set, so the action is transitive unsurprising, since a square's symmetries can carry any corner onto any other.

Example
The stabilizer of a vertex
1234
The mirror through vertices 2 and 4 is the only nontrivial symmetry fixing vertex 2.

From the list just computed, Stab⁡(2)={g:g⋅2=2}={e,r2s}\operatorname{Stab}(2)=\{g:g\cdot2=2\}=\{e,r^2s\}, since only ee and r2sr^2s fixed 22 among the 88 values above. Geometrically r2sr^2s is the reflection through the diagonal joining vertices 22 and 44 the one mirror, besides doing nothing, that leaves vertex 22 in place.

Example
Does D4D_4 act transitively on the diagonals?

The square has 22 diagonals, {1,3}\{1,3\} and {2,4}\{2,4\}, and D4D_4 acts on this 22-element set by g⋅{a,b}={g⋅a,g⋅b}g\cdot\{a,b\}=\{g\cdot a,g\cdot b\}. Computing g⋅{1,3}g\cdot\{1,3\} for all 88 elements: e,r2,s,r2se,r^2,s,r^2s all fix {1,3}\{1,3\} (e.g. r2⋅{1,3}={3,1}={1,3}r^2\cdot\{1,3\}=\{3,1\}=\{1,3\}), while r,r3,rs,r3sr,r^3,rs,r^3s all send it to {2,4}\{2,4\}. So Orb⁡({1,3})={{1,3},{2,4}}\operatorname{Orb}(\{1,3\})=\{\{1,3\},\{2,4\}\}, the whole set yes, transitive with Stab⁡({1,3})={e,r2,s,r2s}\operatorname{Stab}(\{1,3\})=\{e,r^2,s,r^2s\}, order 44.

Side note
Where it goes wrong

An orbit and a stabilizer live in different worlds and are easy to mix up. Orb⁡(2)={1,2,3,4}⊆X\operatorname{Orb}(2)=\{1,2,3,4\}\subseteq X has 44 elements, all of them vertices; Stab⁡(2)={e,r2s}⊆G\operatorname{Stab}(2)=\{e,r^2s\}\subseteq G has 22 elements, both of them symmetries. Neither set is a subset of the other, and there is no reason to expect their sizes to match here they don't (4≠24\ne2), and the relationship between the two sizes is exactly what the next section pins down.

Try it
Try it: orbit and stabilizer of a vertex

Find Orb⁡(1)\operatorname{Orb}(1) and Stab⁡(1)\operatorname{Stab}(1) for D4D_4 acting on the square's vertices.

Show the answer

Every vertex of the square is reachable from vertex 11 by some rotation, so Orb⁡(1)={1,2,3,4}\operatorname{Orb}(1)=\mathbf{\{1,2,3,4\}}. For the stabilizer, only ee and the reflection ss (through vertices 11 and 33) fix vertex 11: Stab⁡(1)={e,s}\operatorname{Stab}(1)=\mathbf{\{e,s\}}.

The Orbit-Stabilizer Theorem

Concept
The orbit-stabilizer theorem

For a finite group GG acting on XX and any x∈Xx\in X,

∣G∣=∣Orb⁡(x)∣⋅∣Stab⁡(x)∣.|G|=|\operatorname{Orb}(x)|\cdot|\operatorname{Stab}(x)|.

Equivalently, ∣Orb⁡(x)∣=[G:Stab⁡(x)]|\operatorname{Orb}(x)|=[G:\operatorname{Stab}(x)]: the orbit size is the index of the stabilizer, so it always divides ∣G∣|G|.

The proof (Why It Works) sets up a bijection between the orbit of xx and the cosets of Stab⁡(x)\operatorname{Stab}(x): the coset gStab⁡(x)g\operatorname{Stab}(x) corresponds to the single point g⋅xg\cdot x, and every element of that coset sends xx to that same point. So "how large is the orbit" and "how large is the stabilizer" are not independent questions they multiply to the fixed number ∣G∣|G|, exactly the way Lagrange's theorem (Topic 5) makes subgroup order and index multiply to ∣G∣|G|. This is, in fact, Lagrange's theorem applied to Stab⁡(x)\operatorname{Stab}(x): the theorem here is what makes that application possible, by identifying the index with something concrete and countable, the orbit.

Example
Checking the theorem on a vertex

For D4D_4 acting on the square's vertices, Section 2 found Orb⁡(2)={1,2,3,4}\operatorname{Orb}(2)=\{1,2,3,4\}, size 44, and Stab⁡(2)={e,r2s}\operatorname{Stab}(2)=\{e,r^2s\}, size 22. Indeed 4⋅2=8=∣D4∣4\cdot2=8=|D_4|, confirming the theorem for this point and since every vertex has the same orbit (all of XX), every vertex's stabilizer must have the same size 8/4=28/4=2, without recomputing each one by hand.

Example
Checking the theorem on the diagonals

Section 2 also found, for D4D_4 acting on the 22 diagonals, Orb⁡({1,3})\operatorname{Orb}(\{1,3\}) of size 22 and Stab⁡({1,3})\operatorname{Stab}(\{1,3\}) of size 44. Again 2⋅4=8=∣D4∣2\cdot4=8=|D_4|. The two examples show the same group splitting 88 two different ways 4×24\times2 for a vertex, 2×42\times4 for a diagonal depending only on how large a piece of XX one point drags along with it.

Example
An orbit size without ever listing the orbit

Let S4S_4 act on its 66 two-element subsets as in Section 1, and find ∣Orb⁡({1,2})∣|\operatorname{Orb}(\{1,2\})| without listing images. A permutation fixes {1,2}\{1,2\} setwise exactly when it permutes {1,2}\{1,2\} among themselves (either fixing both or swapping them, 22 choices) while permuting {3,4}\{3,4\} however it likes (22 choices): Stab⁡({1,2})={e,(1 2),(3 4),(1 2)(3 4)}\operatorname{Stab}(\{1,2\})=\{e,(1\,2),(3\,4),(1\,2)(3\,4)\}, order 44. By the theorem, ∣Orb⁡({1,2})∣=∣S4∣/4=24/4=6|\operatorname{Orb}(\{1,2\})|=|S_4|/4=24/4=6 which must be every 22-element subset, since there are only 66 of them: S4S_4 acts transitively on pairs.

Side note
Where it goes wrong

It is tempting to assume an orbit is always the full size of GG, forgetting the stabilizer can shrink it. D4D_4 has order 88, but Orb⁡(2)\operatorname{Orb}(2) has only 44 elements, not 88 the reflection r2sr^2s already sends 22 back to itself, so the 88 group elements produce only 44 distinct images, each one reached by exactly ∣Stab⁡(2)∣=2|\operatorname{Stab}(2)|=2 different symmetries. An orbit equals ∣G∣|G| only when the stabilizer is trivial.

Try it
Try it: find a stabilizer from the theorem

Given that D4D_4 acts transitively on the square's vertices (∣Orb⁡(3)∣=4|\operatorname{Orb}(3)|=4) and ∣D4∣=8|D_4|=8, find ∣Stab⁡(3)∣|\operatorname{Stab}(3)|, then name its elements.

Show the answer

By the theorem, ∣Stab⁡(3)∣=∣D4∣/∣Orb⁡(3)∣=8/4=2|\operatorname{Stab}(3)|=|D_4|/|\operatorname{Orb}(3)|=8/4=2. Checking directly, the symmetries fixing vertex 33 are ee and the reflection ss through vertices 11 and 33 (the same mirror that fixed vertex 11): Stab⁡(3)={e,s}\operatorname{Stab}(3)=\mathbf{\{e,s\}}.

Burnside's Lemma

Concept
Burnside's lemma

If a finite group GG acts on a finite set XX, the number of orbits equals

1∣G∣∑g∈G∣Fix⁡(g)∣,Fix⁡(g)={x∈X:g⋅x=x}.\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|,\qquad \operatorname{Fix}(g)=\{x\in X:g\cdot x=x\}.

That is: the number of orbits is the average, over the group, of how many points each element fixes.

The proof (Why It Works) counts the pairs (g,x)(g,x) with g⋅x=xg\cdot x=x two ways. Summing over gg first gives ∑g∣Fix⁡(g)∣\sum_g|\operatorname{Fix}(g)| directly. Summing over xx first gives ∑x∣Stab⁡(x)∣\sum_x|\operatorname{Stab}(x)|, and grouping xx by orbit, each orbit OO contributes ∣O∣⋅∣Stab⁡(x)∣=∣G∣|O|\cdot|\operatorname{Stab}(x)|=|G| for any x∈Ox\in O, by the orbit-stabilizer theorem (Section 3) so every orbit contributes exactly ∣G∣|G|, and the total is ∣G∣|G| times the number of orbits. This turns "count the orbits", which looks like it needs listing every point of XX, into "count the fixed points of each of the ∣G∣|G| group elements", often a far shorter list.

Example
Coloring a triangle with 22 colors
123
One of the 8 colorings: two red vertices (1,2), one blue (3).

How many ways are there to color the 33 vertices of a triangle red or blue, where two colorings count as the same if one is a rotation or reflection of the other? Here G=D3G=D_3, ∣G∣=6|G|=6, acting on the 23=82^3=8 colorings. The identity fixes all 88. Each of the 22 nontrivial rotations is a single 33-cycle on the vertices, so it fixes a coloring only if all 33 vertices share one color: 22 colorings each. Each of the 33 reflections fixes one vertex and swaps the other two, so it fixes a coloring exactly when the swapped pair matches: 22 (pair colors) × 2\times\,2 (fixed vertex) =4=4 each. The sum is 8+2⋅2+3⋅4=8+4+12=248+2\cdot2+3\cdot4=8+4+12=24, so the number of orbits is 24/6=424/6=4.

Example
Listing the 44 orbits directly

Check the count of 44 by listing the 88 colorings of the labeled triangle (writing each as vertices 1,2,31,2,3): the 22 monochromatic colorings RRRRRR and BBBBBB are each fixed by every symmetry, so each is its own orbit of size 11. Among the rest, RRB,RBR,BRRRRB,RBR,BRR (one blue vertex) form one orbit of size 33 D3D_3 can move that single blue vertex to any of the 33 positions and RBB,BRB,BBRRBB,BRB,BBR (one red vertex) form a second orbit of size 33, since no symmetry changes a color, only moves positions. That is 1+1+3+3=41+1+3+3=4 orbits, matching Burnside's count exactly.

Example
Coloring a 44-bead necklace with 22 colors, rotation only

Now let G={e,r,r2,r3}G=\{e,r,r^2,r^3\}, the rotations alone (no flipping over), act on 22-colorings of 44 beads in a circle. ee fixes all 24=162^4=16; rr and r3r^3 are single 44-cycles, fixing only the 22 monochromatic colorings each; r2r^2 splits into 22 disjoint 22-cycles, fixing a coloring exactly when each swapped pair matches, 22=42^2=4. The sum is 16+2+4+2=2416+2+4+2=24, giving 24/4=624/4=6 distinct necklaces a different group from the triangle example, but the same lemma.

Side note
Where it goes wrong

The denominator is ∣G∣|G|, never ∣X∣|X|. In the triangle example, ∑g∣Fix⁡(g)∣=24\sum_g|\operatorname{Fix}(g)|=24 and ∣G∣=6|G|=6 gives the correct 44 orbits; dividing by ∣X∣=8|X|=8 instead gives 24/8=324/8=3, which is not even what direct listing found. The sum always runs over group elements (one term per symmetry), and the average is taken over how many symmetries there are, not over how many colorings there are.

Try it
Try it: Burnside on a 55-bead necklace

Using rotations only (G={e,r,r2,r3,r4}G=\{e,r,r^2,r^3,r^4\}, ∣G∣=5|G|=5), how many 22-colorings of 55 beads in a circle are there, up to rotation?

Show the answer

ee fixes all 25=322^5=32. Since 55 is prime, each of the 44 nontrivial rotations is a single 55-cycle, fixing only the 22 monochromatic colorings. The sum is 32+4⋅2=4032+4\cdot2=40, so the count is 40/5=840/5=\mathbf{8}.

Counting Colorings Up to Symmetry

Concept
The cycle trick

For a group GG acting on the positions 1,…,n1,\ldots,n of a figure, and colorings with kk colors,

∣Fix⁡(g)∣=kc(g),|\operatorname{Fix}(g)|=k^{c(g)},

where c(g)c(g) is the number of cycles in gg's disjoint cycle decomposition (Topic 4) of the positions, counting fixed points as 11-cycles. A coloring is unchanged by gg exactly when it assigns the same color to every position within one cycle of gg free choice of color between cycles, none within one which is kk choices per cycle, c(g)c(g) cycles.

This turns Burnside's lemma into pure arithmetic: find each group element's cycle type on the positions (exactly as in Topic 4's permutations), raise kk to the number of cycles, and average. No coloring ever needs to be listed by hand, however large kk or nn gets. The two square examples (Section 2) already illustrated the extremes: the identity has nn cycles (every position its own), giving the largest fixed count knk^n; an nn-cycle rotation has just 11 cycle, giving the smallest nontrivial fixed count kk.

Example
Coloring the square's vertices with 33 colors
1234
One of the 81 colorings of the square's 4 vertices with 3 colors.

How many ways to color the square's 44 vertices with 33 colors, up to the full symmetry group D4D_4 (rotations and reflections)? Cycle counts: ee has 44 cycles (34=813^4=81); r,r3r,r^3 (single 44-cycles) have 11 (33 each); r2r^2 (two 22-cycles) has 22 (99); the two diagonal reflections s,r2ss,r^2s (fixing 22 vertices, swapping the other 22) have 33 cycles (2727 each); the two edge reflections rs,r3srs,r^3s (two 22-cycles, no fixed vertex) have 22 cycles (99 each). The sum is 81+3+3+9+27+27+9+9=16881+3+3+9+27+27+9+9=168, so the count is 168/8=21168/8=21.

Example
Coloring the square's vertices with 22 colors, and listing them all

With only 22 colors (black/white) and the full D4D_4, the same cycle counts give e:16e:16, r,r3:2r,r^3:2 each, r2:4r^2:4, s,r2s:8s,r^2s:8 each, rs,r3s:4rs,r^3s:4 each. The sum is 16+2+2+4+8+8+4+4=4816+2+2+4+8+8+4+4=48, so there are 48/8=648/8=6 colorings. These 66 can be listed directly: all-black, all-white, exactly 11 black vertex, exactly 33 black (complement), 22 black vertices adjacent, and 22 black vertices opposite every other arrangement of black and white is a rotation or reflection of one of these.

Example
A pentagon with 22 colors, rotations and reflections

For a regular pentagon, ∣D5∣=10|D_5|=10: ee has 55 cycles (25=322^5=32); the 44 nontrivial rotations are single 55-cycles since 55 is prime (22 each, total 88); each of the 55 reflections fixes 11 vertex and swaps the other 44 in 22 pairs, so 33 cycles (88 each, total 4040). The sum is 32+8+40=8032+8+40=80, giving 80/10=880/10=8 the same count as the rotation-only pentagon necklace from the Try It above, since here the mirror images happened not to introduce any new coincidences among 22-colorings of 55 positions.

Side note
Where it goes wrong

Using the wrong group changes the answer, even for the same figure and colors. Section 4's rotation-only group gives a DIFFERENT count from the full D4D_4 here once there are enough colors to tell mirror images apart: with 33 colors on the square, rotations alone (C4C_4) give (34+2⋅3+32)/4=(81+6+9)/4=24\big(3^4+2\cdot3+3^2\big)/4=(81+6+9)/4=24, not the 2121 found above with reflections included. Use CnC_n only when the figure genuinely cannot be flipped over (like beads glued to a fixed mount); use DnD_n when a mirror image counts as the same pattern.

Try it
Try it: coloring a triangle with 33 colors

How many ways to color a triangle's 33 vertices with 33 colors, up to D3D_3 (rotation and reflection)?

Show the answer

ee has 33 cycles (33=273^3=27); the 22 nontrivial rotations are single 33-cycles (33 each, total 66); the 33 reflections each fix 11 vertex and swap the other 22, so 22 cycles (99 each, total 2727). The sum is 27+6+27=6027+6+27=60, giving 60/6=1060/6=\mathbf{10}.

Why It Works

Let GG act on XX and fix x∈Xx\in X. First, e∈Stab⁡(x)e\in\operatorname{Stab}(x) since e⋅x=xe\cdot x=x by the action axiom. Closure: if g,h∈Stab⁡(x)g,h\in\operatorname{Stab}(x), then (gh)⋅x=g⋅(h⋅x)=g⋅x=x(gh)\cdot x=g\cdot(h\cdot x)=g\cdot x=x, using the compatibility axiom and then h⋅x=xh\cdot x=x, so gh∈Stab⁡(x)gh\in\operatorname{Stab}(x). Inverses: if g⋅x=xg\cdot x=x, apply g−1g^{-1} to both sides: g−1⋅(g⋅x)=g−1⋅xg^{-1}\cdot(g\cdot x)=g^{-1}\cdot x, and the left side is (g−1g)⋅x=e⋅x=x(g^{-1}g)\cdot x=e\cdot x=x by compatibility, so x=g−1⋅xx=g^{-1}\cdot x, i.e. g−1∈Stab⁡(x)g^{-1}\in\operatorname{Stab}(x). By the subgroup test (Topic 3), Stab⁡(x)≤G\operatorname{Stab}(x)\le G.

Define x∼yx\sim y iff y=g⋅xy=g\cdot x for some g∈Gg\in G. Reflexive: x=e⋅xx=e\cdot x. Symmetric: if y=g⋅xy=g\cdot x then applying g−1g^{-1} gives g−1⋅y=g−1⋅(g⋅x)=(g−1g)⋅x=e⋅x=xg^{-1}\cdot y=g^{-1}\cdot(g\cdot x)=(g^{-1}g)\cdot x=e\cdot x=x, so x=g−1⋅yx=g^{-1}\cdot y. Transitive: if y=g⋅xy=g\cdot x and z=h⋅yz=h\cdot y, then z=h⋅(g⋅x)=(hg)⋅xz=h\cdot(g\cdot x)=(hg)\cdot x. So ∼\sim is an equivalence relation, and its equivalence classes are exactly the orbits Orb⁡(x)={y:y∼x}\operatorname{Orb}(x)=\{y:y\sim x\} which therefore partition XX, the same way cosets partition a group (Topic 5).

Fix x∈Xx\in X and let H=Stab⁡(x)H=\operatorname{Stab}(x). Define φ ⁣:G/H→Orb⁡(x)\varphi\colon G/H\to\operatorname{Orb}(x) (the set of left cosets of HH) by φ(gH)=g⋅x\varphi(gH)=g\cdot x. This is well defined: if gH=g′HgH=g\prime H then g′=ghg\prime=gh for some h∈Hh\in H, so g′⋅x=(gh)⋅x=g⋅(h⋅x)=g⋅xg\prime\cdot x=(gh)\cdot x=g\cdot(h\cdot x)=g\cdot x. It is injective: if φ(gH)=φ(g′H)\varphi(gH)=\varphi(g\prime H), i.e. g⋅x=g′⋅xg\cdot x=g\prime\cdot x, apply g−1g^{-1} to get x=(g−1g′)⋅xx=(g^{-1}g\prime)\cdot x, so g−1g′∈Hg^{-1}g\prime\in H, which means g′∈gHg\prime\in gH, i.e. gH=g′HgH=g\prime H. It is surjective onto Orb⁡(x)\operatorname{Orb}(x) by definition of the orbit: every y∈Orb⁡(x)y\in\operatorname{Orb}(x) is g⋅xg\cdot x for some gg, so y=φ(gH)y=\varphi(gH). So φ\varphi is a bijection, giving ∣Orb⁡(x)∣=[G:H]|\operatorname{Orb}(x)|=[G:H], the number of cosets of HH. By Lagrange's theorem (Topic 5), [G:H]=∣G∣/∣H∣[G:H]=|G|/|H|, so ∣G∣=∣Orb⁡(x)∣⋅∣Stab⁡(x)∣|G|=|\operatorname{Orb}(x)|\cdot|\operatorname{Stab}(x)|.

Count the set of pairs P={(g,x)∈G×X:g⋅x=x}P=\{(g,x)\in G\times X:g\cdot x=x\} two ways. Grouping by gg: ∣P∣=∑g∈G∣Fix⁡(g)∣|P|=\sum_{g\in G}|\operatorname{Fix}(g)|. Grouping by xx: ∣P∣=∑x∈X∣Stab⁡(x)∣|P|=\sum_{x\in X}|\operatorname{Stab}(x)|. Now split the second sum by orbit. If x′∈Orb⁡(x)x\prime\in\operatorname{Orb}(x), say x′=g0⋅xx\prime=g_0\cdot x, then Stab⁡(x′)=g0Stab⁡(x)g0−1\operatorname{Stab}(x\prime)=g_0\operatorname{Stab}(x)g_0^{-1} (for any h∈Stab⁡(x)h\in\operatorname{Stab}(x), (g0hg0−1)⋅x′=(g0hg0−1g0)⋅x=(g0h)⋅x=g0⋅(h⋅x)=g0⋅x=x′(g_0hg_0^{-1})\cdot x\prime=(g_0hg_0^{-1}g_0)\cdot x=(g_0h)\cdot x=g_0\cdot(h\cdot x)=g_0\cdot x=x\prime, and conjugation is reversible), so every element of a single orbit has a stabilizer of the same size, ∣Stab⁡(x)∣|\operatorname{Stab}(x)|. By the orbit-stabilizer theorem, that common size is ∣G∣/∣Orb⁡(x)∣|G|/|\operatorname{Orb}(x)|. So for a single orbit OO, ∑x∈O∣Stab⁡(x)∣=∣O∣⋅∣G∣∣O∣=∣G∣\sum_{x\in O}|\operatorname{Stab}(x)|=|O|\cdot\frac{|G|}{|O|}=|G| each orbit contributes exactly ∣G∣|G|. Summing over all orbits, ∑x∈X∣Stab⁡(x)∣=∣G∣⋅(number of orbits)\sum_{x\in X}|\operatorname{Stab}(x)|=|G|\cdot(\text{number of orbits}). Combining both counts of ∣P∣|P|: ∑g∈G∣Fix⁡(g)∣=∣G∣⋅(number of orbits)\sum_{g\in G}|\operatorname{Fix}(g)|=|G|\cdot(\text{number of orbits}), which is Burnside's lemma after dividing by ∣G∣|G|.