6.3 Permutation Groups, Group Actions and the Class Equation
Every finite group is a group of permutations. Cycle notation, parity and conjugacy in $S_n$; group actions, the orbit–stabiliser theorem and Burnside's counting lemma; and the class equation, which forces every $p$-group to have a non-trivial centre and every group of order $p^2$ to be abelian.
Groups were first studied as groups of permutations: Lagrange, Ruffini and Galois looked at the ways of shuffling the roots of a polynomial, and Cauchy developed the cycle notation we still use. Abstract groups came later, and Cayley's theorem says that nothing was lost: every group is (isomorphic to) a group of permutations. So the symmetric groups $S_n$ are not just one family of examples among many — they are the universal examples, and the language of cycles, parity and conjugacy that we develop for them is used throughout algebra, combinatorics and geometry.
The second idea of the section turns this round. Instead of studying permutations for their own sake, we let a group act on a set — rotations acting on the faces of a cube, a group acting on itself by conjugation, a group acting on the cosets of a subgroup — and read off information from the orbits. Three counting formulas come out of this: the orbit–stabiliser theorem, Burnside's lemma (how many essentially different necklaces are there?) and the class equation (why does every group of order $p^2$ commute?). CSIR NET examines all of this directly: "how many elements of order $4$ in $S_6$?", "which of these are class equations?", "how many colourings up to rotation?", "is the centre of a group of order $p^3$ trivial?" are standard Part B and Part C questions, and the class equation is the engine behind the Sylow theorems of §6.4.
Notation (as in §6.1–6.2): $e$ is the identity, $o(g)$ the order of an element, $[G:H]$ the index, $Z(G)$ the centre, $H\trianglelefteq G$ a normal subgroup, $\mathbb{Z}_n$ the cyclic group of order $n$, $D_n$ the dihedral group of order $2n$ (the symmetries of a regular $n$-gon) and $Q_8=\{\pm1,\pm i,\pm j,\pm k\}$ the quaternion group.
Permutations and Cycle Notation
For a set $X$, $\operatorname{Sym}(X)$ is the group of all bijections $X\to X$ under composition; $S_n=\operatorname{Sym}(\{1,2,\dots,n\})$, a group of order $n!$. We compose right to left, like functions: $\sigma\tau$ means "first $\tau$, then $\sigma$", so $(\sigma\tau)(i)=\sigma(\tau(i))$.
- For distinct $a_1,\dots,a_k$ ($k\ge2$) the $k$-cycle $(a_1\ a_2\ \cdots\ a_k)$ is the permutation $a_1\mapsto a_2\mapsto\cdots\mapsto a_k\mapsto a_1$ that fixes every other point; $k$ is its length. A $2$-cycle is a transposition. The same cycle can be written starting at any of its entries: $(1\ 4\ 7)=(4\ 7\ 1)=(7\ 1\ 4)$.
- The support of $\sigma$ is $\{i:\sigma(i)\ne i\}$. Cycles are disjoint if their supports are disjoint.
- If $\sigma$ is a product of disjoint cycles of lengths $k_1\ge k_2\ge\cdots\ge k_r$, where we also count each fixed point as a cycle of length $1$ so that $k_1+\cdots+k_r=n$, the partition $(k_1,\dots,k_r)$ of $n$ is the cycle type of $\sigma$. We also write it as $1^{m_1}2^{m_2}\cdots n^{m_n}$, where $m_k$ is the number of $k$-cycles; e.g. $(1\ 3\ 5)(2\ 4)\in S_6$ has type $(3,2,1)=1^1\,2^1\,3^1$.
Proof. For $i,j\in\{1,\dots,n\}$ put $i\approx j$ if $j=\sigma^k(i)$ for some $k\in\mathbb{Z}$. This is an equivalence relation ($\sigma^0=e$; $j=\sigma^k(i)\Rightarrow i=\sigma^{-k}(j)$; $\sigma^l(\sigma^k(i))=\sigma^{k+l}(i)$); its classes are the orbits of $\langle\sigma\rangle$. Fix $i$. The points $i,\sigma(i),\sigma^2(i),\dots$ cannot all be distinct, so $\sigma^r(i)=\sigma^s(i)$ for some $r\lt s$, i.e. $\sigma^{s-r}(i)=i$. Let $k\ge1$ be the least exponent with $\sigma^k(i)=i$. Then $i,\sigma(i),\dots,\sigma^{k-1}(i)$ are distinct (an equality $\sigma^a(i)=\sigma^b(i)$ with $0\le a\lt b\lt k$ would give $\sigma^{b-a}(i)=i$ with $0\lt b-a\lt k$), and for any $m\in\mathbb{Z}$, writing $m=qk+r$ with $0\le r\lt k$ gives $\sigma^m(i)=\sigma^r(i)$. So the orbit of $i$ is exactly $\{i,\sigma(i),\dots,\sigma^{k-1}(i)\}$ and $\sigma$ acts on it as the cycle $\gamma_i=(i\ \sigma(i)\ \cdots\ \sigma^{k-1}(i))$. Taking one such cycle for each orbit with at least two points, $\sigma$ and the product of these cycles agree at every point, so they are equal.
Disjoint cycles $\gamma,\delta$ commute: a point in the support of $\gamma$ is moved by $\gamma$ to another point of that support, which $\delta$ fixes, so $\gamma\delta$ and $\delta\gamma$ both act there as $\gamma$; similarly on the support of $\delta$; elsewhere both fix the point. Uniqueness: if $\sigma=\delta_1\cdots\delta_r$ with disjoint cycles $\delta_j$, then on the support of $\delta_j$ the permutation $\sigma$ acts as $\delta_j$, so that support is an orbit of $\langle\sigma\rangle$ and $\delta_j$ is the cycle $\gamma_i$ of any of its points. ∎
(a) A $k$-cycle has order $k$. (b) If $\sigma$ is a product of disjoint cycles of lengths $k_1,\dots,k_r$, then $o(\sigma)=\operatorname{lcm}(k_1,\dots,k_r)$. (c) If $\gamma$ is a $k$-cycle and $j\in\mathbb{Z}$, then $\gamma^j$ is a product of $d=\gcd(j,k)$ disjoint cycles, each of length $k/d$. In particular $\gamma^j$ is again a $k$-cycle iff $\gcd(j,k)=1$.
Proof. (a) Label the cycle $\gamma=(a_0\ a_1\ \cdots\ a_{k-1})$ with indices in $\mathbb{Z}_k$, so $\gamma(a_i)=a_{i+1}$ and $\gamma^j(a_i)=a_{i+j}$. Hence $\gamma^j=e$ iff $j\equiv0\pmod k$. (b) Write $\sigma=\gamma_1\cdots\gamma_r$. Because disjoint cycles commute, $\sigma^m=\gamma_1^m\cdots\gamma_r^m$, and the factors $\gamma_i^m$ move points only inside the (disjoint) supports of the $\gamma_i$. So $\sigma^m=e$ iff $\gamma_i^m=e$ for every $i$ iff $k_i\mid m$ for every $i$, by (a); the least such $m\ge1$ is $\operatorname{lcm}(k_1,\dots,k_r)$. (c) On the labels, $\gamma^j$ is the translation $i\mapsto i+j$ of $\mathbb{Z}_k$. Its orbits are the cosets of the subgroup $\langle j\rangle$ of $\mathbb{Z}_k$, which has order $k/\gcd(j,k)$ (§6.1); there are $\gcd(j,k)$ cosets, each of size $k/\gcd(j,k)$. ∎
Proof. Write down a "template" of brackets of the prescribed lengths — $m_n$ brackets of length $n$, …, $m_1$ brackets of length $1$, in a fixed order — and fill the $n$ slots with $1,\dots,n$ in any order: $n!$ fillings, each giving a permutation of the right type, and every such permutation arises. A permutation arises from exactly $z$ fillings: each $k$-cycle can be started at any of its $k$ entries ($k^{m_k}$ choices for the $k$-cycles), and the $m_k$ cycles of equal length can be put into the $m_k$ brackets of that length in any order ($m_k!$ choices); different choices give different fillings, and these are the only fillings producing the same permutation, by the uniqueness in Theorem 6.32. ∎
Transpositions, Parity and the Alternating Group
Let $n\ge2$.
- Every $\sigma\in S_n$ is a product of transpositions; explicitly $$(a_1\ a_2\ \cdots\ a_k)=(a_1\ a_k)\cdots(a_1\ a_3)(a_1\ a_2),$$ a product of $k-1$ transpositions.
- If $\tau=(a\ b)$ is a transposition then $c(\sigma\tau)=c(\sigma)+1$ when $a,b$ lie in the same cycle of $\sigma$, and $c(\sigma\tau)=c(\sigma)-1$ when they lie in different cycles.
- If $\sigma=\tau_1\tau_2\cdots\tau_m$ with transpositions $\tau_i$, then $(-1)^m=\operatorname{sgn}(\sigma)$. Hence no permutation is both even and odd, and $\operatorname{sgn}:S_n\to\{1,-1\}$ is a surjective homomorphism.
- A $k$-cycle has sign $(-1)^{k-1}$. A permutation is even iff it has an even number of cycles of even length.
Proof. (1) Read the product from the right. $a_1$ goes to $a_2$ under $(a_1\ a_2)$ and no later factor moves $a_2$. For $2\le i\le k-1$, $a_i$ is fixed by the factors before $(a_1\ a_i)$, which sends it to $a_1$, and then $(a_1\ a_{i+1})$ sends $a_1$ to $a_{i+1}$, which no later factor moves. Finally $a_k$ is fixed until the last factor $(a_1\ a_k)$ sends it to $a_1$. Points outside $\{a_1,\dots,a_k\}$ are fixed. Combine with Theorem 6.32 ($e=(1\ 2)(1\ 2)$).
(2) Only the cycles of $\sigma$ through $a$ and $b$ are affected. If they are in one cycle, write it as $(a\ x_1\ \cdots\ x_r\ b\ y_1\ \cdots\ y_s)$ ($r,s\ge0$). Then $\sigma\tau$ sends $a\mapsto\sigma(b)=y_1\mapsto\cdots\mapsto y_s\mapsto a$ and $b\mapsto\sigma(a)=x_1\mapsto\cdots\mapsto x_r\mapsto b$: the cycle splits into $(a\ y_1\ \cdots\ y_s)(b\ x_1\ \cdots\ x_r)$, one more cycle. If they are in different cycles $(a\ x_1\ \cdots\ x_r)(b\ y_1\ \cdots\ y_s)$, then $\sigma\tau$ sends $a\mapsto y_1\mapsto\cdots\mapsto y_s\mapsto b$ and then $b\mapsto x_1\mapsto\cdots\mapsto x_r\mapsto a$: the two cycles merge into one.
(3) Build $\sigma$ from $e$ by multiplying on the right by $\tau_1,\tau_2,\dots,\tau_m$ in turn. We start with $c(e)=n$ and by (2) each step changes $c$ by $\pm1$, so $c(\sigma)\equiv n-m\pmod 2$, i.e. $(-1)^m=(-1)^{n-c(\sigma)}=\operatorname{sgn}(\sigma)$. Thus the parity of $m$ depends only on $\sigma$. If $\sigma$ is a product of $m$ transpositions and $\rho$ of $l$, then $\sigma\rho$ is a product of $m+l$, so $\operatorname{sgn}(\sigma\rho)=(-1)^{m+l}=\operatorname{sgn}(\sigma)\operatorname{sgn}(\rho)$; and $\operatorname{sgn}(1\ 2)=-1$, so sgn is onto. (4) follows from (1) and multiplicativity: a cycle of length $k$ contributes $(-1)^{k-1}$, which is $-1$ exactly when $k$ is even. ∎
Proof. $A_n$ is the kernel of a homomorphism, hence normal, and by the first isomorphism theorem (§6.2) $S_n/A_n\cong\operatorname{sgn}(S_n)=\{\pm1\}$, so the index is $2$. A $3$-cycle is even ($(a\ b\ c)=(a\ c)(a\ b)$), so the $3$-cycles generate a subgroup of $A_n$. Conversely an even permutation is a product of an even number of transpositions; group them in pairs. A pair is either $(a\ b)(a\ b)=e$, or $(a\ b)(a\ c)=(a\ c\ b)$ (one common point), or $(a\ b)(c\ d)=(a\ c\ b)(a\ c\ d)$ (disjoint; multiply out to check). So every even permutation is a product of $3$-cycles. ∎
Conjugacy in $S_n$ and $A_n$
Proof. (a) Let $\gamma=(a_1\ \cdots\ a_k)$. For a point $\tau(a_i)$: $\tau\gamma\tau^{-1}(\tau(a_i))=\tau(\gamma(a_i))=\tau(a_{i+1})$ (indices mod $k$). For a point $x$ not of the form $\tau(a_i)$, $\tau^{-1}(x)\notin\{a_1,\dots,a_k\}$ is fixed by $\gamma$, so $\tau\gamma\tau^{-1}(x)=x$. For a product of cycles use $\tau(\gamma_1\cdots\gamma_r)\tau^{-1}=(\tau\gamma_1\tau^{-1})\cdots(\tau\gamma_r\tau^{-1})$; disjoint cycles stay disjoint because $\tau$ is injective.
(b) By (a), conjugation preserves cycle lengths. Conversely, if $\sigma,\sigma'$ have the same type, write their cycle decompositions — including $1$-cycles — one above the other with cycles of equal length aligned, and let $\tau$ send each symbol of the top row to the symbol below it. Each of $1,\dots,n$ occurs exactly once in each row, so $\tau$ is a bijection, and by (a) $\tau\sigma\tau^{-1}=\sigma'$. (c) Cycle types are exactly the partitions of $n$, and each partition occurs. ∎
Proof. (a) is Theorem 6.35(1). (b) For distinct $a,b\ne1$, $(a\ b)=(1\ a)(1\ b)(1\ a)$ by Theorem 6.37(a) (conjugating $(1\ b)$ by $(1\ a)$ replaces $1$ by $a$). (c) Conjugating $(1\ k)$ by $(k\ \ k{+}1)$ gives $(1\ \ k{+}1)$, so by induction all $(1\ k)$ lie in the subgroup generated by the adjacent transpositions; apply (b). (d) With $\rho=(1\ 2\ \cdots\ n)$, Theorem 6.37(a) gives $\rho^{k}(1\ 2)\rho^{-k}=(\rho^k(1)\ \rho^k(2))=(k{+}1\ \ k{+}2)$ for $0\le k\le n-2$; apply (c). ∎
Proof. In any group, $gag^{-1}=hah^{-1}$ $\iff$ $h^{-1}g\,a=a\,h^{-1}g$ $\iff$ $h^{-1}g\in C_G(a)$ $\iff$ $gC_G(a)=hC_G(a)$. So $gC_G(a)\mapsto gag^{-1}$ is a well-defined bijection from the left cosets of $C_G(a)$ onto $\operatorname{cl}(a)$, and $|\operatorname{cl}(a)|=[G:C_G(a)]$, a divisor of $|G|$ by Lagrange's theorem (§6.1). In $S_n$ the class of $\sigma$ is the set of all permutations of its type (Theorem 6.37(b)), which has $n!/z$ elements (Theorem 6.34); hence $|C_{S_n}(\sigma)|=n!/(n!/z)=z$. ∎
Proof. By Theorem 6.39 applied in $A_n$, $|\operatorname{cl}_{A_n}(\sigma)|=[A_n:C_{A_n}(\sigma)]$, and $C_{A_n}(\sigma)=C_{S_n}(\sigma)\cap A_n$ has index $1$ or $2$ in $C_{S_n}(\sigma)$ (it is the kernel of sgn restricted to $C_{S_n}(\sigma)$). If $C_{S_n}(\sigma)$ contains an odd permutation, the index is $2$ and $|\operatorname{cl}_{A_n}(\sigma)|=\dfrac{n!/2}{z/2}=\dfrac{n!}{z}$: the whole $S_n$-class. If $C_{S_n}(\sigma)\subseteq A_n$, then $|\operatorname{cl}_{A_n}(\sigma)|=\dfrac{n!/2}{z}$, half the $S_n$-class; and for an odd $\rho$ the class of $\rho\sigma\rho^{-1}$ in $A_n$ is the other half (the cosets $A_n$ and $\rho A_n$ conjugate $\sigma$ onto the two halves).
Now the criterion. If $\sigma$ has a cycle $\gamma$ of even length, $\gamma$ commutes with $\sigma$ and is odd. If $\sigma$ has two cycles of the same odd length $k$, say $(a_1\ \cdots\ a_k)$ and $(b_1\ \cdots\ b_k)$ (possibly two fixed points, $k=1$), then $\pi=(a_1\ b_1)(a_2\ b_2)\cdots(a_k\ b_k)$ swaps them, so $\pi\sigma\pi^{-1}=\sigma$ by Theorem 6.37(a), and $\pi$ is odd since $k$ is odd. Conversely, suppose the cycle lengths are distinct and odd, and $\rho\in C_{S_n}(\sigma)$. Then $\rho\sigma\rho^{-1}=\sigma$ is obtained by relabelling each cycle by $\rho$; as the lengths are distinct, $\rho$ maps each cycle $\gamma=(a_1\ \cdots\ a_k)$ onto itself, with $(\rho(a_1)\ \cdots\ \rho(a_k))=\gamma$, so $\rho$ acts on its support as a power of $\gamma$. Thus $\rho$ is a product of powers of the cycles of $\sigma$, all of odd length, hence even. ∎
| type | representative | class size $24/z$ | $|C(\sigma)|=z$ |
|---|---|---|---|
| $1^4$ | $e$ | $1$ | $24$ |
| $2\,1^2$ | $(1\ 2)$ | $6$ | $2\cdot2!=4$ |
| $2^2$ | $(1\ 2)(3\ 4)$ | $3$ | $2^2\cdot2!=8$ |
| $3\,1$ | $(1\ 2\ 3)$ | $8$ | $3$ |
| $4$ | $(1\ 2\ 3\ 4)$ | $6$ | $4$ |
Group Actions: Cayley, Orbit–Stabiliser and Burnside
An action of a group $G$ on a set $X$ is a map $G\times X\to X$, $(g,x)\mapsto g\cdot x$, such that $e\cdot x=x$ and $g\cdot(h\cdot x)=(gh)\cdot x$ for all $g,h\in G$, $x\in X$. For $x\in X$ and $g\in G$:
- the orbit of $x$ is $G\cdot x=\{g\cdot x:g\in G\}$ and the stabiliser of $x$ is $G_x=\{g\in G:g\cdot x=x\}$;
- the fixed set of $g$ is $\operatorname{Fix}(g)=\{x\in X:g\cdot x=x\}$, and $X^G=\{x: g\cdot x=x\text{ for all }g\}$ is the set of fixed points of the action;
- the action is transitive if there is only one orbit, and faithful if only $e$ fixes every point.
Proof. $\lambda_g\lambda_h(x)=g\cdot(h\cdot x)=(gh)\cdot x=\lambda_{gh}(x)$, and $\lambda_e=\mathrm{id}$, so $\lambda_g\lambda_{g^{-1}}=\lambda_{g^{-1}}\lambda_g=\mathrm{id}$: each $\lambda_g$ is a bijection and $\lambda$ is a homomorphism. Its kernel consists of the $g$ with $g\cdot x=x$ for all $x$. The converse is a direct check of the two axioms, and faithful means trivial kernel. ∎
Proof. $G$ acts on the set $G$ by left multiplication, $g\cdot x=gx$: indeed $ex=x$ and $g(hx)=(gh)x$. The action is faithful, since $gx=x$ for all $x$ (even for $x=e$ alone) forces $g=e$. By Theorem 6.41, $\lambda:G\to\operatorname{Sym}(G)$ is an injective homomorphism, so $G\cong\lambda(G)\le\operatorname{Sym}(G)$. If $|G|=n$, numbering the elements of $G$ as $1,\dots,n$ identifies $\operatorname{Sym}(G)$ with $S_n$. ∎
The embedding $\lambda$ is the left regular representation. For $g\ne e$, $\lambda_g$ has no fixed point and all its cycles have length $o(g)$ (the cycle through $x$ is $x,gx,g^2x,\dots$), so $\lambda_g$ is a product of $n/o(g)$ disjoint $o(g)$-cycles. For $\mathbb{Z}_4=\{0,1,2,3\}$ the generator $1$ becomes the $4$-cycle $(0\ 1\ 2\ 3)$; for the Klein group $V_4=\{e,a,b,ab\}$ the three non-identity elements become the three double transpositions of $S_4$.
Proof. (a) $x\sim y\iff y=g\cdot x$ for some $g$ is an equivalence relation: $x=e\cdot x$; $y=g\cdot x\Rightarrow x=g^{-1}\cdot y$; $y=g\cdot x$, $z=h\cdot y\Rightarrow z=(hg)\cdot x$. Its classes are the orbits. (b) $e\in G_x$, and if $g,h\in G_x$ then $(gh)\cdot x=g\cdot(h\cdot x)=x$ and $g^{-1}\cdot x=g^{-1}\cdot(g\cdot x)=x$. Next, $g\cdot x=h\cdot x$ $\iff$ $(h^{-1}g)\cdot x=x$ $\iff$ $h^{-1}g\in G_x$ $\iff$ $gG_x=hG_x$; read from left to right this shows the map is well defined, and from right to left that it is injective. It is onto the orbit by definition. (c) $h\in G_{g\cdot x}$ $\iff$ $hg\cdot x=g\cdot x$ $\iff$ $g^{-1}hg\in G_x$ $\iff$ $h\in gG_xg^{-1}$. ∎
Two actions of $G$ on itself are used constantly. Left multiplication (Cayley) is transitive with trivial stabilisers. Conjugation, $g\cdot x=gxg^{-1}$, has the conjugacy classes as orbits and the centralisers as stabilisers, so Theorem 6.43 contains Theorem 6.39. A third: $G$ acts on the set $G/H$ of left cosets of a subgroup $H$ by $g\cdot xH=gxH$, transitively, with $G_{xH}=xHx^{-1}$.
Proof. Apply Theorem 6.41 to the action on the $n$ cosets: the kernel is $\bigcap_x G_{xH}=\bigcap_x xHx^{-1}\subseteq H$ (take $x=e$), and $G/K$ is isomorphic to a subgroup of $S_n$, so $[G:K]\mid n!$ by Lagrange. (a) If $K=\{e\}$ then $|G|=[G:K]$ divides $n!$. (b) Let $[G:H]=p$. Then $[G:K]=[G:H][H:K]=p\,[H:K]$ divides $p!$, so $[H:K]$ divides $(p-1)!$. But $[H:K]$ divides $|G|$, all of whose prime factors are $\ge p$, while all prime factors of $(p-1)!$ are $\lt p$. Hence $[H:K]=1$, $H=K$ is normal. ∎
Proof. Count the set $F=\{(g,x)\in G\times X: g\cdot x=x\}$ in two ways. Summing over $g$ gives $|F|=\sum_g|\operatorname{Fix}(g)|$. Summing over $x$ gives $|F|=\sum_x|G_x|=\sum_x\dfrac{|G|}{|G\cdot x|}$ by Theorem 6.43. Group the last sum by orbits: an orbit $\mathcal{O}$ contributes $|\mathcal{O}|\cdot\dfrac{|G|}{|\mathcal{O}|}=|G|$. Hence $|F|=|G|\cdot\#\{\text{orbits}\}$. ∎
- Identify the symmetry group $G$ and the set it permutes (beads, faces, edges, vertices). Let $X$ be the set of all colourings with $k$ colours, $|X|=k^{(\text{number of positions})}$.
- For each $g\in G$ find the number $c(g)$ of cycles of $g$ on the positions (fixed positions count as cycles). A colouring is fixed by $g$ iff it is constant on each cycle, so $|\operatorname{Fix}(g)|=k^{c(g)}$.
- Conjugate elements have the same cycle structure, so work class by class: $\#\text{orbits}=\dfrac1{|G|}\sum_{\text{classes}}(\text{class size})\cdot k^{c(g)}$.
- Check: the answer must be an integer, and for $k=1$ it must be $1$.
The Class Equation and $p$-Groups
Proof. The conjugacy classes partition $G$ (they are the orbits of the conjugation action, Theorem 6.43). A class $\operatorname{cl}(a)$ is the single point $\{a\}$ iff $gag^{-1}=a$ for all $g$, i.e. iff $a\in Z(G)$; these one-point classes together contribute $|Z(G)|$. Every other class has $|\operatorname{cl}(a_i)|=[G:C_G(a_i)]\gt1$ elements (Theorem 6.39), a divisor of $|G|$. ∎
Proof. (a) $X$ is the disjoint union of its orbits. An orbit has size $[P:P_x]$, a power of $p$; it has size $1$ exactly when its point is fixed by all of $P$. So $|X|=|X^P|+S$, where $S$ is a sum of positive powers of $p$, and $|X|\equiv|X^P|\pmod p$. (b) Let $P$ act on $X=P$ by conjugation; the fixed points are the elements of $Z(P)$. By (a), $|Z(P)|\equiv|P|\equiv0\pmod p$, and $|Z(P)|\ge1$ because $e\in Z(P)$. Hence $|Z(P)|\ge p$. (In terms of the class equation: every term $[P:C_P(a_i)]$ is a positive power of $p$, so $p$ divides $|P|-\sum_i[P:C_P(a_i)]=|Z(P)|$.) ∎
Proof. Write $Z=Z(G)$ and $G/Z=\langle gZ\rangle$. Every element of $G$ lies in some coset $g^iZ$, so it has the form $g^iz$ with $z\in Z$. For $x=g^iz$ and $y=g^jw$ ($z,w\in Z$): $xy=g^ig^jzw=g^{i+j}zw$ and $yx=g^jg^iwz=g^{i+j}zw$, using that $z,w$ commute with everything. So $G$ is abelian, $Z=G$, and $G/Z$ is trivial. A group of prime order is cyclic and non-trivial, so it cannot be $G/Z(G)$. ∎
Proof. By Theorem 6.47, $|Z(G)|\in\{p,p^2\}$. If $|Z(G)|=p$, then $G/Z(G)$ has order $p$, hence is cyclic, and Theorem 6.48 gives $Z(G)=G$ — a contradiction. So $Z(G)=G$: $G$ is abelian. If $G$ has an element of order $p^2$ it is cyclic, $G\cong\mathbb{Z}_{p^2}$. Otherwise every $a\ne e$ has order $p$. Choose $a\ne e$ and $b\notin\langle a\rangle$. Then $\langle a\rangle\cap\langle b\rangle$ is a proper subgroup of the group $\langle b\rangle$ of prime order, so it is $\{e\}$. The map $\phi:\mathbb{Z}_p\times\mathbb{Z}_p\to G$, $(i,j)\mapsto a^ib^j$, is a homomorphism because $G$ is abelian; it is injective because $a^ib^j=e$ gives $a^i=b^{-j}\in\langle a\rangle\cap\langle b\rangle=\{e\}$, so $p\mid i$ and $p\mid j$; and both groups have $p^2$ elements, so $\phi$ is an isomorphism. Finally $\mathbb{Z}_p\times\mathbb{Z}_p$ has no element of order $p^2$, so it is not cyclic. ∎
Proof. Induction on $n$; the cases $n\le1$ are clear. Let $n\ge2$ and $1\le k\le n$. By Theorem 6.47, $Z(G)\ne\{e\}$; pick $z\ne e$ in $Z(G)$, of order $p^s$ with $s\ge1$; then $c=z^{p^{s-1}}$ is central of order $p$, and $N=\langle c\rangle$ is normal (every subgroup of the centre is normal). The quotient $G/N$ has order $p^{n-1}$, so by induction it has a normal subgroup $\bar M$ of order $p^{k-1}$. By the correspondence theorem (§6.2), $\bar M=M/N$ for a normal subgroup $M$ of $G$ containing $N$, and $|M|=|N|\,|\bar M|=p^k$. ∎
There is no general converse of Lagrange's theorem — $A_4$, of order $12$, has no subgroup of order $6$ (§6.4) — but Theorem 6.50 is a converse for $p$-groups, and in §6.4 the Sylow theorems extend it to the prime-power divisors of any finite group.
- Conventions change products. Right to left, $(1\ 2\ 3)(2\ 3\ 4)=(1\ 2)(3\ 4)$; left to right the same symbols give $(1\ 3)(2\ 4)$. Fix the convention before computing (and in an exam, check which one the options use: both answers often appear).
- The lcm rule needs disjoint cycles. $(1\ 2)(2\ 3)=(1\ 2\ 3)$ has order $3$, not $\operatorname{lcm}(2,2)=2$. Always decompose into disjoint cycles first.
- A $k$-cycle has sign $(-1)^{k-1}$. Even-length cycles are odd permutations: a $4$-cycle is odd, a $3$-cycle and a $5$-cycle are even.
- Divisibility does not give elements. $6$ divides $|A_6|=360$ but $A_6$ has no element of order $6$; $4$ divides $|A_5|=60$ but $A_5$ has no element of order $4$.
- Same cycle type is not enough in $A_n$. $(1\ 2\ 3\ 4\ 5)$ and $(1\ 3\ 5\ 2\ 4)$ are conjugate in $S_5$ but not in $A_5$; in $A_4$, $(1\ 2\ 3)$ and $(1\ 3\ 2)$ are not conjugate.
- Splitting needs distinct odd parts, fixed points included. In $A_5$ the $3$-cycles do not split (type $(3,1,1)$ repeats the part $1$), while in $A_4$ they do (type $(3,1)$).
- Orbits can have different sizes. Only their sizes divide $|G|$. Stabilisers of points in one orbit are conjugate, not equal: in $S_3$ acting on $\{1,2,3\}$ the stabilisers are the three different subgroups of order $2$.
- Burnside averages fixed points. The number of $6$-bead $2$-colour necklaces is not $2^6/6$ (not even an integer) but $14$ — colourings with symmetry have orbits smaller than $|G|$.
- Non-trivial centre does not mean abelian. Every $p$-group has $Z(G)\ne\{e\}$, but $D_4$ and $Q_8$ (order $2^3$) are non-abelian; order $p^2$ is the largest prime-power order that forces commutativity.
- $G/Z(G)$ is never cyclic of order $\gt1$. So $[G:Z(G)]\ne p$; for a non-abelian group of order $p^3$, $|Z(G)|=p$ and $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$.
- Divisor sums are necessary, not sufficient. $6=1+1+1+3$ and $9=1+1+1+3+3$ pass the divisibility test but are not class equations.
- Centres of symmetric groups. $Z(S_n)=\{e\}$ for $n\ge3$, but $S_2\cong\mathbb{Z}_2$ is abelian; $Z(A_n)=\{e\}$ for $n\ge4$, but $A_3\cong\mathbb{Z}_3$.
Exercises
- 1 Write $\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\3&6&5&8&1&2&4&7\end{pmatrix}$ as a product of disjoint cycles; find $o(\sigma)$, $\sigma^{-1}$ and $\sigma^{100}$.
- 2 Compute $(1\ 2\ 3)(2\ 3\ 4)$ and $(2\ 3\ 4)(1\ 2\ 3)$ in $S_4$.
- 3 List all orders of elements of $S_6$.
- 4 Find the least $n$ such that $S_n$ contains an element of order $12$; of order $35$; of order $42$.
- 5 How many elements of order $3$ are there in $S_6$?
- 6 How many $5$-cycles are there in $S_7$?
- 7 Let $\gamma=(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8)$. Write $\gamma^2$, $\gamma^3$ and $\gamma^4$ in cycle notation.
- 8 Prove that an element of prime order $p$ in $S_n$ is a product of disjoint $p$-cycles, and deduce that $S_p$ has exactly $(p-1)!$ elements of order $p$.
- 9 Prove that a permutation $\sigma$ is a product of two disjoint cycles of the same length $k$ whenever $\sigma=\gamma^2$ for a $2k$-cycle $\gamma$, and decide whether every product of two disjoint $3$-cycles is the square of some element of $S_6$.
- 1 Decide the parity of $(1\ 2\ 3\ 4\ 5\ 6)$, of $(1\ 2)(3\ 4\ 5)(6\ 7\ 8\ 9)$, and of the permutation $\sigma$ in I.1.
- 2 Show that for $n\ge3$, $A_n$ is generated by the $3$-cycles $(1\ 2\ k)$, $3\le k\le n$.
- 3 Show that $\sigma=(1\ 2\ 3)(4\ 5\ 6)$ and $\sigma'=(1\ 4\ 2)(3\ 6\ 5)$ are conjugate in $S_6$ and in $A_6$, and find conjugating elements.
- 4 How many conjugacy classes have $S_5$, $S_6$ and $A_5$?
- 5 Find $|C_{S_7}(\sigma)|$ for $\sigma=(1\ 2\ 3)(4\ 5)$ and describe $C_{S_7}(\sigma)$ explicitly.
- 6 Show that $Z(S_n)=\{e\}$ for $n\ge3$.
- 7 Let $n\ge2$ and let $\phi:S_n\to A$ be a homomorphism into an abelian group. Show that $\phi$ is constant on transpositions, and deduce that the only homomorphisms $S_n\to\mathbb{C}^{\times}$ are the trivial one and sgn.
- 8 Which conjugacy classes of $S_6$ split in $A_6$? Write the class equation of $A_6$.
- 9 Prove that for $n\ge3$ the $3$-cycles are all conjugate in $A_n$ when $n\ge5$, but not when $n=3$ or $4$.
- 1 $S_4$ acts on the set of $2$-element subsets of $\{1,2,3,4\}$. Find the orbit and the stabiliser of $\{1,2\}$ and check the orbit–stabiliser theorem.
- 2 Find the order of the rotation group of a regular tetrahedron and of a regular dodecahedron (12 pentagonal faces) by orbit–stabiliser.
- 3 How many different necklaces of $5$ beads in $3$ colours are there up to rotation? Up to rotation and reflection?
- 4 In how many ways can the four edges of a square be coloured with $2$ colours, up to the symmetries of the square?
- 5 Let $G$ act transitively on a finite set $X$ with $|X|\ge2$. Prove that some $g\in G$ has no fixed point.
- 6 Let $H\le G$ with $[G:H]=n$. Show that $H$ contains a normal subgroup $N$ of $G$ with $[G:N]$ dividing $n!$. Deduce that a group of order $36$ with a subgroup of order $9$ is not simple.
- 7 Prove that a group of order $2m$ with $m$ odd has a normal subgroup of index $2$. (Hint: an element of order $2$ acts in the left regular representation as a product of $m$ transpositions.)
- 8 (a) A group of order $25$ acts on a set with $17$ elements. Show that at least two points are fixed by the whole group. (b) Show that a group of order $15$ can act on a set with $17$ elements without any fixed point.
- 1 Write the class equations of $S_3$, $Q_8$ and $D_6$ (order $12$).
- 2 Write the class equation of $S_5$.
- 3 Show that every group of order $25$ is abelian, and list them up to isomorphism.
- 4 Let $G$ be a non-abelian group of order $p^3$. Show that $|Z(G)|=p$ and $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$, and that $G$ has exactly $p^2+p-1$ conjugacy classes. How many classes has a non-abelian group of order $27$?
- 5 Let $G$ be a $p$-group and $N\ne\{e\}$ a normal subgroup. Prove that $N\cap Z(G)\ne\{e\}$.
- 6 Let $G$ be a finite non-abelian group. Prove that the probability that two independently and uniformly chosen elements commute is at most $5/8$, and that $D_4$ attains this bound.
- 7 Show that a group of order $p^n$ ($n\ge1$) has a subgroup of index $p$, and that every such subgroup is normal.
E1. CSIR Part B GATE MA The number of elements of order $4$ in the symmetric group $S_6$ is (A) $90$; (B) $120$; (C) $180$; (D) $270$.
E2. CSIR Part B The number of ways of colouring the six faces of a cube, each face red or blue, where two colourings are regarded as the same if a rotation of the cube carries one to the other, is (A) $8$; (B) $10$; (C) $12$; (D) $64$.
E3. CSIR Part B A group of order $81$ acts on a set with $23$ elements. Which of the following could be the number of points fixed by the whole group? (A) $0$; (B) $1$; (C) $2$; (D) $3$.
E4. CSIR Part C Which of the following statements are true? (One or more options may be correct.) (A) $S_7$ has an element of order $12$. (B) $A_7$ has an element of order $10$. (C) $(1\ 2\ 3)(4\ 5\ 6\ 7)$ and $(1\ 2\ 3\ 4)(5\ 6\ 7)$ are conjugate in $S_7$. (D) $S_7$ has exactly $720$ elements of order $7$.
E5. CSIR Part C GATE MA Let $G$ be a non-abelian group of order $p^3$, $p$ prime. Which of the following are true? (A) $|Z(G)|=p$. (B) $G$ has exactly $p^2+p-1$ conjugacy classes. (C) $G/Z(G)$ is cyclic. (D) Every subgroup of $G$ of order $p$ is normal in $G$.
E6. CSIR Part C A finite group $G$ acts transitively on a finite set $X$ with $|X|=n\ge2$. Which of the following are necessarily true? (A) $n$ divides $|G|$. (B) Some element of $G$ fixes no point of $X$. (C) The stabilisers of any two points are conjugate subgroups. (D) If $G$ is abelian, every stabiliser is trivial.
Suggested plan — 3 lectures × 60 min.
- Permutations. Fix the right-to-left convention on the board first. Theorems 6.32–6.34 with Example 1 done live; project Interactive 1 on the Example-1 permutation and on the out-shuffle. Example 2 (Landau-type questions) as a class race. Then parity: Theorem 6.35 via split/merge — press "× transposition" a few times and let students predict split or merge — and Theorem 6.36, Example 3.
- Conjugacy and actions. Theorem 6.37 by "relabelling"; Example 4(b) as a two-minute exercise; class sizes (Theorem 6.39) and the $A_n$ splitting rule (Theorem 6.40) with the rule cards for $S_4,A_4,S_5,A_5$. Define actions; Cayley; orbit–stabiliser; Example 5 (the cube is very concrete — bring one).
- Burnside and $p$-groups. Burnside's lemma with Interactive 2 ($n=6$, $k=2$, rotations, then dihedral); Example 6. Class equation, Theorems 6.47–6.50, and Example 7 as a "true or false" round. Finish with Exam-corner E3 and E5.
Discussion questions. (1) Why must conjugate permutations have the same cycle type, and why is the converse true in $S_n$ but not in $A_n$? (2) Burnside's lemma counts orbits by averaging fixed points; why would counting "colourings divided by $|G|$" overcount symmetric colourings? (3) The class equation of a $p$-group forces a non-trivial centre; what goes wrong for $|G|=6$?
Misconceptions to watch for. Mixing composition conventions; applying the lcm rule to non-disjoint cycles; "a $4$-cycle is even because $4$ is even"; "same cycle type ⇒ conjugate in $A_n$"; dividing the number of colourings by $|G|$; believing that $p$-groups are abelian; accepting any list of divisors as a class equation.
Suggested homework. I(1, 4, 5, 7, 8), II(1, 3, 4, 6, 8), III(1, 3, 4, 5, 7), IV(1, 3, 4, 6); Exam corner E1, E4, E6.
Research question. A "perfect" riffle shuffle cuts a deck exactly in half and interleaves the halves card by card. How many perfect shuffles bring a deck back to its original order — and why does the answer for $52$ cards jump from $8$ to $52$ when the top card is allowed to move?
Why it matters. Stage magicians and casino dealers have used perfect shuffles for centuries, and the mathematics of shuffling (how many ordinary riffle shuffles make a deck random?) became a research field in probability in the 1980s and 1990s. The same permutations — "perfect shuffles" of $2n$ positions — are used to route data in parallel computers (the shuffle–exchange network) and in fast Fourier transform algorithms.
What to do.
- Number the positions $0,1,\dots,2n-1$. Write the out-shuffle (top card stays on top) and the in-shuffle (top card goes to second place) as permutations of the positions, and find their cycle decompositions for $2n=8,10,52$ by hand or with a short program.
- Compute their orders with Theorem 6.33 and tabulate them for $2n\le60$.
- Show that the out-shuffle fixes positions $0$ and $2n-1$ and acts on the other positions as $x\mapsto2x\pmod{2n-1}$; deduce that its order is the multiplicative order of $2$ modulo $2n-1$ (§5.3). Find the corresponding formula for the in-shuffle.
- Decide the parity of the out-shuffle for several deck sizes and look for a pattern.
Tools: Python (a permutation is a list; compose and count cycles); the multiplicative-order material of §5.3.
Hand in: A one-page table of orders for $2n\le60$, the two order formulas with a proof for the out-shuffle, and one surprising observation.
Going further. A magician can move the top card to any position $k$ by a sequence of in- and out-shuffles read off from the binary digits of $k$. Find the rule, and read about which permutations of a deck can be generated by the two perfect shuffles together.
🧪 Self-check quiz
Q1. The order of $(1\ 2\ 3)(4\ 5)(6\ 7\ 8\ 9)$ in $S_9$ is
Q2. Which of these permutations is even?
Q3. Two permutations in $S_n$ are conjugate in $S_n$ if and only if
Q4. The number of necklaces with $4$ beads, each black or white, counted up to rotation, is
Q5. Let $p$ be a prime. Every group of order $p^2$ is