MATH40003 Linear Algebra and Groups
Part II: Groups
David Evans
Department of Mathematics, Imperial College∗
March 7, 2022
Contents
1 Groups and Subgroups 2
1.1 Binary operations; groups; basic facts . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Examples of groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Powers and Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Orders of elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 More on cyclic groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Generating other subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Lagrange’s Theorem and Cosets 15
3 Homomorphisms 18
4 More on Sn 22
4.1 Disjoint cycle form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Applications of disjoint cycle form . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Dihedral groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 The sign of a permutation; Determinants again . . . . . . . . . . . . . . . . 28
∗© David M. Evans (2021) These notes are provided for the personal study of students taking this
module. The distribution of copies in part or whole is not permitted.
1
1 Groups and Subgroups
Lecture
10
1.1 Binary operations; groups; basic facts
Definition 1.1. Suppose S is a set. A binary operation ∗ on S assigns to each ordered
pair (a, b) of elements of S an element a∗b of S . More formally, ∗ is a function S×S → S .
(Where S × S is the Cartesian product set {(a, b) : a, b ∈ S} .)
This is a very general notion. Here are some examples involving M2(R): not all of them will
lead to groups!
Examples: Let S =M2(R). The following are binary operations on S .
(1) a ∗ b = ab , the usual matrix multiplication.
(2) ∗ is matrix addition.
(3) a ∗ b = a for all a, b ∈ A (‘projection onto the first coordinate’)
(4) a ∗ b = ab− ba (called the Lie product).
(5) Let S1 = {a ∈ M2(R) : a is invertible} . For a, b ∈ S1 let a ∗ b be the usual matrix
product ab . As the product of two invertible matrices is invertible, this is a binary operation
on S1 .
(6) If in (5) we had taken a ∗ b = a + b , this would not be a binary operation on S1 as the
sum of two invertible matrices need not be invertible.
You will have seen this before:
Definition 1.2. A binary operation ∗ on a set S is associative if
for all a, b, c ∈ S we have a ∗ (b ∗ c) = (a ∗ b) ∗ c.
Exercise: Which of the binary operations above are associative?
Associativity means that we can unambiguously write an expression such as
((a1 ∗ a2) ∗ (a3 ∗ a4)) ∗ a5
as a1 ∗ a2 ∗ a3 ∗ a4 ∗ a5 . The bracketing is redundant. From now on, we will usually do this
when dealing with associative operations.
Puzzle: How many ways are there of bracketing a1 ∗ a2 ∗ . . . ∗ an? Try it for n = 4, 5. Can
you find a general expression?
Now, here is the main definition.
Definition 1.3. A group (G, ∗) consists of a set G with a binary operation ∗ on G satisfying
the following:
2
G1 (Associativity) For all g, h, k ∈ G we have
(g ∗ h) ∗ k = g ∗ (h ∗ k).
G2 (Identity axiom) There exists an element e ∈ G such that for all g ∈ G we have
e ∗ g = g ∗ e = g.
We will show that G1 and G2 imply that there is a unique such e ∈ G , which we will denote
by e or eG and call it the identity element of the group.
G3 (Existence of inverses) With e as in G2, for all g ∈ G there is an element h ∈ G such
that
g ∗ h = h ∗ g = e.
We will show that the h here is uniquely determined by g : we call it the inverse of g and
usually denote it by h−1.
Remarks: Here, G1,G2,G3 are called the group axioms. In some books you will see that
the following is also included as an axiom:
G0 (Closure) If g, k ∈ G , then g ∗ k ∈ G .
It’s not necessary to include this as we are assuming that ∗ is a binary operation on G and
so G0 holds anyway.
Remarks 1.4. Here are some remarks on simplifications to notation and terminology which
we shall use throughout.
(1) It is more common to use . instead of ∗ for the group operation: so from now on, you
will see g.h rather than g ∗ h . In fact, just as in ordinary arithmetic, we often omit the .
and just write gh instead of g.h . We call the operation the product in the group.
(2) A group (G, ∗) is called abelian or commutative if for all g, h ∈ G we have g ∗ h = h ∗ g .
In such cases, we often write the operation as +. When we do this we write the identity
element as 0 and the inverse of g as −g .
Remarks 1.5. We now justify the claims made in Definition 1.3. Suppose (G, .) is a group.
(1) We have to show the following, using axioms G1 and G2.
If e, e′ ∈ G and for all g ∈ G
e.g = g.e = g and e′.g = g.e′ = g
then e = e′ .
3
Proof: Using these equations, we have e = e.e′ = e′ (exercise: say which of the equations
were used here!) 2
(2) We have to show the following using the group axioms.
Suppose g, g′, g′′ ∈ G and
gg′
(1)
= e
(2)
= g′g and gg′′
(3)
= e
(4)
= g′′g.
Then g′ = g′′ .
Proof: We have
(g′g)g′′
(2)
= eg′′ = g′′ and g′(gg′′)
(3)
= g′e = g′.
So by Associativity g′ = g′′ .
[Exercise: Why is the following not a proof? ‘From the equations, we have g′ = g−1 and
g′′ = g−1 , so g′ = g′′ .’]
We will use the following all the time, usually without mentioning that it’s what we are
using. It’s about manipulating equations in a group.
Lemma 1.6. (Equations in groups) Suppose (G, .) is a group and g, h ∈ G.
(1) For x ∈ G we have gx = h⇔ x = g−1h
(2) For y ∈ G we have yg = h⇔ y = hG−1 .
Proof: (1) ⇒: Multiply on the left by g−1 :
gx = h⇒ g−1(gx) = g−1h G1⇒ (g−1g)x = g−1h⇒ ex = g−1h⇒ x = g−1h.
⇐ : Check that all of the above arrows can be reversed.
(2) Similar, but multiply on the right by g−1 . 2
The following will look very familiar from matrix multiplication.
Lemma 1.7. (Inverse of a product) Suppose (G, .) is a group.
(1) If g, h ∈ G, then (gh)−1 = h−1g−1 .
(2) If g1, . . . , gn ∈ G, then
(g1g2 . . . gn)
−1 = g−1n . . . g
−1
2 g
−1
1 .
Proof: (1) Note that
(h−1g−1)(gh) = h−1(g−1)g)h = h−1eh = h−1h = e.
Similarly gh(h−1g−1) = e .
(2) Prove this by induction on n . The base case n = 2 is (1). 2
[Before the next lecture, review the material in the Introductory Module about Bijections
(Sections 2.3 and 2.4 there).]
4
1.2 Examples of groups
Examples 1.8. Examples from fields Lecture
11
(1) R with the operation + is a group. The identity element is 0 and the inverse of a ∈ R
is −a . We refer to this as the additive group of the field R .
(2) R× = R \ {0} with the operation . is a group. The identity element is 1 and the inverse
of a ∈ R× is a−1 . We refer to this as the multiplicative group of the field R .
(3) Examples (1), (2) work with any field, not just R .
(4) If F is any field and n ∈ N , then (F n,+) is a group.
(5) If V is a vector space (over a field F ) then (V,+) is a group.
(6) Let n ∈ N and suppose F is a field. The general linear group GL(n, F ) (or GLn(F )) is
the set G of n × n invertible matrices (over F ) and operation matrix multiplication. This
is a group:
• Binary operation: If A,B ∈ G , you can check that AB ∈ G (because the inverse of
AB is B−1A−1 ).
• G1, Associativity: If A,B,C ∈ G , then A(BC) = (AB)C : this is a general property
of matrix multiplication.
• G2, Existence of identity element: The identity matrix In ∈ G has the required
property.
• G3, Existence of inverses: this follows from the definition of G .
Note: GL(1, F ) is the multiplicative group F× .
Definition 1.9. The Symmetric Groups.
Suppose X is any (non-empty) set. (For example, X = {1, 2, . . . , n} .) A permutation of X
is a bijection α : X → X .
For example, if X = {1, 2, 3, 4} let α be the map denoted by:(
1 2 3 4
2 4 1 3
)
with α(1) = 2, α(2) = 4, etc.
More generally we use the following ‘two-row’ notation for permutations on the set X =
[n] = {1, 2, . . . , n} . We denote a permutation α : [n]→ [n] by:(
1 2 . . . n
α(1) α(2) . . . α(n)
)
.
5
Note that the second row here is a ‘rearrangement’ of 1, 2, 3, . . . , n .
Exercise: If α, β : X → X are permutations, then so is the composition α ◦ β : X → X
(α ◦ β)(x) = α(β(x)), for x ∈ X.
- See the Introductory Module if you are unsure about this.
Example: If
α =
(
1 2 3 4
2 4 1 3
)
and β =
(
1 2 3 4
2 1 4 3
)
then
α ◦ β =
(
1 2 3 4
4 2 3 1
)
and β ◦ α =
(
1 2 3 4
1 3 2 4
)
.
Let Sym(X) denote the set of all permutations of X . If n ∈ N and X = [n] = {1, 2, . . . , n} ,
we will also denote this by Sym(n) or Sn .
Theorem 1.10. Suppose X is any (non-empty) set. Then Sym(X) with the operation ◦ of
composition is a group. It is called the symmetric group on X .
Proof: By the above exercise, we know that ◦ is a binary operation on Sym(X). We proceed
to check the group axioms.
G1 (Associativity): Composition of functions is associative: if α, β, γ ∈ Sym(X), then
α ◦ (β ◦ γ) and (α ◦ β) ◦ γ are the same function X → X (for x ∈ X they both send x to
α(β(γ(x)))).
G2 (identity element): The identtity function ι : X → X , with ι(x) = x for all x ∈ X , is in
Sym(X) and has the required properties.
G3 (Existence of inverses): If α ∈ Sym(X), then it is a bijection and so has an inverse α−1
which is also a bijection: α−1(y) = x⇔ α(x) = y . 2
Remarks: If α, β ∈ Sym(X) we will often write αβ instead of α ◦ β . Remember that this
is composition of functions and so this means ‘apply β first, then α .’
Warning: Some books or lecture notes will use the notation the other way round.
Example/ Exercise: Consider the following elements of S6 :
α =
(
1 2 3 4 5 6
2 3 4 5 6 1
)
and β =
(
1 2 3 4 5 6
1 6 5 4 3 2
)
.
Compute αβ, βα, α−1, β−1, αβα−1.
Label the vertices of a regular hexagon 1, 2, 3, 4, 5, 6 (clockwise) and think about how the
permutations α, β and these other permutations correspond to symmetries of the regular
hexagon.
Definition 1.11. We say that a group (G, .) is a finite group if the set G is a finite set. In
this case, the order of (G, .) is |G| , the number of elements in the group.
6
Theorem 1.12. If n ∈ N, then |Sn| = n!
Proof: We have to count the number of permutations
α =
(
1 2 . . . n
a1 a2 . . . an
)
where a1, . . . , an are 1, . . . , n in some order.
There are
n choices for a1 ;
n− 1 choices for a2 ;
n− 2 choices for a3 ;
. . .
So there are a total of n(n− 1)(n− 2) . . . 2.1 = n! possibilities for α . 2
1.3 Powers and Subgroups
Lecture
12Definition 1.13. Suppose (G, ·) is a group. For g ∈ G , we let
g0 = e, g1 = g, g2 = g · g, g3 = g · g · g, . . . .
More precisely, for n ∈ N we define inductively
g0 = e, g1 = g and gn+1 = gn · g.
We also define g−n = (g−1)n .
Using this as our definition, we can then prove the following.
Lemma 1.14. With this notation, if m,n ∈ Z, then
(o) gm+1 = gmg and gmg = ggm ;
(i) (gm)−1 = g−m ;
(ii) gmgn = gm+n = gngm ;
(iii) gmn = (gm)n .
Example: Let
g =
(
1 2 3 4
2 3 4 1
)
∈ S4.
Then
g2 =
(
1 2 3 4
3 4 1 2
)
, g3 =
(
1 2 3 4
4 1 2 3
)
= g−1, g4 = ι, g5 = g, . . . , g19 = g3
7
the last of these because 19 = 4.4 + 3 and so
g19 = (g4)4g3 = ι4g3 = g3
using the lemma.
Similarly if n ≡ k (mod 4), gn = gk .
Proof of Lemma: It’s not trivial to get all of the details correct, though it is quite tedious.
The proof should remind you of some things you discussed around Peano’s axioms in the
Introductory module.
(o) For the first part, if m ≥ 0, this is by definition. So assume m = −k where k ∈ N
and prove by induction on k that g−k+1 = g−kg . The base case is k = 1, which follows
from g0 = e = g−1g . For the inductive step suppose we know g−k+1 = g−kg . Then
g−(k+1)g = (g−1)k+1g = ((g−1)kg−1)g = g−k , as required (the first two equalities comes from
the definitions). The second part is an exercise.
(i) Prove for m ≥ 0 that (gm)(g−m) = e , by induction on m . Then deduce for m < 0.
(ii) We first prove this for n ≥ 0. We do this by induction on n , regarding m as fixed.
Base case n = 0: We have gm+0 = gm and gmg0 = gme = gm , so gm+0 = gmg0 .
Inductive step: Suppose we know that gm+n = gmgn . Then
gm+(n+1) = g(m+n)+1
(o)
= gm+ng = (gmgn)g = gm(gng) = gmgn+1
as required.
Exercise: Complete the proof of (ii) by considering the case n < 0.
(iii) Similar, using (ii). 2
Remark: on additive notation. If our group is (G,+) and n ∈ N , we write g + . . .+ n (n
times) as ng (not gn ).
Definition 1.15. Suppose (G, .) is a group and H ⊆ G . We say that H is a subgroup of
G (or of (G, .)) if H with the binary operation from G is a group, that is:
for all h1, h2 ∈ H we have h1.h2 ∈ H
and (H, .) satisfies axioms G1,G2,G3. We will write H ≤ G to indicate that H is a subgroup
of G .
Examples: (1) G is a subgroup of G ;
(2) {e} is a subgroup of G .
In practice, what we use to decide whether a given subset of a group is a subgroup is the
direction ⇐ of the following.
8
Theorem 1.16. (Test for a subgroup) Suppose (G, .) is a group and H ⊆ G. Then H is a
subgroup of G if and only if
(1) H ̸= ∅;
(2) for all h1, h2 ∈ H we have h1h2 ∈ H (closure under the group operation);
(3) for all h ∈ H we have h−1 ∈ H (closure under inverses).
Example: If g ∈ G , let H = {gm : m ∈ Z} . This is a subgroup of G , by 1.16 and 1.14.
Proof of 1.16: ⇐: Suppose (1), (2), (3) hold for H . By (2), the multiplication . in G gives
a binary operation on H . So we need to check that (H, .) satisfies the group axioms.
G1 follows from associativity in G .
For G2, it is enough to show that eG ∈ H . By (1), there is some h ∈ H . By (3), h−1 ∈ H .
Then by (2), hh−1 ∈ H . So eG ∈ H .
Then G3 follows from (3).
⇒: If H is a subgroup of G , then (2) holds by definition.
By G2, we know that H ̸= ∅ , so (1) holds.
For (3) we first show that eG ∈ H . Let h ∈ H . As (H, .) is a group, there is some x ∈ H
with hx = h . But the only solution to this equation in G is x = eG . So eG ∈ H . Similarly,
the only solution to hh′ = eG in G is h′ = h−1 . As H is a group, there must be a solution
in H , so h−1 ∈ H , as required for (3). 2
Remark: The direction ⇒ shows that if H is a subgroup of G then eG ∈ H and inverses
are the same in H as they are in G .
Before we give some examples of using the test, we formalise the example given before the
above proof by giving some terminology.
Definition 1.17. (1) Suppose (G, .) is a group and g ∈ G . The cyclic subgroup generated
by g is ⟨g⟩ = {gm : m ∈ Z}.
(2) We say that a group G is cyclic if there is g ∈ G with ⟨g⟩ = G . In this case, g is called
a generator of G .
Examples 1.18. (1) Let G = GL(n,R) (the group of n × n invertible matrices over R).
We give some subgroups.
(1) Let H = {g ∈ G : det(g) = 1} . We use the subgroup test to check that this is a subgroup
of G :
H ̸= ∅ as In ∈ H .
H is closed under . as det(g1g2) = det(g1)det(g2) so if g1, g2 ∈ H , then g1g2 ∈ H .
H is closed under inverses as det(g−1) = 1/det(g) for g ∈ G , so if h ∈ H , then h−1 ∈ H .
9
(2) You can use the subgroup test to show that
K = {
(
cos θ − sin θ
sin θ cos θ
)
: θ ∈ R} ≤ GL2(R).
Note K consists of linear maps R2 → R2 given by rotations about 0. The subgroup
K is abelian, but not cyclic (for example, K is uncountable, whereas any cyclic group is
countable).
(3) We have:
2Z ≤ Z ≤ Q ≤ R ≤ (C,+),
where 2Z consists of the even integers. Note that Z = ⟨1⟩ and 2Z = ⟨2⟩ are cyclic, but
none of the other groups is cyclic.
(4) Consider the unit circle in the complex plane:
U = {eiθ : θ ∈ R} = {z ∈ C : |z| = 1} = {z ∈ C : zz¯ = 1}.
This is a subgroup of (C×, .), the multiplicative group of the field of complex numbers. It is
abelian, but not cyclic.
[Puzzle: What is the relationship to the group K in (2)?]
(5) Let n ∈ N and ζ = e2πi/n ∈ C× . So ζn = 1. Then ⟨ζ⟩ ≤ U and
⟨ζ⟩ = {1, ζ, ζ2, . . . , ζn−1}
is a cyclic group of order n .
[Note that if you draw the elements of ⟨ζ⟩ on an Argand diagram, they form the vertices of
a regular n-gon on the unit circle.]
(6) Suppose F is any field and n ∈ N . Consider the group (F n,+). Any subspace of F n is
a subgroup of this, but the converse is not necessarily true. For example Q2 is a subgroup
of R2 , but it is not a subspace.
(7) Let
α =
(
1 2 3 4
2 1 4 3
)
, β =
(
1 2 3 4
3 4 1 2
)
, γ =
(
1 2 3 4
4 3 2 1
)
∈ S4.
Then V = {ι, α, β, γ} ≤ S4 is a subgroup of S4 , called the Klein four-group. We have g2 = ι
for all g ∈ V . So V is abelian but not cyclic.
[Remark: it would be good to revise thing in the Introductory module around the Division
- Remainder Theorem, gcd’s and the Euclidean algorithm.]
10
1.4 Orders of elements
Lecture
13
From now on we will usually write ‘G is a group’ instead of (G, .) is a group.’
Definition 1.19. Suppose G is a group and g ∈ G . We say that g has finite order if there
is n ∈ N (with n ≥ 1) such that gn = e . In this case, the least such n with gn = e is called
the order of g , denoted by ord(g). If there is no such n ∈ N , we say that g has infinite
order.
Examples: (1) For any group G , the identity element e has order 1.
(2)
(
1 2 3
2 3 1
)
∈ S3 has order 3;
(
1 2 3
2 1 3
)
has order 2.
(3) 2 ∈ R× has infinite order; −1 ∈ R× has order 2.
(4) For n ∈ N , ζ = e2πi/n ∈ C× has order n .
(5) The matrix
0 0 11 0 0
0 1 0
 ∈ GL3(R) has order 3.
(6) (Ex.) Think about orders of rotations in GL2(R).
Theorem 1.20. Suppose G is a group and g ∈ G has finite order n. Then:
(1) For m, l ∈ Z we have
gl = gm ⇔ n | (l −m)⇔ l ≡ m (modn).
(2) In particular, gm = e⇔ n | m.
(3) We have ⟨g⟩ = {e, g, g2, . . . , gn−1} and |⟨g⟩| = n.
So ord(g) = |⟨g⟩|.
Proof: (1) ⇐: Let s = l −m and suppose n | s . So there is t ∈ Z with s = nt . Then
gs = gnt = (gn)t = et = e.
Thus e = gs = gl−m = glg−m. Multiplying by gm , we obtain gm = gl , as required.
⇒: Suppose gl = gm . Then gl−m = e . By the Quotient - Remainder Theorem (Introductory
Module, 3.2.3) there are q, r ∈ Z with
l −m = qn+ r and 0 ≤ r < n.
Then
e = gl−m = gqn+r = gqngr = (gn)qgr = egr = gr.
By minimality of n and 0 ≤ r < n , we therefore have r = 0. Thus n | (l−m), as required.
11
(2) By (1) with l = 0.
(3) Every l ∈ Z is congruent modulo n exactly one of 0, 1, . . . , n − 1. So the result we
require follows from (1). 2
The following is a useful simplification of the test for being a subgroup of a finite group.
Theorem 1.21. Suppose G is a finite group.
(1) Every element of G has finite order.
(2) If H ⊆ G is a non-empty subset of G and for all h1, h2 ∈ H we have h1h2 ∈ H , then
H is a subgroup of G.
Proof: (1) Consider g, g2, g3, . . . ∈ G . As |G| is finite, there exist 0 < m < l with gm = gl .
Then gl−m = e and l −m > 0. So g has finite order.
(2) We have to show that H is closed under inverses. Let h ∈ H . By (1) there is n ∈ N
with hn = e . We want to show h−1 ∈ H . We can assume that h ̸= e , so n > 1. Then
h−1 = hn−1 and n− 1 ≥ 1. As h ∈ H and H is closed under multiplication, it follows that
hn−1 ∈ H . So h−1 ∈ H . 2
1.5 More on cyclic groups
Lecture
14The following tells us everything about subgroups of cyclic groups.
Theorem 1.22. Suppose (G, .) is a cyclic group and G = ⟨g⟩.
(1) If H ≤ G, then H is cyclic.
(2) Suppose |G| = n (that is, g has order n), and m ∈ Z. Let d = gcd(m,n), the greatest
common divisor of m and n. Then
⟨gm⟩ = ⟨gd⟩ and |⟨gd⟩| = n/d.
In particular,
⟨gm⟩ = G⇔ gcd(m,n) = 1.
(3) If |G| = n and k ≤ n, then G has a subgroup of order k if and only if k | n. In this
case, the subgroup is ⟨gn/k⟩.
Example/ Exercise: Let g = e2πi/6 ∈ C× and G = ⟨g⟩ . So G is a cyclic group of order
6. The subgroups of G have orders 1,2,3 and 6. They are:
{1} ;
⟨g3⟩ = {1,−1} ;
⟨g2⟩ = {1, g2, g4} ;
12
⟨g⟩ = G .
There is one element of order 2, two elements of order 3, and two elements of order 6.
Proof of Theorem: (1) We may assume that H ̸= {e} . Let d be the least element of
{n ∈ N : gn ∈ H} (noting that this set is non-empty).
Claim: H = ⟨gd⟩ .
As gd ∈ H and H ≤ G , we have ⟨gd⟩ ≤ H . So let h ∈ H . Then h = gm for some m ∈ Z .
We can write m = qd + r for some q, r ∈ Z with 0 ≤ r < d . So h = gqd+r = (gd)qgr .
Thus gr = h(gd)−q ∈ H , as h ∈ H and gd ∈ H . Minimality of d therefore gives r = 0. So
h = gqd = (gd)q ∈ ⟨gd⟩ , as required.
(2) As d = gcd(m,n) there are k, l ∈ Z with d = km+ ln (the Be´zout Identity).
To show that ⟨gm⟩ = ⟨gd⟩ it is enough to prove that gm ∈ ⟨gd⟩ and gd ∈ ⟨gm⟩ . Because
d | m , gm is a power of gd , so the first of these is true. For the second, note that
gd = gkm+ln = (gm)k(gn)l = (gm)k
as n = ord(g), so gn = e . This gd ∈ ⟨gm⟩ .
Now consider what is |⟨gd⟩| . Because d | n we can write n = df for some f ∈ N . Then ⟨gd⟩ =
{g0, gd, . . . , g(f−1)d} as gfd = e . Now, g0, gd, g2d, . . . , g(f−1)d are distinct as d, . . . , (f − 1)d
are less than n . It follows that |⟨gd⟩| = f = n/d .
(3) The first part is by (1) and (2). If k | n , then by (2), the unique subgroup with k
elements is ⟨gn/k⟩ . 2
An application. We will give an application of the previous theorem to prove a result due
to Gauss on the Euler totient function: an important function in elementary number theory.
You can find an application of Gauss’ result on the problem sheet, where it is used to prove
the useful fact that every finite subgroup of the multiplicative group of a field is cyclic.
Definition: For n ∈ N , the Euler totient function ϕ(n) is
|{k ∈ N : 1 ≤ k ≤ n and gcd(k, n) = 1}|.
Thej following Corollary to Theorem 1.22 is due to C. F. Gauss.
Corollary 1.23. For all n ∈ N we have∑
1≤d≤n, d|n
ϕ(d) = n.
Example: n = 6 has divisors d = 1, 2, 3, 6. We compute that ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2,
ϕ(6) = 2. Summing these does indeed give 6.
Proof of Corollary: Let G be a cyclic group of order n . By 1.22(3), if d | n then G has a
unique subgroup Gd of order d . Thus, Gd contains every element of G of order d (because
this will generate a subgroup of order d).
13
We also know, by 1.22(1), that Gd is cyclic, and therefore by 1.22(2), Gd has ϕ(d) elements
of order d .
Any element of G has order dividing n = |G| (by 1.22(2)). Then counting elements of G
according to their possible orders (and therefore which Gd they generate) gives∑
1≤d≤n, d|n
ϕ(d) = n.2
1.6 Generating other subgroups
What about subgroups generated by more than one element? In general, this is a much
harder question than understanding cyclic groups (or cyclic subgroups). But at least we can
make some definitions.
Definition 1.24. Suppose (G, .) is a group and S ⊆ G is non-empty. Let
S−1 = {g−1 : g ∈ S}
and
⟨S⟩ = {g1g2 . . . gk : k ∈ N and g1, g2, . . . , gk ∈ S ∪ S−1}.
So ⟨S⟩ is the set of all products of elements of S and their inverses (allowing repetitions).
We could also define ⟨∅⟩ = {e} , if we wish.
Lemma 1.25. With this notation:
(1) ⟨S⟩ is a subgroup of G.
(2) If H ≤ G and S ⊆ H , then ⟨S⟩ ⊆ H .
Proof: Exercise: use the test for being a subgroup. 2
So ⟨S⟩ is the ‘smallest’ subgroup of G containing S . It is called the subgroup of G generated
by S .
If S = {x1, . . . , xr} , write ⟨S⟩ as ⟨x1, . . . , xr⟩ .
If G is abelian then
⟨x1, . . . , xr⟩ = {xk11 xk22 . . . xkrr : k1, . . . , kr ∈ Z}.
But in general, understanding ⟨x1, . . . , xr⟩ is a hard problem even for r = 2.
14
2 Lagrange’s Theorem and Cosets
Lecture
15In this section we will prove the following and give some applications. The method of proof,
involving cosets, is also an important idea which you will see more of in later modules.
Theorem 2.1. (Lagrange’s Theorem) Suppose (G, .) is a finite group and H is a subgroup
of G. Then |H| divides |G|.
So one thing that this tells us is that G = S5 , which has order 5! = 120, cannot have a
subgroup of order 50. Here are some more general applications.
Theorem 2.2. Suppose G is a finite group of order n. Let g ∈ G. Then:
(1) The order of g divides n.
(2) gn = e.
Proof: (1) The order of g is |⟨g⟩| (by 1.20(3)). As ⟨g⟩ is a subgroup of G , the result therefore
follows from Lagrange’s Theorem.
(2) Suppose ord(g) = k . By (1) we have k | n . Moreover gn = (gk)n/k = en/k = e. 2
As a special case we have the well-known:
Corollary. (Fermat’s Little Theorem) Suppose p is any prime. If x ∈ Z and p ̸ |x , then
xp−1 ≡ 1 (mod p).
[ It follows that for all k ∈ Z we have kp ≡ k (mod p).]
Proof: Let Fp be the field with p elements (that is, Zp ). Consider (F×p , .), the multiplicative
group of the field, consisting of the non-zero elements. Then |F×p | = p− 1.
So for every g ∈ Fp , we have gp−1 = [1]p , the identity element of the field, the residue
class of 1, modulo p . If x ∈ Z and p ̸ |x , then [x]p ̸= [0]p . So taking g = [x]p we obtain
[1]p = [x]
p−1
p = [x
p−1]p . In other words, xp−1 ≡ 1 (mod p). 2
Examples 2.3. Let G = S3 . So |G| = 6. Let α =
(
1 2 3
2 3 1
)
and β =
(
1 2 3
2 1 3
)
.
Then ⟨α, β⟩ = G .
Indeed, note that α has order 3 and β has order 2. As ⟨α, β⟩ ≤ S3 has subgroups ⟨α⟩ and
⟨β⟩ , it follows from Lagrange’s theorem that the order of ⟨α, β⟩ is divisible by 2 and by 3,
and therefore by 6. As S3 has order 6, it follows that ⟨α, β⟩ = S3 .
Theorem 2.4. Suppose p is a prime and G is group of order p. Then G is cyclic. In fact,
if e ̸= g ∈ G, then ⟨g⟩ = G.
Proof: By Lagrange’s Theorem |⟨g⟩| divides p . As e, g ∈ ⟨g⟩ and e ̸= g we therefore have
|⟨g⟩| = p , because p is a prime. 2
We now turn to the proof of Lagrange’s Theorem and the key idea of cosets.
15
Definition 2.5. Suppose (G, .) is a group and H ≤ G . Let g ∈ G . The subset
gH = {gh : h ∈ H} ⊆ G
is called a left coset of H in G . (Sometimes we will say ‘left H -coset.’)
So if H = {h1, . . . , hr} , then gH = {gh1, . . . , ghr} .
Another way of saying this is that a subset X of G is a left coset of H in G if there exists
some g ∈ G such that X = gH . Note that g ∈ gH , so this might give us some clue about
which g to take here.
[Remark: Some books, lecture notes and past exam questions will refer to right cosets
Hg = {hg : h ∈ H} . Essentially everything we do will also work with right cosets in place
of left cosets. But we should not mix them.]
In some situations, cosets are actually quite familiar. Here are some examples.
Examples 2.6. (1) Let G = (C×, .) and H = {z ∈ C× : |z| = 1} . So H is a subgroup of
G . Let g = 2 ∈ C× . Then the left coset
2H = {2eiθ : θ ∈ R} = {z ∈ G : |z| = 2}.
Note that this is not a subgroup of G .
More generally, if w ∈ C× , then wH = {z ∈ C× : |z| = |w|} .
(2) Let G = (Z,+) and H = {5m : m ∈ Z} . So H is a subgroup of G . As the group G is
written additively, we shall also write H -cosets additively:
0 +H = H = [0]5 ;
1 +H = {1 + 5m : m ∈ Z} = {k ∈ Z : k ≡ 1 (mod 5) = [1]5 ;
. . .
4 +H = [4]5 ;
. . .
6 +H = {6 + 5m : m ∈ Z} = {1 + 5m : m ∈ Z} = {k ∈ Z : k ≡ 1 (mod 5) = [1]5 .
So there are 5 left H -cosets
0 +H, 1 +H, . . . , 4 +H
and these partition G = Z .
(3) Let A be an m × n matrix with entries from R . Let W = {x ∈ Rn : Ax = 0m} , the
solution set of the system of homogeneous linear equations with coefficient matrix A . So W
is a subspace of (Rn,+), and therefore a subgroup. Suppose b ∈ Rm and there is c ∈ Rn
with Ac = b . Then
Ax = b⇔ A(x− c) = 0⇔ x− c ∈ W ⇔ x ∈ c+W.
So if the the set of solutions to Ax = b is non-empty, then it is a coset of W in Rn .
16
Lecture
16
We saw in these examples that, for a fixed subgroup H , the left H -cosets partition G : every
element of G is in exactly one left H -coset. The following lemma supplies the proof of this
in general.
Lemma 2.7. Suppose (G, .) is a group and H ≤ G.
(1) If g1, g2 ∈ G and g2 ∈ g1H , then g2H = g1H .
(2) If g, k ∈ G and gH ∩ kH ̸= ∅, then gH = kH .
Proof (1) We first show that if g2 ∈ g1H , then g2H ⊆ g1H .
As g2 ∈ g1H there is h ∈ H with g2 = g1h . Any element of g2H is of the form g2h′ for
some h′ ∈ H . Then g2h′ = (g1h)h′ = g1(hh′). Because H ≤ G , we have hh′ ∈ H . So
g2h
′ ∈ g1H , as required.
Also g1 = g2h
−1 and h−1 ∈ H , so g1 ∈ g2H . Thus, the same argument gives g1H ⊆ g2H .
Putting the two parts together gives g1H = g2H .
(2) Let x ∈ gH ∩ kH . By (1), applied twice, we have gH = xH = kH . 2
Lemma 2.8. Suppose (G, .) is a group and H ≤ G. If g ∈ G, then the map H → gH given
by h 7→ gh is a bijection. In particular, if H is finite, then |H| = |gH|.
Proof: By definition, the map is surjective. Also, if gh1 = gh2 , then h1 = h2 , so the map is
also injective. 2
We can now give a proof of Lagrange’s Theorem.
Suppose G is a finite group and H ≤ G .
Consider the left cosets of H in G .
Any one of these has |H| elements (by 2.8).
Any two of them are disjoint (by 2.7).
Moreover, any g ∈ G lies in some left H -coset, namely gH .
Thus |G| is equal to |H| times the number of distinct left H -cosets.
So |H| divides |G| and |G|/|H| is equal to the number of left H -cosets in G . This concludes
the proof of Lagrange’s Theorem. 2
Definition 2.9. The number of left cosets of H in G is called the index of H in G .
Remarks: If G is finite, this is equal to |G|/|H| , by the above. It is also equal to the
number of right cosets of H in G , by the same proof. But it is also possible to write down
an explicit bijection between the set of left H -cosets and the set of right H -cosets. Can you
do this?
17
We can give a different approach to the proof using equivalence relations, which you encoun-
tered in the Introductory Module. But this is really just the same proof!
Theorem 2.10. Suppose G is a group and H ≤ G. Define the relation ∼ on G by
g ∼ k ⇔ g−1k ∈ H.
Then
(1) ∼ is an equivalence relation on G.
(2) g ∼ k iff gH = kH .
Proof: (1) is on Question sheet 6.
(2) By 2.7
g−1k ∈ H ⇔ g−1kH = H ⇔ kH = gH.2
Note that this tells us that the ∼-equivalence classes are the left H -cosets.
Exercise: write down an equivalence relation on G whose classes are the right H -cosets.
Example / Exercise: Let G = S3 and H = ⟨α⟩ where α =
(
1 2 3
1 3 2
)
. What are the
left H -cosets?
Note that H = {ι, α} so |H| = 2 and |G| = 6. So there are 3 left H -cosets, one of
which is H = ιH = αH . Take β =
(
1 2 3
2 3 1
)
. As β ̸∈ H we have βH ̸= H and of
course βH = {β, βα} . We compute that βα =
(
1 2 3
2 1 3
)
. So let γ =
(
1 2 3
3 1 2
)
. As
γ ̸∈ H ∪ βH the remaining left H -coset is γH = {γ, γα} .
As a further exercise, you could write down the right H -cosets and observe, for example,
that βH ̸= Hβ .
Another observation you could make is that:
H consists of the permutations taking 1 7→ 1;
βH consists of the permutations taking 1 7→ 2;
γH consists of the permutations taking 1 7→ 3.
Find an exercise on the problem sheets which relates to this.
3 Homomorphisms
We have spent some time discussing groups. Now we briefly consider the appropriate maps
between groups. You should think about how this compares with what happens with vector
18
spaces where the most important maps between vector spaces are linear maps: the maps
which ‘respect’ the vector space structure.
Definition 3.1. Suppose (G, .) and (H, .) are groups.
(1) A function ϕ : G→ H is a homomorphism if for all g1, g2 ∈ G we have
ϕ(g1g2) = ϕ(g1)ϕ(g2).
[Note that on the left hand side here, the product g1g2 uses the group operation in G whereas
on the right-hand side, the product ϕ(g1)ϕ(g2) uses the group operation in H .]
(2) If ϕ : G→ H is a homomorphism, the image of ϕ is
imϕ = {ϕ(g) : g ∈ G}.
The kernel of ϕ is
kerϕ = {g ∈ G : ϕ(g) = eH}.
(3) If the homomorphism ϕ : G→ H is a bijection, then we say that ϕ is an isomorphism.
We say that groups G , H are isomorphic if there exists an isomorphism ϕ : G → H . In
this case we write G ∼= H .
If two groups are isomorphic, then, from the group theoretic viewpoint, they are really ‘the
same’ group with the elements labelled in a different way.
Before we give some examples, we note the following, which should remind you of basic
results (and their proofs) about linear maps.
Lemma 3.2. Suppose G,H are groups and ϕ : G→ H is a homomorphism. Then:
(i) ϕ(eG) = eH ;
(ii) ϕ(g−1) = (ϕ(g))−1 , for all g ∈ G;
(iii) imϕ ≤ H and kerϕ ≤ G.
Proof: (i) We have ϕ(eG) = ϕ(eGeG) = ϕ(eG)ϕ(eG). In H , the equation h = hh implies
h = eH , so we obtain ϕ(eG) = eH .
(ii) We have
eH
(i)
= ϕ(eG) = ϕ(gg
−1) = ϕ(g)ϕ(g−1)
and so the result follows.
(iii) Exercise: use 1.16. 2
Examples 3.3. (0) (Trivial examples) Suppose G is any group. The identity map i : G→ G
(with i(g) = g for all g ∈ G) is an isomorphism.
If G,H are groups, the map ψ : G→ H with ψ(g) = eH for all g ∈ G is a homomorphism.
19
(1) Suppose F is a field and G = GL(n, F ). The determinant map
det : G→ (F×, .)
is a homomorphism, by the product formula det(g1g2) = det(g1)det(g2).
(2) Suppose (H, .) is any group and h ∈ H . Define ϕ : (Z,+) → H by ϕ(n) = hn , for
n ∈ Z . By the rules for exponents, we know that
ϕ(m+ n) = hm+n = hmhn = ϕ(m)ϕ(n)
so ϕ is a homomorphism. The image of ϕ is ⟨h⟩ . If h has infinite order, then kerϕ = {0} .
If h has finite order n , then kerϕ = nZ , by 1.20(2).
(3) The exponential map
exp : (R,+)→ (R>0, .)
is a homomorphism as exp(x+ y) = exp(x) exp(y). As exp here is also a bijection, we have
that it is an isomorphism (which may be a bit of a surprise as we would not normally think
of the groups (R,+) and (R>0, .) as being ‘the same group’).
(4) The modulus map | · | : (C×, .)→ (R×, .) is a homomorphism with kernel
{z ∈ C× : |z| = 1} .
Lecture
17Again, the following lemma corresponds to things you already know about linear maps.
Lemma 3.4. Suppose G,H,K are groups.
(i) A homomorphism ϕ : G→ H is injective if and only if kerϕ = eG .
(ii) If ϕ : G→ H and ψ : H → K are homomorphisms, then the composition ψ◦ϕ : G→ K
is a homomorphism.
(iii) If ϕ : G → H is an isomorphism, then the inverse map ϕ−1 : H → G is also an
isomorphism. (So if G ∼= H , then H ∼= G.)
Proof: (i) ⇒: We know that ϕ(eG) = eH , so eG ∈ kerϕ . Injectivity tells us that |kerϕ| ≤ 1.
So we must have kerϕ = {eG} .
⇐: Suppose kerϕ = {eG} and ϕ(g1) = ϕ(g2). Then by 3.2, we have ϕ(g1g−12 ) = eH , thus
g1g
−1
2 = eG . So g1 = g2 .
(ii), (iii): Exercises. 2
The first part of the following completes the understanding of cyclic groups. Once you have
proved the 1st Isomorphism Theorem in year 2, you will be able to give a more elegant proof
using Example 3.3 (2).
Theorem 3.5. (1) Suppose G,H are cyclic groups of the same order. Then there is an
isomorphism α : G→ H .
(2) If V1, V2 are non-cyclic groups of order 4, then V1 ∼= V2 .
20
Proof: (1) Suppose G,H are finite, cyclic of order n with G = ⟨g⟩ and H = ⟨h⟩ . Define
α : G→ H by α(gk) = hk for k ∈ Z .
We need to check:
α is well-defined: if gk = gl , then hk = hl . To see this, use 1.20 and the fact that g, h both
have order n :
gk = gl ⇒ gl−k = eG ⇒ n | (l − k)⇒ hl−k = eH ⇒ hl = hk.
α is injective: All of the above arrows reverse!
α is surjective: By definition.
So α is a bijection and for all k, l ∈ Z we have:
α(gkgl) = α(gk+l) = hk+l = hkhl = α(gk)α(hk).
So α is also a homomorphism.
Now suppose G,H are of infinite order. The only think we need to change in the above
proof is when checking α is well-defined and injective. But in this case, if l ≥ k we have:
gk = gl ⇒ gl−k = eG
and so l = k as g is of infinite order. The same idea works when reversing the arrows to get
injectivity.
(2) So what we want to prove is:
Claim If V1, V2 are non-cyclic groups of order 4, then V1 and V2 are isomorphic.
Proof: Write the groups mulitplicatively and let V1 = {e, a, b, c} . As V1 is non-cyclic, there
is no element of order 4 in V1 . By 2.2, the order of an element divides 4, so each of a, b, c
has order 2. Now we show that ab = c . The reason is that all of the other possibilities lead
to a contradiction:
ab = a⇒ b = e ;
ab = b⇒ a = e ;
ab = e⇒ ab = e = a2 ⇒ b = a .
Similarly we obtain bc = a and ca = b . As V1 is abelian we therefore have the complete
‘multiplication table’ of V1 .
But now if we write V2 = {e′, a′, b′, c′} the same reasoning applies: so the nonidentity
elements are of order 2 and a′b′ = c′ etc. It follows that the map
e 7→ e′; a 7→ a′; b 7→ b′; c 7→ c′
is an isomorphism from V1 to V2 . 2
21
4 More on Sn
4.1 Disjoint cycle form
Recall that for n ∈ N we denote by Sn the group of all permutations on [n] = {1, 2, . . . , n}
(we did not use the notation [n] before, but it’s useful). The identity element of Sn is usually
denoted by ι , but you can call it e if you prefer.
Definition 4.1. Let f, g ∈ Sn and x ∈ [n] . We say that f fixes x if f(x) = x and f moves
x if f(x) ̸= x . The support of f is {y ∈ [n] : f(y) ̸= y} . This is denoted by supp(f).
We say that f, g have disjoint supports (or are disjoint) if supp(f) ∩ supp(g) = ∅ .
Note that as f is a bijection, if f(y) ̸= y then f(f(y)) ̸= f(y): so f(y) ∈ supp(f). Also
supp(f) = supp(f−1).
Example: (i) f =
(
1 2 3 4 5 6
1 4 3 6 5 2
)
; then supp(f) = {6, 4, 2} .
(ii) g =
(
1 2 3 4 5 6
3 2 5 4 1 6
)
; then supp(g) = {1, 3, 5} .
So f, g have disjoint supports.
Lemma 4.2. If f, g ∈ Sn have disjoint supports, then:
(i) fg = gf ;
(ii) For all m ∈ Z we have (fg)m = fmgm .
Proof: This was Question 7 on Problem sheet 5. 2
Definition 4.3. Let n ∈ N and r ≤ n . Suppose i1, . . . , ir ∈ [n] are distinct. If f ∈ Sn
fixes the other elements of [n] and
f(i1) = i2; f(i2) = i3; . . . , f(ir−1) = ir; f(ir) = i1,
then f is called an r -cycle (or a cycle of length r) and we write f as (i1, i2, i3, . . . , ir) or
(missing out the commas) (i1i2i3 . . . ir).
Examples 4.4. (1) f =
(
1 2 3 4 5 6
1 4 3 5 2 6
)
is a 3-cycle: f = (2, 4, 5) ∈ S6 .
Note that this is the same permutation as (4, 5, 2) ∈ S6 . Note also that it easy to compute
directly from the cycle that f 2 = (254) and f 3 = ι (the identity).
(2) (1234) ∈ S5 is the permutation
(
1 2 3 4 5
2 3 4 1 5
)
.
(3) A 1-cycle is the identity permutation!
22
(4) We multiply cycles as follows: remember they are permutations so they multiply like
composition of functions - you start at the right.
If f = (123) ∈ S6 and g = (4526) ∈ S6 , then
fg = (126453) and gf = (164523) (both in S6 ).
Note that we do not always end up with a cycle here:
taking (12) and (13425) in S6 we have:
(12)(13425) = (134)(25)(6) = (134)(25) as (6) is just the identity. Note that by Lemma 3.2,
we have (134)(25) = (25)(134) as the two cycles here have disjoint supports.
Have we simplified (12)(13425) by writing it as (134)(25)? Yes, because in the second of
these, the cycles are disjoint, so we can use Lemma 4.2 to compute powers. More on this
later. Lecture
18
(5) Note that when we write, say, f = (12345) ∈ S6 , the cycle goes from left to right, so
f(1) = 2 etc. Some books might use the same notation to mean f(2) = 1.... so be careful.
It is easy to write down the inverse of a cycle: you just write it out the other way. For
example if f = (12345) then f−1 = (54321). Think about why this is and write down a
proof using the definition:
Lemma 4.5. If f = (i1i2 . . . ir) ∈ Sn , then f−1 is the r -cycle g = (irir−1 . . . i2i1).
Proof: Check that for all x ∈ [n] we have f(g(x)) = x = g(f(x)). 2
The following result is important and generalises what was happening in Example (4) above:
writing a permutation as a product of cycles with disjoint supports. The method in the
proof is straightforward to apply, but the actual proof is a bit technical so we will leave it
until we have done some examples.
Theorem 4.6. If f ∈ Sn , then there exist cycles f1, f2, . . . , fk ∈ Sn with disjoint supports
such that f = f1f2 . . . fk .
Remarks: The condition on disjoint supports means that if 1 ≤ i < j ≤ k then supp(fi)∩
supp(fj) = ∅ . If we say that the fi are not 1-cycles (and assume f is not the identity
permutation) and also that supp(fi) ⊆ supp(f), then the representation of f as a product
of disjoint cycles is unique, up to rearranging the order of the disjoint cycles in the product.
We refer to this as the disjoint cycle form of f . A sketch proof of uniqueness is given
below.. There are interesting analogies between the result and the Fundamental Theorem of
Arithmetic, even though they are very different results.
Example: (i) Write
g =
(
1 2 3 4 5 6 7 8 9 10
4 5 1 10 9 3 8 7 2 6
)
23
in disjoint cycle form.
Solution: The method is to take an element and keep applying g to see what cycle it
produces. If all elements have been used, then we stop; otherwise we take an element not
appearing in the cycle and repeat. We keep doing this until there are no more elements left
to consider (or if there are only fixed points left to consider, which will only give us 1-cycles
and we can ignore these). Doing this we get:
g = (1, 4, 10, 6, 3)(2, 5, 9)(7, 8).
(I put the commas in because of the 10: (141063) might have been confusing.)
(ii) Compute g2 and g−1 .
Solution: Use 4.2: so writing g = g1g2g3 in disjoint cycle form we have
g2 = g21g
2
2g
2
3 = (1, 10, 3, 4, 6)(2, 9, 5)(7)(8)
(and we could miss out (7)(8)) and
g−1 = g−11 g
−1
2 g
−1
3 = (3, 6, 10, 4, 1)(9, 5, 2)(8, 7).
(iii) Let f = (2, 4, 6)(1, 3, 8)(9, 10) ∈ S10 . Compute fg in disjoint cycle form.
Solution: Apply the method to the product to get: fg = (1, 6, 8, 7)(2, 5, 10)(3)(4, 9) ∈ S10.
Now we can give:
Proof of Theorem 4.6: We prove the result by induction on m = |supp(f)| . If m = 0 then
f = ι = (1) and there is nothing to prove.
Assume m ≥ 1 (and therefore m ≥ 2 - think about why m = 1 cannot happen) and take
i1 ∈ supp(f). So f(i1) ̸= i1 . Let f(i1) = i2 , i3 = f(i2), . . . . Choose r as small as possible
with f(ir) ∈ {i1, . . . , ir−1} . Note that there is such an r with r ≤ n .
Claim: f(ir) = i1 .
Otherwise f(ir) = ij for some j with 2 ≤ j ≤ r − 1. So f(ir) = ij = f(ij−1) and therefore
(as f is injective) ir = ij−1 . But then f(ir−1) = ir ∈ {i1, . . . , ir−2} contradicting minimality
of r . 2Claim .
It follows that f = gf1 where f1 = (i1, i2, . . . , ir) and g has support supp(f) \ {i1, . . . , ir} .
By induction hypothesis we can write g = f2 . . . fk where f2, . . . , fk have disjoint supports.
So f = f2 . . . fkf1 , a product of cycles with disjoint supports. Note that f = f1f2 . . . fk , by
4.2. 24.6
Remarks: We can also prove the uniqueness of the expression of a permutation as a product
of disjoint cycles by induction on the size of the support:
Use the same notation as in the above proof and suppose we also have f = h1 . . . hl where
the hi are cycles with disjoint supports. We want to prove that k = l and the hi are a
24
rearrangement of the fj . Assume, inductively, this would be true for permutations with
smaller support size.
Let i1 ∈ supp(f). By rearranging the cycles if necessary we can assume that i1 is in the cycles
fk and hl . As in the above proof, let r be as small as possible with f
r(i1) = i1 . Then by the
argument in the proof of the claim in 4.6 we have fk = (i1, f(i1), f
2(i1), . . . , f
r−1(i1)) = hl .
We can therefore ‘cancel’ fk and hl in the two expressions for f and obtain f1 . . . fk−1 =
h1 . . . hl−1 . The inductive hypothesis then gives that k−1 = l−1, so k = l , and f1, . . . , fk−1
is a rearrangement of h1, . . . , hl−1 , as required.
4.2 Applications of disjoint cycle form
Remarks 4.7. Here’s another example of using the method in the proof of 4.6 to write down
disjoint cycle form.
f =
(
1 2 3 4 5 6
2 1 4 5 3 6
)
= (12)(345)(6).
This expression is unique up to missing out 1-cycles and rearranging the order: we also have
f = (345)(12). Note that we can also display the cycles in a number of ways: for example
(345) = (453) = (534).
Definition 4.8. The cycle shape of a permutation f ∈ Sn is the sequence of cycle lengths in
descending order, including repetitions and fixed points, when it is written in disjoint cycle
form.
Examples: (1) (12)(345)(6) ∈ S6 has cycle shape 3, 2, 1.
(2) (12)(345)(678)(9, 10, 11, 12)(13) ∈ S13 has cycle shape 4,3,3,2,1. We also abbreviate this
to (4, 32, 2, 1) to show that we have two 3-cycles; in this notation, the brackets are optional.
(3) The identity ι ∈ S9 has cycle shape 19 .
Examples 4.9. What are the possible cycle shapes of elements of S4? How many permu-
tations are there of each cycle shape?
Note: The number of r -cycles on a set of size r is 1
r
r! . This is because we have r! ways of
writing the r elements as a sequence i1, i2, . . . , ir and each r -cycle can be represented in r
different ways
(i1, i2, . . . , ir) = (i2, . . . , ir, i1) = . . . = (ir, i1, i2, . . . , ir−1).
Thus the number of distinct r -cycles on a set of size n ≥ r is(
n
r
)
1
r
r! =
n!
r(n− r)! .
(It’s probably better to understand the reasoning here than memorizing the formula.)
25
Back to the question:
We see that the possible cycle shapes correspond to the possible partitions of 4: that is, the
number of ways of writing 4 as a sum of a sequence of non-zero natural numbers. It’s easiest
to write these down starting with the biggest number.
The possibilities are:
(i) Cycle shape: 4; Example: (1234); Number of these: 3! = 6.
(ii) Cycle shape: 3,1; Example: (123)(4); Number of these: 4.2 = 8.
(iii) Cycle shape: 2,2; Example: (12)(34); Number of these: 1
2
(
4
2
)
= 3.
- Explanation of the counting: there are 4 choices for the first 2-cycle and then the remaining
2 elements form the other 2-cycle. But each permutation with this cycle shape is then chosen
twice as (12)(34) = (34)(12), so we divide by 2.
(iv) Cycle shape: 2, 1, 1; Example: (12)(3)(4); Number of these:
(
4
6
)
= 6
- note that the double-counting in the previous example does not occur here.
(v) Cycle shape: 1,1,1,1; this is the identity permutation and the number of these is 1.
Note that as a check we add up the possibilities: 6 + 8 + 3 + 6 + 1 = 24 = |S4|.
The following allows us to easily compute the order of a permutation from its cycle shape.
Theorem 4.10. Suppose g ∈ Sn is written in disjoint cycle form as g = g1g2 . . . gk where
gi is an ri -cycle (for i = 1, . . . , k) and g1, . . . , gk are disjoint. If m ∈ N, then:
(i) gm = gm1 g
m
2 . . . g
m
k ;
(ii) gm = ι⇔ gmi = ι for all i = 1, . . . , k .
(iii) The order of g is the least common multiple lcm(r1, . . . , rk) of the lengths of the disjoint
cycles in g .
(iv) g−1 = g−11 . . . g
−1
k .
Before giving the proof, we do some examples.
Examples 4.11. (0) We can write down the orders of the elements in S4 :
Cycle shape: 4; Example: (1234); order 4.
Cycle shape: 3,1; Example: (123)(4); order 3.
Cycle shape: 2,2; Example: (12)(34); order 2.
Cycle shape: 2, 1, 1; Example: (12)(3)(4); order 2.
Cycle shape: 1,1,1,1; order 1.
26
(1) (12)(345)(6789) ∈ S9 has order lcm(2, 3, 4) = 12.
(2) Find an element of order 15 in S9 : as 15 = lcm(5, 3, 1) and 9 = 5 + 3 + 1 we can write
down (12345)(678)(9) ∈ S9 .
(3) There is no element of order 20 in S8 .
To see this we need to show that there do not exist r1, . . . , rk ∈ N such that lcm(r1, . . . , rk) =
20 and
∑
i ri = 8. Suppose there are such ri . Then one of them would have to be divisible
by 5, and therefore be at least 5. One of them would have to be divisible by 4, and therefore
be at least 4. So the smallest possibility for having an element of order 20 is 9, not 8.
(Note: (12345)(6789) ∈ S9 has order 20.)
Proof of Theorem 4.10: (i) is an easy generalisation of Lemma 4.2 (ii).
(ii) ⇒ is by (i). For ⇐ , note that if gm = ι , then by (i) gm1 gm2 . . . gmk = ι . The permutations
gmi have disjoint supports (although they are not necessarily cycles) as the gi have disjoint
supports. So each gmi is the identity.
(iii) By (ii) gm = ι ⇔ gmi = ι for all i = 1, . . . , k. As gi is an ri -cycle, its order is ri .
Therefore gmi = ι⇔ ri|m . So the smallest m ∈ N with gm = ι is lcm(r1, . . . , rk).
(iv) We already know that g−1 = g−1k . . . g
−1
1 . Note that supp(gi) = supp(g
−1
i ) so g
−1
1 , . . . , g
−1
k
are disjoint and therefore commute. So g−1 = g−11 . . . g
−1
k . 24.10
4.3 Dihedral groups
Lecture
19Suppose n ∈ N and n ≥ 3. Informally, the dihedral group D2n is the group of symmetries
of a regular n-gon. This is a bit vague, so we shall think of the regular n-gon as centred
at 0 ∈ R3 and having vertices in the xy -plane, labelled 1, 2, . . . , n in a clockwise direction.
Every symmetry of the n-gon is determined by its effect on the set of vertices and of course
this is a permutation of the vertices. So we may think of the group of symmetries as a
subgroup of Sn .
First, we describe the symmetries geometrically:
(a) rotate about the axis (the z -axis) through 0 and perpendicular to the n-gon, through
an angle which is a multiple of 2π/n . There are n such rotational symmetries.
(b) (i) Case n odd: Flip (i.e. rotate by π ) the n-gon about an axis through 0 and a vertex
(we can also view this as a reflection in this axis).
(ii) Case n even: Flip about an axis through two opposite vertices - there are n/2 of these;
OR flip about an axis through the mid-points of two opposite edges - also n/2 of these.
Exercise: Draw some pictures for these in the cases n = 4 and n = 5.
The composition of two symmetries is another symmetry and each is invertible. Thus we
have a group of 2n different symmetries of the regular n-gon. As discussed above, we will
27
think of this as a subgroup of Sn (the group of all permutations of the vertices) and denote
it by D2n . It is called the dihedral group of order 2n . (Some books will denote it by Dn .)
We should justify why there are no more that the 2n symmetries listed above. It will be
enough to show:
Theorem 4.12. The group G ≤ Sn of permutations induced on the vertices of a regular
n-gon by symmetries of the n-gon has size 2n.
Proof: Note that as there is a rotation taking any vertex to any other vertex we have
{g(1) : g ∈ G} = [n] , the set of all vertices. By Question 8 on Sheet 7, we therefore have
|G| = n|H| where H = {g ∈ G : g(1) = 1} . But the only symmetries fixing the vertex 1
are the identity and the flip about the axis which passes through 0 and 1. So |H| = 2 and
|G| = 2n , as required. 2
The lecture could stop here, but maybe you think this is still too informal. In which case we
could make things completely precise, but less geometric, in the following way. The idea of
course is that a is the flip which fixes 1 and b is the flip which interchanges 1 and n .
Definition 4.13. Let n ∈ N with n ≥ 3. Consider the following elements of Sn in disjoint
cycle form:
a = (1)(2, n)(3, n− 1) . . .
and
b = (1, n)(2, n− 1) . . . .
(The precise formulas will depend on whether n is odd or even. If you wish, you can write
out the two cases separately, but do the exercise below first.) We define the dihedral group
D2n to be D2n = ⟨a, b⟩ ≤ Sn .
Exercise: Write these out for the cases n = 4 and n = 5.
If you did the exercise, then you should be able to see that a and b are both permutations of
the vertices of the n-gon which are induced by symmetries. So to justify why ⟨a, b⟩ contains
all symmetries, and therefore why the definition is reasonable, we prove:
Theorem 4.14. We have |⟨a, b⟩| = 2n.
Proof: Clearly a, b are of order 2. So by Question 5 of Sheet 8, it will suffice to prove that ab
is of order n . But ab is the cycle (123 . . . n) (not completely trivial to prove: you would have
to check the cases n odd or even separately if you wanted to avoid geometric arguments,
but check it for the cases n = 4, 5). So we are done. 2
4.4 The sign of a permutation; Determinants again
Lecture
20[On the MathSoc website, you should be able to find Professor Buzzard’s M2PM2 (Algebra
2) notes from 2014. He probably also has a webpage with these on. Section 3 of the notes
28
has material about the sign (or signature) of a permutation; section 7 gives an alternative
way of doing determinants using this.]
In Question 3 of Problem Sheet 8, we see that every permutation in Sn can be written as a
product of 2-cycles. For example:
(123) = (12)(23)
(1234) = (12)(23)(34)
...
(1234 . . . r) = (12)(23) . . . (r − 1, r).
There is no uniqueness to the factorisation here: the 2-cycles are not assumed to be disjoint.
The number of 2-cycles used can vary: for example
(123) = (13)(32)(13)(32).
However, we will see that, for any particular permutation, the number of 2-cycles used is
either always odd, or always even.
To prove this, we are going to define a very special homomorphism sgn : Sn → {1,−1} . The
group on the right here is considered under multiplication: it is of course a cyclic group of
order 2. We might denote it by ±1 if we get bored with set brackets. The homomorphism
will be non-trivial if n ≥ 2.
Some people call sgn(f) the signature of f ∈ Sn ; others call it the signum of f . I will call
it the sign of f . The definition will involve a small detour involving polynomials in several
variables.
Let n ∈ N with n ≥ 2. Let x1, . . . , xn be variables. If P (x1, . . . , xn) is any polynomial
in variables x1, . . . , xn and f ∈ Sn , then we define f(P ) to be the polynomial obtained by
permuting the variables using f : so xi is replaced by xf(i) .
Example: Suppose n = 3. Consider the permutations f = (123) and g = (12) ∈ S3 . Let
P (x1, x2, x3) = 3x
2
1 − 2x1x3 . Then:
fP is the polynomial 3x22 − 2x2x1 ;
g(fP ) is the polynomial 3x21 − 2x1x2 .
Notice that (gf) = (1)(23) and so:
(gf)P is the polynomial 3x21 − 2x1x2 . Thus (gf)P = g(fP ).
More generally we have:
Lemma 4.15. For all f, g ∈ Sn and polynomials P in variables x1, . . . , xn we have:
(i) If α ∈ R, then: f(αP ) = αf(P ).
(ii) g(f(P )) = (gf)(P ).
Proof: (i) This should be clear.
(ii) To compute g(f(P )) we make the successive substitutions
xi 7→ xf(i) 7→ xg(f(i)),
29
the first gives us f(P ) and the second gives g(f(P )). But this is also what we would get by
making the substitution xi 7→ x(gf)(i) and this is (gf)(P ). 2
Now we focus on the polynomial (over R) ∆ = ∆(x1, . . . , xn) given by the product of all
expressions (xi − xj) with 1 ≤ i < j ≤ n :
∆ =
∏
1≤i(xi − xj).
You may remember that you have seen this expression before in the Vandermonde determi-
nant.
Example: If n = 3 and f = (123) then ∆ = (x1 − x2)(x1 − x3)(x2 − x3) and f(∆) =
(x2 − x3)(x2 − x1)(x3 − x1) = ∆ (as there have been two changes of sign here).
If g = (12) ∈ S3 then g(∆) = (x2 − x1)(x2 − x3)(x1 − x3) = −∆ (there is one change of
sign).
Lemma 4.16. For any n ≥ 2 and f ∈ Sn , either f(∆) = ∆ or f(∆) = −∆.
Proof: If k ̸= l we have a factor ±(xk − xl) appearing exactly once in f(∆). It comes from
the factor ±(xi − xj) in ∆, where {i, j} = {f−1(l), f−1(k)} . 2
Definition 4.17. With this notation, we let sgn(f) = 1 if f(∆) = ∆ and sgn(f) = −1 if
f(∆) = −∆. Thus f(∆) = sgn(f)∆.
Now we have the main result:
Theorem 4.18. Suppose n ≥ 2 and f, g ∈ Sn .
(i) We have sgn(fg) = sgn(f)sgn(g), so sgn : Sn → ±1 is a homomorphism.
(ii) If f is a 2-cycle, then sgn(f) = −1.
(iii) If g is an r -cycle, then sgn(g) = (−1)r−1 .
Note that using this it is easy to compute the sign of any h ∈ Sn . We write h in disjoint
cycle form as h = h1h2 . . . hk . Using (i), sgn(h) = sgn(h1)sgn(h2) . . . sgn(hk), and (iii) tells
us how to compute each of the sgn(hi).
Example: Let h = (123)(45)(6789) ∈ S9 . Then sgn(h) = (−1)2(−1)1(−1)3 = 1.
Proof of 4.18 :
(i) We have
(gf)(∆)
4.15(ii)
= g(f(∆))
def
= g(sgn(f)∆)
4.15(i)
= sgn(f)g(∆) = sgn(f)sgn(g)∆.
But also (gf)(∆) = sgn(gf)∆. So sgn(gf) = sgn(f)sgn(g) = sgn(g)sgn(f).
30
(ii) First we note that if f = (12), then f(∆) = −1 as the only factor in ∆ which changes
sign is (x1 − x2).
Now suppose 1 ≤ i < j ≤ n and consider the 2-cycle (ij). There is some k ∈ Sn with
k(i) = 1 and k(j) = 2. Then one computes that k−1(12)k = (ij) (Exercise!) But then by
(i),
sgn((ij)) = sgn(k−1)sgn((12))sgn(k) = sgn((12)) = −1.
(Using that ±1 is an abelian group.)
[There is a different proof of this in Professor Buzzard’s notes.]
(iii) An r -cycle g can be written as a product of r−1 2-cycles: see the solution to Question
9(i) on Sheet 8. So by (i) and (ii), sgn(g) = (−1)r−1. 2
Remarks 4.19. (1) A permutation f ∈ Sn is called even if sgn(f) = 1 and odd if sgn(f) =
−1. This is a bit confusing because a cycle of odd length is an even permutation etc.
The set of even permutations in Sn is a subgroup of Sn (it is the kernel of the homomorphism
sgn) called the alternating group An . If n ≥ 2, then the index of An in Sn is 2: the two
cosets are An and the set of odd permutations (Ex: prove this!).
(2) By the solution to Question 3(ii) on sheet 8, every permutation g ∈ Sn can be written
as a product of 2-cycles. There is no uniqueness statement here, but because of the sgn
function, the parity of the the number of 2-cycles needed cannot be changed for g : we need
an even number of 2-cycles if g is an even permutation and an odd number of 2-cycles if g
is an odd permutation. This explains the terminology (partly).
Now we can give another expression for the determinant of a matrix A = (aij) ∈ Mn(F )
(where F is a field).
Theorem 4.20. For every matrix A = (aij) ∈Mn(F ) we have:
det(A) =
∑
f∈Sn
sgn(f)a1f(1)a2f(2) . . . anf(n).
So this is a sum of n! terms each one of which is a product of n entries of A where there is
exactly one entry from each row and column.
Exercise: Write out the above formula in the cases n = 2 and n = 3 and compare with
the usual expressions you know for det in these cases.
Professor Buzzard’s notes take this formula as the definition of the determinant. He then
proves that determinants can be computed by first-row expansion (Proposition 7.5 of his
notes). So this gives a proof of the above Theorem. I will sketch a proof of the Theorem
which is independent from Professor Buzzard’s notes If you want to understand it, it might
help to write it out in the case n = 3, checking all of the assertions.
Sketch of proof of Theorem:
31
Before we start, note that the set of even permutation in Sn is the subgroup An and if g is
any odd permutation, then gAn = Sn \An = Ang (compare Question 6 on probelm sheet 7,
or you can prove this directly). In particular, any odd permutation h can be written in the
form h = fg for some unique even permutation f = hg−1 .
For A = (aij) ∈Mn(F ), write
det′(A) =
∑
f∈Sn
sgn(f)a1f(1)a2f(2) . . . anf(n).
We want to show that det′(A) = det(A). Recall that det is the unique function Mn(F )→ F
satisfying the properties D1, D2, D3, D4 (as in Section 5.1 of Linear Algebra notes; compare
with Exercise 1 on Sheet 2). It is not hard to show that det′ satisfies D1, D2, D4, so it is
enough to prove that det′ satisfies D3. In other words, we have to show that if A has two
consecutive rows equal then det′(A) = 0. To simplify the notation, assume that rows 1 and
2 of A are equal, so a1j = a2j for all j ≤ n .
Let g ∈ Sn be the permutation g = (12). This is an odd permutation so Sn = An ∪ Ang
and thus
det′(A) =
∑
f∈An
sgn(f)a1f(1)a2f(2) . . . anf(n) +
∑
f∈An
sgn(fg)a1fg(1)a2fg(2) . . . anfg(n).
Now, sgn(fg) = −sgn(f) = −1 and g(1) = 2, g(2) = 1, g(3) = 3, . . . , g(n) = n . So
det′(A) =
∑
f∈An
a1f(1)a2f(2) . . . anf(n) −
∑
f∈An
a1f(2)a2f(1)a3f(3) . . . anf(n).
As a1f(2) = a2f(2) and a2f(1) = a1f(1) , we obtain det
′(A) = 0. 2
A different sketch roof: If f ∈ Sn let Mf be the n × n matrix with ij entry equal to 1 if
j = f(i) and 0 otherwise. Note that another way of thinking of this is that Mf is obtained
from the identity matrix In by applying the permutation f
−1 to the rows of In : so row i of
In is row f
−1(i) of Mf . (As an exercise, check this with f = (123) ∈ S3 ).
Let A(f) be the n× n matrix with ij entry equal to aif(i) if j = f(i) and 0 otherwise. So
det(A(f)) = a1f(1)a2f(2) . . . anf(n)det(Mf ).
We can use the linearity property (D2) of determinants (and other properties in 5.1.4 - 5.1.8)
to show that
det(A) =
∑
f∈Sn
det(A(f)).
So it remains to prove that det(Mf ) = sgn(f). We obtain Mf from In by applying the
permutation f−1 to the rows of In . Write f−1 as a product of 2-cycles g1 . . . gk . When
we apply this to the rows of In we are doing k elementary row operations, each of which
interchanges two rows. So det(Mf ) = (−1)kdet(In) = (−1)k . But also sgn(f) = sgn(f−1) =
(−1)k as f−1 is a product of k 2-cycles. Hence the result. 2
32