Group Theory & Abstract Algebra¶
This is the most abstract stretch of the course, and abstraction is where marks leak away — not because the ideas are hard, but because vague writing gets capped at two points. The good news: nearly every question is answered by one of three things — the axioms, Lagrange's theorem, or cycle notation. If you can recognise which of the three a problem wants, you're most of the way there.
A quick orientation before the formalities: a group is the mathematical distillation of "a set of moves you can undo and combine" — rotations of a shape, shuffles of a deck, additions on a clock. The axioms below are just the minimum rules that make "combine and undo" behave sensibly.
The group axioms¶
A group \((G, *)\) is a set \(G\) with an operation \(*\) satisfying four rules:
| Axiom | Statement | In words |
|---|---|---|
| Closure | \(x * y \in G\) | combining two members stays inside the set |
| Associativity | \((x * y) * z = x * (y * z)\) | grouping doesn't matter |
| Identity | some \(e\) has \(e * x = x * e = x\) | there's a "do nothing" element |
| Inverses | each \(x\) has \(x^{-1}\) with \(x * x^{-1} = e\) | every move can be undone |
If, on top of these, the order never matters (\(x * y = y * x\) for all \(x, y\)), the group is abelian (commutative). Many familiar groups are abelian; the symmetric groups below are the important ones that aren't.
Two things called "order" — don't confuse them:
- The order of the group \(\lvert G \rvert\) is how many elements it has.
- The order of an element \(g\) is the smallest \(k > 0\) with \(g^k = e\) — how many times you apply \(g\) before returning to the start.
Same word, different meanings; problems exploit the confusion.
You don't need all four axioms to check a subgroup
A subgroup is a subset that's a group in its own right. To verify \(H \subseteq G\) is a subgroup you only need: \(H\) is non-empty, closed under \(*\), and closed under inverses. Associativity is inherited from \(G\) for free, and the identity is forced by the other two. For a finite \(H\), it's even easier — non-empty and closed under \(*\) already does it (inverses come along automatically).
Lagrange's theorem¶
The single most useful theorem in the topic, and the one most likely to crack open an exam problem in one line.
Lagrange's theorem
If \(H\) is a subgroup of a finite group \(G\), then
— the size of a subgroup always divides the size of the group.
Why it's true (and where you've seen this before). The subgroup \(H\) chops \(G\) into cosets, each of which has exactly \(\lvert H \rvert\) elements, and these cosets partition \(G\) — no overlaps, covering everything. So \(G\) is just some whole number of equal-sized blocks of size \(\lvert H \rvert\), which forces \(\lvert H \rvert\) to divide \(\lvert G \rvert\). It's the exact same "equivalence relation → partition" idea from the logic chapter, wearing group-theory clothes.
The corollaries you'll actually use:
- The order of any element divides \(\lvert G \rvert\) (apply Lagrange to the subgroup \(\langle g \rangle\) it generates).
- \(g^{\lvert G \rvert} = e\) for every \(g\). (Fermat's little theorem is precisely this, for the group \(\mathbb{Z}_p^{\times}\) — the two theorems are the same statement!)
- Every group of prime order is cyclic, generated by any non-identity element.
Lagrange only goes one way — the converse is false
Lagrange says a subgroup's size must divide \(\lvert G \rvert\). It does not promise a subgroup for every divisor. So use it to rule subgroups out, never to conjure one into being. To show a subgroup of some size exists, you must actually exhibit one.
Exam (May 2024, Problem 6a): does \(S_6\) have a subgroup of size 7?
The group \(S_6\) has \(\lvert S_6 \rvert = 6! = 720\) elements. A size-\(7\) subgroup would need \(7 \mid 720\) — but \(720 = 7 \cdot 102 + 6\), so \(7 \nmid 720\). By Lagrange, no such subgroup exists.
That's the entire answer: one divisibility check. This "rule it out" direction is exactly what Lagrange is for.
Cosets, concretely¶
The proof of Lagrange rests on cosets, and it's worth seeing them move. Given a subgroup \(H \le G\), the (left) coset of an element \(g\) is \(gH = \{\, g * h : h \in H \,\}\) — the whole subgroup "shifted" by \(g\). Two properties do all the work:
- Every coset has the same size \(\lvert H \rvert\) (shifting is a bijection).
- Cosets are either identical or disjoint — they partition \(G\) into equal blocks. The number of blocks is the index \([G : H] = \lvert G\rvert / \lvert H\rvert\).
Worked: the cosets of \(H = \{0, 3\}\) in \(\mathbb{Z}_6\)
Here \(G = \mathbb{Z}_6\) (addition mod \(6\)) and \(H = \{0, 3\}\), size \(2\). Build cosets \(g + H\):
and \(3+H = \{3,0\} = 0+H\), \(4+H = 1+H\), \(5+H = 2+H\) — no new ones. So the three cosets \(\{0,3\}, \{1,4\}, \{2,5\}\) tile \(\mathbb{Z}_6\) into equal pairs. That's Lagrange made visible: \(\lvert H\rvert = 2\) divides \(\lvert G\rvert = 6\) because \(G\) is exactly \([G:H] = 3\) copies of \(H\). (These cosets are also the elements of the quotient group \(\mathbb{Z}_6 / H \cong \mathbb{Z}_3\) — adding cosets behaves like adding mod \(3\).)
Cyclic groups¶
A group is cyclic if a single element \(g\) generates everything by taking powers: \(G = \langle g \rangle = \{\dots, g^{-1}, e, g, g^2, \dots\}\). Cyclic groups are the simplest kind — one generator drives the whole thing.
Two facts do most of the work:
- Every cyclic group is abelian (powers of the same \(g\) obviously commute).
- Therefore, not abelian ⟹ not cyclic. This contrapositive is the fastest non-cyclicity proof there is: show two elements that don't commute, and you're done.
- \(\mathbb{Z}_n\) under addition is cyclic, generated by \(1\) (add \(1\) repeatedly and you reach everything).
The structure inside a cyclic group¶
Take the model cyclic group \(\mathbb{Z}_n\) (under addition). Everything about its elements and subgroups is governed by one number — a gcd:
Order of an element in \(\mathbb{Z}_n\)
The element \(k\) has order
In particular \(k\) generates the whole group (has order \(n\)) exactly when \(\gcd(n, k) = 1\). So the number of generators of \(\mathbb{Z}_n\) is \(\varphi(n)\), the totient.
Why the gcd. Repeatedly adding \(k\) lands on the multiples \(0, k, 2k, \dots\); you return to \(0\) at the first multiple of \(k\) that is also a multiple of \(n\) — that's \(\operatorname{lcm}(n,k)\). The number of steps is \(\operatorname{lcm}(n,k)/k = n/\gcd(n,k)\).
Two more facts complete the picture, and both are pure divisor bookkeeping:
- Subgroups of a cyclic group are cyclic, and a cyclic group of order \(n\) has exactly one subgroup of order \(d\) for each divisor \(d \mid n\) — no more, no fewer. (Contrast Lagrange, which only forbids non-divisors; for cyclic groups the converse actually holds.)
- Every subgroup of \(\mathbb{Z}_n\) has the form \(\langle n/d \rangle\) and consists of the multiples of \(n/d\).
Worked: orders and generators in \(\mathbb{Z}_{12}\)
Using \(\operatorname{ord}(k) = 12/\gcd(12,k)\):
| \(k\) | \(\gcd(12,k)\) | order |
|---|---|---|
| \(1,5,7,11\) | \(1\) | \(12\) — these are the generators |
| \(2,10\) | \(2\) | \(6\) |
| \(3,9\) | \(3\) | \(4\) |
| \(4,8\) | \(4\) | \(3\) |
| \(6\) | \(6\) | \(2\) |
| \(0\) | \(12\) | \(1\) |
There are \(\varphi(12) = 4\) generators, matching the top row. And the subgroup orders that appear — \(1,2,3,4,6,12\) — are exactly the divisors of \(12\), one subgroup each, as promised.
Exam (May 2024, Problem 6b–d): subgroups of \(S_6\)
(b) A cyclic subgroup of order 4. Take a single 4-cycle, e.g. \(g = (1\,2\,3\,4)\). Then \(\langle g \rangle = \{\mathrm{id}, g, g^2, g^3\}\) has \(4\) elements and is cyclic by construction (one generator). ✓
(c) A subgroup of order 4 that is not cyclic. Take two disjoint transpositions \(h_1 = (1\,2)\) and \(h_2 = (3\,4)\). Because they move different points, \(h_1^2 = h_2^2 = \mathrm{id}\) and \(h_1 h_2 = h_2 h_1\), so
is closed and hence a subgroup of order \(4\). It's not cyclic: every element squares to the identity, so nothing has order \(4\) — and a cyclic group of order \(4\) needs an element of order \(4\). (This little group is famous: the Klein four-group.)
(d) Is \(S_6\) cyclic? No — and there are two clean ways to say so:
- By element orders. If \(S_6 = \langle g \rangle\), then \(g\) would need order \(6! = 720\). But in cycle form, an element's order is the lcm of its cycle lengths, and those lengths add up to at most \(6\) — so the order is at most \(6\) (well under \(720\)). Contradiction.
- By commutativity. Cyclic ⟹ abelian, but \(S_6\) isn't abelian: \((1\,2)(1\,3) \neq (1\,3)(1\,2)\). Done in one line.
The second argument is shorter and generalises: \(S_n\) is non-abelian for every \(n \geq 3\), hence never cyclic.
Direct products¶
You can build a bigger group out of two smaller ones by running them side by side. The direct product \(G \times H\) has as elements the pairs \((g, h)\), combined coordinate-wise: \((g_1, h_1) * (g_2, h_2) = (g_1 g_2,\ h_1 h_2)\). Its order is just \(\lvert G\rvert \cdot \lvert H\rvert\), and the order of an element is the lcm of the two coordinate orders.
The one examinable theorem ties directly back to the Chinese Remainder Theorem:
When is a product of cyclic groups cyclic?
Why the gcd condition. The element \((1, 1)\) has order \(\operatorname{lcm}(m, n)\). For the product to be cyclic it needs an element of order \(mn\) — and \(\operatorname{lcm}(m,n) = mn\) happens exactly when \(\gcd(m,n) = 1\). When they share a factor, every element's order divides \(\operatorname{lcm}(m,n) < mn\), so no generator exists.
Worked: \(\mathbb{Z}_2 \times \mathbb{Z}_3\) versus \(\mathbb{Z}_2 \times \mathbb{Z}_2\)
- \(\mathbb{Z}_2 \times \mathbb{Z}_3\): \(\gcd(2,3)=1\), so it's cyclic, \(\cong \mathbb{Z}_6\). The element \((1,1)\) has order \(\operatorname{lcm}(2,3) = 6\) and generates everything — this is CRT wearing group-theory clothes (\(x \equiv 1 \bmod 2\), \(x \equiv 1 \bmod 3\) pins down \(x\) mod \(6\)).
- \(\mathbb{Z}_2 \times \mathbb{Z}_2\): \(\gcd(2,2)=2 \neq 1\), so not cyclic. Every non-identity element has order \(2\) (no element of order \(4\)), and indeed this is the Klein four-group again — the same group that showed up as a non-cyclic subgroup of \(S_6\).
Isomorphisms and homomorphisms¶
A homomorphism is a map between groups that respects the operation — it doesn't matter whether you combine first and then map, or map first and then combine:
An isomorphism is a homomorphism that is also a bijection. If one exists, we write \(G_1 \cong G_2\) and say the groups are the same up to renaming — structurally identical, just with different labels on the elements.
- To prove isomorphic: produce the map \(\varphi\), check it respects the operation, and check it's a bijection.
- To prove not isomorphic: find a structural feature preserved by every isomorphism that one group has and the other lacks — different size, one abelian and the other not, a different number of elements of order \(2\), one cyclic and the other not, and so on. Any such mismatch settles it.
A homomorphism is pinned down by what it does to generators
If \(G = \langle g \rangle\), then knowing \(\varphi(g)\) determines \(\varphi\) everywhere (since every element is a power of \(g\)). More generally, fixing \(\varphi\) on a generating set fixes it completely. That's exactly why the exam's \(S_n \to \mathbb{Z}_2\) problem reduces to a single question: what does \(\varphi\) do to one transposition?
Exam (May 2024, Problem 9): homomorphisms \(S_n \to \mathbb{Z}_2\)
Claim to prove: any homomorphism \(\varphi: S_n \to \mathbb{Z}_2\) is either identically \(0\), or it's exactly the sign map (\(\varphi(g) = 1\) iff \(g\) is an odd permutation).
The strategy: every permutation is a product of transpositions, so \(\varphi\) is completely determined by its values on transpositions. So we only need to understand those.
Case 1. If \(\varphi(\tau) = 0\) for every transposition \(\tau\), then \(\varphi\) sends every product of transpositions to \(0\) — so \(\varphi = 0\). That's the first alternative.
Case 2. Otherwise some transposition has \(\varphi(\tau) = 1\), say \(\tau = (i\,j)\). The key fact is that all transpositions are conjugate — any one can be turned into any other by relabelling. Made concrete, for any other transposition \(\tau' = (k\,l)\):
Apply \(\varphi\) (and remember \(\mathbb{Z}_2\) adds, with \(2x = 0\)):
since each repeated term appears twice and cancels. So every transposition maps to \(1\), which means a product of \(k\) transpositions maps to \(k \bmod 2\) — precisely \(\operatorname{sign}(g)\). That's the second alternative. \(\square\)
Notice the shape of the argument: "determined by generators" reduced the whole problem to transpositions, and "all transpositions are conjugate" forced them to behave uniformly.
Permutations¶
A permutation is a bijection of \(\{1, \dots, n\}\) to itself — a rearrangement. The symmetric group \(S_n\) is all of them under composition.
Cycle notation¶
Every permutation breaks uniquely into disjoint cycles: \((1\,2\,3)\) means "1→2, 2→3, 3→1", and disjoint cycles touch different elements. Because they touch different elements, disjoint cycles commute — which is what makes the order formula work.
Order of a permutation
The order of a permutation is the least common multiple of its disjoint cycle lengths.
Why the lcm. A cycle of length \(\ell\) returns to start every \(\ell\) applications. The whole permutation is back to the identity only when all its cycles are simultaneously home — which first happens at the lcm of their lengths. So \((1\,2\,3)(4\,5)\) has order \(\operatorname{lcm}(3, 2) = 6\). (Finding the largest possible order in \(S_n\) is therefore a puzzle about splitting \(n\) to maximise an lcm.)
Sign: odd and even¶
Every permutation can also be written as a product of transpositions (2-cycles — single swaps). The number of transpositions isn't unique, but its parity (even/odd) always is, and that parity is the permutation's sign:
- Even number of transpositions ⟹ even permutation, \(\operatorname{sign} = +1\).
- Odd number ⟹ odd permutation, \(\operatorname{sign} = -1\).
A useful shortcut: a \(k\)-cycle splits into \(k - 1\) transpositions, so it's even exactly when \(k\) is odd. To find a permutation's sign, add up \((k_i - 1)\) over its cycles: \(\operatorname{sign} = (-1)^{\sum (k_i - 1)}\).
Sign is multiplicative — \(\operatorname{sign}(gh) = \operatorname{sign}(g)\operatorname{sign}(h)\) — which is just the statement that sign is a homomorphism \(S_n \to \{\pm 1\} \cong \mathbb{Z}_2\). And by Problem 9 above, it's essentially the only non-trivial homomorphism out of \(S_n\) to \(\mathbb{Z}_2\). The threads tie together.