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.
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).
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.
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.