MATH08064

Fundamentals of Pure Mathematics

Algebra

Lecture notes by Clark Barwick, Tudor Dimofte, Ana Rita Pires,

Brent Pym, Sue Sierra, and Michael Wemyss
2

ˆ The course follows closely the book

[J] Groups by Jordan and Jordan.

ˆ References to the above book in these notes will be abbreviated by [J]; for
example [J, §1.2] refers to section 1.2, whilst [J, Ex.7.4] refers to Exercise 4
in Section 7. When revision of some first year topics is required, your first
year book

[L] A Concise Introduction to Pure Mathematics by Liebeck

will be referenced.

ˆ Throughout the semester, all course materials will be available from the course
LEARN page.

ˆ In the notes there are some paragraphs inside large squares. These correspond
to proofs and computations that we encourage to try to do on your own
before reading. Similary, we encourage you to try to solve the Check Your
Understanding exercises before reading their solutions. This is a very good
way to cement your understanding of the material.
Contents

0 Revision 5
0.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2 Making counting arguments rigorous . . . . . . . . . . . . . . . . . 6
0.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1 Symmetries and Groups 17

1.1 Symmetries of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Groups and Examples . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Symmetries give groups . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4 Product groups and first properties of groups . . . . . . . . . . . . 31
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2 Subgroups and Lagrange’s Theorem 41

2.1 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Orders of elements and cyclic subgroups . . . . . . . . . . . . . . . 44
2.3 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3 Going between Groups 61

3.1 Homomorphisms and Isomorphisms . . . . . . . . . . . . . . . . . . 61
3.2 Products and Isomorphisms . . . . . . . . . . . . . . . . . . . . . . 64
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4 Groups Acting 69
4.1 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 Orbits and Stabilizers . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 The Orbit-Stabilizer Theorem . . . . . . . . . . . . . . . . . . . . . 75
4.4 First applications of the Orbit-Stabilizer Theorem . . . . . . . . . . 77
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3
4 CONTENTS

5 Counting and Cayley 83

5.1 Pólya counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Conjugacy and the class equation . . . . . . . . . . . . . . . . . . . 86
5.3 Conjugacy in Sn is determined by cycle type . . . . . . . . . . . . . 90
5.4 Actions, homomorphisms, and Cayley’s Theorem . . . . . . . . . . 94
5.5 Application to Platonic solids . . . . . . . . . . . . . . . . . . . . . 96
5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapter 0

Revision

We need the following first year material, and will use it extensively throughout.
We will revise other first year material as we require it.

0.1 Functions
We need everything in [L, §19], so you are strongly recommended to review this
material. It is also contained in [J, §2.2]. As notation, in this course we will write
a function f from X to Y as f : X → Y . Further, we will write the composition of
functions f : X → Y and g : Y → Z as g ◦ f , so g ◦ f means ‘do f first, then g ’.
Definition 0.1.1. A function f : X → Y is called
ˆ injective if f (x1 ) = f (x2 ) implies that x1 = x2 (equivalently, if x1 ̸= x2 then
f (x1 ) ̸= f (x2 )).
ˆ surjective if for every y ∈ Y , there exists x ∈ X such that f (x) = y .
ˆ bijective if it is both injective and surjective.
If f is bijective, we denote its inverse function by f −1 .
An easy way to remember this is via the pictures

∃x y

X Y X Y X Y
injective surjective bijective
‘don’t lose information’ ‘hits everything’ ‘the same’

5
6 CHAPTER 0. REVISION

One key property of functions is that

(h ◦ g ) ◦ f = h ◦ (g ◦ f ).
This is easy to verify; see for example [J, p15].

0.2 Making counting arguments rigorous

We use counting arguments all the time, and we are often satisfied with a relatively
informal style when we give them. We often say things like, ‘you’re choosing 5
things, and those choices are independent.’ That’s perfectly fine, particularly in a
short argument, but what does ‘independent’ really mean?
This isn’t just an academic question. In the course of a complex argument, it can
be surprisingly tricky to know whether this sort of ‘independence’ argument is really
valid. One of the goals in this course is to make sure you know precisely what’s
behind these sorts of claims and that you can carefully check their correctness.
Here is the source of all our counting arguments.
Theorem 0.2.1. Let S and T be two finite sets. Let f : S → T be a map. Then
the cardinality of S is equal to the sum, over elements t of T , of the cardinalities
of the inverse images f −1 ({t}) ⊆ S:
X
|S| = |f −1 ({t})| .
t∈T

Proof. Recall that for any element t ∈ T , the set f −1 ({t}) is the set of elements
s ∈ S such that f (s) = t; it’s a subset of S. Since every element of S must be
carried, under f , to some element of T , it follows that S is equal to the union of
all the subsets f −1 ({t}): [
S= f −1 ({t}) .
t∈T

Furthermore, if t1 , t2 ∈ T are two distinct elements (so that t1 ̸= t2 ), then the

subsets f −1 ({t1 }) and f −1 ({t2 }) are disjoint; that is, f −1 ({t1 }) ∩ f −1 ({t2 }) = ∅.
(Indeed, if s were an element of both f −1 ({t1 }) and f −1 ({t2 })), then t1 = f (s) =
t2 , and that’s what we just said wasn’t true!) We say that S is the disjoint union
of the various subsets f −1 ({t}). The theorem now follows from [L, 17.2].
Corollary 0.2.2. Let S and T be two finite sets. Then |S × T | = |S||T |.
Proof. Recall that S × T is the set of pairs (s, t), where s ∈ S and t ∈ T . So
we can define a function p : S × T → S by sending (s, t) 7→ s. Now the for any
s ∈ S, the inverse image p −1 ({s}) is the set of pairs (s, t) with t ∈ T . In order to
apply Theorem 0.2.1 to the map p, we just need to compute |p −1 ({s})| for each
s ∈ S. To do that, let’s look at the map q : p −1 ({s}) → T that sends (s, t) 7→ t.
Note that it is a bijection. (Why?) Hence |p −1 ({s})| = |T | for any s ∈ S. Now
we conclude X X
|S × T | = |p −1 ({s})| = |T | = |S||T | ,
s∈S s∈S
0.2. MAKING COUNTING ARGUMENTS RIGOROUS 7

just as we suspected.

Check Your Understanding. If S and T are finite sets, then how many maps are
there S → T ?

Corollary 0.2.3. Let S and T be two finite sets, and let f : S → T be a map. If
f is an injection, then |S| ≤ |T |. If f is a surjection, then |S| ≥ |T |. If f is an
bijection, then |S| = |T |.

Proof. This is because f is an injection if and only if, for any t ∈ T , one has
|f −1 ({t})| ≤ 1, and f is an surjection if and only if, for any t ∈ T , one has
|f −1 ({t})| ≥ 1.

Example 0.2.4. Let S and T be two finite sets, and assume that |S| > |T |. Let
f : S → T be any map. Then f isn’t injective; in other words, there exist two
elements s1 , s2 ∈ S that have the same value under f , so that f (s1 ) = f (s2 ). This
is sometimes called the pigeonhole principle.

Definition 0.2.5. For any two sets S and T , let us write Σ(S, T ) for the set of
bijections S → T .

The previous corollary implies that if S and T have different cardinality, then
Σ(S, T ) is empty. On the other hand, if S and T have the same cardinality, then
we can use Theorem 0.2.1 to compute the cardinality Σ(S, T ).
Before we give this result and its precise proof, we should give an informal
argument. When |S| = |T | = n, what does it take to specify a bijection f : S → T ?
For each element s ∈ S, you have to give a value f (s) ∈ T , but you have to do so
in such a way that you never repeat any value. So if you start with some element,
call it s1 , of S, then you may choose any value you like of T ; you have n options.
But then for the next element you take, s2 , you can choose any element of T other
than f (s1 ) as your value for f (s2 ); you have n − 1 options. This process continues,
and in the end you’re left with n(n − 1)(n − 2) · · · 1 = n! options for how to specify
your bijection. Now, how do we formalise this? Well, as a rule, any time we use
the phrase ‘and so on’ or ‘this process continues’, what we’re really doing is an
induction argument.

Theorem 0.2.6. Let S and T be two finite sets, and assume that |S| = |T | = n.
Then there are n! bijections S → T .

Proof. Let us induct on n. When n = 1, there is a unique map S → T , and it is a

bijection. Thus |Σ(S, T )| = 1 = 1!.
Now assume that the theorem holds for n = k−1; we aim to prove it when n = k.
So assume that S and T each have cardinality k, and choose an element s ∈ S,
which we’ll leave fixed for the rest of the proof. Define a map e : Σ(S, T ) → T by
the rule
e(f ) = f (s) .
To compute the cardinality of Σ(S, T ), we want to compute the cardinality of the
inverse images e −1 ({t}), and then employ Theorem 0.2.1. Now for any t ∈ T , the
8 CHAPTER 0. REVISION

set e −1 ({t}) is the set of bijections f : S → T such that f (s) = t. For any t ∈ T ,
if g : S − {s} → T − {t} is a bijection, then we can define a bijection G : S → T
by the rule (
g (x) if x ̸= s ;
G (x) =
t if x = s .

This defines a bijection Σ(S − {s}, T − {t}) → e −1 ({t}). By our induction hy-
pothesis, |Σ(S − {s}, T − {t})| = (k − 1)!, so |e −1 ({t})| = (k − 1)! Now Theorem
0.2.1 implies that
X X
|Σ(S, T )| = |e −1 ({t})| = (k − 1)! = k(k − 1)! = k! ,
t∈T t∈T

as claimed.

0.3 Permutations
A permutation is a bijection from a set to itself. In this section, we’re going to
compute the number of permutations of a set X , we’re going to show how to
compose permutations, and we’re going to show that permutations have inverses.
This material is all revision from Proofs and Problem Solving.

Definition 0.3.1. A permutation of a finite set X is a bijection X → X . We write

Sn for the set of permutations of {1, 2, ... , n}.

What’s the point of considering permutations instead of general bijections? The

biggest value is that it is possible to compose permutations: if f and g are permu-
tations X → X , then so is the composition gf , where

(gf )(s) = (g ◦ f )(s) = g (f (s)).

This is called the product permutation.

Check Your Understanding. Hey, wait a minute. Why is it that if you compose
two permutations, you get another permutation?

Example 0.3.2. Every set X has a special permutation, called the identity e : X →
X . This sends s 7→ s. Please note thet for any other permutation σ : X → X , we
have
es = s and se = s .
Example 0.3.3. Here’s an element σ ∈ S3 :

1 7→ 3 , 2 7→ 2 , 3 7→ 1 .

Here’s another, which we’ll call τ :

1 7→ 2 , 2 7→ 3 , 3 7→ 1 .
0.3. PERMUTATIONS 9

Let’s compose! Here’s στ :

1 7→ 2 , 2 7→ 1 , 3 7→ 3 .

Here’s τ σ:
1 7→ 1 , 2 7→ 3 , 3 7→ 2 .
Please note that στ ̸= τ σ. This product is not commutative!
Example 0.3.4. To try to make things a little easier for ourselves, we can use the
following ‘array’ notation for permutations: the ‘array’ notation where an element
σ ∈ Sn is specified by the 2-row array
 
1 2 ... n
.
σ(1) σ(2) ... σ(n)
Thus the elements of S3 from the previous example can be written
       
1 2 3 1 2 3 1 2 3 1 2 3
σ= , τ= , στ = , τσ = .
3 2 1 2 3 1 2 1 3 1 3 2
Example 0.3.5. Here’s an element
 
1 2 3 4 5 6
σ= ∈ S6
3 5 2 4 6 1
Let’s take powers of σ.
 
2 1 2 3 4 5 6
σ = σσ =
2 6 5 4 1 3
 
1 2 3 4 5 6
σ 3 = σσσ =
5 1 6 4 3 2
 
1 2 3 4 5 6
σ4 =
6 3 1 4 2 5
Now σ 5 turns out to be the identity permutation e! In this case, we say that σ has
order 5.
Definition 0.3.6. More generally, if σ : X → X is a permutation, then the order
of σ is the smallest natural number k > 0 such that σ k = e.
Proposition 0.3.7. Every element of Sn has a finite order.
Proof. Let σ ∈ Sn be a permutation. Define a function

N = {1, 2, ... } → Sn

that carries i to σ i . Since N is infinite but Sn is finite, this map cannot be injective.
Hence there exist two natural numbers 0 < i < j such that σ i = σ j . So of course
j − i > 0, and for any x ∈ {1, ... , n}, note that

σ i (x) = σ j (x) = σ i (σ j−i (x)) .

10 CHAPTER 0. REVISION

Since σ i is a bijection, it follows that x = σ j−i (x). But since this is true for every
x ∈ {1, ... , n}, we deduce that σ j−i = e. Now since there exists a positive natural
number k such that σ k = e, there must also exist a smallest such positive natural
number.

It can be a bit of a drag to write a permutation down explicitly. After all,

to write an element σ of Sn , you somehow have to be able to list all n of the
values σ(1), σ(2), ... , σ(n). Sometimes, your permutation doesn’t actually change
the value, so you’re there writing σ(x) = x. People who work with permutations a
lot deal with this by using a particular notation, called the cycle notation. To start,
you specify a k-cycle in Sn by giving a sequence

(a1 a2 · · · ak )

of k distinct elements of {1, ... , n}. The corresponding element of Sn is the unique
permutation σ of {1, ... , n} such that

ai+1 if x = ai for 1 ≤ i ≤ k − 1 ;

σ(x) = a1 if x = ak ;

x otherwise.


We just write
σ = (a1 a2 · · · ak ) .
Let’s illustrate with examples.
Example 0.3.8. When we write the 3-cycle (1 3 4) ∈ S5 , we mean the permutation
 
1 2 3 4 5
3 2 4 1 5

This cycle is equal to (4 1 3) and (3 4 1); these are three ways of writing the same
thing.
Similarly, when we write the transposition (2 5) ∈ S5 , we mean the permutation
 
1 2 3 4 5
1 5 3 4 2

This cycle is equal to (5 2)

So cycle representations are not quite unique, but they’re pretty close! Note
also that a k-cycle always has order k.
Example 0.3.9. Let’s say you wanted to write the permutation σ ∈ S5 given by
 
1 2 3 4 5
σ=
3 5 4 1 2

in cycle notation. That is, you want to write this permutation as a product of
cycles. What you do is you follow what’s called the orbits of the elements. (We’ll
0.3. PERMUTATIONS 11

talk more about orbits later.) So σ carries 1 to 3, and it carries 3 to 4, and it carries
4 to 1; so σ involves the cycle (1 3 4). But that’s not all σ does: it also carries 2
to 5 and 5 back to 2; thus σ also involves a 2-cycle (2 5) – aka a transposition.
Since that accounts for all the elements, our σ is written as a product

σ = (1 3 4)(2 5) = (2 5)(1 3 4) .

Check Your Understanding. The last example illustrates a phenomenon. If

{a1 , ... , ak } and {b1 , ... , bl } are two disjoint subsets of {1, ... , n}, then we say that
the cycles σ = (a1 · · · ak ) and τ = (b1 · · · bl ) are disjoint. In this case, one has

στ = τ σ .

Why?
Example 0.3.10. You cannot expect cycles to commute unless they are disjoint. To
see this, let’s look at the transpositions (1 2) and (2 3) in S3 . One one hand we
have
(1 2)(2 3) = (1 2 3) ,
but on the other, we have
(2 3)(1 2) = (1 3 2) .
It turns out that any element of Sn can be written as a product of disjoint
cycles. This representation is not quite unique, but it’s close: the only obstacles to
unicity are that you can write the products in a different order, or you can cyclically
permute the entries of any cycle.
For counting purposes, it’s often convenient to require that the first entry of
any cycle is as small as possible, and that the factors in a product of disjoint cycles
are ordered by that first entry, from smallest to largest. So if you take the product

(4 6 2)(1 3 9) ∈ S9 ,

then you can rewrite it in ‘standard’ form it as

(1 3 9)(2 4 6) .

Now every element of Sn can be written as a product of disjoint cycles in this

standard form in a unique fashion.
Example 0.3.11. Let’s write all six of the permutations of {1, 2, 3} in cycle notation.
ˆ First we have the identity, which carries everything to itself. This is hard
to write in cycle notation, since nothing’s really happening; so for lack of
anything better to do, we just call the identity permutation as e.
ˆ Now we have three transpositions:

(12) , (13) , (23) .

Note that (32) is just another way of writing (23).

12 CHAPTER 0. REVISION

ˆ And lastly, we have two 3-cycles:

(123) , (132) .

Example 0.3.12. Let’s write all 24 of the permutations of {1, 2, 3, 4} in cycle nota-
tion.

Example 0.3.13. Now let’s write all 120 of the permutations of {1, 2, 3, 4, 5} in
cycle notation.
Oof . . . actually . . . let’s not. Let’s see if we can account for all of them by
thinking through how we’d go about listing them all if we had to, though.

ˆ We have one identity permutation, as always.

ˆ A transposition (ab) – where we might as well require that

a < b – is uniquely
determined by selecting two elements. So there are 52 = 10 of those.

ˆ For any triple of numbers a < b < c, there are
two 3-cycles with these
numbers: (abc) and (acb). Therefore, there are 2 53 = 20 of those.
0.4. EXERCISES 13

ˆ For any quadruple of numbers a < b < c < d, to pick out a 4-cycle, you start
with a, and then
there is a unique 4-cycle with any ordering of b, c, and d.
So there are 6 54 = 30 of those.

ˆ For a 5-cycle in Σ5 , one simply chooses an ordering of 2, 3, 4, 5. So there are

24 of those. So far, that accounts for 85 of the 120 permutations in Σ5 .

ˆ To get the remaining ones, we have to contemplate compositions. A nontrivial

product (ab)(cd) of transpositions is uniquely


determined by choosing two
disjoint pairs of numbers. There are 21 54 42 = 15 of those.

ˆ Finally, a nontrivial product (abc)(de) of a 3-cycle with a transposition is

determined by the 3-cycle alone. These are the last 20 permutations.

Example 0.3.14. In general, the number of k-cycles in Σn is

 
n n(n − 1)(n − 2) · · · (n − k + 1)
(k − 1)! = .
k k

Can you prove this (say, by induction)?

There is one more thing you can do with permutations. You can invert them. If
σ : X → X is a permutation, then you can define σ −1 : X → X as the function that
carries an element x ∈ X to the unique element σ −1 (x) such that σ(σ −1 (x)) = x.
In other words, since σ is a bijection, the inverse image σ −1 {x} ⊆ X has exactly
one element, and σ −1 (x) is that element.
The inverse of σ is thus the unique permutation σ −1 such that σσ −1 = σ −1 σ =
e.
Example 0.3.15. Any transposition (in any Sn ) is its own inverse: (a b)−1 = (a b).
Example 0.3.16. More generally, if you take a cycle

σ = (a1 a2 · · · ak ) ,

then its inverse can be obtained by reversing the entries:

σ −1 = (ak ak−1 · · · a1 ) = (a1 ak ak−1 · · · a2 ) .

So, for instance

(1 2 3)−1 = (1 3 2) , and (1 2 3 4 5 6)−1 = (1 6 5 4 3 2) .

0.4 Exercises
Exercise on functions (revision)

Exercise 0.1. We often take functions for granted, but this is dangerous. Are the
following functions?
14 CHAPTER 0. REVISION

1. f : Z → Z sending a 7→ a + 2.
a a
2. f : Q → Q sending b 7→ b + 2.
a
3. f : Q → Z sending b 7→ a + b.
4. f : Z × Z → Z sending (a, b) 7→ a + 2.

5. f : Q × Z → Q sending ( ba , z) 7→ a
bz + 2.
6. f : Q × Q → Q sending ( ba , dc ) 7→ a
b + dc .
7. f : Q × Q → Q sending ( ba , dc ) 7→ a+c
b+d .

Remark: You will see that not all of the examples above are functions. In this
situation, where we have written down something that looks like the definition of a
function but that does not actually define a function, mathematicians often say “f
is not well-defined.”
Chapter 1

Symmetries and Groups

You are advised to read [J, §1]. Beware that it is an introductory chapter and so
many things will only fully make sense later! The theme of [J, §1], and this first
chapter, is the slogan ‘symmetries give groups’.

1.1 Symmetries of graphs

This section is a little more general than [J, §1.1], and will generate us many, many
examples.
Definition 1.1.1 (similar to [L, §9]). A graph is a finite set of vertices joined by
edges. We will assume that there is at most one edge joining two given vertices
and no edge joins a vertex to itself. The valency of a vertex is the number of edges
emerging from it.
Example 1.1.2. The following are graphs.

(a) (b) (c)

(d) (e) (f )

The following are not graphs.

(g) (h)

15
16 CHAPTER 1. SYMMETRIES AND GROUPS

Note that the definition of a graph only refers to the set of vertices, and to
which pairs of vertices are joined by an edge. Thus it is possible to draw the same
graph in many different ways. For instance, if we take graph (c), rotate it, and
stretch the triangles, we get a picture of a graph with the same essential structure:

(c ′ )

The vertices in the two pictures are in one-to-one correspondence with each other,
and so are the edges that join them.
This sort of situation—where two seemingly different objects have the same
structure—is so prevalent in mathematics that there is a special word we use when-
ever the situation arises: that word is isomorphism from the Greek “isos” (equal)
and “morphe” (form). This word appears in many different contexts (we will see
another one later in the course), but in the specific context of graphs, we can
formulate the notion precisely as follows:

Definition 1.1.3. An isomorphism between two graphs is a bijection between them

that preserves all edges. More precisely, if Γ1 and Γ2 are graphs, with sets of vertices
V1 and V2 , respectively, then an isomorphism from Γ1 to Γ2 is a bijection

f : V1 → V2

such that f (v1 ) and f (v2 ) are joined by an edge if and only if v1 and v2 are joined
by an edge.
We say that Γ1 and Γ2 are isomorphic if there exists an isomorphism f : Γ1 → Γ2 .

Example 1.1.4. Let’s prove mathematically that the graphs (c) and (c’) are really
isomorphic.
To do this, let’s give their vertices names:

1 4
D

A C

B
2 3

(c) (c ′ )

Thus the two sets of vertices are V = {1, 2, 3, 4} and V ′ = {A, B, C , D}. Let us
define a function f : V → V ′ by the following rules:

f (1) = A, f (2) = B, f (3) = C , f (4) = D.

Then f describes what happens to the vertices under our operation of rotating and
stretching. Let us check that f does indeed satisfy the axioms of an isomorphism.
1.1. SYMMETRIES OF GRAPHS 17

Example 1.1.5. We get another bijection if we swap the even-numbered vertices,

so that
f (1) = A, f (2) = D, f (3) = C , f (4) = B.
In the picture, this has the effect of doing a vertical reflection after we rotate and
stretch, so it also preserves edges. We can check it carefully by going through all
pairs of edges as before.
Example 1.1.6. In contrast, the function f : V → V ′ defined by f (v ) = A for all
v ∈ V is not an isomorphism since it is not a bijection. Meanwhile, the function
defined by
f (1) = D, f (2) = C , f (3) = B, f (4) = A
is a bijection, but is still not an isomorphism as it does not preserve edges. For
instance 2 and 4 are joined by an edge, whereas f (2) = C and f (4) = A are not.
Check Your Understanding. Check that the bijection in Example 1.1.5 is an
isomorphism. In fact, there are four possible isomorphisms; we have only described
two of them. Find the other two.
Example 1.1.7. Graph (a) above is not isomorphic to graph (b); indeed, (a) has 8
vertices, but (b) only has 7, so there cannot be any bijection between their sets of
vertices.
18 CHAPTER 1. SYMMETRIES AND GROUPS

Example 1.1.8. Graphs (c) and (d) are also not isomorphic. They do have the same
number of vertices, so it is possible to find a bijection between their vertex sets.
However, in graph (d) every pair of vertices is connected by an edge, whereas in
graph (c) the top left and bottom right vertices are not. Hence the bijection cannot
preserve all edges.
We will use the notion of a graph isomorphism to define our first key concept:
a symmetry of a graph.
Definition 1.1.9. A symmetry of a graph is an isomorphism from the graph to
itself, i.e. if the set of vertices is V , then a symmetry is a bijection f : V → V that
preserves edges. That is, a symmetry is a bijection f : V → V such that f (v1 ) and
f (v2 ) are joined by an edge if and only if v1 and v2 are joined by an edge.
Remark 1.1.10. The mathematical definition of symmetry is independent of how
we draw the graph. Thus you must use the mathematical definition, and not just
rely on your intuition.
Remark 1.1.11. A symmetry f : V → V must preserve the valency of a vertex (prove
this!). For example, if v1 has valency three, then f (v1 ) must also have valency three.
Example 1.1.12. Describe all symmetries of the graph

For convenience, number the vertices

5

1 2 3 4

so V , the set of vertices, is V = {1, 2, 3, 4, 5}.

Let f : V → V be a symmetry of the graph. Since 5 is the only vertex with
valency two, and symmetries preserve valencies, f (5) = 5. Since 2 and 3 are the
only vertices that have valency three, either they are fixed (f (2) = 2 and f (3) = 3),
or they are swapped (f (2) = 3 and f (3) = 2).
Case 1. Suppose that they are fixed. Thus by above 2, 3 and 5 are all fixed
by f . Now f (1) must be connected to f (2) = 2 and also have valency one, hence
f (1) = 1. Similarly f (4) = 4. This means that f is the identity.
Case 2. Suppose that they are swapped. Thus by above we know f (5) = 5,
f (2) = 3 and f (3) = 2. Now f (1) must be connected to f (2) = 3 and have valency
one, so f (1) = 4. Similarly f (4) = 1, so f is the symmetry

Thus there are precisely two symmetries of the graph, namely the identity and
the above reflection.
1.2. GROUPS AND EXAMPLES 19

Logic 1.1.13. When faced with a graph, it is often easy to guess some symmetries.
However, when you want to determine all symmetries, you must argue that there
are no more. This is usually more difficult. For example, in Example 1.1.12 we took
an arbitrary symmetry and argued that it must be one of two things. This shows
there are precisely two symmetries.
Example 1.1.14. Find all symmetries of the square

and draw what they are.

Check Your Understanding. Do Exercises 0.1 and 1.1. Show that there are 6
symmetries of the triangle graph:

and draw them all.

1.2 Groups and Examples

1.2.1 The definition of a group
Definition 1.2.1 ([J, §4.2]). Let S be any nonempty set. An operation ∗ on S is
a rule which, for every ordered pair (a, b) of elements of S, determines a unique
20 CHAPTER 1. SYMMETRIES AND GROUPS

element a ∗ b of S. Equivalently, if we recall that

S × S := {(a, b) | a, b ∈ S},

then an operation is a function S × S → S.

Example 1.2.2. For any graph, we can consider the set

S := {symmetries of that graph}.

The key point is that we can compose two symmetries f and g to obtain another
symmetry (see the proof of G1 in Theorem 1.2.4 below). Thus we define ∗ by the
rule f ∗ g := f ◦ g (composition of functions), then this gives an operation on S.

Definition 1.2.3 (Definition of a group, [J, §4.3]). We say that a nonempty set G
is group under ∗ if

G1. (Closure) ∗ is an operation, so g ∗ h ∈ G for all g , h ∈ G .

G2. (Associativity) g ∗ (h ∗ k) = (g ∗ h) ∗ k for all g , h, k ∈ G .

G3. (Identity) There exists an identity element e ∈ G such e ∗ g = g ∗ e = g for

all g ∈ G .

G4. (Inverses) Every element g ∈ G has an inverse g −1 ∈ G such that g ∗ g −1 =

g −1 ∗ g = e.

If G is a finite group, the number of elements of G is written |G |, and is called the

order of G . If G is infinite then we say that |G | = ∞, the order of G is infinite.

Groups are one of the basic building blocks of pure mathematics. One of the
main reasons they are so important is that they appear often, and in many different
contexts.

Theorem 1.2.4. The set of symmetries of a graph forms a group (under composi-
tion).
1.2. GROUPS AND EXAMPLES 21

Notation 1.2.5. In the definition of a group, since associativity holds we usually

drop brackets and write g ∗ h ∗ k instead of g ∗ (h ∗ k) or (g ∗ h) ∗ k.

1.2.2 Examples of groups

Groups unify many things that you already know. We claim that you already know
lots of examples of groups.
1. The integers Z = {... , −3, −2, −1, 0, 1, 2, 3, ...} form a group under the op-
eration g ∗ h := g + h. Just check the axioms — if g and h are integers, so
is g + h and so the operation is closed. Adding integers is associative. The
identity is 0 (since 0 + g = g + 0 = g for all g ∈ Z) and the inverse of g
is −g (since g + (−g ) = (−g ) + g = e for all g ∈ Z). Warning: Don’t be
confused by the fact that we usually think that g ∗ h is g × h! Note that there
are infinitely many integers. Hence the order of this group is |Z| = ∞.
2. Similarly Q, R and C are all groups under addition, and they all have infinite
order.
3. [L, p109] For all n ∈ N, the integers mod n, Zn = {0, 1, ... , n − 1}, forms
a group under addition. Again the identity is 0, and the inverse of x is −x
(taken mod n). This group has order |Zn | = n.
22 CHAPTER 1. SYMMETRIES AND GROUPS

4. Zn = {0, 1, ... , n − 1} with multiplication mod n is not a group. Although the

set is closed and there exists an identity element, namely 1, not all elements
have inverses. For example, 0 doesn’t have an inverse. Even if we leave 0 out
and think of the set Z∗n = {1, ... , n − 1} there may still be elements without
inverses. For example, in Z∗8 = {1, 2, 3, 4, 5, 6, 7} the element 2 doesn’t
have an inverse (prove this). The set of all elements in Z∗n that do have
multiplicative inverses is denoted by U(n) and is a group under multiplication
mod n. For n = 8, U(8) = {1, 3, 5, 7} is a group under multiplication mod 8
(prove this).

5. For any n ∈ N the sets of vectors Qn , Rn and Cn are groups under addition
of vectors, with identity the zero vector. Here we are forgetting the “extra
structure” that one can also multiply a vector by a scalar. More generally
every vector space V is a group under addition of vectors.

6. Mn (R) = {n × n matrices with coefficients in R} is a group under addition,

of order |Mn (R)| = ∞.

7. The non-zero real numbers R∗ form a group under multiplication (by which
we mean x ∗ y := xy ) with identity 1 and the inverse of x being 1/x. Similarly
C∗ and Q∗ are groups under multiplication. These groups have order |R∗ | =
|Q∗ | = |C∗ | = ∞. Similarly, if p ∈ N is a prime number, then the non-zero
elements Z∗p of Zp form a group under multiplication, with identity 1, inverse
x −1 = x p−2 , and order Z∗p = p − 1. (Check this!)

All the groups in the list above share an important property:

Definition 1.2.6. Suppose that G is a group and g , h ∈ G . If g ∗ h = h ∗ g then

we say that g and h commute. If g ∗ h = h ∗ g for all g , h ∈ G , then we say G is
an abelian group.

Abelian groups are named after the Norwegian mathematician Niels Henrik Abel
(1802-1829).
Remark 1.2.7. It is very important to remember that not all groups are abelian. In
fact, you already know an example of a non-abelian group. What is it?

Check Your Understanding. Do Exercises 1.7 and 1.8. Find a graph from Sec-
tion 1.1 whose symmetry group is not abelian.

1.3 Symmetries give groups

Roughly speaking, a symmetry of an object is a bijection (i.e. one-to-one corre-
spondence) from the object to itself that preserves its structure. This is not a
mathematical definition, it just gives you the theme of [JJ, §1–§3]. This will be
made more precise in the examples below (see §1.1, §1.3.1, §1.3.4 and §1.3.5). As
a slogan, ‘symmetries give groups’.
1.3. SYMMETRIES GIVE GROUPS 23

1.3.1 Symmetries of regular polygons (dihedral groups)

Note that we can view a regular n-gon as a graph, e.g.:

n=3 n=4 n=5 n=6 n=7

In particular, by Theorem 1.2.4, the symmetries of an n-gon form a group. We call
this group the dihedral group Dn . Here we investigate these groups in more detail.
(Note that Dn is usually only defined for n ≥ 3.)

1.3.2 Symmetries of an equilateral triangle

Consider a 3-gon, i.e. an equilateral triangle. Note that there are precisely six
symmetries of the 3-gon:

g g ◦g

ˆ e the identity (not drawn above).

ˆ Rotation anticlockwise by 2π/3 (which we call g ), and rotation anticlockwise
by 4π/3. The latter is drawn in the second diagram, and corresponds to
performing g twice.
ˆ The three reflections in the lines through the three vertices. These are drawn
in the last three diagrams.
The proof that these six symmetries are all the symmetries of the 3-gon is rather
similar to the proof in Example 1.1.12 (see Exercise 1.2). Let us label the vertices
as follows:
3

1 2

The composition h ◦ g (i.e. g first then h) is given by

3 2 1
g h

1 2 3 1 3 2
24 CHAPTER 1. SYMMETRIES AND GROUPS

Clearly it is equal to the reflection

Similarly g ◦ h is equal to

Therefore the symmetry group D3 of the triangle is given by

D3 = {e, g , g ◦ g , h, g ◦ h, h ◦ g }.

See also Exercise 1.2.

Notation 1.3.1. We usually drop the symbol ◦, and write D3 = {e, g , g 2 , h, gh, hg }.

Check Your Understanding. Check that h ◦ g = g ◦ g ◦ h, so we also have

D3 = {e, g , g 2 , h, gh, g 2 h}.

1.3.3 The dihedral group

Consider now a regular n-gon (where n ≥ 3). Its symmetry group, the dihedral
group Dn , has precisely |Dn | = 2n elements, namely:

ˆ The identity e ∈ Dn .

ˆ The n − 1 rotations anticlockwise through angles k · 2π

n , for k = 1, ... , n − 1.
If we denote g to be the rotation anticlockwise through 2π n , i.e.

then the rotations are {g , g 2 , ... , g n−1 }.

ˆ The n reflections. The pictures of these reflection depend on whether n is

even or odd. For example when n = 5, there are five reflections which all take
place in lines through vertices
1.3. SYMMETRIES GIVE GROUPS 25

whereas if n = 6 there are six reflections

where some lines don’t pass through any vertices. Regardless of whether n is
even or odd, there are n reflections.

Let us denote by h the reflection in the line through the bottom left vertex, i.e.

h h

n even n odd

Then we have

Dn = {e, g , g 2 , ... , g n−1 , h, gh, g 2 h, ... , g n−1 h}.

You should check this by doing Exercise 1.3.

1.3.4 Symmetries of finite sets (symmetric groups)

Definition 1.3.2. The set Sn of all symmetries of {1, ... , n} is called the symmetric
group.

The use of the term ‘group’ is justified by the following

Lemma 1.3.3. The set Sn is a group under composition of order |Sn | = n!.

Proof. We can view Sn as the set of symmetries of the graph

...

where there are n vertices and no edges. Thus Sn is a group by Theorem 1.2.4.
26 CHAPTER 1. SYMMETRIES AND GROUPS

We usually label the elements of a set X with n elements by numbers, so

X = {1, 2, ... , n}. Thus to give a bijection X → X , we have to specify where every
number gets sent. Recall from [L, §20] that there are two ways of doing this.
Remark 1.3.4. We have now seen two groups of order 6: the dihedral group D3
has 2 · 3 = 6 elements, and the symmetric group S3 has 3! = 6 elements. In fact,
it turns outs that although these two groups have different definitions, they are in
some sense the “same” group, viewed two different ways, i.e. they are isomorphic as
groups. This is a different notion from the isomorphisms of graphs that we discussed
before, but the idea is similar. We will give a more precise definition later in the
course. In contrast, Dn and Sn are not isomorphic for n ≥ 4; note that they don’t
even have the same order!
We will come back to symmetric groups later.

1.3.5 Rotational symmetries of regular solids

Recall [L, p77–78] that there are five platonic solids: “fire, earth, air, ether and
water”. These are the three-dimensional convex bodies whose faces are all the
same regular n-gon, and for which every vertex is identical. They are:
Faces Edges Vertices Faces per vertex
tetrahedron 4 triangles 6 4 3
hexahedron 6 squares 12 8 3
octahedron 8 triangles 12 6 4
dodecahedron 12 pentagons 30 20 3
icosahedron 20 triangles 30 12 5
The tetrahedron:

B C
C
B

A A A

The hexahedron (=the cube):

E
A
E

D
A B B
F

The octahedron:
1.3. SYMMETRIES GIVE GROUPS 27

D D

A
A G
D
B B

E
H
E

The dodecahedron:

B
E

L B
F K
A J D I
L
H D G
C J
G

H
The icosahedron:

E K
F

B R
Q
E
I

F
I

A D N
L

B K Q J
G
M

C
R S
O

D T
H

P
N

In this course we will consider their groups of rotational symmetries, namely

those rotations (necessarily about the centres of faces, vertices and edges) that
leave the solid fixed.

Check Your Understanding. The paragraph above states that the rotational sym-
metries of a Platonic solid form a group. What would you need to do to prove this?

The Platonic solids have interesting symmetries, but it is much harder to prove
anything about them (e.g. how many rotational symmetries there are) by arguing
directly as in §1.1. We will come back to these examples throughout the course, as
we learn more theory.

1.3.6 Symmetries of vector spaces

Recall from linear algebra that if A, B, C ∈ Mn (R) are n × n matrices, then
28 CHAPTER 1. SYMMETRIES AND GROUPS

1. A is invertible if and only if det A ̸= 0.

2. If A and B are invertible, so is AB, and moreover (AB)−1 = B −1 A−1 .

3. (AB)C = A(BC ).

Definition 1.3.5. The set of invertible n × n matrices with entries in R is denoted

GL(n, R). Similarly, if p is a prime, then the set of invertible n × n matrices with
entries in Zp is denoted GL(n, Zp ).

Theorem 1.3.6. GL(n, R) is a group under matrix multiplication.

Similarly, when p is a prime, GL(n, Zp ) is a group under matrix multiplication.

Check Your Understanding. Which of the groups defined in this section are
abelian?

Check Your Understanding. Do Exercises 1.3, 1.4, and 1.5.

1.4 Product groups and first properties of groups

1.4.1 Products
In the previous section we saw many examples of groups. Here we’ll see a general
method to build even more examples: to make a new group out of given ones, we
can form their ‘product’:

Theorem 1.4.1. Let G , H be groups. The product

G × H = {(g , h) | g ∈ G , h ∈ H}

has the natural structure of a group as follows:

ˆ The group operation is (g , h) ∗ (g ′ , h′ ) := (g ∗G g ′ , h ∗H h′ ), where we write

∗G and ∗H for the group operations in G and H, respectively.
1.4. PRODUCT GROUPS AND FIRST PROPERTIES OF GROUPS 29

ˆ The identity e in G × H is e := (eG , eH ), where eG and eH are the identity

elements in G and H, respectively.

ˆ The inverse of (g , h) is (g −1 , h−1 ), where the inverse of g is taken in G , and

the inverse of h is taken in H.

Proof. We need to check the axioms to ensure that G × H is a group. This is a

good exercise, or see [J, §4.6].

Notation 1.4.2. Whenever G and H are groups, we will always regard G × H as a

group under the operation defined above. We will usually drop the subscripts ∗G
and ∗H from the notation and write them both as ∗.
Remark 1.4.3. If G , H are both finite then the order of their product is the product
of their orders:
|G × H| = |G | |H| .
Example 1.4.4. You already know some examples of product groups.

1. Let R be regarded as an abelian group under addition. Then R2 , regarded as

a group under addition, is just R × R defined above.

2. Consider the graph (e) in Example 1.1.2. Its symmetry group is S2 × S2 , since
any symmetry is given by specifying a permutation of the up–down arms, and
a permutation of the left–right arms, i.e. a pair of permutations.

Remark 1.4.5. Examples 2 and 3 are a bit imprecise. Technically, a symmetry of

A ∪ B in Example 3 is a permutation of the vertices of A ∪ B which preserves
edges, and an element of G × H is an ordered pair consisting of a permutation of
the vertices of A (that preserves edges) and a permutation of the vertices of B.
However, we have seen that defining a symmetry of A ∪ B is the same thing as
defining a symmetry of A together with a symmetry of B.
The precise statement we’re looking for is that the symmetry group of A ∪ B is
isomorphic to G × H — but we need to define what this means! We’ll come back
to this point.
We will come back to products later.

Check Your Understanding. Do Exercise 1.12.

1.4.2 First Properties of Groups

One of the themes of the course is that groups have a great deal of structure,
which is not obvious from Definition 1.2.3 but emerges from the properties in the
definition. Here we give the first examples of this emergent structure.

Lemma 1.4.6. Let G be a group. If g , h ∈ G , then

1. There is one and only one element k ∈ G such that k ∗ g = h.

2. There is one and only one element k ∈ G such that g ∗ k = h.

30 CHAPTER 1. SYMMETRIES AND GROUPS

Proof. 1. Let k := h ∗ g −1 . Then

k ∗ g = (h ∗ g −1 ) ∗ g = h ∗ (g −1 ∗ g ) = h ∗ e = h,
which proves existence. Now suppose that k ′ ∗ g = h. Then
k = h ∗ g −1 = (k ′ ∗ g ) ∗ g −1 = k ′ ∗ (g ∗ g −1 ) = k ′ ∗ e = k ′
and so k is unique.
2. is very similar (check!).
Remark 1.4.7. Note how every equality in the above proof is either an appeal to
something we have already defined, or is justified by one of the axioms.
Corollary 1.4.8 (see also [J, §4.5]). The following statements are true:
1. In a group you can always cancel: if g ∗ s = g ∗ t then s = t. Similarly, if
s ∗ g = t ∗ g then s = t.
2. Inverses are unique: given g ∈ G then there is one and only one element
h ∈ G such that g ∗ h = e. In particular, e −1 = e and (g −1 )−1 = g .
3. A group has only one identity: if g ∗ h = h (even just for one particular h)
then g = e.

Check Your Understanding. Do Exercise 1.10.

1.5 Exercises
Suitable questions from Jordan and Jordan
ˆ We will come back to the exercises in Chapter 1 once we have done group
actions.
ˆ Chapter 2, Questions 1–2, 4, 6–12 and 14–20 are practise with permutations,
and should mainly be revision from Proofs and Problem Solving [L, §20]. It
is important that you can do them.
ˆ Chapter 4, Questions 1–11 (all questions).
1.5. EXERCISES 31

Exercises on symmetries of graphs

Exercise 1.1. Find a graph whose only symmetry is the identity.

Exercise 1.2. Consider the group D3 , which has as elements the identity e and

g ◦h

h h◦g

g g ◦g

1. Verify that these are all the symmetries of the 3-gon.

2. Verify that h ◦ g = g ◦ g ◦ h and so the elements of D3 are {e, g , g ◦ g , h, g ◦
h, g ◦ g ◦ h}. We drop the ◦ and write D3 = {e, g , g 2 , h, gh, g 2 h}.
3. (Cayley Table) Calculate all possible multiplications in D3 . In other words
complete the table below, where by definition the entry in the (r , c) position
(where r is the row, c the column) is the product r ◦ c
e g g2 h gh g 2h
e e g g2
g g g2 e
g2 g2 e g
h
gh
g 2h

Exercise 1.3. Show that in Dn , the identity e, the n − 1 rotations and the n
reflections are precisely the elements
{e, g , g 2 , ... , g n−1 , h, gh, g 2 h, ... , g n−1 h},
2π
where g is counterclockwise rotation by n , h is a reflection, and

g n−1 = e, h2 = e, hg = g n−1 h..

Then, by modifying your argument to Problem 1.2, show that these are all the
symmetries of the n-gon.

Exercise 1.4. We can view the symmetric group Sn as symmetries of the graph
with n vertices and no edges. For every n ≥ 2, produce a different graph which
also has symmetry group Sn . This is part of the general phenomenon that many
different graphs can have the same symmetry group.
32 CHAPTER 1. SYMMETRIES AND GROUPS

Exercises on other groups

Exercise 1.5. We would like an example of a rotational symmetry of the cube which,
if repeated three times, gives the identity. The identity itself has this property. Are
there any others?

Exercise 1.6. How many elements does GL(2, Z2 ) have? How about GL(n, Zp )
with p a prime?

Exercises on the definition of a group

Exercise 1.7. Are the following operations? For the ones that are operations, do
they make the set into a group?

1. Z with a ∗ b := a + 2.

2. Z with a ∗ b := a + b.
a c a
3. Q, with b ∗ d := b + dc .
a c a+c
4. Q, with b ∗ d := b+d .

Exercise 1.8. Are the following groups?

1. The set G = {a + bi | a, b ∈ Z} with group operation given by addition of

complex numbers.

2. The set G = {a + bi | a, b ∈ Z and a, b not both zero} with group operation

given by multiplication of complex numbers.

3. The set G = {a + bi | a, b ∈ Q and a, b not both zero} with group operation

given by multiplication of complex numbers.

4. The set K = {e, x, y , z} with the abelian multiplication defined by

x 2 = y 2 = z 2 = e, xy = z, yz = x, zx = y

and eg = g for all g ∈ K . (Note: you need to check for the existence of
inverses and for whether the multiplication is associative: try and organize
your reasoning for the latter, exploiting symmetry rather than checking all 64
possibilities.)

Exercise 1.9. Fix n ∈ N and consider multiplication mod n. Let G be the subset
of {1, 2, ... , n − 1} consisting of all those elements that have a multiplicative in-
verse (under multiplication mod n). Show that G is a group under multiplication.
Describe this group when n = 12.
1.5. EXERCISES 33

Exercises on abelian groups

Exercise 1.10. Show that if g 2 = e for all g ∈ G , then G is abelian.

Exercise 1.11. Prove that a group (G , ∗) is abelian if and only if for all g , h in G ,

(g ∗ h)2 = g 2 ∗ h2 . (1.1)

Exercises on products

Exercise 1.12. Give examples of graphs which have symmetry groups Z2 , S3 × Z2

and S3 × D3 respectively.

Exercise 1.13. Show that if G and H are groups, then G × H is abelian if and only
if G and H are both abelian.
34 CHAPTER 1. SYMMETRIES AND GROUPS
Chapter 2

Subgroups and Lagrange’s

Theorem

2.1 Subgroups
Definition 2.1.1 ([J, §5]). Let G be a group. We say that a nonempty subset H
of G is a subgroup of G if H itself is a group (under the operation from G ). We
write H ≤ G if H is a subgroup of G . If also H ̸= G , we write H < G and say that
H is a proper subgroup.

Lemma 2.1.2. Suppose that H ≤ G . Then

1. eH = eG

2. If h ∈ H, the inverse of h in H equals the inverse of h in G .

Proof. 1. eH ∗ eH = eH by the identity axiom in H and eG ∗ eH = eH by the identity

axiom in G . Hence eH ∗ eH = eG ∗ eH so by cancellation eH = eG .
2. Let a denote the inverse of h in H, so a ∗ h = h ∗ a = eH . By part 1,
a ∗ h = h ∗ a = eG so a is also the inverse of h in G .

Theorem 2.1.3 (Test for a subgroup). H ⊆ G is a subgroup of G if and only if

S1. H is not empty.

S2. If h, k ∈ H then h ∗ k ∈ H

S3. If h ∈ H then h−1 ∈ H.

35
36 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Theorem 2.1.4 (Alternative test for a subgroup). H ⊆ G is a subgroup of G if

and only if

S1.
f H is not empty.

f If h, k ∈ H then h ∗ k −1 ∈ H
S2.

Check Your Understanding. Prove Theorem 2.1.4.

Remark 2.1.5. If G is finite, then there is a slightly easier test for a subgroup. See
Exercise 2.1.
Example 2.1.6. The test for a subgroup can be used to establish all the following
examples.

1. G is a subgroup of itself. Also, {e} is a subgroup of G , called the trivial

subgroup.

2. Z < Q < R < C (all abelian groups under addition).

3. Consider G = S3 . Let H denote all the permutations that send 1 to itself.

(There are two of them, the identity and the one that swaps 2 and 3.) Then
H < G.
2.2. ORDERS OF ELEMENTS AND CYCLIC SUBGROUPS 37

4. Let G = Z8 (under addition) and let H = {0, 2, 4, 6}. Then H < G .

5. More generally let G = Zn where n = kl with k, l > 1. Then H < G where

H = {0, k, 2k, ... , (l − 1)k}.

6. Let G = GL(n, R), and H be all the upper-triangular elements of G . Then

H < G.

7. There are also many other interesting subgroups of GL(n, R), for example

(a) SL(n, R) := {A ∈ GL(n, R) | det A = 1}.

(b) O(n, R) := A ∈ GL(n, R) AT = A−1 .


(c) SO(n, R) := A ∈ GL(n, R) det A = 1 and AT = A−1 .



See [J, §5.2].

Check Your Understanding. Show that SL(n, R), O(n, R) and SO(n, R) are indeed
subgroups of GL(n, R).

Remark 2.1.7. The subgroup SO(3, R) of GL(3, R) is particularly easy to visualise:

it is the subgroup of GL(3, R) consisting of matrices that perform rotations on R3 .
One can use this subgroup to show that the groups of rotational symmetries of
Platonic solids defined in Section 1.3.5 are in fact groups, although we do not give
the details.

2.2 Orders of elements and cyclic subgroups

Before we go any further, let us introduce some important notational simplifica-
tions that will make our lives easier. Make sure you are comfortable with these
conventions!
Notation 2.2.1. When dealing with a general group G , as much as possible we will
write gh for g ∗ h.
We make this notational simplification because it is tedious to keep on writing
∗. However, dropping the ∗ can be a little dangerous. For example, when the group
is Z or Zn (under addition), if we write ab for a ∗ b, then

ab := a ∗ b = a + b.

This would imply that we are writing ab to mean ‘add a and b’. Since you are so
used to writing ab to mean ‘multiply a and b’, this will cause confusion. Hence,
when we are dealing with groups under addition (like Z or Zn ), it is helpful to keep
the ∗ or + in the notation (see for example Example 2.2.5(3) and Example 2.3.5
later). Nevertheless, when discussing a general group G , we will drop the ∗ as much
as possible.
38 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Notation 2.2.2. Similarly, it is useful to have a shorthand for expressions such as

g ∗ · · · ∗ g . If G is a group, g ∈ G and k ∈ Z, we define the power g k by

k
 z }| {
∗ · ·· ∗ g



 g if k > 0
g k := e if k = 0
−1 −1

 g
 |
 ∗ · · · ∗ g if k < 0
 {z }
−k

Definition 2.2.3 (Order of a group). A finite group G is one with only a finite
number of elements. The order of a finite group, written |G |, is the number of
elements in G . (Note that if X is a set, we also often write |X | to be the number
of elements in X .)

Definition 2.2.4 (Order of an element, [J, §6.3]). Let G be a group and g ∈ G .

Then the order o(g ) of g is the least natural number n such that

g n = e.

If no such n exists, we say that g has infinite order.

Example 2.2.5. Here are some simple examples of orders:

1. From Section 1.3.3 |Dn | = 2n. From Definition 1.3.2 |Sn | = n!

2. In D3 , if g is defined as before as

then

3 2 1 3
g g g

1 2 3 1 2 3 1 2

Thus g t ̸= e for 1 < t < 3 and g 3 = e, and so o(g ) = 3.

3. Consider 1 ∈ Z. Then 1 ∗ 1 = 1 + 1 = 2, 1 ∗ 1 ∗ 1 = 3,..., and so

1| ∗ {z
... ∗ 1} = n ̸= 0 = e
n

for any n > 0. Hence 1 ∈ Z has infinite order.

2.2. ORDERS OF ELEMENTS AND CYCLIC SUBGROUPS 39

4. See Exercise 2.10 through 2.15 for many examples of finite order.
Theorem 2.2.6. In a finite group, every element has finite order.

Corollary 2.2.7. Let g be an element of a finite group G . Then there exists k ∈ N

such that g k = g −1 .
Proof. By Theorem 2.2.6 o(g ) is finite. Thus there exists t ∈ N such that g t = e.
Applying g −1 to both sides gives g t−1 = g −1 .
Given an element of a group, there is an easy way to produce a subgroup [J,
§6]:
Definition 2.2.8. Let G be a group and let g ∈ G be an element. We define the
subset
⟨g ⟩ := {g k | k ∈ Z} = {... , g −2 , g −1 , e, g , g 2 , ...}.
Note that if G is finite, then ⟨g ⟩ (being a subset of G ) is finite, and we can
think of ⟨g ⟩ as
⟨g ⟩ = {e, g , ... , g o(g )−1 }
by Theorem 2.2.6 and Corollary 2.2.7.
Lemma 2.2.9. If G is a group and g ∈ G , then ⟨g ⟩ is a subgroup of G .
Check Your Understanding. Prove Lemma 2.2.9 using the test for a subgroup
(Theorem 2.1.3). In your proof, it is useful to note the fact that g a g b = g a+b for
all a, b ∈ Z. Although easy (it follows directly from the axioms of a group), the
proof of this fact is tedious since it involves splitting into cases depending whether
a (and b) are positive, negative or zero.
Definition 2.2.10. A subgroup H ≤ G is cyclic if H = ⟨h⟩ for some h ∈ H. In
this case, we say that H is the cyclic subgroup generated by h. If G = ⟨g ⟩ for some
g ∈ G , then we say that the group G is cyclic, and that g is a generator.
40 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Example 2.2.11. Here are some examples of cyclic (sub)groups:

1. Zn (under addition) is cyclic, since ⟨1⟩ = Zn .

2. In Z8 the cyclic subgroup generated by 2 is ⟨2⟩ = {0, 2, 4, 6}. This is strictly

contained in Z8 .

3. In Dn , the subgroup H consisting of the identity and all the rotations, i.e.

H = {e, g , g 2 , ... , g n−1 }

is a cyclic subgroup since H = ⟨g ⟩. Note also that H = g −1 .

Remark 2.2.12. If g ∈ G , then by the line above, o(g ) = |⟨g ⟩|, i.e. the order of an
element equals the order of the subgroup that it generates.

Remark 2.2.13. If G is cyclic then necessarily G is abelian. See Problem 2.4. In

particular, D3 is not cyclic, since we calculated in Section 1.3.2 that gh ̸= hg .

Lemma 2.2.14. Let G be a finite group. Then

G is cyclic ⇐⇒ G contains an element of order |G |.

Proof. (⇐) Suppose g ∈ G has order |G |. Then ⟨g ⟩ ≤ G with |⟨g ⟩| = |G | by

Remark 2.2.12. Hence ⟨g ⟩ and G have the same number of elements, so ⟨g ⟩ = G .
(⇒) Suppose G = ⟨g ⟩ is cyclic, then counting the number of elements on both
sides gives |G | = |⟨g ⟩|. By 1, this means that g has order |G |.

This gives another proof that D3 is not cyclic, since it has no element of order
6. The only possible orders are 1 (the identity), 3 (the two rotations) and 2 (the
three reflections).
We next investigate how cyclic groups behave with respect to our previous
constructions in Section 2.1 (subgroups) and Section 1.4.1 (product groups).

Theorem 2.2.15. Let G be a cyclic group and let H be a subgroup of G . Then H

is cyclic.
2.2. ORDERS OF ELEMENTS AND CYCLIC SUBGROUPS 41

Thus by above any subgroup of any cyclic group is also cyclic. However, products
of cyclic groups are not so well behaved.
Theorem 2.2.16. Let m, n ∈ N, let G = ⟨g ⟩ be a cyclic group of order m and
H = ⟨h⟩ be a cyclic group of order n. Then
G × H is cyclic ⇐⇒ m and n are coprime (i.e. gcd(m, n) = 1).
42 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

2.3 Cosets
In the next section we will prove Lagrange’s Theorem, the first main theorem of
this course. This theorem is so important we will state it now, although it is not
proved until Theorem 2.4.2.
Theorem 2.3.1 (Lagrange’s Theorem). Let G be a finite group and let H be a
subgroup of G . Then |H| divides |G |.
Note that this theorem does not follow immediately from the definitions! In
fact, you might want to try to prove it yourself before reading further to get an
appreciation of the new theoretical tools we need to develop for this proof.

2.3.1 Recap on equivalence relations

Recall [L, §18] and [J, §8]. Intuitively, we often think of sets schematically as blobs
containing elements, drawn as dots:

For various reasons, often we want to partition this set into smaller pieces, which
we draw as

Whenever we need to partition a set into pieces in this way, the tool to use is an
equivalence relation.
Definition 2.3.2 ([L,§18]). Let X be a set, and R a subset of X × X ; thus R
consists of some ordered pairs (s, t) with s, t ∈ X . If (s, t) ∈ R we write s ∼ t
and say “s is related to t”. We call ∼ a relation on X . A relation ∼ is called an
equivalence relation on X if it has satisfies the following three axioms:
2.3. COSETS 43

R. (Reflexive) x ∼ x for all x ∈ X

S. (Symmetric) x ∼ y implies that y ∼ x for all x, y ∈ X

T. (Transitive) x ∼ y and y ∼ z implies that x ∼ z for all x, y , z ∈ X .

The key point from Proofs and Problem Solving [L, 18.1] is that equivalence
relations partition sets. If ∼ is an equivalence relation on a set X , then the set X
is partitioned into pieces called the equivalence classes. In our previous picture

the shaded region is the equivalence class containing x, which by definition is just
all elements that are related to x. It is denoted cl(x). In mathematical symbols,
the shaded region

cl(x) := {all elements that are related to x} = {s ∈ X | x ∼ s}.

Check Your Understanding. Remind yourself (see [L], Exercise 18.4) of the rela-
tionship between partitions and equivalence relations. That is, suppose X is parti-
Sn if x ∈ X , then
tioned into the subsets X1 , ... , Xn of X . (Recall that this means that
x is an element of exactly one of the subsets Xj : that is, (i) X = j=1 Xj , and (ii),
if i ̸= j then Xi ∩ Xj = ∅.) Prove that the relation:

x ∼ y if and only if x and y are both elements of the same Xj

defines an equivalence relation on X , and that the equivalence classes are just the
Xj .

2.3.2 Cosets and equivalence relations on groups

In this section we introduce the important concept of a coset, and show that cosets
give equivalence relations on groups. In the next section, we will use this to prove
Lagrange’s Theorem.
Notation 2.3.3. Let A, B be subsets of a group G and let g ∈ G . Then

AB := {ab | a ∈ A, b ∈ B} , gA := {ga | a ∈ A} ,

and similarly for other obvious variants.

44 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Definition 2.3.4 ([J, §10.1]). Let H ≤ G and let g ∈ G . Then a left coset of H
in G is a subset of G of the form gH, for some g ∈ G .

Example 2.3.5. Consider Z4 under addition, and let H = {0, 2}. Recall e = 0. Now
the cosets of H in G are

eH =e ∗H = {e ∗ h | h ∈ H} = {0 + h | h ∈ H} = {0, 2}.
1H =1∗H = {1 ∗ h | h ∈ H} = {1 + h | h ∈ H} = {1, 3}.
2H =2∗H = {2 ∗ h | h ∈ H} = {2 + h | h ∈ H} = {0, 2}.
3H =3∗H = {3 ∗ h | h ∈ H} = {3 + h | h ∈ H} = {1, 3}.

Hence there are two cosets, namely

0 ∗ H = 2 ∗ H = {0, 2} and 1 ∗ H = 3 ∗ H = {1, 3}.

The above shows that g1 H = g2 H is possible, even when g1 ̸= g2 .

Definition 2.3.6. We denote the set of left cosets of H in G by G /H.

Example 2.3.7. Continuing with Example 2.3.5, we have

G /H = {eH = 2H, 1H = 3H} = {{0, 2}, {1, 3}}.

As in this example, usually the number of members of G /H (which we denote

by |G /H|) is less than |G |. See Corollary 2.4.3 for the precise answer later.

Theorem 2.3.8. Let H ≤ G .

1. For all h ∈ H, hH = H. In particular eH = H.

2. For g1 , g2 ∈ G , the following are equivalent

(a) g1 H = g2 H.

(b) there exists h ∈ H such that g2 = g1 h.

(c) g2 ∈ g1 H.

3. For g1 , g2 ∈ G , define g1 ∼ g2 if and only if g1 H = g2 H. Then ∼ defines an

equivalence relation on G .
2.4. LAGRANGE’S THEOREM 45

Check Your Understanding. Let D5 be the dihedral group of symmetries of a

regular pentagon, and let H = ⟨g ⟩ < D5 be the subgroup of rotations. Determine
the left cosets of H.

Definition 2.3.9. The right cosets of H in G are subsets of the form Hg .

Remark 2.3.10. The properties of right cosets are entirely analogous to those of left
cosets. In particular, Theorem 2.3.8 holds equally well if we replace all left cosets
with right cosets.

2.4 Lagrange’s Theorem

2.4.1 The proof of Lagrange’s Theorem
In the previous section, we saw that if G is a group and H is a subgroup, then
the cosets of H partition G . This takes us most of the way towards proving La-
grange’s Theorem. What remains is to show that each coset has the same number
of elements.

Lemma 2.4.1. Suppose that H ≤ G and H is finite.

1. Then |gH| = |H| for all g ∈ G .

2. For a fixed g ∈ G , the number of g1 ∈ G such that gH = g1 H is equal to

|H|.
46 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Proof. 1. There is an obvious map H → gH given by h 7→ gh. It is clearly surjective,

by definition of gH. It is injective by Corollary 1.4.8, since gh1 = gh2 implies that
h1 = h2 .
2. By Theorem 2.3.8, part 2, gH = g1 H if and only if g1 ∈ gH. Since |gH| = |H|
(by part 1), there are precisely |H| possibilities.

Theorem 2.4.2 ([J, §10]). Suppose that G is a finite group.

1. (Lagrange’s theorem) If H ≤ G , then |H| divides |G |.

2. Let g ∈ G . Then o(g ) divides |G |.

3. For all g ∈ G , we have that g |G | = e.

Proof. 1. By Theorem 2.3.8 part 3, there is an equivalence relation ∼ defined on

G . Thus G is partitioned into a (disjoint union) of the equivalence classes, which
we denote A1 , A2 , ... .

A3
A1
A2
A4

Consequently we can count the elements of G by counting the elements in each

piece of the partition, and by doing this we obtain
X
|G | = |A| .
equiv classes A

Now pick one of the A, then by definition of equivalence class A = cl(g ) for some
g ∈ G . By Lemma 2.4.1, the equivalence class containing g (i.e. A) has precisely |H|
members. Since A was arbitrary, every equivalence class has precisely |H| members,
and so

|G | = |H| + ... + |H| = (number of equiv classes) × |H| . (2.1)

| {z }
number of equiv classes

Hence |H| divides |G |.

2. Just note that ⟨g ⟩ is a subgroup of size o(g ), so apply part 1.
3. By part 2, say |G | = k × o(g ). Then g |G | = (g o(g ) )k = e k = e.

In the proof of Lagrange’s Theorem, equation (2.1) shows that the number of
|G |
equivalence classes is |H| . This then implies:
2.4. LAGRANGE’S THEOREM 47

|G |
Corollary 2.4.3. |G /H| = |H| .

Definition 2.4.4. The index of H ≤ G is defined to be the number of distinct left

|G |
cosets of H in G , which by above is |G /H| = |H| .

Remark 2.4.5. We could alternatively prove Lagrange’s Theorem by using right

cosets. Then Corollary 2.4.3 would show that the number of distinct right cosets is
|G |
equal to |H| . Hence the number of distinct right cosets is the same as the number
of distinct left cosets, even although the right cosets might not be the same as the
left cosets (see for example Problem 2.16).

2.4.2 First applications of Lagrange

With Lagrange’s theorem in hand, we can start to prove some interesting non-
obvious results about the structure of groups.
Theorem 2.4.6. Suppose that G is a group with |G | = p, where p is prime. Then
G is a cyclic group.
Proof. Choose g ∈ G with g ̸= e. Then H := ⟨g ⟩ is a subgroup of G with at
least two elements (e and g ). But |H| must divide |G | = p. Hence |H| = p and so
H = G.
Corollary 2.4.7. Suppose that G is a group with |G | < 6. Then G is abelian.
Proof. If |G | = 1 then G is abelian (there is nothing to prove). If |G | = 2, 3 or
5 then G is cyclic (by 2.4.6) and hence abelian (by Problem 2.4). The only other
case is |G | = 4. In this case, if G has an element of order four then it is cyclic, and
hence abelian (by Problem 2.4). Therefore we can assume that G has no element
of order four. Only the identity has order one, so by Lagrange (2.4.2 part 2) every
non–identity element must have order two. Hence g 2 = e for all g ∈ G , and so G
is abelian (by Problem 1.10).
We saw in Section 1.3.2 that the dihedral group D3 has six elements and that
D3 is non-abelian. This tells you two things:
48 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

1. By the corollary, D3 is the smallest example of a non-abelian group.

2. The corollary is the ‘best possible’, in the sense that the bound |G | < 6 cannot
be made any stronger.
The following result is an application of Lagrange’s Theorem to number theory.
Theorem 2.4.8 (Fermat’s Little Theorem). If p is a prime and a ∈ Z, then

ap ≡ a mod p.

Proof. If a ≡ 0, then the result is obviously true, since then ap ≡ 0 ≡ a. Hence we

can assume that a ̸≡ 0, and so view a as an element of the group Z∗p = {z ∈ Zp |
z ̸= 0} (which is a group under multiplication, with identity 1, see Section 1.2.2(6)).
This group has precisely p − 1 elements, so by Theorem 2.4.2(3) we deduce that
g p−1 = 1 for all g ∈ Z∗p . Since a ∈ Z with a ̸≡ 0, viewing a ∈ Z∗p it follows that
ap−1 ≡ 1 mod p. Multiplying both sides by a yields the result.

2.5 Exercises
Suitable questions from Jordan and Jordan
ˆ Chapter 5, Questions 1–13 (all questions).
ˆ Chapter 6, Questions 1–21 (all questions).
ˆ Chapter 10, Questions 1, 4–8, and 10–14.

Exercises on subgroups

Exercise 2.1. Suppose that G is a finite group and let H be a non-empty subset
of G . Show that H is a subgroup of G if and only if h, k ∈ H implies that hk ∈ H.

Exercise 2.2. For each of the following, is H a subgroup of G ?

1. G = Z (under addition) and H is all the elements that are multiples of both
3 and 5.
2. G = Z (under addition) and H is all the elements that are multiples of 3 or
multiples of 5.
3. Consider a non-zero vector v in Rn . Take G = GL(n, R) and

H = {g ∈ G | gv = λv for some λ ∈ R} .

Exercise 2.3. Let H1 , ... , Hk be subgroups of G . Prove that their intersection

T
j=1,...,k Hj is a subgroup of G .
2.5. EXERCISES 49

Exercises on cyclic and abelian groups

Exercise 2.4. Show that if G is cyclic, then G is abelian. Give an example of an

abelian group that is not cyclic.

Exercise 2.5. Let G be cyclic and suppose G = ⟨g ⟩. Show that if H ≤ G and

g ∈ H then H = G .

Exercise 2.6. Find a non-trivial symmetry f of the square (that is, an element of
D4 that is not the identity) that commutes with all the other elements. Which of
the groups Dn have such an element?

Exercise 2.7. Let G be the group of 2 × 2 invertible matrices with entries in R.

Let H be the subset consisting of those matrices which are upper-triangular and of
determinant 1. Show that H is a subgroup of G . Show that if we replace R by Z3 ,
then H is cyclic and hence abelian. Show also that if we replace R by Z5 then H is
not abelian.

Exercise 2.8. Show that Z∗7 (the multiplicative group of nonzero integers mod 7)
is a cyclic group.

Exercises on order

Exercise 2.9. Let x = (g , h) ∈ G × H. Express the order of x in G × H in terms

of the order of g in G and the order of h in H. (A proof is required!)

Exercise 2.10. In the dihedral group D6 what are the orders of the various sym-
metries? (Think carefully and if necessary cut a regular hexagon out of paper and
experiment.)

Exercise 2.11. What is the order of the various elements of the symmetric group
S3 ?

Exercise 2.12. Consider Zn under addition. Find the orders of all the elements in
the cases n = 3, 4, 5, 6. What is your guess for the possible orders of elements in
Zn ?

Exercise 2.13. Suppose o(g ) = k. If n ∈ N, show that g n = e if and only if n is

a multiple of k.

Exercise 2.14. Suppose o(g ) = k. What can you say about the order of g 2 ?

Exercise 2.15. Is o(g ) = o(g −1 ) always? Give a proof or a counterexample.

Exercises on cosets and Lagrange

50 CHAPTER 2. SUBGROUPS AND LAGRANGE’S THEOREM

Exercise 2.16. Consider the group D3 . Find the left and right cosets of H in D3
where:
1. H = ⟨g ⟩ = {e, g , g 2 }.
2. H = ⟨h⟩ = {e, h}

where g and h were defined in Problem 1.2.

Exercise 2.17. Show that if G is abelian and H ≤ G , then the left cosets of H in
G are the same as the right cosets. Find the cosets in the case where G = Z9 and
H = {0, 3, 6}.

Exercise 2.18. Find all the subgroups of D3 .

Exercise 2.19. Find all the subgroups of Z5 and Z6 .

Exercise 2.20. What are all the subgroups of D4 ?

Chapter 3

Going between Groups

3.1 Homomorphisms and Isomorphisms

In linear algebra we study linear transformations—functions from Rn to Rm that
are “compatible” with the algebra of vectors (addition and scalar multiplication).
Similarly, in group theory, we study homomorphisms between groups: functions
that are compatible with the group operations.
This section covers [J, §9.1, §9.2].

Definition 3.1.1. Let G , H be groups. A map ϕ : G → H is called a group

homomorphism if
ϕ(xy ) = ϕ(x)ϕ(y ) for all x, y ∈ G .

Note that in the definition, the product xy on the left is formed using the group
operation in G , whilst the product ϕ(x)ϕ(y ) is formed using the group operation in
H.

Definition 3.1.2. A group homomorphism ϕ : G → H that is also a bijection is

called an isomorphism of groups. In this case we say that G and H are isomorphic
and we write G ∼= H. An isomorphism G → G is called an automorphism of G .

Remark 3.1.3. An isomorphism thus matches up the two groups and their group
operations perfectly. In other words, if G and H are isomorphic groups then they
are algebraically indistinguishable. In the world of group theory, isomorphism is the
idea of equality; we view two isomorphic groups as ‘the same’. (Recall that when
two graphs are isomorphic, then from the point of view of graph theory, they are
‘the same’.)
Example 3.1.4. Here are some examples of isomorphisms:

1. Consider R under addition and R∗+ (the group of positive real numbers) under
multiplication. The map exp : R → R∗+ is a group homomorphism since
exp(x + y ) = exp(x) exp(y ). It is bijective, hence is an isomorphism.

51
52 CHAPTER 3. GOING BETWEEN GROUPS

2. We denote by 2Z the set of all even integers. It is easy to check that it is a

group under the usual operation of addition. It is actually a subgroup of the
group Z. The map θ : Z → 2Z defined by θ(k) = 2k is an isomorphism. This
example shows that it is possible for a group to be isomorphic to a proper
subgroup.

3. If n ∈ N, then every cyclic group of order n is isomorphic. (Proof: suppose

G = ⟨g ⟩ and H = ⟨h⟩ both have order n. The map G → H sending
g t 7→ ht is a group homomorphism which is clearly bijective.) This is why we
often refer to the cyclic group of order n. The standard notation for this is
Cn = {g , g 2 , g 3 , ... , g n = e}.

4. Let S2 = {e, σ} where σ is the non-trivial permutation. We have σ 2 = e and

so S2 = {e, σ} is cyclic of order 2. Since Z2 is also cyclic of order 2, by part
2 we have S2 ∼= Z2 .

5. More generally, every group of order 2 is isomorphic to Z2 , since by Theo-

rem 2.4.6 G is necessarily cyclic.

6. The map ϕ : D3 → S3 that takes a symmetry of the triangle to the corre-

sponding permutation of the vertices is bijective. It is also a homomorphism
of groups (one way to see this is to use the Cayley table [J, §1] in Problem 1.2
and check where every product gets sent to), hence it is an isomorphism, so
D3 ∼= S3 .

7. Let Γ and Γ′ be graphs. Let G be the group of symmetries of Γ and let G ′

be the group of symmetries of Γ′ . If Γ and Γ′ are isomorphic graphs, then
G ∼= G ′ . On the other hand, you should easily be able to come up with
examples where G ∼= G ′ but Γ and Γ′ are not isomorphic.

Check Your Understanding. Show that if ϕ : G → H is an isomorphism of groups,

then so is ϕ−1 : H → G .

Check Your Understanding. Show that the relation ∼

= on groups is an equivalence
relation.

Lemma 3.1.5. Let ϕ : G → H be a group homomorphism. Then

1. ϕ(e) = e and further ϕ(g −1 ) = (ϕ(g ))−1 for all g ∈ G .

2. If ϕ is injective, the order of g ∈ G equals the order of ϕ(g ) ∈ H.

3.1. HOMOMORPHISMS AND ISOMORPHISMS 53

Definition 3.1.6. Let ϕ : G → H be a group homomorphism.

1. The image of ϕ is defined to be

im ϕ := {h ∈ H | h = ϕ(g ) for some g ∈ G }

2. We define the kernel of ϕ to be

ker ϕ := {g ∈ G | ϕ(g ) = eH }.

In pictures, they are the shaded regions

∃g h e

G H G H
im ϕ ker ϕ

Note that im ϕ is a subgroup of H and that ker ϕ is a subgroup of G (use the test
for a subgroup).
Furthermore, recall from the second algebra handin the definition of a normal
subgroup:
Definition 3.1.7. A subgroup N ≤ G is normal if the left and right cosets of N
are equal: gN = Ng for all g ∈ G .
If N is a normal subgroup of G we write N ◁ G .
It turns out that kernels of homomorphisms are always normal subgroups.
Proposition 3.1.8. Let ϕ : G → H be a group homomorphism. Then ker ϕ ◁ G .
Proof. See Exercises 3.4 and 3.5
54 CHAPTER 3. GOING BETWEEN GROUPS

Proposition 3.1.9. Let ϕ : G → H be a group homomorphism. Then

1. ϕ : G → H is injective if and only if ker ϕ = {eG }.

2. If ϕ : G → H is injective, then ϕ gives an isomorphism G ∼

= im ϕ.

Proof. See Workshop.

Check Your Understanding. Do Exercises 3.2 and 3.3 below, as well as Exercise
9.5 from [J].

3.2 Products and Isomorphisms

Given two groups H and K , and a third group G , we may ask whether G is isomor-
phic to H × K . Such an isomorphism is useful, because it means that G can be
broken down into the “simpler” pieces H and K .
We begin in Theorem 3.2.1 with an abstract results that tells us when we have
such an isomorphism, then show in Example 3.2.4 and Example 3.2.5 that this gives
us very concrete examples of some isomorphic groups.
To state the theorem, we need to recall some notation from Section 2.3.2: if S
and T are subsets of G , then we define

ST := {st | s ∈ S, t ∈ T } .

Theorem 3.2.1 ([J, §14.3]). Let H, K ≤ G be subgroups with H ∩ K = {e}.

1. The map ϕ : H × K → HK given by ϕ : (h, k) 7→ hk is bijective.

2. If further every element of H commutes with every element of K when mul-

tiplied in G (i.e. hk = kh for all h ∈ H, k ∈ K ), then HK is a subgroup of G ,
and furthermore it is isomorphic to H × K , via ϕ.

Remark 3.2.2. The logic in the above is that H and K start life as given subgroups
of G . However, we can simply regard them as groups in their own right and take
their abstract product to form H × K . Under the assumption that H ∩ K = {e}, the
conclusion of the first claim is that HK is a set which is bijective to H × K . Under
the further assumption that hk = kh for all h ∈ H, k ∈ K , the second claim is that
actually HK is a subgroup of G , and furthermore HK is the same as (=isomorphic
to) H × K as groups, not just as sets.
3.2. PRODUCTS AND ISOMORPHISMS 55

Corollary 3.2.3. Let H, K ≤ G be finite subgroups of a group G such that H ∩K =

{e}. Then |HK | = |H| × |K |.
Proof. Since HK is bijective to H × K by Theorem 3.2.1 (part 1), this is obvious
(recall Remark 1.4.3).
Example 3.2.4. Consider D6 , the symmetries of a regular hexagon. Consider one of
the equilateral triangles formed by the vertices of the hexagon.

h
g

Consider the set H consisting of those symmetries of the hexagon which are
also symmetries of the triangle. Since H contains precisely the symmetries of the
triangle, H is a subgroup of D6 which is isomorphic to D3 . Explicitly,

H = {e, g 2 , g 4 , h, g 2 h, g 4 h} ∼
= D3 .

Now consider K = g 3 = {e, g 3 }, where g 3 ∈ D6 is the half turn. This subgroup is

isomorphic to Z2 (all groups of order two are). We claim that D6 ∼
= H×K ∼ = D3 ×Z2 .

Example 3.2.5. More examples of product groups:

1. The group G of symmetries of the graph (e) in Example 1.1.2 has 4 elements.
The reflection in the horizontal line generates a subgroup H with two elements
56 CHAPTER 3. GOING BETWEEN GROUPS

which is thus isomorphic to Z2 . Similarly for the reflection in the vertical line
— it generates a subgroup K which is isomorphic to Z2 . These two reflections
commute, hence HK ∼ = Z2 ×Z2 . Since HK ⊆ G and both have four elements,
G = HK and so G ∼ = Z2 × Z2 .

2. Similarly, in the graph (b) in Example 1.1.2 there is a subgroup H isomorphic

to S3 from permuting the three danglers on the left, and a subgroup K
isomorphic to Z2 from permuting the danglers on the right. Elements from
these two subgroups commute, and so HK ∼ = S3 × Z2 . Again by looking at
the number of elements, G = HK and so G ∼ = S3 × Z2 .

Check Your Understanding. Do Exercises 3.8 and 3.12.

3.3 Exercises
Suitable questions from Jordan and Jordan
ˆ Chapter 9, Questions 1–4 and 9–10.

Exercises on homomorphisms

Exercise 3.1. Show that exp is a group homomorphism between R (under addition)
and R∗ := R − {0} (under multiplication). What is its kernel and what is its image?
Now answer the same question for exp : C → C∗ .

Exercise 3.2. Let p, q be different primes. Show that the only homomorphism
ϕ : Cp → Cq is the trivial one (i.e. ϕ(g ) = e for all g ). (Hint: consider kernels and
images.)

Exercise 3.3. Consider the function det : GL(n, R) → R∗ . Show that it is a group
homomorphism. Identify its kernel and image.

Exercises on normal subgroups

Exercise 3.4. Show that a subgroup N ≤ G is normal if and only if gNg −1 ⊆ N

for all g ∈ G .

Exercise 3.5. Show that if ϕ : G → H is a group homomorphism, that ker ϕ ◁ G .

Exercises on isomorphisms and products

Exercise 3.6. Consider the group C under addition. Show that complex conjugation
ϕ : z → z̄ is an isomorphism C → C.
3.3. EXERCISES 57

Exercise 3.7. Prove that every group G of order 4 is isomorphic to C4 or C2 × C2 .

(Hint: If G has an element of order 4 then we know the group is isomorphic to C4 .
So the only possibility is that every non-identity element has order 2. Call them
x, y , z. What are xy and yx equal to?)

Exercise 3.8. Describe a subgroup of S7 isomorphic to S3 × S4 .

Exercise 3.9. Let a, b ∈ N. True or false: a!b! always divides (a + b)!

Exercise 3.10. Consider the argument in lectures showing that D6 ∼ = D3 × Z2 .

Does a similar argument apply to Dn , with n even, n ≥ 6? What about D4 ?

Exercise 3.11. If G ∼= H × Z2 , show that G contains an element a of order 2 with

the property that ag = ga for all g ∈ G . Deduce (briefly!) that the dihedral group
D2n+1 (where n ≥ 1) is not isomorphic to a product H × C2 .

Exercise 3.12. Show that no two of the three abelian groups of size 8

Z2 × Z2 × Z2 , Z2 × Z4 , Z8

are isomorphic.

Exercise 3.13. Let G be a group and let x ̸= y be elements of order 2 that

commute (so xy = yx). Show that {e, x, y , xy } is a subgroup of G isomorphic to
C2 × C2 .
58 CHAPTER 3. GOING BETWEEN GROUPS
Chapter 4

Groups Acting

4.1 Group Actions

We first met groups as symmetry groups: thus we were given not only a set of
symmetries, but an object which the symmetries are symmetries of. We formalise
this in the definition of a group action. Group actions will be the major topic in the
second half of the course.

Definition 4.1.1. Let G be a group, and let X be a nonempty set. Then a (left)
action of G on X is a map

G × X → X,

written (g , x) 7→ g · x, such that

g1 · (g2 · x) = (g1 g2 ) · x and e · x = x

for all g1 , g2 ∈ G and all x ∈ X .

The definition is dense, and a little hard to understand first time round. What
it says is that if we take an element g ∈ G and an element x ∈ X (i.e. an element
(g , x) ∈ G ×X ), we can combine them to produce another element of X (the image
of (g , x) under the map G × X → X ), which we denote g · x. We want to think
of elements of G as “symmetries” of X in some sense, although what this means
in practice can be a bit confusing.
In our blob picture of the set X , if we pick x ∈ X , and g ∈ G , then these
combine to produce some element g · x ∈ X . We think of this as “g takes x to
g · x” and draw it

59
60 CHAPTER 4. GROUPS ACTING

g ·x
g·

Example 4.1.2. Here are some examples of group actions:

1. Let G be the symmetry group of a graph, and let V be the set of vertices of
the graph. We claim that G acts on V by g · x := g (x).

Important special cases:

(a) The symmetric group Sn acts on the set {1, 2, ... , n}.
(b) The group Dn acts on the set {1, 2, ... , n}, where we think of the numbers
as labelling the vertices of the n-gon.

2. Let G be the symmetry group of a graph, and let E be the set of edges of the
graph. Then G acts on E , since if e ∈ E connects vertices v1 and v2 , define
g · e := the edge connecting g (v1 ) and g (v2 ). The two axioms follow in a
similar way as above.

3. A group can act on many different sets. For example Dn acts on the set
{1, 2, ... , n} as above. Alternatively, if we label the two faces of the n-gon
T , B (“top” and “bottom”), then Dn also acts on the set X := {T , B} where
g ∈ Dn acts by the identity if it leaves the n-gon the same way up (i.e. g is
a rotation), and by swapping T , B if it turns it over (i.e. g is a reflection).

4. Let G be any group and X any (nonempty) set. Then g · x := x for all g ∈ G
and all x ∈ X defines an action. We call this the trivial action. This action
tells us no information, but it does always exist.

5. G acts on itself (i.e. take X = G ), in many different ways. Three of these are
4.1. GROUP ACTIONS 61

(a) ‘Left action’ defined g · h := gh for all g ∈ G , h ∈ X = G . Thus the

action is left multiplication by g . This is an action because:

(b) ‘Right action’ defined g · h := hg −1 for all g ∈ G , h ∈ X = G . Thus

the action is right multiplication by g −1 . Note carefully that the inverse
g −1 appears.
(c) ‘Conjugate action’ defined g · h := ghg −1 for all g ∈ G , h ∈ X = G .

Check Your Understanding. Check that the definition of the right action of a
group on itself above does define an action.

Every action of a group G on a set X defines a subgroup: the elements of G

which act trivially on X .

Proposition 4.1.3. Suppose G acts on X . Define

N := {g ∈ G | g · x = x for all x ∈ X } .

Then N is a subgroup of G .

Check Your Understanding. Show that the subgroup N defined above is actually
a normal subgroup of G . (Hint: Exercise 3.4.)

Definition 4.1.4. Suppose that G acts on X . Then the subgroup N defined above
in Proposition 4.1.3 is called the kernel of the action. If N = {e} then we say that
the action is faithful. See [J,§15.2].

Thus an action is faithful if g · x = x for all x ∈ X implies that g = e. In words

“the only member of G that fixes everything in X is the identity”.
62 CHAPTER 4. GROUPS ACTING

Remark 4.1.5. Note in [J] the kernel of an action is denoted by ker ·, but this
notation is quite hard to read.
Example 4.1.6. Here are some examples and non-examples of faithful actions:
1. Let G be the symmetry group of a graph acting on the set V of vertices. Only
the identity fixes every vertex, so the action is faithful. (See Exercise 4.2.)
2. Let G be the rotational symmetry group of a Platonic solid acting on the set
of faces. Again, only the identity fixes every face, so the action is faithful.
3. The action of Dn on the set {T , B} in Example 4.1.2(3) is not faithful, since
for example the rotation g fixes both T and B.
Check Your Understanding. Do Exercises 4.1 and 4.2.

4.2 Orbits and Stabilizers

We build up to the next main theorem in the course, the orbit–stabilizer theorem
(Corollary 4.3.5). This section covers [J, §7.2, §7.3].
Definition 4.2.1. Let G act on X , and let x ∈ X . The stabilizer of x is defined to
be
StabG (x) := {g ∈ G | g · x = x} .
We will omit the G from the notation when it is clear what group we are considering.
Lemma 4.2.2. For all x ∈ X , the stabilizer StabG (x) is a subgroup of G .
Proof. See Problem 4.3.
Check Your Understanding. If G acts on X , let N be the kernel of the action (see
Definition 4.1.4). Prove that N is the intersection of all of the stabilizer subgroups:
\
N= StabG (x).
x∈X

Definition 4.2.3. Let G act on X , and let x ∈ X . The orbit of x under G is

OrbG (x) = {g · x | g ∈ G } .
The orbit is all the elements of X that you can ‘reach’ from x by applying
elements of G , so in the picture below, all of the labelled points lie in OrbG (x):

g1 · x
g1 ·

x g2 · g2 · x
4.2. ORBITS AND STABILIZERS 63

In contrast, the stabilizer is all the elements of G that don’t ‘move’ x, i.e. all those
g ∈ G for which the picture looks like this:

g·

In particular, note that the orbit is a subset of X , and the stabilizer is a subset (in
fact a subgroup) of G .
Example 4.2.4. Here are some examples of orbits and stabilizers:
1. Consider the symmetry group G of the graph

v1 v2 v3

Then G = {e, h} where h is the following reflection:

Thus
OrbG (v1 ) = {g · v1 | g ∈ G } = {v1 , v3 }
OrbG (v2 ) = {g · v2 | g ∈ G } = {v2 }
OrbG (v3 ) = {g · v3 | g ∈ G } = {v3 , v1 }
and
StabG (v1 ) = {g ∈ G | g · v1 = v1 } = {e}
StabG (v2 ) = {g ∈ G | g · v2 = v2 } = {e, h} = G
StabG (v3 ) = {g ∈ G | g · v3 = v3 } = {e}.

2. Let H ≤ G and consider the ‘right action’ of H on G = X defined by h · g :=

gh−1 (you need an inverse for the same reason as in Example 4.1.2(5)(b)).
Then the orbit containing g ∈ G is precisely
64 CHAPTER 4. GROUPS ACTING

The stabilizer of g ∈ G = X is

3. See Problems 4.3 – 4.7 for more examples of orbits and stabilizers.

Check Your Understanding. Let H ≤ G and consider the ‘left action’ of H on G

defined by h · g := hg . Show that the orbits under this action are the right cosets
of H in G .

Theorem 4.2.5. [J, 8.4] Let G act on X . Then

x ∼ y ⇐⇒ y = g · x for some g ∈ G

defines an equivalence relation on X . The equivalence classes are the orbits of G .

Thus when G acts on X , we obtain a partition of X into orbits.

Example 4.2.6. Continuing Example 4.2.4(1), G acts on the set of vertices V =

{v1 , v2 , v3 }, and by our previous calculation, {v1 , v3 } ∪ {v2 } is the partition of V
into orbits.

Definition 4.2.7. An action of G on X is transitive if for all x, y ∈ X there exists

g ∈ G such that y = g · x. Equivalently, X is a single orbit under G .

Example 4.2.8. 1. For any given graph, as in Example 4.1.2 part 1, the group
of symmetries acts on the set of vertices. This action may or may not be
transitive (see Problem 4.2).

2. The dihedral group acts transitively on the set of vertices V of the n-gon.
Let v1 , v2 be vertices, then certainly there exists some rotation g t for which
v1 = g t · v2 .

Check Your Understanding. Do Exercises 4.2, 4.3, and 4.4.

4.3. THE ORBIT-STABILIZER THEOREM 65

4.3 The Orbit-Stabilizer Theorem

The material in this section is from [J, §11.1].
The Orbit-Stabilizer Theorem is the second main result of the course. We state
it here:
Theorem 4.3.1. Suppose G is a finite group acting on a set X , and let x ∈ X .
Then |OrbG (x)| × |StabG (x)| = |G |, or in words

size of orbit × size of stabilizer = order of group.

In particular, the size of an orbit divides the order of the group.

We prove the Orbit-Stabilizer Theorem by showing that there is a bijection
between the orbit OrbG (x) and the set of left cosets of StabG (x), and our next task
is to set up the machinery to define the bijection.
Notation 4.3.2 ([J, top p87]). Suppose G acts on X and x, y ∈ X . If y and x are
in the same orbit,
sendx (y ) := {g ∈ G | g · x = y }
is a non-empty subset of G .
Proposition 4.3.3. [J, p107] Let G act on X , let x ∈ X and set H := StabG (x).
If y = g · x for some g ∈ G (i.e. y and x are in the same orbit), then

sendx (y ) = gH.

Recall from Definition 2.3.6 that if H ≤ G then we write G /H for the set (which
might not be a group!) of left cosets of H in G .
Theorem 4.3.4. [J, p117] Let G act on X , let x ∈ X , and set H := StabG (x)
Then the map

sendx : OrbG (x) → G /H which sends y 7→ sendx (y )

is a bijective map of sets.

66 CHAPTER 4. GROUPS ACTING

We can now prove Theorem 4.3.1, which we restate below.

Corollary 4.3.5 (The orbit-stabilizer theorem). Suppose G is a finite group
acting on a set X , and let x ∈ X . Then |OrbG (x)| × |StabG (x)| = |G |, or in words

size of orbit × size of stabilizer = order of group.

In particular, the size of an orbit divides the order of the group.

Proof. By Theorem 4.3.4 |OrbG (x)| = |G / StabG (x)|. By Corollary 2.4.3 this is
|G |
equal to |Stab G (x)|
.

Check Your Understanding. Do Exercise 4.8.

4.4 First applications of the Orbit-Stabilizer Theo-

rem
The orbit–stabilizer theorem is useful both theoretically and computationally (see
below, and the problem sheets, for both theory and nice applications), so it is very
important.
Example 4.4.1. Here are some sample practical applications:
1. (Order of the groups of rotational symmetries of Platonic solids) Let G be
the rotational symmetry group of the tetrahedron. Consider G acting on the
set F of four faces, and pick a face f ∈ F . Since the action is transitive (you
can take any face to any other face just by rotating), OrbG (f ) = F , so in
particular |OrbG (f )| = 4. Also, the stabilizer StabG (f ) consists of just the
identity together with the rotations about the centre of that face. Thus

|G | = |StabG (f )| × |OrbG (f )| = 3 × 4 = 12.

A similar argument applies to all Platonic solids — see Problem 4.9.

On the other hand, as a theoretical application of the orbit–stabilizer theorem,
we have the following.
Theorem 4.4.2 (Cauchy’s Theorem). Let G be a group, p be a prime. If p divides
|G |, then G contains an element of order p.
4.4. FIRST APPLICATIONS OF THE ORBIT-STABILIZER THEOREM 67

Proof. We divide the proof into steps:

1. Consider the set

X := {(g0 , g1 , ... , gp−1 ) ∈ G × ... × G | g0 g1 ... gp−1 = e}.

| {z }
p

Then |X | = (|G |)p−1 since the first p−1 elements g0 , ... , gp−2 can be arbitrary
and then there is one and only one gp−1 such that (g0 ... gp−2 )gp−1 = e (by
Lemma 1.4.6).

2. We next claim that

k · (g0 , g1 , ... , gp−1 ) := (gk , gk+1 , ... , gp−1 , g0 , ... , gk−1 )

defines an action of the group Zp on X . The key is to show that k ·

(g0 , g1 , ... , gp−1 ) ∈ X , as the remaining axioms are easy. This is just be-
cause

(g0 ... gk−1 )(gk ... gp−1 ) = e ⇐⇒ (gk ... gp−1 )(g0 ... gk−1 ) = e,

since an element always commutes with its own inverse.

3. Note that the orbits of size one are those of the form {(g , g , ... , g )} where
g p = e.

4. Since |Zp | = p, by orbit-stabilizer (applied to the action of Zp on the set X )

every orbit has size 1 or size p, since its size must divide |Zp | = p. Since
orbits partition X ,
X
|X | = |Oi | .
orbits Oi

Certainly there is at least one orbit of size one (namely (e, e, ... , e)), so
X
|X | = 1 + |Oi | (4.1)
all other orbits

Now by step 1, |X | is a multiple of p, so if all of the remaining orbits have size

p, the equation (4.1) gives a contradiction. Hence at least one other orbit
must have size one, so by step 3 there exists at least one g ̸= e with g p = e.

This shows that o(g ) ≤ p, in fact it shows that p must be a multiple of o(g ) by [J,
Thm 3(iii), p60]. Since p is prime and o(g ) ̸= 1, it follows that o(g ) = p.

See Problem 4.11 for another theoretical application of the orbit–stabilizer the-
orem.

Check Your Understanding. Do Exercises 4.9 and 4.10.

68 CHAPTER 4. GROUPS ACTING

4.5 Exercises
Suitable questions from Jordan and Jordan
ˆ Chapter 1, Questions 4–10 are good practice for orbits and stabilizers.

ˆ Chapter 7, Questions 1–4, 8–9 and 13–15 and Chapter 11, Questions 1 and
5–8 mainly involve the orbit–stabilizer theorem.

Exercises on group actions

Exercise 4.1. Let a group G act on X . Show that if y = g · x then x = g −1 · y .

(Note: you must argue from the axioms for a group action.)

Exercise 4.2. Show that the symmetry group of any graph always acts faithfully
on the set of vertices. Find a graph (with at least two edges) whose symmetry
group acts transitively on the set of vertices. Find one whose symmetry group does
not act transitively.

Exercises on orbits and stabilizers

Exercise 4.3. Let G act on X and let x ∈ X . Prove that the stabilizer of x is a
subgroup of G .

Exercise 4.4. Consider the group G = Sn acting on X = {1, 2, ... , n}. Let x = n.
How many elements does the stabilizer StabG (x) have? To what group is this
stabilizer isomorphic?

Exercise 4.5. Fix a line L through opposite vertices of a cube. Consider the
subgroup H of the symmetries of the cube generated by g , where g is a rotation
by 1/3 of a turn about L (this is the element in Problem 1.5). Then H acts on the
set of vertices of the cube. Describe the orbits.
Exercise 4.6. Consider the rotational symmetry group G of the cube acting on
the set of vertices of the cube. Describe the stablizer of a particular chosen vertex.
How many elements does it have? Now do the same for the action of G on the set
of faces and the set of edges.

Exercise 4.7. Consider the group G = GL(2, Z2 ). Then G acts on the vectors in Z22
in the usual way by multiplication. Let X be the set of 1-dimensional subspaces of
Z22 . Then G acts on X . Show that |G | = 6, |X | = 3, and that every permutation of
the elements of X is realized by an element of G . (Hence this is another realization
of S3 acting by permutation on {1, 2, 3}.)

Exercises on the orbit–stabilizer theorem

4.5. EXERCISES 69

Exercise 4.8. Check the orbit-stabilizer theorem for the case of the group Sn acting
on a set of n objects by permuting them.

Exercises on first applications and Cauchy’s theorem

Exercise 4.9. The rotational symmetry group G of a dodecahedron acts transi-

tively on the set V of its 20 vertices. Pick v ∈ V . How many elements are in the
stabilizer of v ? (You may have to make the model of the dodecahedron and play
with it.) Deduce the order of G . Using a similar method, deduce the order of the
group of rotational symmetries of the octahedron.

Exercise 4.10. By Problem 4.9 you should know that there are 24 elements in the
group of rotational symmetries of the octahedron. What are they? (You just have
to describe 24 distinct symmetries, then automatically you have them all.)

Exercise 4.11. (Challenge question — Sylow’s 1st Theorem) Let G be a finite

group and let p be a prime factor of |G |, and suppose that k ∈ N is largest such
that p k divides |G |. Then G contains a subgroup H such that |H| = p k . Prove this
in stages:

1. Let S := {U ⊆ G : |U| = p k }, i.e. the set of all subsets of G with p k

elements. Show that G acts on S via the rule g · U := gU.
2. Argue that p does not divide |S|.
3. By 1, S is partitioned into orbits. Using 2, deduce that there exists an orbit
A such that p does not divide |A|.
4. Pick an element V ∈ A, and consider H := StabG (V ). Why is H a subgroup?
5. Argue that p k divides |H| by using the orbit-stabilizer theorem.
6. Argue directly that |H| ≤ p k .

7. By combining your answer to 4, 5 and 6, prove the 1st Sylow Theorem.

70 CHAPTER 4. GROUPS ACTING
Chapter 5

Counting and Cayley

5.1 Pólya counting

Pólya counting is a beautiful application of group theory and of the Orbit-Stabilizer
Theorem: it is a very clever way of counting things that at first glance seem to be
hard to count.
To state the theorem, we need the following
Definition 5.1.1. Let G be a finite group acting on a finite set X . For g ∈ G
define the fixed point set of g to be
Fix(g ) := {x ∈ X | g · x = x}
Thus |Fix(g )| is the number of elements of X that g fixes.
In the picture below, x is in Fix(g ), but y is not:

g· y
g·

x g ·y

We have the following beautiful formula, which is known by several names: the
orbit-counting theorem, Burnside’s lemma, the Pólya counting theorem. We’ll call
the technique from this theorem Pólya counting in this course.
Theorem 5.1.2 ([J, 11.3]). Let G be a finite group acting on a finite set X . Then
1 X
the number of orbits in X = |Fix(g )| .
|G |
g ∈G

71
72 CHAPTER 5. COUNTING AND CAYLEY

Proof. Consider the set

Z := {(g , x) | g · x = x} .
We compute |Z | in two different
P ways. Firstly, for each g ∈ G there are |Fix(g )|
possible x’s and so |Z | = g ∈G |Fix(g )|.
P On the other hand, for each x ∈ X there are |Stab(x)| possible g ’s, so |Z | =
x∈X |Stab (x)|.
|G |
But by orbit–stabilizer |Stab(x)| = |Orb(x)| , and so on comparing expressions for
|Z | we see that
X X |G |
|Fix(g )| = .
|Orb(x)|
g ∈G x∈X

and so
1 X X 1
|Fix(g )| = .
|G | |Orb(x)|
g ∈G x∈X

Finally, since orbits always partition X , this means we can split X into pieces
O1 , ... , On . Thus we can write
X 1 X 1 X 1
= + ... +
|Orb(x)| |Orb(x)| |Orb(x)|
x∈X x∈O1 x∈On
   
 1 1   1 1 
= + ... +  + ... +  + ... +
   
 |O1 | |O1 |   |On | |On | 
 
| {z } | {z }
|O1 | |On |
= 1 + ... + 1
= the number of orbits in X ,

as desired.

Example 5.1.3. How many essentially different ways are there of colouring the
vertices of a regular 7-gon with three colours? We will say that two colourings are
the same if they can be made to coincide by an element of the dihedral group D7 .
It is not required that every colouring uses all three colours.
Examples include

The colourings
5.1. PÓLYA COUNTING 73

are equivalent.
To solve this, we consider the action of D7 on the set X of all 37 = 2187 possible
colourings. The problem just asks how many orbits there are, so by Theorem 5.1.2
we must analyse the fixed points.

ˆ The identity fixes every coloured 7-gon in X , so |Fix(e)| = 2187.

ˆ Consider any non-trivial rotation (there are 6 of them). Clearly the only way
a coloured 7-gon is fixed under the action of a rotation is if all the colours on
all the vertices are the same. There are only 3 such diagrams.
ˆ Consider any reflection (there are 7 of them). Then for a coloured 7-gon to
be fixed, the colour of the vertex through which the reflection line passes can
be arbitrary, whereas the colours of the other vertices have to match up as in
the following picture:

Hence there are 34 = 81 choices, and so 81 fixed points per reflection.

Hence by Pólya counting the number of orbits is equal to

1
|G | (2187 + 3 + ... + 3 + 81 + ... + 81) = 198.
| {z } | {z }
6 7

Example 5.1.4. How many essentially different ways can a tetrahedron be coloured
using n colours, each face being a single colour? (Two colourings are regarded as
the same if one can be obtained from the other by a rotational symmetry.)
There are 12 rotational symmetries of the tetrahedron, and further we know their
explicit form. The group of rotational symmetries G acts on the set X of all possible
n4 colourings. The question asks for the number of orbits, so by Theorem 5.1.2 we
must analyse the fixed points.
ˆ The identity fixes everything, so |Fix(e)| = n4 .
ˆ Consider a vertex–face rotation (of which there are eight).

B
A
74 CHAPTER 5. COUNTING AND CAYLEY

Then for a colouring to be fixed, the face through which the rotation takes
place (A in the above picture) can have an arbitrary colour, whereas the
remaining faces must all have the same colour. Thus the fixed set contains
n2 elements.
ˆ Consider an edge-edge rotation (of which there are three)

B
A

For a colouring to be fixed, the face A in the picture must have the same
colour as the back face that touches the bottom line. Similarly, the face B
must have the same colour as the back face that touches the top line. Thus
the fixed set contains n2 elements.
Hence by Pólya counting the number of orbits is equal to
4
1
12 (n + n2 + ... + n2 + n2 + ... + n2 ) = 1 2 2
12 n (n + 11).
| {z } | {z }
8 3

Remark 5.1.5. See [J, §12] for many other types of these problems.
Remark 5.1.6. Read [J, §12.1] for what ‘essentially the same’ should mean in this
context.
Check Your Understanding. Do Exercises 5.1 and 5.2, as well as the problems in
[J, chapter 12].

5.2 Conjugacy and the class equation

In this section we let G act on itself, then apply the Orbit-Stabilizer Theorem.
Lemma 5.2.1. Let h ∈ G and g ∈ G := X . Then
h · g := hgh−1
defines an action of a group G on itself.
Proof.
5.2. CONJUGACY AND THE CLASS EQUATION 75

This action of G on itself is called the conjugation action. The orbits are called
the conjugacy classes of G . We say that g , g ′ ∈ G are conjugate if there exists
h ∈ G such that g ′ = hgh−1 . That is, two elements are conjugate if they lie in the
same conjugacy class.
Orbits of a group action of G on a set X always partition X (Theorem 4.2.5).
Since here X = G , the orbits of the conjugacy action (=the conjugacy classes)
partition G , so we can draw:

where the shaded piece is the conjugacy class containing g . By definition it contains
all the elements that are in the same orbit as g , i.e. all the elements h · g as h runs
through the elements of G . In mathematical symbols, the bold piece is thus

{hgh−1 | h ∈ G }.

Example 5.2.2. Here are some examples of conjugacy classes:

1. Two matrices in GL(n, R) are conjugate if and only if they are similar.

2. See Exercise 5.10 for the conjugacy classes in D4 .

3. See Section 5.3 for conjugacy in the symmetric group Sn .

Check Your Understanding. Let G be an abelian group. Determine the conjugacy

classes of G .

When G acts on itself via conjugation, the stabilizer of an element g ∈ G is the

subgroup
C (g ) := {h ∈ G | gh = hg } ,
which we call the centralizer of g in G .

Proof.
76 CHAPTER 5. COUNTING AND CAYLEY

Check Your Understanding. Give a one-sentence proof that C (g ) is a subgroup

of G .
Example 5.2.3. Here are some examples of centralizers of elements g in the group
G = GL(2, R). (It is a good exercise to check these calculations.)
1. If g = λ I for some λ ∈ R∗ , then gh = hg for any h ∈ G . Hence the
centralizer is C (g ) = GL(2, R), the whole group.
 
2. If g = 0a b0 with a ̸= b ∈ R∗ , then a matrix h commutes with g if and
only if it is diagonal. Hence C (g ) ⊂ GL(2, R) is the set of invertible diagonal
matrices.
 
Check Your Understanding. Let G = GL(2, R) and let g = 10 11 ∈ G . Deter-
mine the centralizer C (g ).
Definition 5.2.4. Let G be a group.
[J, 13.5] We define the centre of a group G to be

C (G ) := {g ∈ G | gh = hg for all h ∈ G } .

If g ∈ C (G ), we say that g is central.

T
It is easy to check that C (G ) = g ∈G C (g ), i.e. the centre of a group is
the intersection of all the centralizers. Indeed, the centre is precisely the kernel
of the conjugation action in the sense of Definition 4.1.4, while the centralizers
are the stabilizers of the action, so this is just a special case of the Check Your
Understanding problem from the beginning of Section 4.2.
Example 5.2.5. Here are some examples of centres of groups:
1. G is abelian if and only if C (G ) = G .
2. In GL(n, R) the centre is {λ I | λ ∈ R∗ }. See Exercise 5.8.
We obtain the following results entirely for free from the previous sections.
Corollary 5.2.6. Let G be a group.
1. For all g ∈ G , the centralizer C (g ) is a subgroup of G .
2. The centre C (G ) is a subgroup of G .
3. If G is finite and g ∈ G , then

(the number of conjugates of g in G ) × |C (g )| = |G | .

4. {e} is always a conjugacy class of G

5. {g } is a conjugacy class if and only if g ∈ C (G ). Hence C (G ) is the union
of all the one-element conjugacy classes.
5.2. CONJUGACY AND THE CLASS EQUATION 77

Proof. 1. C (g ) =TStabG (g ), and stabilizers are always subgroups (by Lemma 4.2.2).
2. Note C (G ) = g ∈G C (g ), and an intersection of subgroups is always a subgroup
(Exercise 2.3).
3. This is just the orbit-stabilizer theorem (Corollary 4.3.5).
4. If g is conjugate to e, then there exists h ∈ G such that g = heh−1 , so
g = hh−1 = e. Thus the only element conjugate to e is e itself.
5. {g } is a conjugacy class ⇐⇒ the only element conjugate to g is g itself ⇐⇒
g = hgh−1 for all h ∈ G ⇐⇒ gh = hg for all h ∈ G ⇐⇒ g ∈ C (G ).

The following is also just a special case of what we already know.

Theorem 5.2.7. Suppose that G is a finite group with conjugacy classes

Conj1 , ... , Conjn .

We adopt the convention that Conj1 = {e}. Let the conjugacy classes have sizes
c1 = | Conj1 |, ... , cn = | Conjn | (so that c1 = 1).

|G |
1. If g ∈ Conjk , then ck = |C (g )| . In particular, ck divides the order of the group.

2. We have
|G | = c1 + c2 + ... + cn ,

and further each of the cj divides |G |. This is called the class equation of G .

Proof. Part 1 is just the orbit-stabilizer theorem (Corollary 4.3.5) applied to the con-
jugacy action. Part 2 is a trivial consequence of G being partitioned into conjugacy
classes. Each cj divides |G | by part 1.

Example 5.2.8. See Problems 5.11 – 5.12 for examples of the class equation.
The class equation has theoretical consequences. The proof of part one in the
following should remind you of the argument in the proof of Cauchy’s Theorem
(Theorem 4.4.2).

Theorem 5.2.9. Let G be a group.

1. If |G | = p k where p is prime and k ∈ N, then |C (G )| ≥ p.

2. Every group G of order p 2 (where p is prime) is abelian.

Proof.
78 CHAPTER 5. COUNTING AND CAYLEY

Check Your Understanding. Do Exercises 5.3, 5.5, 5.10, and 5.12.

5.3 Conjugacy in Sn is determined by cycle type

This section is an extended example, where we work out the conjugacy classes in
the symmetric group Sn . We first give some basic facts about symmetric groups.
You are recommended to revise [J, §2] and [L, §20]. Recall
Definition 5.3.1. Let n ∈ N, let 1 ≤ r ≤ n and let {a1 , a2 , ... , ar } be r distinct
numbers between 1 and n. The cycle (a1 a2 ... ar ) denotes the element of Sn that
sends a1 to a2 , a2 to a3 , ..., ar −1 to ar , ar to a1 , and leaves the remaining n − r
numbers fixed. We say that the length of the cycle (a1 a2 ... ar ) is r .
It is clear that our choice of starting point for the cycle is irrelevant, so (a1 a2 ... ar ) =
(a2 ... ar a1 ) etc.
Definition 5.3.2. Two cycles (a1 a2 ... ar ) and (b1 b2 ... bs ) are disjoint if

{a1 , a2 , ... , ar } ∩ {b1 , b2 , ... , bs } = ∅.

For example, (1534) and (27) are disjoint, but (1534) and (57) are not.
Check Your Understanding. Prove that if σ1 and σ2 are disjoint cycles, then
σ1 σ2 = σ2 σ1 .
Theorem 5.3.3 (See [L, 20.3]). Every permutation can be written as a product of
disjoint cycles.
Proof. We will do this in one example, from which you will probably be able to
write down the general proof yourself (if not, consult [L, §20]). Consider
 
1 2 3 4 5 6 7 8 9
σ= .
5 7 4 1 3 6 2 9 8
5.3. CONJUGACY IN Sn IS DETERMINED BY CYCLE TYPE 79

Start with the number 1. Tracing through, 1 7→ 5 7→ 3 7→ 4 7→ 1 and we are back

where we started. Next, choose the lowest number which does not appear in this
cycle. Here, that is 2. Tracing through, 2 7→ 7 7→ 2 and again we are back at where
we started. Next, choose the lowest number which does not appear in the last
two cycles — here that is 6. Tracing through, 6 gets sent to itself. Next, choose
the smallest number that has not yet appeared. This is 8, and tracing through
8 7→ 9 7→ 8. Thus
σ = (1534)(27)(6)(89).
is a product of cycles.

Remark 5.3.4. Since disjoint cycles commute, above we could equally write

σ = (1534)(27)(6)(89) = (6)(89)(27)(1534) = (89)(6)(27)(1534) = · · · ,

etc., in any order.

Definition 5.3.5. Given σ ∈ Sn , write σ = σ1 · · · σk as a product of disjoint cycles

σ1 , ... , σk , as in Theorem 5.3.3. For each t = 1, ... , n let mt denote the number of
cycles in this product that have length t. Then we say that σ has cycle type

1, ... , 1, 2, ... , 2, ... , n, ... , n,

| {z } | {z } | {z }
m1 m2 mn

which we often write simply as 1m1 , 2m2 , ... , nmn .

For an equivalent way of defining cycle type, see Exercise 5.15.

Example 5.3.6. In S4 , the element (123)(4) has cycle type 1,3. The element (1234)
has cycle type 4. The identity e = (1)(2)(3)(4) has cycle type 14 .

Check Your Understanding. Express the permutation

 
1 2 3 4 5 6 7 8
σ= ∈ S8
5 4 3 2 7 6 8 1

as a product of disjoint cycles and determine its cycle type.

The conjugation action is easy to express in cycle notation:

Lemma 5.3.7. Let σ ∈ Sn , and write σ as a product of disjoint cycles, say

σ = (a1 ... ar )(b1 ... bs ) ...

Then for all τ ∈ Sn ,

τ στ −1 = (τ (a1 ) ... τ (ar ))(τ (b1 ) ... τ (bs )) ...

which is a product of disjoint cycles.

80 CHAPTER 5. COUNTING AND CAYLEY

Proof.

Theorem 5.3.8. Two permutations in Sn are conjugate if and only if they have the
same cycle type (up to ordering).

Proof. (⇒) is Lemma 5.3.7.

For (⇐) we need to prove that elements with the same cycle type are always
conjugate.

It turns out that we can easily count the number of elements of a given cycle
type in Sn , and thus determine the size of the conjugacy classes.

Theorem 5.3.9. The number of elements of Sn of cycle type 1m1 , 2m2 , ... , nmn is

n!
.
m1 ! ... mn !1m1 2m2 ... nmn

Check Your Understanding. Prove Theorem 5.3.9.

Example 5.3.10. Here are some examples of how to use this theorem:
5.4. ACTIONS, HOMOMORPHISMS, AND CAYLEY’S THEOREM 81

1. How many elements of type 12 , 3, 4 are there in S9 ? Well, m1 = 2, m3 =

1, m4 = 1 and all other m’s are equal to zero. By the formula, there are
9!
2.1.1.12 .31 .41 = 15120 such elements.

2. The three possible cycle types in S3 are 13 , and 1, 2, and 3. By the formula,
these contain one, three and two elements respectively.

3. By part 2, we can work out all the conjugacy classes in S3 . There are three
conjugacy classes (since there are three cycle types), and so the conjugacy
classes in S3 are described by

cycle type number of elements conjugacy class

13 1 {e}
1, 2 3 {(1)(23), (2)(13), (3)(12)}
3 2 {(123), (132)}

The class equation for S3 is thus 6 = 1 + 2 + 3.

4. How many elements are conjugate to (123)(4567)(8)(9) in S9 ? By Theo-

rem 5.3.8, this is equal to the number of elements of cycle type 12 , 3, 4. By
Theorem 5.3.9, this is equal to 15120.

Check Your Understanding. Do Exercise 5.17 (on conjugacy classes in S4 ).

5.4 Actions, homomorphisms, and Cayley’s Theo-

rem
We now explain a close connection between group actions and permutations.
If X is a set, we denote

bij(X ) := {bijections X → X }.

This is a group under composition of functions (just amend slightly the proof of
Theorem 1.2.4). Note that if X is finite, then bij(X ) = S|X | , the symmetric group
on |X | letters.
In this section we see that an action of the group G on the set X gives exactly
the same information as a group homomorphism from G to bij(X ).

Lemma 5.4.1 ([J, 7.4]). If G acts on a set X , then for all g ∈ G the map

fg : X → X

defined x 7→ g · x is a bijection.
82 CHAPTER 5. COUNTING AND CAYLEY

Proof.

Theorem 5.4.2. [J, 7.4, 9.3] Let G be a group, and let X be a set. Then

1. An action of G on X is equivalent to a group homomorphism ϕ : G → bij(X ).

2. The action is faithful if and only if ϕ is injective.

3. If the action is faithful, then ϕ gives an isomorphism of G with im ϕ ≤ bij(X ).

Proof. 1. Suppose that · defines an action. Then define ϕ : G → bij(X ) by g 7→ fg ,

where fg is defined as in Lemma 5.4.1. We know that fg ∈ bij(X ) by Lemma 5.4.1,
and further ϕ is a group homomorphism since

ϕ(g1 g2 ) = fg1 g2 sends x 7→ (g1 g2 ) · x = g1 · (g2 · x)

whereas the composition of functions ϕ(g1 )ϕ(g2 ) sends x 7→ g2 · x 7→ g1 · (g2 · x).

Hence, as functions it follows that

ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 ).

Conversely, given a group homomorphism ϕ : G → bij(X ), define g · x := ϕ(g )(x).

You can check that this gives a group action, and that these are inverse operations.
2. We have
Proposition 3.1.9
ϕ is injective ⇐⇒ ker ϕ = {e}
⇐⇒ {g ∈ G | fg = Id} = {e}
⇐⇒ {g ∈ G | fg (x) = x for all x ∈ X } = {e}
⇐⇒ {g ∈ G | g · x = x for all x ∈ X } = {e}
definition
⇐⇒ the action is faithful

3. By part 2, there is an injective group homomorphism ϕ : G → bij(X ), so the

result follows from Proposition 3.1.9.

This theorem has a remarkable consequence for the structure of finite groups:

Corollary 5.4.3 (Cayley’s Theorem). Every finite group is isomorphic to a sub-

group of a symmetric group.
5.5. APPLICATION TO PLATONIC SOLIDS 83

Proof. The left action of G on itself (g · h = gh) is faithful since if g ̸= e, then

gh ̸= h. Thus by Theorem 5.4.2 part 3, G is isomorphic to a subgroup of S|G | .

Example 5.4.4. Every finite group is isomorphic to a subgroup of a symmetric group,

but not necessarily in a unique way.

1. By Cayley’s Theorem, the group G of rotational symmetries of the dodecahe-

dron (which turns out to have order 60, see Exercise 4.9) is thus a subgroup
of S60 . Thus we have embedded our group G into another group, of order
60!. Note that 60! is a very large number.
But G also acts on the set X consisting of the 12 faces of the dodecahedron.
This action is faithful, since every nontrivial symmetry clearly sends at least
one face to a different one. Hence by Theorem 5.4.2 part 3, G is also a
subgroup of bij(X ) = S|X | = S12 .

2. Consider C3 = {e, g , g 2 } acting on itself (as in Cayley’s Theorem). Re-label

e ↔ 1, g ↔ 2 and g 2 ↔ 3. Then the action of g on X = G sends 1 to 2, 2
to 3, and 3 to 1, i.e. multiplication by g acts as the element
 
1 2 3
2 3 1

on the set
G =X =  {1, 2, 3}. Thus in Cayley’s Theorem, g gets sent to the
1 2 3
element of S3 . Hence
2 3 1
 
1 2 3
C3 = ⟨g ⟩ ∼
= ≤ S3 .
2 3 1

Check Your Understanding. Do Exercise 5.19 and Exercise 5.20.

5.5 Application to Platonic solids

As an application of the ideas of the previous section, we describe the rotational
symmetry groups of the Platonic solids.

5.5.1 Alternating groups

Before discussing Platonic solids, we define the alternating groups. Recall from [L,
§20] the definition of an even or odd permutation. If you reread this, especially the
definition of even permutations [L, p173], you might see that it can all be expressed
in the language of group actions:

Definition 5.5.1. Let n ∈ N and set

Y
P= (xi − xj ).
1≤i<j≤n
84 CHAPTER 5. COUNTING AND CAYLEY

Let X = {P, −P}. Then Sn acts on X by

Y
σ·P = (xσ(i) − xσ(j) )
1≤i<j≤n

If σ ∈ Sn has the property that σ · P = P, we say that σ is even. If σ · P = −P,

we say that σ is odd.
Remark 5.5.2. Since a cycle of length k is odd if and only if k is even, a permutation
σ ∈ Sn is even if and only if there are an even number of cycles of even length in
the cycle decomposition of σ.
Remark 5.5.3. Alternatively, σ ∈ Sn is even (odd) if and only if σ can be written
as a product of an even (odd) number of transpositions (swaps of two elements).
Check Your Understanding. Determine if the following permutations are even or
odd, and verify this by writing them as a product of transpositions:
1. (1 2 3 4)(5 6 7)
2. (1 2 3)(3 4 5)
Theorem 5.5.4. Let An denote the set of all even permutations in Sn . Then An is
a subgroup of Sn , with |An | = |S2n | = n!
2.

Definition 5.5.5. We call An the alternating group.

Example 5.5.6. The group A4 consists of the identity, eight 3-cycles and three
elements of cycle type 2, 2. Explicitly, these are
e, (123), (132), (124), (142), (134), (143), (234), (243), (12)(34), (13)(24), (14)(23).

5.5.2 Symmetry groups of Platonic solids

We now show how to use Theorem 5.4.2 to understand the symmetry groups of
Platonic solids. Working through the examples below is helpful in understanding
what is going on in Theorem 5.4.2 as well.
We first show how to reduce the number of shapes we need to think about from
5 to 3. On every Platonic solid, draw a dot at the centre of each face, and connect
two dots if the faces meet at an edge. We call the resulting polytope the dual.
Doing this1 , we obtain
1 Image from http://xploreandxpress.blogspot.co.uk/2011/05/fun-with-mathematics-art-and-

science-of.html
5.5. APPLICATION TO PLATONIC SOLIDS 85

So for example, the cube duals to the octahedron, which then duals back to the
cube. Hence we can draw a cube inside an octahedron inside a cube. Because of
this,
symm of (outer) cube ⊆ symm of octahedron ⊆ symm of cube
and thus we have equality throughout. This shows that the symmetries of the
cube gives the same group as symmetries of the octahedron (its dual). In exactly
the same way, the symmetries of the dodecahedron give the same group as the
symmetries of the icosahedron.
Thus, to determine the rotational symmetry groups of all the Platonic solids,
we need only determine
1. The rotational symmetry group of the tetrahedron.
2. The rotational symmetry group of the cube.
3. The rotational symmetry group of the dodecahedron.
We consider each in turn:

The cube Consider the group G of rotational symmetries of the cube, acting on
the set X of diagonals of the cube. Note that |X | = 4. This gives us a group
homomorphism ϕ : G → S4 = S|X | , as in Theorem 5.4.2. Now no non-identity
element of the cube fixes all the diagonals (we know all 24 rotational symmetries,
so just check each), hence the action is faithful. Again, by Theorem 5.4.2 this
shows that G ∼= im ϕ ≤ S4 . Since we already know that |G | = 24, this means that
im ϕ is a subset of S4 with 24 elements. But |S4 | = 4! = 24, so im ϕ = S4 . Hence
G∼ = S4 (via ϕ).
86 CHAPTER 5. COUNTING AND CAYLEY

The tetrahedron Let G be the group of rotational symmetries of the tetrahedron.

Then G acts on the set X of 4 vertices. Thus, as in Theorem 5.4.2 we have a group
homomorphism ϕ : G → S4 = S|X | . The only symmetry which fixes all the vertices
is the identity, hence ϕ is injective and so again G ∼
= im ϕ. Now all members of
G give even permutations of the vertices (since rotations about a vertex give 3-
cycles and rotations about midpoints of opposite edges have cycle-type 2,2), hence
G ∼= im ϕ ≤ A4 . Since |im ϕ| = |G | = 12 = |A4 |, necessarily im ϕ = A4 and so
G∼ = A4 .

The dodecahedron This is harder, but only because it is a little more difficult to
visualize. Pack the dodecahedron with 5 tetrahedra2 , as in

Let G be the group of rotational symmetries of the dodecahedron. Then G acts

on the set X of 5 tetrahedra. As above we have a group homomorphism ϕ : G →
S5 = S|X | , and the same strategy shows that G ∼
= A5 .

5.6 Exercises
Suitable questions from Jordan and Jordan
ˆ Chapter 11, Questions 2–4 and 9–10 involve fixed sets and Pólya counting.

ˆ Chapter 7, Questions 5 and 13–16 deal with group actions as homomorphisms

ˆ Chapter 9, Questions 6–8 deal with actions ↔ homomorphisms

ˆ Chapter 13, Q1–21 are good practice for conjugates, centralizers and centres
and cycle types.

ˆ Chapter 7, Questions 6–7 deal with signs of permutations

2 Image from http://davidf.faricy.net/polyhedra/platonic solids.html
5.6. EXERCISES 87

ˆ Chapter 12, Questions 1–14 cover symmetries of polyhedra, and also review
Pólya counting and actions as homomorphisms.

Exercises on Pólya counting

Exercise 5.1. Dice have the numbers 1, 2, 3, 4, 5, 6 on the faces of a cube in such
a way that opposite faces add up to 7. How many different dice are there? (Two
dice are the same if they differ by a rotational symmetry of the cube. There are 24
such symmetries.) You can solve this by “pure thought” only because the numbers
involved are small; try to find a group-theoretic answer.

Exercise 5.2. How many ways are there of colouring the vertices of a 6-gon with two
colours, where two colourings are regarded as the same if they differ by an element
of D6 ? (Be careful to think about the different sorts of rotation and reflection. )

Exercises on conjugate elements, centres and centralizers

Exercise 5.3. Let g ∈ G . Show that ⟨g ⟩ ≤ C (g ).

Exercise 5.4. Let g ∈ G . Prove directly (i.e. without using general properties of
group actions) that C (g ) ≤ G .
 
1 1
Exercise 5.5. Let A = ∈ G = GL(2, Z3 ). Show that |C (A)| = 4. What is
0 2
|G |? How many conjugates does A have in G ?

Exercise 5.6. Let ϕ : G → GL(n, k) be a group homomorphism. Show that the

function f : G → k defined by f (g ) = tr ϕ(g ) is constant on every conjugacy class
of G .
Exercise 5.7. Consider D6 , the symmetries of a regular hexagon. Let H ≤ G
be the subgroup consisting of the identity and the five nontrivial rotations. Let g
denote a rotation by 1/6 of a turn. Show that H ≤ C (g ). Find an element in D6
that does not commute with g and hence use Lagrange’s theorem to deduce that
C (g ) = H. From this, deduce that g is conjugate to only one other element of D6 ,
and find that element.
Exercise 5.8. Let n ∈ N. Show that the centre of GL(n, R) is {λ I | λ ∈ R∗ }. (It is
clear that the centre contains at least these matrices. The content in the question
is that it does not contain other things.)

Exercise 5.9. What is the centre of the dihedral group Dn ? (Hint: consider n odd
and even separately.)

Exercises on conjugacy classes

88 CHAPTER 5. COUNTING AND CAYLEY

Exercise 5.10. Find the conjugacy classes in D4 . (If necessary, cut out a square
from paper, label the corners and play with it.)

Exercise 5.11. Let G = H × K . Show that (h, k) is conjugate to (h′ , k ′ ) in G if

and only if h and h′ are conjugate in H, and k and k ′ are conjugate in K . This
shows that every conjugacy class in G is of the form C × D where C is a conjugacy
class in H, and D is a conjugacy class in K . Hence write down the class equation
for C2 × S3 .

Exercise 5.12. Write down the class equation for D4 . (You should have done most
of the work in Problem 5.10.)

Exercise 5.13. Let p be a prime. You know that every group of order p is cyclic,
and thus abelian (by Problem 2.4). You also know that every group of order p 2 is
abelian. Is the same true for p 3 , i.e. is every group of order p 3 abelian?

Exercises on conjugacy in Sn and cycle type

Exercise 5.14. Let σ ∈ Sn have cycle type l1 , ... , lk . What is the order of σ? What
are the possible orders of elements in S7 ?

Exercise 5.15. Let σ ∈ Sn and let H := ⟨σ⟩ act on {1, 2, ... , n} in the obvious way.
Convince yourself that the cycle type of σ is the list of the sizes of all the orbits of
this action.

Exercise 5.16. Consider the cycles c = (125) and d = (234) in S5 . Find g ∈ S5

such that d = gcg −1 . How many such g are there?

Exercise 5.17. S4 has five conjugacy classes. Find them, and the number of
elements in each, and hence write down the class equation for S4 .

Exercise 5.18. Show that (12)(34) together with its conjugates and the identity
form a subgroup of S4 isomorphic to C2 × C2 .

Exercises on actions, homomorphisms, and Cayley’s theorem

Exercise 5.19. Let D3 act on itself by conjugation. Write down the corresponding
homomorphism D3 → S|D3 | = S6 given by Theorem 5.4.2. Is the action faithful?

Exercise 5.20. Identify the subgroup of S4 that arises in Cayley’s theorem applied
to C2 × C2 . Do the same for C4 .

Exercises on alternating groups

5.6. EXERCISES 89

Exercise 5.21. Let σ ∈ Sn . Another notation for writing σ is the following: write
the numbers 1, ... , n in two rows, one above the other. Then for every number i in
the top row, draw a line between i (in the top row) and σ(i) on the bottom row,
for example
1 2 3 4 5

1 2 3 4 5

represents 1 7→ 1, 2 7→ 4, 3 7→ 2, 4 7→ 3 and 5 7→ 5. From this picture, can you tell

whether a permutation is odd or even? Also, how do you compose permutations
using this picture?

Exercise 5.22. Prove that A4 is not isomorphic to D6 .