MATH40003 Linear Algebra and Groups
Part II: Groups
David Evans
Department of Mathematics, Imperial College
March 7, 2022
Contents
1 Groups and Subgroups 2
1.1 Binary operations; groups; basic facts . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Examples of groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Powers and Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Orders of elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 More on cyclic groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Generating other subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Lagrange’s Theorem and Cosets 15
3 Homomorphisms 18
4 More on Sn 22
4.1 Disjoint cycle form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Applications of disjoint cycle form . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Dihedral groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 The sign of a permutation; Determinants again . . . . . . . . . . . . . . . . 28
David M. Evans (2021) These notes are provided for the personal study of students taking this
module. The distribution of copies in part or whole is not permitted.
1
1 Groups and Subgroups
Lecture
10
1.1 Binary operations; groups; basic facts
Definition 1.1. Suppose S is a set. A binary operation on S assigns to each ordered
pair (a, b) of elements of S an element a b of S . More formally, is a function S×S → S .
(Where S × S is the Cartesian product set {(a, b) : a, b ∈ S} .)
This is a very general notion. Here are some examples involving M2(R): not all of them will
lead to groups!
Examples: Let S =M2(R). The following are binary operations on S .
(1) a b = ab , the usual matrix multiplication.
(2) is matrix addition.
(3) a b = a for all a, b ∈ A (‘projection onto the first coordinate’)
(4) a b = ab ba (called the Lie product).
(5) Let S1 = {a ∈ M2(R) : a is invertible} . For a, b ∈ S1 let a b be the usual matrix
product ab . As the product of two invertible matrices is invertible, this is a binary operation
on S1 .
(6) If in (5) we had taken a b = a + b , this would not be a binary operation on S1 as the
sum of two invertible matrices need not be invertible.
You will have seen this before:
Definition 1.2. A binary operation on a set S is associative if
for all a, b, c ∈ S we have a (b c) = (a b) c.
Exercise: Which of the binary operations above are associative
Associativity means that we can unambiguously write an expression such as
((a1 a2) (a3 a4)) a5
as a1 a2 a3 a4 a5 . The bracketing is redundant. From now on, we will usually do this
when dealing with associative operations.
Puzzle: How many ways are there of bracketing a1 a2 . . . an Try it for n = 4, 5. Can
you find a general expression
Now, here is the main definition.
Definition 1.3. A group (G, ) consists of a set G with a binary operation on G satisfying
the following:
2
G1 (Associativity) For all g, h, k ∈ G we have
(g h) k = g (h k).
G2 (Identity axiom) There exists an element e ∈ G such that for all g ∈ G we have
e g = g e = g.
We will show that G1 and G2 imply that there is a unique such e ∈ G , which we will denote
by e or eG and call it the identity element of the group.
G3 (Existence of inverses) With e as in G2, for all g ∈ G there is an element h ∈ G such
that
g h = h g = e.
We will show that the h here is uniquely determined by g : we call it the inverse of g and
usually denote it by h 1.
Remarks: Here, G1,G2,G3 are called the group axioms. In some books you will see that
the following is also included as an axiom:
G0 (Closure) If g, k ∈ G , then g k ∈ G .
It’s not necessary to include this as we are assuming that is a binary operation on G and
so G0 holds anyway.
Remarks 1.4. Here are some remarks on simplifications to notation and terminology which
we shall use throughout.
(1) It is more common to use . instead of for the group operation: so from now on, you
will see g.h rather than g h . In fact, just as in ordinary arithmetic, we often omit the .
and just write gh instead of g.h . We call the operation the product in the group.
(2) A group (G, ) is called abelian or commutative if for all g, h ∈ G we have g h = h g .
In such cases, we often write the operation as +. When we do this we write the identity
element as 0 and the inverse of g as g .
Remarks 1.5. We now justify the claims made in Definition 1.3. Suppose (G, .) is a group.
(1) We have to show the following, using axioms G1 and G2.
If e, e′ ∈ G and for all g ∈ G
e.g = g.e = g and e′.g = g.e′ = g
then e = e′ .
3
Proof: Using these equations, we have e = e.e′ = e′ (exercise: say which of the equations
were used here!) 2
(2) We have to show the following using the group axioms.
Suppose g, g′, g′′ ∈ G and
gg′
(1)
= e
(2)
= g′g and gg′′
(3)
= e
(4)
= g′′g.
Then g′ = g′′ .
Proof: We have
(g′g)g′′
(2)
= eg′′ = g′′ and g′(gg′′)
(3)
= g′e = g′.
So by Associativity g′ = g′′ .
[Exercise: Why is the following not a proof ‘From the equations, we have g′ = g 1 and
g′′ = g 1 , so g′ = g′′ .’]
We will use the following all the time, usually without mentioning that it’s what we are
using. It’s about manipulating equations in a group.
Lemma 1.6. (Equations in groups) Suppose (G, .) is a group and g, h ∈ G.
(1) For x ∈ G we have gx = h x = g 1h
(2) For y ∈ G we have yg = h y = hG 1 .
Proof: (1) : Multiply on the left by g 1 :
gx = h g 1(gx) = g 1h G1 (g 1g)x = g 1h ex = g 1h x = g 1h.
: Check that all of the above arrows can be reversed.
(2) Similar, but multiply on the right by g 1 . 2
The following will look very familiar from matrix multiplication.
Lemma 1.7. (Inverse of a product) Suppose (G, .) is a group.
(1) If g, h ∈ G, then (gh) 1 = h 1g 1 .
(2) If g1, . . . , gn ∈ G, then
(g1g2 . . . gn)
1 = g 1n . . . g
1
2 g
1
1 .
Proof: (1) Note that
(h 1g 1)(gh) = h 1(g 1)g)h = h 1eh = h 1h = e.
Similarly gh(h 1g 1) = e .
(2) Prove this by induction on n . The base case n = 2 is (1). 2
[Before the next lecture, review the material in the Introductory Module about Bijections
(Sections 2.3 and 2.4 there).]
4
1.2 Examples of groups
Examples 1.8. Examples from fields Lecture
11
(1) R with the operation + is a group. The identity element is 0 and the inverse of a ∈ R
is a . We refer to this as the additive group of the field R .
(2) R× = R {0} with the operation . is a group. The identity element is 1 and the inverse
of a ∈ R× is a 1 . We refer to this as the multiplicative group of the field R .
(3) Examples (1), (2) work with any field, not just R .
(4) If F is any field and n ∈ N , then (F n,+) is a group.
(5) If V is a vector space (over a field F ) then (V,+) is a group.
(6) Let n ∈ N and suppose F is a field. The general linear group GL(n, F ) (or GLn(F )) is
the set G of n × n invertible matrices (over F ) and operation matrix multiplication. This
is a group:
Binary operation: If A,B ∈ G , you can check that AB ∈ G (because the inverse of
AB is B 1A 1 ).
G1, Associativity: If A,B,C ∈ G , then A(BC) = (AB)C : this is a general property
of matrix multiplication.
G2, Existence of identity element: The identity matrix In ∈ G has the required
property.
G3, Existence of inverses: this follows from the definition of G .
Note: GL(1, F ) is the multiplicative group F× .
Definition 1.9. The Symmetric Groups.
Suppose X is any (non-empty) set. (For example, X = {1, 2, . . . , n} .) A permutation of X
is a bijection α : X → X .
For example, if X = {1, 2, 3, 4} let α be the map denoted by:(
1 2 3 4
2 4 1 3
)
with α(1) = 2, α(2) = 4, etc.
More generally we use the following ‘two-row’ notation for permutations on the set X =
[n] = {1, 2, . . . , n} . We denote a permutation α : [n]→ [n] by:(
1 2 . . . n
α(1) α(2) . . . α(n)
)
.
5
Note that the second row here is a ‘rearrangement’ of 1, 2, 3, . . . , n .
Exercise: If α, β : X → X are permutations, then so is the composition α β : X → X
(α β)(x) = α(β(x)), for x ∈ X.
– See the Introductory Module if you are unsure about this.
Example: If
α =
(
1 2 3 4
2 4 1 3
)
and β =
(
1 2 3 4
2 1 4 3
)
then
α β =
(
1 2 3 4
4 2 3 1
)
and β α =
(
1 2 3 4
1 3 2 4
)
.
Let Sym(X) denote the set of all permutations of X . If n ∈ N and X = [n] = {1, 2, . . . , n} ,
we will also denote this by Sym(n) or Sn .
Theorem 1.10. Suppose X is any (non-empty) set. Then Sym(X) with the operation of
composition is a group. It is called the symmetric group on X .
Proof: By the above exercise, we know that is a binary operation on Sym(X). We proceed
to check the group axioms.
G1 (Associativity): Composition of functions is associative: if α, β, γ ∈ Sym(X), then
α (β γ) and (α β) γ are the same function X → X (for x ∈ X they both send x to
α(β(γ(x)))).
G2 (identity element): The identtity function ι : X → X , with ι(x) = x for all x ∈ X , is in
Sym(X) and has the required properties.
G3 (Existence of inverses): If α ∈ Sym(X), then it is a bijection and so has an inverse α 1
which is also a bijection: α 1(y) = x α(x) = y . 2
Remarks: If α, β ∈ Sym(X) we will often write αβ instead of α β . Remember that this
is composition of functions and so this means ‘apply β first, then α .’
Warning: Some books or lecture notes will use the notation the other way round.
Example/ Exercise: Consider the following elements of S6 :
α =
(
1 2 3 4 5 6
2 3 4 5 6 1
)
and β =
(
1 2 3 4 5 6
1 6 5 4 3 2
)
.
Compute αβ, βα, α 1, β 1, αβα 1.
Label the vertices of a regular hexagon 1, 2, 3, 4, 5, 6 (clockwise) and think about how the
permutations α, β and these other permutations correspond to symmetries of the regular
hexagon.
Definition 1.11. We say that a group (G, .) is a finite group if the set G is a finite set. In
this case, the order of (G, .) is |G| , the number of elements in the group.
6
Theorem 1.12. If n ∈ N, then |Sn| = n!
Proof: We have to count the number of permutations
α =
(
1 2 . . . n
a1 a2 . . . an
)
where a1, . . . , an are 1, . . . , n in some order.
There are
n choices for a1 ;
n 1 choices for a2 ;
n 2 choices for a3 ;
. . .
So there are a total of n(n 1)(n 2) . . . 2.1 = n! possibilities for α . 2
1.3 Powers and Subgroups
Lecture
12Definition 1.13. Suppose (G, ·) is a group. For g ∈ G , we let
g0 = e, g1 = g, g2 = g · g, g3 = g · g · g, . . . .
More precisely, for n ∈ N we define inductively
g0 = e, g1 = g and gn+1 = gn · g.
We also define g n = (g 1)n .
Using this as our definition, we can then prove the following.
Lemma 1.14. With this notation, if m,n ∈ Z, then
(o) gm+1 = gmg and gmg = ggm ;
(i) (gm) 1 = g m ;
(ii) gmgn = gm+n = gngm ;
(iii) gmn = (gm)n .
Example: Let
g =
(
1 2 3 4
2 3 4 1
)
∈ S4.
Then
g2 =
(
1 2 3 4
3 4 1 2
)
, g3 =
(
1 2 3 4
4 1 2 3
)
= g 1, g4 = ι, g5 = g, . . . , g19 = g3
7
the last of these because 19 = 4.4 + 3 and so
g19 = (g4)4g3 = ι4g3 = g3
using the lemma.
Similarly if n ≡ k (mod 4), gn = gk .
Proof of Lemma: It’s not trivial to get all of the details correct, though it is quite tedious.
The proof should remind you of some things you discussed around Peano’s axioms in the
Introductory module.
(o) For the first part, if m ≥ 0, this is by definition. So assume m = k where k ∈ N
and prove by induction on k that g k+1 = g kg . The base case is k = 1, which follows
from g0 = e = g 1g . For the inductive step suppose we know g k+1 = g kg . Then
g (k+1)g = (g 1)k+1g = ((g 1)kg 1)g = g k , as required (the first two equalities comes from
the definitions). The second part is an exercise.
(i) Prove for m ≥ 0 that (gm)(g m) = e , by induction on m . Then deduce for m < 0.
(ii) We first prove this for n ≥ 0. We do this by induction on n , regarding m as fixed.
Base case n = 0: We have gm+0 = gm and gmg0 = gme = gm , so gm+0 = gmg0 .
Inductive step: Suppose we know that gm+n = gmgn . Then
gm+(n+1) = g(m+n)+1
(o)
= gm+ng = (gmgn)g = gm(gng) = gmgn+1
as required.
Exercise: Complete the proof of (ii) by considering the case n < 0.
(iii) Similar, using (ii). 2
Remark: on additive notation. If our group is (G,+) and n ∈ N , we write g + . . .+ n (n
times) as ng (not gn ).
Definition 1.15. Suppose (G, .) is a group and H G . We say that H is a subgroup of
G (or of (G, .)) if H with the binary operation from G is a group, that is:
for all h1, h2 ∈ H we have h1.h2 ∈ H
and (H, .) satisfies axioms G1,G2,G3. We will write H ≤ G to indicate that H is a subgroup
of G .
Examples: (1) G is a subgroup of G ;
(2) {e} is a subgroup of G .
In practice, what we use to decide whether a given subset of a group is a subgroup is the
direction of the following.
8
Theorem 1.16. (Test for a subgroup) Suppose (G, .) is a group and H G. Then H is a
subgroup of G if and only if
(1) H = ;
(2) for all h1, h2 ∈ H we have h1h2 ∈ H (closure under the group operation);
(3) for all h ∈ H we have h 1 ∈ H (closure under inverses).
Example: If g ∈ G , let H = {gm : m ∈ Z} . This is a subgroup of G , by 1.16 and 1.14.
Proof of 1.16: : Suppose (1), (2), (3) hold for H . By (2), the multiplication . in G gives
a binary operation on H . So we need to check that (H, .) satisfies the group axioms.
G1 follows from associativity in G .
For G2, it is enough to show that eG ∈ H . By (1), there is some h ∈ H . By (3), h 1 ∈ H .
Then by (2), hh 1 ∈ H . So eG ∈ H .
Then G3 follows from (3).
: If H is a subgroup of G , then (2) holds by definition.
By G2, we know that H = , so (1) holds.
For (3) we first show that eG ∈ H . Let h ∈ H . As (H, .) is a group, there is some x ∈ H
with hx = h . But the only solution to this equation in G is x = eG . So eG ∈ H . Similarly,
the only solution to hh′ = eG in G is h′ = h 1 . As H is a group, there must be a solution
in H , so h 1 ∈ H , as required for (3). 2
Remark: The direction shows that if H is a subgroup of G then eG ∈ H and inverses
are the same in H as they are in G .
Before we give some examples of using the test, we formalise the example given before the
above proof by giving some terminology.
Definition 1.17. (1) Suppose (G, .) is a group and g ∈ G . The cyclic subgroup generated
by g is g = {gm : m ∈ Z}.
(2) We say that a group G is cyclic if there is g ∈ G with g = G . In this case, g is called
a generator of G .
Examples 1.18. (1) Let G = GL(n,R) (the group of n × n invertible matrices over R).
We give some subgroups.
(1) Let H = {g ∈ G : det(g) = 1} . We use the subgroup test to check that this is a subgroup
of G :
H = as In ∈ H .
H is closed under . as det(g1g2) = det(g1)det(g2) so if g1, g2 ∈ H , then g1g2 ∈ H .
H is closed under inverses as det(g 1) = 1/det(g) for g ∈ G , so if h ∈ H , then h 1 ∈ H .
9
(2) You can use the subgroup test to show that
K = {
(
cos θ sin θ
sin θ cos θ
)
: θ ∈ R} ≤ GL2(R).
Note K consists of linear maps R2 → R2 given by rotations about 0. The subgroup
K is abelian, but not cyclic (for example, K is uncountable, whereas any cyclic group is
countable).
(3) We have:
2Z ≤ Z ≤ Q ≤ R ≤ (C,+),
where 2Z consists of the even integers. Note that Z = 1 and 2Z = 2 are cyclic, but
none of the other groups is cyclic.
(4) Consider the unit circle in the complex plane:
U = {eiθ : θ ∈ R} = {z ∈ C : |z| = 1} = {z ∈ C : zzˉ = 1}.
This is a subgroup of (C×, .), the multiplicative group of the field of complex numbers. It is
abelian, but not cyclic.
[Puzzle: What is the relationship to the group K in (2) ]
(5) Let n ∈ N and ζ = e2πi/n ∈ C× . So ζn = 1. Then ζ ≤ U and
ζ = {1, ζ, ζ2, . . . , ζn 1}
is a cyclic group of order n .
[Note that if you draw the elements of ζ on an Argand diagram, they form the vertices of
a regular n-gon on the unit circle.]
(6) Suppose F is any field and n ∈ N . Consider the group (F n,+). Any subspace of F n is
a subgroup of this, but the converse is not necessarily true. For example Q2 is a subgroup
of R2 , but it is not a subspace.
(7) Let
α =
(
1 2 3 4
2 1 4 3
)
, β =
(
1 2 3 4
3 4 1 2
)
, γ =
(
1 2 3 4
4 3 2 1
)
∈ S4.
Then V = {ι, α, β, γ} ≤ S4 is a subgroup of S4 , called the Klein four-group. We have g2 = ι
for all g ∈ V . So V is abelian but not cyclic.
[Remark: it would be good to revise thing in the Introductory module around the Division
- Remainder Theorem, gcd’s and the Euclidean algorithm.]
10
1.4 Orders of elements
Lecture
13
From now on we will usually write ‘G is a group’ instead of (G, .) is a group.’
Definition 1.19. Suppose G is a group and g ∈ G . We say that g has finite order if there
is n ∈ N (with n ≥ 1) such that gn = e . In this case, the least such n with gn = e is called
the order of g , denoted by ord(g). If there is no such n ∈ N , we say that g has infinite
order.
Examples: (1) For any group G , the identity element e has order 1.
(2)
(
1 2 3
2 3 1
)
∈ S3 has order 3;
(
1 2 3
2 1 3
)
has order 2.
(3) 2 ∈ R× has infinite order; 1 ∈ R× has order 2.
(4) For n ∈ N , ζ = e2πi/n ∈ C× has order n .
(5) The matrix
0 0 11 0 0
0 1 0
∈ GL3(R) has order 3.
(6) (Ex.) Think about orders of rotations in GL2(R).
Theorem 1.20. Suppose G is a group and g ∈ G has finite order n. Then:
(1) For m, l ∈ Z we have
gl = gm n | (l m) l ≡ m (modn).
(2) In particular, gm = e n | m.
(3) We have g = {e, g, g2, . . . , gn 1} and | g | = n.
So ord(g) = | g |.
Proof: (1) : Let s = l m and suppose n | s . So there is t ∈ Z with s = nt . Then
gs = gnt = (gn)t = et = e.
Thus e = gs = gl m = glg m. Multiplying by gm , we obtain gm = gl , as required.
: Suppose gl = gm . Then gl m = e . By the Quotient – Remainder Theorem (Introductory
Module, 3.2.3) there are q, r ∈ Z with
l m = qn+ r and 0 ≤ r < n.
Then
e = gl m = gqn+r = gqngr = (gn)qgr = egr = gr.
By minimality of n and 0 ≤ r < n , we therefore have r = 0. Thus n | (l m), as required.
11
(2) By (1) with l = 0.
(3) Every l ∈ Z is congruent modulo n exactly one of 0, 1, . . . , n 1. So the result we
require follows from (1). 2
The following is a useful simplification of the test for being a subgroup of a finite group.
Theorem 1.21. Suppose G is a finite group.
(1) Every element of G has finite order.
(2) If H G is a non-empty subset of G and for all h1, h2 ∈ H we have h1h2 ∈ H , then
H is a subgroup of G.
Proof: (1) Consider g, g2, g3, . . . ∈ G . As |G| is finite, there exist 0 < m < l with gm = gl .
Then gl m = e and l m > 0. So g has finite order.
(2) We have to show that H is closed under inverses. Let h ∈ H . By (1) there is n ∈ N
with hn = e . We want to show h 1 ∈ H . We can assume that h = e , so n > 1. Then
h 1 = hn 1 and n 1 ≥ 1. As h ∈ H and H is closed under multiplication, it follows that
hn 1 ∈ H . So h 1 ∈ H . 2
1.5 More on cyclic groups
Lecture
14The following tells us everything about subgroups of cyclic groups.
Theorem 1.22. Suppose (G, .) is a cyclic group and G = g .
(1) If H ≤ G, then H is cyclic.
(2) Suppose |G| = n (that is, g has order n), and m ∈ Z. Let d = gcd(m,n), the greatest
common divisor of m and n. Then
gm = gd and | gd | = n/d.
In particular,
gm = G gcd(m,n) = 1.
(3) If |G| = n and k ≤ n, then G has a subgroup of order k if and only if k | n. In this
case, the subgroup is gn/k .
Example/ Exercise: Let g = e2πi/6 ∈ C× and G = g . So G is a cyclic group of order
6. The subgroups of G have orders 1,2,3 and 6. They are:
{1} ;
g3 = {1, 1} ;
g2 = {1, g2, g4} ;
12
g = G .
There is one element of order 2, two elements of order 3, and two elements of order 6.
Proof of Theorem: (1) We may assume that H = {e} . Let d be the least element of
{n ∈ N : gn ∈ H} (noting that this set is non-empty).
Claim: H = gd .
As gd ∈ H and H ≤ G , we have gd ≤ H . So let h ∈ H . Then h = gm for some m ∈ Z .
We can write m = qd + r for some q, r ∈ Z with 0 ≤ r < d . So h = gqd+r = (gd)qgr .
Thus gr = h(gd) q ∈ H , as h ∈ H and gd ∈ H . Minimality of d therefore gives r = 0. So
h = gqd = (gd)q ∈ gd , as required.
(2) As d = gcd(m,n) there are k, l ∈ Z with d = km+ ln (the Be′zout Identity).
To show that gm = gd it is enough to prove that gm ∈ gd and gd ∈ gm . Because
d | m , gm is a power of gd , so the first of these is true. For the second, note that
gd = gkm+ln = (gm)k(gn)l = (gm)k
as n = ord(g), so gn = e . This gd ∈ gm .
Now consider what is | gd | . Because d | n we can write n = df for some f ∈ N . Then gd =
{g0, gd, . . . , g(f 1)d} as gfd = e . Now, g0, gd, g2d, . . . , g(f 1)d are distinct as d, . . . , (f 1)d
are less than n . It follows that | gd | = f = n/d .
(3) The first part is by (1) and (2). If k | n , then by (2), the unique subgroup with k
elements is gn/k . 2
An application. We will give an application of the previous theorem to prove a result due
to Gauss on the Euler totient function: an important function in elementary number theory.
You can find an application of Gauss’ result on the problem sheet, where it is used to prove
the useful fact that every finite subgroup of the multiplicative group of a field is cyclic.
Definition: For n ∈ N , the Euler totient function (n) is
|{k ∈ N : 1 ≤ k ≤ n and gcd(k, n) = 1}|.
Thej following Corollary to Theorem 1.22 is due to C. F. Gauss.
Corollary 1.23. For all n ∈ N we have∑
1≤d≤n, d|n
(d) = n.
Example: n = 6 has divisors d = 1, 2, 3, 6. We compute that (1) = 1, (2) = 1, (3) = 2,
(6) = 2. Summing these does indeed give 6.
Proof of Corollary: Let G be a cyclic group of order n . By 1.22(3), if d | n then G has a
unique subgroup Gd of order d . Thus, Gd contains every element of G of order d (because
this will generate a subgroup of order d).
13
We also know, by 1.22(1), that Gd is cyclic, and therefore by 1.22(2), Gd has (d) elements
of order d .
Any element of G has order dividing n = |G| (by 1.22(2)). Then counting elements of G
according to their possible orders (and therefore which Gd they generate) gives∑
1≤d≤n, d|n
(d) = n.2
1.6 Generating other subgroups
What about subgroups generated by more than one element In general, this is a much
harder question than understanding cyclic groups (or cyclic subgroups). But at least we can
make some definitions.
Definition 1.24. Suppose (G, .) is a group and S G is non-empty. Let
S 1 = {g 1 : g ∈ S}
and
S = {g1g2 . . . gk : k ∈ N and g1, g2, . . . , gk ∈ S ∪ S 1}.
So S is the set of all products of elements of S and their inverses (allowing repetitions).
We could also define = {e} , if we wish.
Lemma 1.25. With this notation:
(1) S is a subgroup of G.
(2) If H ≤ G and S H , then S H .
Proof: Exercise: use the test for being a subgroup. 2
So S is the ‘smallest’ subgroup of G containing S . It is called the subgroup of G generated
by S .
If S = {x1, . . . , xr} , write S as x1, . . . , xr .
If G is abelian then
x1, . . . , xr = {xk11 xk22 . . . xkrr : k1, . . . , kr ∈ Z}.
But in general, understanding x1, . . . , xr is a hard problem even for r = 2.
14
2 Lagrange’s Theorem and Cosets
Lecture
15In this section we will prove the following and give some applications. The method of proof,
involving cosets, is also an important idea which you will see more of in later modules.
Theorem 2.1. (Lagrange’s Theorem) Suppose (G, .) is a finite group and H is a subgroup
of G. Then |H| divides |G|.
So one thing that this tells us is that G = S5 , which has order 5! = 120, cannot have a
subgroup of order 50. Here are some more general applications.
Theorem 2.2. Suppose G is a finite group of order n. Let g ∈ G. Then:
(1) The order of g divides n.
(2) gn = e.
Proof: (1) The order of g is | g | (by 1.20(3)). As g is a subgroup of G , the result therefore
follows from Lagrange’s Theorem.
(2) Suppose ord(g) = k . By (1) we have k | n . Moreover gn = (gk)n/k = en/k = e. 2
As a special case we have the well-known:
Corollary. (Fermat’s Little Theorem) Suppose p is any prime. If x ∈ Z and p |x , then
xp 1 ≡ 1 (mod p).
[ It follows that for all k ∈ Z we have kp ≡ k (mod p).]
Proof: Let Fp be the field with p elements (that is, Zp ). Consider (F×p , .), the multiplicative
group of the field, consisting of the non-zero elements. Then |F×p | = p 1.
So for every g ∈ Fp , we have gp 1 = [1]p , the identity element of the field, the residue
class of 1, modulo p . If x ∈ Z and p |x , then [x]p = [0]p . So taking g = [x]p we obtain
[1]p = [x]
p 1
p = [x
p 1]p . In other words, xp 1 ≡ 1 (mod p). 2
Examples 2.3. Let G = S3 . So |G| = 6. Let α =
(
1 2 3
2 3 1
)
and β =
(
1 2 3
2 1 3
)
.
Then α, β = G .
Indeed, note that α has order 3 and β has order 2. As α, β ≤ S3 has subgroups α and
β , it follows from Lagrange’s theorem that the order of α, β is divisible by 2 and by 3,
and therefore by 6. As S3 has order 6, it follows that α, β = S3 .
Theorem 2.4. Suppose p is a prime and G is group of order p. Then G is cyclic. In fact,
if e = g ∈ G, then g = G.
Proof: By Lagrange’s Theorem | g | divides p . As e, g ∈ g and e = g we therefore have
| g | = p , because p is a prime. 2
We now turn to the proof of Lagrange’s Theorem and the key idea of cosets.
15
Definition 2.5. Suppose (G, .) is a group and H ≤ G . Let g ∈ G . The subset
gH = {gh : h ∈ H} G
is called a left coset of H in G . (Sometimes we will say ‘left H -coset.’)
So if H = {h1, . . . , hr} , then gH = {gh1, . . . , ghr} .
Another way of saying this is that a subset X of G is a left coset of H in G if there exists
some g ∈ G such that X = gH . Note that g ∈ gH , so this might give us some clue about
which g to take here.
[Remark: Some books, lecture notes and past exam questions will refer to right cosets
Hg = {hg : h ∈ H} . Essentially everything we do will also work with right cosets in place
of left cosets. But we should not mix them.]
In some situations, cosets are actually quite familiar. Here are some examples.
Examples 2.6. (1) Let G = (C×, .) and H = {z ∈ C× : |z| = 1} . So H is a subgroup of
G . Let g = 2 ∈ C× . Then the left coset
2H = {2eiθ : θ ∈ R} = {z ∈ G : |z| = 2}.
Note that this is not a subgroup of G .
More generally, if w ∈ C× , then wH = {z ∈ C× : |z| = |w|} .
(2) Let G = (Z,+) and H = {5m : m ∈ Z} . So H is a subgroup of G . As the group G is
written additively, we shall also write H -cosets additively:
0 +H = H = [0]5 ;
1 +H = {1 + 5m : m ∈ Z} = {k ∈ Z : k ≡ 1 (mod 5) = [1]5 ;
. . .
4 +H = [4]5 ;
. . .
6 +H = {6 + 5m : m ∈ Z} = {1 + 5m : m ∈ Z} = {k ∈ Z : k ≡ 1 (mod 5) = [1]5 .
So there are 5 left H -cosets
0 +H, 1 +H, . . . , 4 +H
and these partition G = Z .
(3) Let A be an m × n matrix with entries from R . Let W = {x ∈ Rn : Ax = 0m} , the
solution set of the system of homogeneous linear equations with coefficient matrix A . So W
is a subspace of (Rn,+), and therefore a subgroup. Suppose b ∈ Rm and there is c ∈ Rn
with Ac = b . Then
Ax = b A(x c) = 0 x c ∈ W x ∈ c+W.
So if the the set of solutions to Ax = b is non-empty, then it is a coset of W in Rn .
16
Lecture
16
We saw in these examples that, for a fixed subgroup H , the left H -cosets partition G : every
element of G is in exactly one left H -coset. The following lemma supplies the proof of this
in general.
Lemma 2.7. Suppose (G, .) is a group and H ≤ G.
(1) If g1, g2 ∈ G and g2 ∈ g1H , then g2H = g1H .
(2) If g, k ∈ G and gH ∩ kH = , then gH = kH .
Proof (1) We first show that if g2 ∈ g1H , then g2H g1H .
As g2 ∈ g1H there is h ∈ H with g2 = g1h . Any element of g2H is of the form g2h′ for
some h′ ∈ H . Then g2h′ = (g1h)h′ = g1(hh′). Because H ≤ G , we have hh′ ∈ H . So
g2h
′ ∈ g1H , as required.
Also g1 = g2h
1 and h 1 ∈ H , so g1 ∈ g2H . Thus, the same argument gives g1H g2H .
Putting the two parts together gives g1H = g2H .
(2) Let x ∈ gH ∩ kH . By (1), applied twice, we have gH = xH = kH . 2
Lemma 2.8. Suppose (G, .) is a group and H ≤ G. If g ∈ G, then the map H → gH given
by h 7→ gh is a bijection. In particular, if H is finite, then |H| = |gH|.
Proof: By definition, the map is surjective. Also, if gh1 = gh2 , then h1 = h2 , so the map is
also injective. 2
We can now give a proof of Lagrange’s Theorem.
Suppose G is a finite group and H ≤ G .
Consider the left cosets of H in G .
Any one of these has |H| elements (by 2.8).
Any two of them are disjoint (by 2.7).
Moreover, any g ∈ G lies in some left H -coset, namely gH .
Thus |G| is equal to |H| times the number of distinct left H -cosets.
So |H| divides |G| and |G|/|H| is equal to the number of left H -cosets in G . This concludes
the proof of Lagrange’s Theorem. 2
Definition 2.9. The number of left cosets of H in G is called the index of H in G .
Remarks: If G is finite, this is equal to |G|/|H| , by the above. It is also equal to the
number of right cosets of H in G , by the same proof. But it is also possible to write down
an explicit bijection between the set of left H -cosets and the set of right H -cosets. Can you
do this
17
We can give a different approach to the proof using equivalence relations, which you encoun-
tered in the Introductory Module. But this is really just the same proof!
Theorem 2.10. Suppose G is a group and H ≤ G. Define the relation ～ on G by
g ～ k g 1k ∈ H.
Then
(1) ～ is an equivalence relation on G.
(2) g ～ k iff gH = kH .
Proof: (1) is on Question sheet 6.
(2) By 2.7
g 1k ∈ H g 1kH = H kH = gH.2
Note that this tells us that the ～-equivalence classes are the left H -cosets.
Exercise: write down an equivalence relation on G whose classes are the right H -cosets.
Example / Exercise: Let G = S3 and H = α where α =
(
1 2 3
1 3 2
)
. What are the
left H -cosets
Note that H = {ι, α} so |H| = 2 and |G| = 6. So there are 3 left H -cosets, one of
which is H = ιH = αH . Take β =
(
1 2 3
2 3 1
)
. As β ∈ H we have βH = H and of
course βH = {β, βα} . We compute that βα =
(
1 2 3
2 1 3
)
. So let γ =
(
1 2 3
3 1 2
)
. As
γ ∈ H ∪ βH the remaining left H -coset is γH = {γ, γα} .
As a further exercise, you could write down the right H -cosets and observe, for example,
that βH = Hβ .
Another observation you could make is that:
H consists of the permutations taking 1 7→ 1;
βH consists of the permutations taking 1 7→ 2;
γH consists of the permutations taking 1 7→ 3.
Find an exercise on the problem sheets which relates to this.
3 Homomorphisms
We have spent some time discussing groups. Now we briefly consider the appropriate maps
between groups. You should think about how this compares with what happens with vector
18
spaces where the most important maps between vector spaces are linear maps: the maps
which ‘respect’ the vector space structure.
Definition 3.1. Suppose (G, .) and (H, .) are groups.
(1) A function : G→ H is a homomorphism if for all g1, g2 ∈ G we have
(g1g2) = (g1) (g2).
[Note that on the left hand side here, the product g1g2 uses the group operation in G whereas
on the right-hand side, the product (g1) (g2) uses the group operation in H .]
(2) If : G→ H is a homomorphism, the image of is
im = { (g) : g ∈ G}.
The kernel of is
ker = {g ∈ G : (g) = eH}.
(3) If the homomorphism : G→ H is a bijection, then we say that is an isomorphism.
We say that groups G , H are isomorphic if there exists an isomorphism : G → H . In
this case we write G ～= H .
If two groups are isomorphic, then, from the group theoretic viewpoint, they are really ‘the
same’ group with the elements labelled in a different way.
Before we give some examples, we note the following, which should remind you of basic
results (and their proofs) about linear maps.
Lemma 3.2. Suppose G,H are groups and : G→ H is a homomorphism. Then:
(i) (eG) = eH ;
(ii) (g 1) = ( (g)) 1 , for all g ∈ G;
(iii) im ≤ H and ker ≤ G.
Proof: (i) We have (eG) = (eGeG) = (eG) (eG). In H , the equation h = hh implies
h = eH , so we obtain (eG) = eH .
(ii) We have
eH
(i)
= (eG) = (gg
1) = (g) (g 1)
and so the result follows.
(iii) Exercise: use 1.16. 2
Examples 3.3. (0) (Trivial examples) Suppose G is any group. The identity map i : G→ G
(with i(g) = g for all g ∈ G) is an isomorphism.
If G,H are groups, the map ψ : G→ H with ψ(g) = eH for all g ∈ G is a homomorphism.
19
(1) Suppose F is a field and G = GL(n, F ). The determinant map
det : G→ (F×, .)
is a homomorphism, by the product formula det(g1g2) = det(g1)det(g2).
(2) Suppose (H, .) is any group and h ∈ H . Define : (Z,+) → H by (n) = hn , for
n ∈ Z . By the rules for exponents, we know that
(m+ n) = hm+n = hmhn = (m) (n)
so is a homomorphism. The image of is h . If h has infinite order, then ker = {0} .
If h has finite order n , then ker = nZ , by 1.20(2).
(3) The exponential map
exp : (R,+)→ (R>0, .)
is a homomorphism as exp(x+ y) = exp(x) exp(y). As exp here is also a bijection, we have
that it is an isomorphism (which may be a bit of a surprise as we would not normally think
of the groups (R,+) and (R>0, .) as being ‘the same group’).
(4) The modulus map | · | : (C×, .)→ (R×, .) is a homomorphism with kernel
{z ∈ C× : |z| = 1}