Math 120A — Introduction to Group Theory
Neil Donaldson
Fall 2023
1 Introduction: what is abstract algebra and why study groups?
To be abstract means to remove context and application. A large part of modern mathematics in-
volves studying patterns and symmetries (often those observed in the real world) from an abstract
viewpoint so as to see commonalities between structures in seemingly distinct places.
One reason to study groups is that they are relatively simple: a set and a single operation which
together satisfy a few basic properties. Indeed you’ve been using this structure almost since Kinder-
garten!
Example 1.1. The integers Z = {. . . , −1, 0, 1, 2, 3, . . .} together with the operation + is a group.
We’ll see a formal definition shortly, at which point we’ll be able to verify that (Z, +) really is a
group. The simplicity of the group structure means that it is often used as a building block for
more complicated structures.
1
Better reasons to study groups are their ubiquity and multitudinous
applications. Here are just a few of the places where the language of group theory is essential.
Permutations The original use of group was to describe the ways in which a set could be reordered.
Understanding permutations is of crucial importance to many areas of mathematics, particu-
larly combinatorics, probability and Galois Theory: this last, the crown jewel of undergraduate
algebra, develops a deep relationship between the solvability of a polynomial and the permuta-
tion group of its set of roots.
Geometry Figures in Euclidean geometry (e.g. triangles) are congruent if one may be transformed to
the other by an element of the Euclidean group (translations, rotations & reflections). More general
geometries are also be described by their groups of symmetries. Geometric properties may also
be encoded by various groups: for example, the number of holes in an object (a sphere has
none, a torus one, etc.) is related to the structure of its fundamental group.
Chemistry Group Theory may be applied to describe the symmetries of molecules and of crystalline
substances.
Physics Materials science sees group theory similarly to chemistry. Modern theories of the nature of
the universe and fundamental particles/forces (e.g. gauge/string theories) also rely heavily on
groups.
Of course, the best reason to study groups is simply that they’re fun!
1
For example, Z together with the two basic operations of addition and multiplication is a ring, as you’ll study in a
future course.
1
Example 1.2. To introduce the idea of abstraction, we consider what an equilateral triangle and the
set {1, 2, 3} have in common.
The obvious answer is the number three, but we can say a lot more. Both objects have symmetries:
rotations/reflections of the triangle and permutations of the set {1, 2, 3}. By considering compositions
of these symmetries, we shall see that the sets of such are essentially identical.
Permutations of {1, 2, 3} These can be written as functions using cycle notation.
2
For instance, the
cycle (1 2) is the function which swaps 1 and 2 and leaves 3 alone, while (1 2 3) permutes all three
numbers:
(1 2) :
1 7→ 2
2 7→ 1
3 7→ 3
and (123) :
1 7→ 2
2 7→ 3
3 7→ 1
It is not hard to convince yourself that there are six distinct permutations of {1, 2, 3}; for brevity, we
use the symbols e, µ
1
, µ
2
, µ
3
, ρ
1
, ρ
2
.
Identity: leave everything alone Swap two numbers Permute all three
e = () µ
1
= (2 3) ρ
1
= (1 2 3)
µ
2
= (1 3) ρ
2
= (1 3 2)
µ
3
= (1 2)
Since the permutations are functions, we may compose them. For instance (remember to do ρ
2
first!),
µ
1
◦ρ
2
= (2 3)(1 3 2) :
1 7→ 3 7→ 2
2 7→ 1 7→ 1
3 7→ 2 7→ 3
The result is the same as that obtained by the permutation (1 2) = µ
3
, whence we write
µ
1
◦ρ
2
= µ
3
The full list of compositions may be assembled in a table; read the left column first, then the top row.
◦ e ρ
1
ρ
2
µ
1
µ
2
µ
3
e e ρ
1
ρ
2
µ
1
µ
2
µ
3
ρ
1
ρ
1
ρ
2
e µ
3
µ
1
µ
2
ρ
2
ρ
2
e ρ
1
µ
2
µ
3
µ
1
µ
1
µ
1
µ
2
µ
3
e ρ
1
ρ
2
µ
2
µ
2
µ
3
µ
1
ρ
2
e ρ
1
µ
3
µ
3
µ
1
µ
2
ρ
1
ρ
2
e
2
We will return to this notation in Chapter 5, so don’t feel you have to be an expert now. The permutation (12) is known
as a 2-cycle because it permutes two objects. The permutation (123) is similarly a 3-cycle.
2
The Equilateral Triangle What does all this have to do with a triangle?
If we label the vertices of an equilateral triangle 1,2,3, then the above permutations correspond to
symmetries of the triangle: ρ
1
and ρ
2
are rotations, while each µ
i
performs a reflection in the altitude
through the i
th
vertex.
The two sets of symmetries apply to different objects, but the
structure of their compositions are identical.
What do we gain from this correspondence? Intuition, for one
thing! There is a qualitative difference between the rotations
ρ
1
, ρ
2
and the reflections µ
1
, µ
2
, µ
3
of the triangle: since reflections
flip the triangle upside down, it is completely obvious that com-
position of reflections produces a rotation! The corresponding
idea that composition of 2-cycles makes a 3-cycle is not so clear.
1
2
3
µ
1
µ
2
µ
3
ρ
1
ρ
2
Group theory, and abstract algebra more generally, is about ideas like this; by prioritizing abstract
symmetries and patterns associated to objects over the objects themselves, unexpected connections
are sometimes revealed.
Summary In this introductory example we considered two groups, which we now name:
S
3
is the symmetric group on three letters (permutations of {1, 2, 3})
D
3
is the dihedral group of order six (symmetries of the equilateral triangle)
The formal way to say that the resulting group structures are identical is to call them isomorphic,
3
and
we’ll write S
3
∼
=
D
3
.
As we progress, we’ll see more examples of such relationships between seemingly different struc-
tures. In the first half of the course (Chapters 2–5) the primary goal is to become familiar with the
most commonly encountered examples of groups so that they may quickly be recognized, even when
well-disguised. The second half of the course is more abstract, with relatively few new examples of
groups; comfort with the standard examples will be crucial in making sense of this harder material.
3
We will explain the term isomorphic more concretely in Section 2.3 and revisit both examples in Chapter 5. For the
present, observe the use of the congruence symbol
∼
=
; given your understanding of congruent objects in geometry, think
about why the use of this symbol isn’t unreasonable.
3
2 Groups: Axioms and Basic Examples
In this chapter we define our main objects of study and introduce some of the common language
that will be used throughout the course. Most of the examples are very simple and many should be
familiar. We start by individually considering the axioms of a group.
2.1 The Axioms of a Group
Definition 2.1 (Closure). A binary operation ∗ on a set G is a function ∗ : G ×G → G. Equivalently,
∀x, y ∈ G, we have x ∗y ∈ G (†)
We say that G is closed under ∗, and that (G, ∗) is a binary structure.
In the abstract, including most theorems, we typically drop the symbol and use juxtaposition (x ∗y =
xy). In explicit examples this might be a bad idea, say if ∗ is addition. . .
Examples 2.2. 1. Addition (+) is a binary operation on the set of integers Z: explicitly,
Given x, y ∈ Z, we know that x + y ∈ Z
This isn’t a claim you can prove since it is really part of the definition of addition on the integers.
2. Subtraction (−) is not a binary operation on the positive integers N = {1, 2, 3, 4, . . .}. This you
can prove; to show that (†) is false, simply exhibit a counter-example
1 −7 = −6 ∈ N (∃x, y ∈ N such that x −y ∈ N)
On the integers, however, subtraction is a binary operation.
3. It can be convenient to use a table to represent a binary operation on a
small set; for instance the example describes an operation on a set of three
elements {e, a, b}. Read the left column first, then the top row; thus
ab = e
∗ e a b
e e a b
a a e e
b b e a
We’ll continue checking these examples for each of the group axioms.
Definition 2.3 (Associativity). A binary structure (G, ∗) is associative if
∀x, y, z ∈ G, x( yz) = (xy)z
Associativity means that the expression xyz has unambiguous meaning, as does the usual exponen-
tial/power notation shorthand, e.g. x
n
= x ···x.
Examples (ver. II). 1. Addition is associative: x + (y + z) = (x + y) + z for any integers.
2. ( Z, −) is non-associative: e.g. (1 −1) −2 = −2 = 2 = 1 − (1 −2).
3.
{e, a, b}, ∗
is non-associative: e.g. a(b
2
) = a
2
= e = b = eb = (ab)b.
4
Definition 2.4 (Identity). A binary structure (G, ∗) has an identity element e ∈ G if
∀x ∈ G, ex = xe = x
Examples (ver. III). 1. Addition has identity 0: that is 0 + x = x + 0 = x for any integer x.
2. ( Z, −) does not have an identity: e.g. if e − x = x, then e = −2x depends on x!
3.
{e, a, b}, ∗
has identity e; observe the first row and column of the table.
By convention, if G is finite and has an identity (e.g. Example 3,) we list it first. Indeed, we can always
list it first, since. . .
Lemma 2.5 (Uniqueness of identity). If a binary structure (G, ∗) has an identity, then it is unique.
It is now legitimate to refer to the identity e using the definite article. Uniqueness proofs in mathematics
typically follow a pattern: suppose there are two such objects and show that they are identical.
Proof. Suppose e, f ∈ G are identities. Then
e f =
(
f since e is an identity
e since f is an identity
We conclude that f = e.
We used almost nothing about (G, ∗); in particular it need not be associative (e.g. example 3).
Definition 2.6 (Inverse). Let (G, ∗) have identity e. An element x ∈ G has an inverse y ∈ G if
xy = yx = e
Examples (ver. IV). 1. Every integer x has an inverse under addition: x + (−x) = (−x) + x = 0.
2. Since ( Z, −) has no identity, the question of inverses makes no sense.
3. Since e
2
= a
2
= ab = ba = e, we see that every element has an
inverse; indeed a has two inverses!
Element e a b
Inverse(s) e a, b a
Lemma 2.7 (Uniqueness of inverses). Suppose (G, ∗) is associative and has an identity. If x ∈ G has
an inverse, then it is unique.
Proof. Suppose x has inverses y, z ∈ G. Then,
z(xy) = (zx)y =⇒ ze = ey =⇒ z = y
Note where associativity was used in the proof. Example 3 shows that this condition is necessary: a
non-associative structure can have non-unique inverses.
5
Definition 2.8 (Commutativity). Let (G, ∗) be a binary structure. Elements x, y ∈ G commute if
xy = yx. We say that ∗ is commutative if all elements commute:
∀x, y ∈ G, xy = yx
Examples (ver.V). 1. Addition of integers is commutative: ∀x, y ∈ Z, x + y = y + x.
2. Subtraction is non-commutative: e.g. 2 − 3 = 3 −2.
3. The relation is commutative since its table is symmetric across its main ↘ diagonal.
We simply assemble the pieces to obtain our main definition.
Definition 2.9 (Group axioms). A group is a binary structure (G, ∗) satisfying the associativity and
identity axioms, and for which all elements have inverses. This is summarized by the mnemonic
Closure, Associativity, Identity, Inverse
The order of G is its cardinality
|
G
|
. Moreover, G abelian if ∗ is commutative.
Of our examples, only (Z, +) is a group; indeed an abelian, infinite (order), additive
4
group (the oper-
ation is addition). The same observations show that (Q, +), (R, +) and (C, +) are abelian groups.
Examples 2.10. 1. The non-zero real numbers R
×
forms an abelian group under multiplication.
Closure If x, y = 0, then xy = 0
Associativity ∀x, y, z, x(yz) = (xy)z
Identity If x = 0, then 1 · x = x ·1 = x, so 1 ∈ R
×
is an identity
Inverse Given x = 0, observe that x
−1
=
1
x
is an inverse: x ·
1
x
=
1
x
· x = 1
Commutativity If x, y = 0, then xy = yx
Similarly, (Q
×
, ·) and (C
×
, ·) are abelian groups.
2. The even integers 2Z = {2z : z ∈ Z} form an abelian group under addition.
3. The odd integers 1 + 2Z = {1 + 2n : n ∈ Z} do not form a group under addition since they are
not closed: for instance, 1 + 1 = 2 ∈ 1 + 2Z.
4. Every vector space is an abelian group under addition.
5. ( R, ·) is not a group, since 0 has no multiplicative inverse. Similarly (Q, ·), (C, ·) are not groups.
6. Groups of small order may be depicted in Cayley tables
5
.
Groups of orders 1, 2 and 3 are shown: you should check
that these are groups.
Note the magic square property: each row/column con-
tains every element exactly once (see Exercise 13).
∗ e
e e
∗ e a
e e a
a a e
∗ e a b
e e a b
a a b e
b b e a
4
The operation is addition; a multiplicative group follows the multiplication/juxtaposition convention. These are dis-
tinctions only of notation: e.g. x + x + x = 3x in an additive group corresponds to xxx = x
3
in a multiplicative group.
5
Englishman Arthur Cayley (1821–1895) was a pioneer of group theory. Abelian similarly honors the Norwegian math-
ematician Niels Abel (1802–1829).
6
Theorem 2.11 (Cancellation laws & inverses). Suppose G is a group and x, y, z ∈ G. Then
1. xy = xz =⇒ y = z 2. xz = yz =⇒ x = y
3. (xy)
−1
= y
−1
x
−1
Proof. The first two parts are exercises. For the third,
y
−1
x
−1
(xy) = y
−1
(x
−1
x) y = y
−1
ey = y
−1
y = e
Thus y
−1
x
−1
is an inverse of xy. Since inverses are unique, (Lemma 2.7) we are done.
Associativity and Functional Composition
Theorem 2.12. Let X be a set. Composition of functions f : X → X is associative.
Proof. Let f , g, h : X → X. We have equality ( f ◦ g) ◦ h = f ◦ (g ◦h) if and only if these functions do
the same thing to every element x ∈ X. But this is trivial:
( f ◦ g) ◦ h
(x) = ( f ◦ g)
h(x)
= f
g(h(x))
and,
f ◦(g ◦h)
(x) = f
(g ◦h)(x)
= f
g(h(x))
It follows that ◦ is associative.
By viewing rotations and reflections as functions, the theorem verifies associativity for the following.
Corollary 2.13. The rotations of a geometric figure form a group under composition.
The symmetries (rotations and reflections) of a geometric figure form a group under composition.
Checking the other axioms is an exercise: the identity is considered a rotation (by 0°!).
Definition 2.14. 1. If ρ
k
is rotation counter-clockwise by
2πk
n
radians, then R
n
= {ρ
0
, . . . , ρ
n−1
} is the
rotation group of a regular n-gon.
2. The dihedral group D
n
is the symmetry group of a regular n-gon.
3. The Klein four-group
6
(denoted V) is the symmetry group of a rectangle (or a rhombus), where
a represents rotation by 180° and b, c are reflections.
◦ e a b c
e e a b c
a a e c b
b b c e a
c c b a e
a
c
b
6
From the German Vierergruppe. Felix Klein (1849–1925) was a pioneer in the application of group theory to geometry.
7
Since multiplication by an n × n matrix amounts to a function (e.g. A ∈ M
n
(R ) corresponds to a
linear map R
n
→ R
n
: x 7→ Ax), we immediately conclude:
Corollary 2.15. Multiplication of square matrices is associative.
Example 2.16. The general linear group comprises the invertible n × n matrices under multiplication
GL
n
(R ) = {A ∈ M
n
(R ) : det A = 0}
Invertibility is assumed, associativity is the corollary, and closure follows from the familiar result
det AB = det A det B
Finally the identity is given by (drum roll. . . ) the identity matrix I =
1 0
0 1
.
.
.
.
.
.
.
.
.
0
0 1
!!
This group is non-abelian (when n ≥ 2).
Look again at part 3 of Theorem 2.11: seem familiar?
Exercises 2.1. Key concepts/definitions: make sure you can state the formal definitions
Group (closure, associativity, identity, inverse) Commutativity/abelian Cayley table V GL
n
(R )
1. Given the binary operation table, calculate
(a) c ∗d (b) a ∗(c ∗b)
(c) (c ∗b) ∗ a (d) (d ∗c) ∗(b ∗a)
∗ a b c d
a c d a b
b d c b a
c a b c d
d b a d c
2. A table for a binary operation on {a, b, c}is given. Compute a ∗(b ∗c)
and (a ∗ b) ∗ c. Does the expression a ∗ b ∗ c make sense? Explain
why/why not.
∗ a b c
a b c b
b c a a
c b a c
3. Are the binary operations in the previous questions commutative? Explain.
4. (a) Describe (don’t write them all out!) all possible binary operation tables on a set of two
elements {a, b}. Of these, how many are commutative?
(b) How many commutative/non-commutative operations are there on a set of n elements?
(Hint: a commutative table has what sort of symmetry?)
5. Which are binary structures? For those that are, which are commutative and which associative?
(a) ( Z, ∗), a ∗ b = a −b (b) ( R, ∗), a ∗ b = 2(a + b)
(c) ( R, ∗), a ∗ b = 2a + b (d) ( R, ∗), a ∗ b =
a
b
(e) ( N, ∗), a ∗ b = a
b
(f) ( Q
+
, ∗), a ∗ b = a
b
, where Q
+
= {x ∈ Q : x > 0}
(g) ( N, ∗), a ∗ b = product of the distinct prime factors of ab. Also define 1 ∗1 = 1.
(e.g. 42 ∗10 = (2 ·3 ·7) ∗ (2 ·5) = 2 ·3 ·5 ·7 = 210)
8
6. For each axiom of an abelian group: if true, write it down; if false, provide a counter-example.
(a) N = {1, 2, 3, . . .} under addition. (b) Q under multiplication.
(c) X = {a, b, c} with x ∗y := y. (d) R
3
with the cross/vector product ×.
(e) For each n ∈ R, the set nZ = {nz : z ∈ Z} of multiples of n under addition.
7. Determine whether each of the following sets of matrices is a group under multiplication.
(a) K = {A ∈ M
2
(R ) : det A = ±1} (b) L = {A ∈ M
2
(R ) : det A = 7}
(c) N =
a b
0 d
∈ M
2
(R ) : ad = 0
8. (a) Prove the cancellation laws (Theorem 2.11 parts 1 & 2).
(b) True or false: in a group, if xy = e, then y = x
−1
.
(c) In a (multiplicative) group, prove that (x
−1
)
n
= (x
n
)
−1
for any x and any n ∈ N. How
would we write this in an additive group (see footnote 4)?
9. Let G be a group. Prove the following:
(a) ∀x, y ∈ G, (xyx
−1
)
2
= xy
2
x
−1
(b) ∀x ∈ G, (x
−1
)
−1
= x
(c) G is abelian ⇐⇒ ∀x, y ∈ G, (xy)
−1
= x
−1
y
−1
10. (a) Suppose X contains at least two distinct elements x = y. Prove that there exist functions
f , g : X → X for which f ◦ g = g ◦ f .
(b) Show that multiplication of n ×n matrices is non-commutative when n ≥ 2.
11. (a) Describe the symmetry group and Cayley table of a non-equilateral isosceles triangle.
(b) Explicitly state the Cayley table for the rotation group R
4
of a square.
(c) Explain why the order of the dihedral group D
n
is 2n.
(d) Prove the rotation part of Corollary 2.13.
12. Let U be a set and P(U) its power set (the set of subsets of U).
(a) Which of the group axioms is satisfied by the union operator ∪ on P(U)?
(b) Repeat part (a) for the intersection operator.
(c) The symmetric difference of sets A, B ⊆ U is the set
A△B := (A ∪ B) \ (A ∩ B)
i. Use Venn diagrams to give a sketch argument that △ is associative on P(U) .
ii. Is
P(U), △
a group? Explain your answer.
13. (Magic Square) Suppose (G, ∗) is associative and G is finite.
Prove that (G, ∗) is a group if and only if its (multiplication) table satisfies two conditions:
i. One row and column (by convention the first) is a perfect copy of G itself.
ii. Every element of G appears exactly once in each row and column.
9
2.2 Subgroups
In mathematics, the prefix sub- usually indicates a subset that retains whatever structure follows.
Definition 2.17 (Subgroup). Let G be a group. A subgroup of G is a subset H ⊆ G which is a group
with respect to the same binary operation; we write H ≤ G.
A subgroup H is a proper subgroup if H = G; this is written H < G.
The trivial subgroup is the 1-element set {e}; all other subgroups are non-trivial.
Examples 2.18. The following are immediate from the definition:
1. {e} ≤ G and G ≤ G for any G 2. ( Z, +) < (Q, +) < (R, +) < (C, +)
3. ( Q
×
, ·) < (R
×
, ·) < (C
×
, ·) 4. ( R
n
, +) < (C
n
, +)
5. ( 2Z, +) < (Z, +) 6. (R
3
, ◦) ≤ (R
6
, ◦) (rotation groups)
Thankfully you don’t have to check all the group axioms to see that a subset is a subgroup.
Theorem 2.19 (Subgroup criterion). Let G be a group. A non-empty subset H ⊆ G is a subgroup if
and only if it is closed under the group operation and inverses. Otherwise said,
∀h, k ∈ H, hk ∈ H and h
−1
∈ H
Proof. (⇒) H is a group and therefore satisfies all the axioms, including closure and inverse.
( ⇐) Since H is a subset of G, the group operation on G is automatically associative
7
on H. By as-
sumption, H also satisfies the closure and inverse axioms, so it remains only to check the identity.
Since H = ∅, we may choose some (any!) h ∈ H, from which
e = hh
−1
∈ H
since inverses and products remain in H. The identity e of G therefore in H, and so H is a group.
Examples 2.20. 1. All the above examples can be confirmed using the theorem. For instance,
2Z = {. . . , −2, 0, 2, 4, . . .} = {2z : z ∈ Z}
is certainly a non-empty subset of the integers. Moreover, if 2m, 2n ∈ 2Z, then
2m + 2n = 2(m + n) ∈ 2Z and −(2m) = 2(−m) ∈ 2Z
whence 2Z is closed under addition and inverses (negation).
2. The positive integers N = {1, 2, . . .} are closed under addition but not inverses (for instance no
x ∈ N satisfies x + 2 = 0). Thus N is not a subgroup of Z under addition.
3. Let 1 + 3Z be the set of integers with remainder 1 when divided by 3:
1 + 3Z = {1 + 3n : n ∈ Z} = {1, 4, 7, 10, 13, . . . , −2, −5, −8, . . .}
Since 1 ∈ 1 + 3Z but 1 + 1 = 2 ∈ 1 + 3Z, we see that 1 + 3Z is not a subgroup of (Z, +).
7
Definition 2.3 makes no claim as to where x(yz) = (xy)z lives!
10
Subgroup Diagrams It can be helpful to represent subgroup relations pictorially,
where a descending line indicates a subgroup relationship. For instance, the dia-
gram on the right summarizes four subgroup relations
6Z < 2Z < Z and 6Z < 3Z < Z
Z
2Z 3Z
6Z
where all four are groups under addition. If G has only finitely many subgroups, then its subgroup
diagram is the complete depiction of all subgroups.
Matrix subgroups In Example 2.16 we saw that the invertible matrices GL
n
(R ) form a group under
multiplication; here is one of its many subgroups, some others are in Exercise 10.
Example 2.21. The set O
n
(R ) = {A ∈ M
n
(R ) : A
T
A = I} forms a subgroup of GL
n
(R ).
• I ∈ O
n
(R ) so we have a non-empty set. Moreover, if A ∈ O
n
(R ), then
1 = det I = det A det A
T
= (det A)
2
=⇒ det A = 0 =⇒ A ∈ GL
n
(R )
• If A, B ∈ O
n
(R ), then
(AB)
T
(AB) = B
T
A
T
AB = B
T
IB = B
T
B = I, and,
(A
−1
)
T
A
−1
= (A
T
)
T
A
T
= (AA
T
)
T
= I
T
= I
whence AB and A
−1
∈ O
n
(R ).
We call this the orthogonal group. When n = 2 or 3, its elements may be recognized as rotations and
reflections. For instance, the matrix
1
√
2
1 −1
1 1
∈ O
2
(R ) rotates R
2
counter-clockwise by 45°.
Geometric subgroup proofs Arranging figures such that every symmetry of one is also a symmetry
of the other immediately results in a subgroup relationship!
Example 2.22. A regular hexagon has symmetry group D
6
=
{ρ
0
, . . . , ρ
5
, µ
0
, . . . , µ
5
} consisting of six rotations and six reflec-
tions:
• ρ
k
is rotation counter-clockwise by 60k°; the identity is ρ
0
.
• The µ
k
are reflections across ‘diameters’ of the hexagon as
indicated in the pictures below.
Now draw two equilateral triangles inside the hexagon.
Each of the six symmetries of the equilateral triangle is also a sym-
metry of the hexagon! It follows that the symmetry group D
3
of
the triangle is a subgroup of D
6
in two different ways:
{e, ρ
2
, ρ
4
, µ
0
, µ
2
, µ
4
} < D
6
and {e, ρ
2
, ρ
4
, µ
1
, µ
3
, µ
5
} < D
6
µ
0
µ
2
µ
4
ρ
2
ρ
4
µ
1
µ
3
µ
5
ρ
2
ρ
4
11
Exercises 2.2. Key concepts/definitions:
(Proper/trivial/non-trivial) Subgroup Closure under operation/inverses Subgroup diagram
1. Use Theorem 2.19 to verify that Q
×
is a subgroup of R
×
under multiplication.
2. Give two reasons why the non-zero integers do not form a subgroup of Z under addition.
3. Explain the relationship between positive integers m and n whenever (mZ, +) ≤ (nZ, +).
4. Prove or disprove: the set H = {
a
2
n
: a ∈ Z, n ∈ N
0
} forms a group under addition.
5. Use Theorem 2.19 to explain why the set of rotations of a planar geometric figure is a subgroup
of the group of its rotations and reflections.
6. (a) Find the complete subgroup diagram of the Klein four-group.
(b) Modelling Example 2.22, draw three pictures which describe different ways in which the
Klein four-group may be viewed as a subgroup of D
6
.
7. Find the subgroups and subgroup diagram of the rotation group R
6
= {ρ
0
, . . . , ρ
5
}, where ρ
k
is
counter-clockwise rotation by 60k°.
8. Suppose H and K are subgroups of G. Prove that H ∩K is also a subgroup of G.
9. Let H be a non-empty subset of a group G. Prove that H is a subgroup of G if and only if
∀x, y ∈ H, xy
−1
∈ H
10. Prove that the following sets of matrices are groups under multiplication.
(a) Special linear group: SL
n
(R ) =
A ∈ M
n
(R ) : det A = 1
(b) Special orthogonal group: SO
n
(R ) = {A ∈ M
n
(R ) : A
T
A = I and det A = 1}
(c) Q
n
=
A ∈ M
n
(R ) : det A ∈ Q
×
(d) Symplectic group: Sp
2n
(R ) =
A ∈ M
2n
(R ) : A
T
JA = J
, where J =
0 I
n
−I
n
0
is a block
matrix and I
n
the n ×n identity matrix.
(e) SL
n
(Z ) =
A ∈ M
n
(Z ) : det A = 1
: all entries in these matrices are integers.
(Hint: look up the classical adjoint adj A of a square matrix)
Now construct a diagram showing the subgroup relationships between the groups
GL
n
(R ), SL
n
(R ), O
n
(R ), SO
n
(R ), Q
n
, SL
n
(Z ) (ignore Sp
2n
(R ))
11. The set Q
8
= {±1, ±i, ±j, ±k} forms a group of order eight under ‘multiplication’ subject to
the following properties:
• 1 is the identity.
• −1 commutes with everything; e.g. (−1)i = −i = i(−1), etc.
• (−1)
2
= 1, i
2
= j
2
= k
2
= −1 and ij = k.
• Multiplication is associative.
(a) Find the Cayley table of (Q
8
, ·).
(Hint: You should easily be able to fill in 44 of 64 entries; now use associativity. . . )
(b) Find all subgroups of Q
8
and draw its subgroup diagram.
12
2.3 Homomorphisms & Isomorphisms
A key goal of abstract mathematics is the comparison of similar/identical structures with outwardly
different appearances. We describe such comparisons using functions.
Definition 2.23 (Homomorphism). Suppose (G, ∗) and (H, ⋆ ) are binary structures and ϕ : G → H
a function. We say that ϕ is a homomorphism of binary structures if
∀x, y ∈ G, ϕ(x ∗y) = ϕ(x) ⋆ ϕ(y)
For most of this course (certainly after this chapter), the binary structures will be groups.
Examples 2.24. 1. The function ϕ : (N, +) → (R, +) defined by ϕ(x) =
√
2x is a homomorphism,
ϕ(x + y) =
√
2(x + y) =
√
2x +
√
2y = ϕ(x) + ϕ(y)
It is worth spelling this out, since there are two ways to combine addition and ϕ:
• Sum x + y, then map to R to obtain ϕ(x + y).
• Map to R, then sum to obtain ϕ(x) + ϕ(y).
The homomorphism property says the results are always identical.
2. If V, W are vector spaces then every linear map T : V → W is a group homomorphism:
8
∀v
1
, v
2
∈ V, T(v
1
+ v
2
) = T(v
1
) + T(v
2
)
This shows that you’ve been encountering homomorphisms your entire mathematical career,
even in calculus:
d
dx
( f + g) =
d f
dx
+
dg
dx
is a homomorphism property!
The most useful homomorphisms are bijective: these get a special name.
Definition 2.25 (Isomorphism). An isomorphism is a bijective/invertible homomorphism.
9
We say that G and H are isomorphic, written G
∼
=
H, if there exists an isomorphism ϕ : G → H.
Why do we care about isomorphisms? It is because isomorphic groups have exactly the same struc-
ture; one is simply a relabelled version of the other!
Here is the procedure for showing that binary structures (G, ∗) and (H, ⋆) are isomorphic:
Definition: Define ϕ : G → H (if necessary). As we’ll see starting in Chapter 3, if G is a set
of equivalence classes you might need to check that ϕ is well-defined.
Homomorphism: Verify that ϕ(x ∗y) = ϕ(x) ⋆ ϕ(y) for all x, y ∈ G.
Injectivity/1–1: Check ϕ(x) = ϕ(y) =⇒ x = y.
Surjectivity/onto: Check range ϕ = H. Equivalently ∀h ∈ H, ∃g ∈ G such that h = ϕ(g).
The last three steps can be done in any order. Injectivity/surjectivity might also be combined by
exhibiting an explicit inverse function ϕ
−1
: H → G.
8
The scalar multiplication condition T(λv) = λT(v) of a linear map is not relevant here.
9
These terms come from ancient Greek: homo- (similar, alike), iso- (equal, identical), and morph(e) (shape, structure).
13
Examples 2.26. 1. We show that ( 2Z, +) and (3Z, +) are isomorphic groups.
Definition: The obvious function is ϕ(x) =
3
2
x; plainly ϕ(2m) = 3n whence ϕ : 2Z → 3Z.
Homomorphism: ϕ(x + y) =
3
2
(x + y) =
3
2
x +
3
2
y = ϕ(x) + ϕ(y)
Injectivity: ϕ(x) = ϕ(y) =⇒
3
2
x =
3
2
y =⇒ x = y.
Surjectivity: If z = 3n ∈ 3Z, then z =
3
2
·
2
3
z =
3
2
(2n) = ϕ(2n) ∈ range ϕ.
In the last step we essentially observed that the inverse function is ϕ
−1
( z) =
2
3
z.
More generally, whenever m, n = 0, the groups (mZ, +) and (nZ, +) are isomorphic.
2. The function ϕ(x) = e
x
is an isomorphism of abelian groups ϕ : (R, +)
∼
=
(R
+
, ·).
Definition: This is unnecessary since ϕ is given. However, note that both domain and codomain
are abelian groups and that R
+
= (0, ∞) means the positive real numbers.
Homomorphism: This is the familiar exponential law!
ϕ(x + y) = e
x+y
= e
x
e
y
= ϕ(x)ϕ(y)
Bijectivity: ϕ
−1
( z) = ln z is the inverse function of ϕ.
Non-isomorphicity & Structural Properties
Unless you have very small sets, you cannot realistically test every function ϕ : G → H to see that
structures are non-isomorphic! Instead we have to be a little more cunning.
Definition 2.27 (Structural properties). A structural property is any property which is preserved
under isomorphism: i.e. if ϕ : (G, ∗) → (H, ⋆) is an isomorphism then (G, ∗) and (H, ⋆) have identical
structural properties.
The following is a non-exhaustive list of structural properties: we’ll check a few in Exercise 6.
Cardinality/order: Since G and H are bijectively paired, their cardinalities are the same.
Commutativity & Associativity: For instance, if ∗ is commutative, then
∀x, y ∈ G, ϕ(x) ⋆ ϕ(y) = ϕ(x ∗y) = ϕ(y ∗ x) = ϕ(y) ⋆ ϕ(x)
Since ϕ is bijective, this says that ⋆ is commutative on H.
Identities & Inverses: For instance, if G has identity e, then ϕ(e) is the identity for H.
Solutions to equations: Related equations in G and H have the same number of solutions: e.g.
x ∗x = x ⇐⇒ ϕ(x) ⋆ ϕ(x) = ϕ(x)
The equations x ∗x = x and z ⋆ z = z therefore have the same number of solutions.
Being a group If G is a group, so also is H.
14
Examples 2.28. 1. The binary structures (N
0
, +) and (N, +) are non-isomorphic, since N
0
=
{0, 1, 2, 3, . . .} contains an identity element 0 while N does not.
2. The binary structures defined by the two tables are non-isomorphic;
the first is commutative while the second is not.
∗ a b
a a b
b b a
⋆ c d
c c d
d c d
3. To see that (Q, +) and (R, +) are non-isomorphic groups, it is enough to recall that the sets
have different cardinalities: Q is countably infinite while R is uncountable.
4. GL
2
(R ) and (R, +) have the same cardinality; however, since the first is non-abelian and the
second abelian, the two groups are non-isomorphic.
Many properties are non-structural and therefore cannot be used to show non-isomorphicity: the type
of element (number, matrix, etc.), the type of binary operation (addition, multiplication, etc.).
Transferring a Binary Structure
We can turn a bijection into an isomorphism by imposing the homomorphism property. If (H, ⋆) and
a bijection ϕ : G → H are given, we can define a binary operation ∗ on G by pulling-back ⋆:
∀x, y ∈ G, x ∗y := ϕ
−1
ϕ(x) ⋆ ϕ(y)
Plainly ϕ : (G, ∗)
∼
=
(H, ⋆) is an isomorphism! We can similarly push-forward a structure from G to H:
w ⋆ z := ϕ
ϕ
−1
( w) ∗ϕ
−1
( z)
Example 2.29. ϕ(x) = x
3
+ 8 is a bijection R → R. If ϕ : (R, ∗) → (R, +) is an isomorphism, then
x ∗y := ϕ
−1
ϕ(x) + ϕ(y)
= ϕ
−1
(x
3
+ y
3
+ 16) =
3
q
x
3
+ y
3
+ 8
Since (R, +) is an abelian group and ϕ
−1
an isomorphism, it follows that (R, ∗) is also an abelian
group. Moreover, its identity must be
ϕ
−1
(0) =
3
√
−8 = −2
As a sanity check, observe that
x ∗(−2) =
3
q
x
3
+ (−2)
3
+ 8 = x
Up to Isomorphism: a common shorthand
This phrase is ubiquitous in abstract mathematics. For an example of how it is used,
note that if ({e, a}, ∗) is a group with identity e, then its Cayley table must be as shown
(recall Example 2.10.6). This might be summarized by the phrase:
∗ e a
e e a
a a e
Up to isomorphism, there is a unique group of order two.
More precisely: if G is any group of order two, then there exists an isomorphism ϕ : {e, a} → G. The
expression ‘up to isomorphism’ is essential; without it, the sentence is false, since there are infinitely
many distinct groups of order two!
15
Exercises 2.3. Key concepts/definitions:
Homomorphism Injective/surjective/bijective Isomorphism Structural property
‘Up to isomorphism’
1. Which of the following are homomorphisms/isomorphisms of binary structures? Explain.
(a) ϕ : (Z, +) → (Z, +), ϕ(n) = −n (b) ϕ : (Z, +) → (Z, +), ϕ(n) = n + 1
(c) ϕ : (Q, +) → (Q, +), ϕ(x) =
4
3
x (d) ϕ : (Q, ·) → (Q, ·), ϕ(x) = x
2
(e) ϕ : (R, ·) → (R, ·), ϕ(x) = x
5
(f) ϕ : (R, +) → (R, ·), ϕ(x) = 2
x
(g) ϕ : (M
2
(R ), ·) → (R, ·), ϕ(A) = det A
(h) ϕ : (M
n
(R ), +) → (R, +), ϕ(A) = tr A = trace of the matrix A (add the entries on the
main diagonal).
2. Show that ( Z, +)
∼
=
( nZ, +) for any non-zero constant n.
3. Prove or disprove: (R
3
, +)
∼
=
(R
3
, ×) (cross product).
4. ϕ(n) = 2 − n is a bijection of Z with itself. For each of the following, define a binary relation ∗
on Z such that ϕ is an isomorphism of binary relations.
(a) ϕ : (Z, ∗)
∼
=
(Z, + )
(b) ϕ : (Z, ∗)
∼
=
(Z, ·)
(c) ϕ : (Z, ∗)
∼
=
(Z, max(a, b))
5. ϕ(x) = x
2
is a bijection ϕ : R
+
→ R
+
. Find x ∗ y if ϕ is to be an isomorphism of binary
structures
(a) ϕ : (R
+
, ∗) → (R
+
, +)
(b) ϕ : (R
+
, +) → (R
+
, ∗)
6. Suppose ϕ : (G, ∗) → (H, ⋆) is an isomorphism of binary structures. Prove the following:
(a) If e is an identity for G, then ϕ(e) is an identity for H.
(b) If x ∈ G has an inverse y, then ϕ(x) ∈ H has an inverse ϕ(y).
(c) If ∗ is associative, so is ⋆.
7. Let ϕ : (G, ∗) → (H, ⋆) be a homomorphism of binary structures. Prove that the image
ϕ( G) = Im ϕ = {ϕ(x) : x ∈ G}
is closed under ⋆ (thus (ϕ(G), ⋆) is a binary structure). If (G, ∗) and (H, ⋆) are both groups,
show that ϕ(G) is a subgroup of H.
8. Revisit Exercise 6a. Suppose e is an identity for (G, ∗) and that ϕ : G → H is merely a homo-
morphism. Must ϕ(e) be an identity for H? Explain why/why not: does it matter whether ϕ is a
homomorphism of groups?
16
9. Let G be the group of rotations of the plane about the origin under composition.
(a) Show that ϕ : (R, +) → G defined by
ϕ(x) = rotate counter-clockwise x radians
is a homomorphism of groups.
(b) Prove or disprove: ϕ is an isomorphism.
10. (a) Prove that S :=
a −b
b a
∈ M
2
(R )
forms a group under matrix addition.
(b) Prove that T = S \{0} (S except the zero matrix) forms a group under matrix multiplica-
tion.
(c) Define ϕ
a −b
b a
= a + ib. Prove that ϕ : S → C and ϕ
T
: T → C
×
are both isomorphisms
ϕ : (S, +)
∼
=
(C, + ), ϕ
|
T
: (T, ·)
∼
=
(C
×
, ·)
(In a future class, ϕ will be described as an isomorphism of rings/fields)
11. The groups (Q, +) and (Q
+
, ·) are both abelian and both have the same cardinality. Assume,
for contradiction, that ϕ : Q → Q
+
is an isomorphism.
(a) If c ∈ Q is constant, what equation in Q
+
corresponds to x + x = c?
(b) By considering how many solutions these equations have, obtain a contradiction and
hence conclude that ( Q, +) ≇ (Q
+
, ·).
(Extra challenge) Suppose ψ : (Q, +) → (R, ·) is a homomorphism and that ψ(1) = a: find a
formula for ψ(x).
12. Recall the magic square property (Exercise 2.1.13).
(a) Up to isomorphism, explain why there is a unique group of order 3; its Cayley table should
look like that of the rotation group R
3
.
(b) Show that there are only two ways to complete a Cayley table of order 4 up to isomor-
phism.
(Hints: if G = {e, a, b, c}, why may we assume, without loss of generality, that b
2
= e? Your
answers should look like the Klein four-group V and the rotation group R
4
.)
13. Prove that isomorphic is an equivalence relation on any collection of groups: that is, for all
groups G, H, K, we have
Reflexivity G
∼
=
G
Symmetry G
∼
=
H =⇒ H
∼
=
G
Transitivity G
∼
=
H and H
∼
=
K =⇒ G
∼
=
K
17
3 Cyclic groups
3.1 Definitions and Basic Examples
Cyclic groups are a basic family of groups whose complete structure can be easily described. The
foundational idea is that a cyclic group can be generated by a single element.
Examples 3.1. 1. The group of integers (Z, +) is generated by 1. Otherwise said, all integers may be
produced simply by combining 1 with itself using only the group operation (+) and inverses
(−). Indeed, if n is a positive integer, then
n = 1 + 1 + ··· + 1
The inverse operation produces −n, and the identity is 0 = 1 + (−1).
2. Recall the group R
n
= {ρ
0
, . . . , ρ
n−1
} of rotations of a regular n-gon (Definition 2.14). Since
ρ
k
= ρ
k
1
, the group is generated by ρ
1
, the ‘1-step’ counter-clockwise rotation by
2π
n
radians.
We formalize this idea by considering a subset of a group G that is produced starting with a single
element g. Since this is abstract, we follow the convention of writing G multiplicatively.
Lemma 3.2 (Cyclic subgroup). Let G be a group and g ∈ G. The set
⟨
g
⟩
:= {g
n
: n ∈ Z} = {. . . , g
−1
, e, g, g
2
, . . .}
is a subgroup of G.
Proof. Non-emptiness: Plainly e ∈
⟨
g
⟩
.
Closure: Every element of
⟨
g
⟩
has the form g
k
for some k ∈ Z. The required condition is
nothing more than standard exponential notation:
g
k
· g
l
= g
k+l
∈
⟨
g
⟩
Inverses: This is immediate by Exercise 2.1.8c: (g
k
)
−1
= g
−k
∈
⟨
g
⟩
.
Definition 3.3 (Cyclic group). The subgroup
⟨
g
⟩
is the cyclic subgroup of G generated by g.
The order of an element g ∈ G is the order (cardinality)
|⟨
g
⟩|
of the subgroup generated by g.
G is a cyclic group if ∃g ∈ G such that G =
⟨
g
⟩
: we call g a generator of G.
Warning! Don’t confuse the order of a group G with the order of an element g ∈ G. Cyclic groups are the
precisely those groups containing elements (generators) whose order equals that of the group.
Examples (3.1 cont). 1. Z =
⟨
1
⟩
=
⟨
−1
⟩
is generated by either 1 or −1. Note that this is an additive
group, thus the subgroup generated by 2 is the group of even numbers under addition
⟨
2
⟩
= {. . . , −2, 0, 2, 4, . . .} = {2m : m ∈ Z} = 2Z
2. R
n
=
⟨
ρ
1
⟩
. This group has other generators, but we’ll delay finding them until the next section.
18
Modular Arithmetic
It is now time we introduced the most commonly encountered family of finite groups.
Definition 3.4. Let n be a positive integer. We denote by Z
n
the set of equivalence classes modulo n.
It is most common to denote the elements of Z
n
as remainders,
10
that is
Z
n
= {0, 1, . . . , n −1}
You should be familiar with addition and multiplication modulo n, and you have several options for
notation. For instance, here is a calculation in Z
5
written four ways:
(a) Modular arithmetic: 4 + 2 ≡ 6 ≡ 1 (mod 5).
(b) Equivalence classes: [4]
5
+ [2]
5
= [6]
5
= [1]
5
.
(c) Decorate the operations: 4 +
5
2 = 6 = 1.
(d) Drop almost all notation: 4 + 2 = 6 = 1 in Z
5
.
Warning! If you choose version (d), you must make clear
that you are working in Z
5
. If the distinction between num-
bers and equivalence classes is confusing, use one of the
other notations!
[0]
= {. . . , −5, 0, 5, 10, . . .}
[1]
= {
. . . ,
−
9,
−
4, 1, 6, . . .
}
[2]
= {
. . . ,
−
8,
−
3, 2, 7, . . .
}
[3]
= {
. . . ,
−
7,
−
2, 3, 8, . . .
}
[4]
= {
. . . ,
−
6,
−
1, 4, 9, . . .
}
+1
+1
+1
+1
+1
Adding 1 in Z
5
Theorem 3.5. Z
n
forms a cyclic, abelian group under addition modulo n.
A direct rigorous proof is tedious right now. It will come for free in Chapter 6 when we properly
define Z
n
as a factor group. For the present, note simply that Z
n
is cyclic since it is generated by 1.
Examples 3.6. Here are the Cayley tables for Z
1
, Z
2
, Z
3
, Z
4
.
+
1
0
0 0
+
2
0 1
0 0 1
1 1 0
+
3
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
+
4
0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
Compare these to Example 2.10.6.
10
It is crucial to appreciate that these aren’t numbers but equivalence classes. Thus Z
n
=
[0], [1], . . . , [n −1]
where the
equivalence class [x] of x ∈ Z is the set of integers with the same remainder as x:
[x] = {z ∈ Z : x ≡ z (mod n)} = {. . . , x −n, x, x + n, x + 2n . . .} = {x + kn : k ∈ Z} = x + nZ
Modular addition and multiplication of equivalence classes are well-defined. For addition: if [x] = [w] and [y] = [z], then
w = x + kn and z = y + ln for some k, l ∈ Z, from which
[w] +
n
[z] = [w + z] =
(x + kn) + (y + ln)
=
x + y + n(k + l)
= [x + y] = [x] +
n
[y]
All this should be familiar from a previous course. We’ll revisit this in Chapter 6 when we define Z
n
as a factor group.
19
These groups are typically the cyclic groups to which others are compared. Indeed, as we’ll see
shortly, any cyclic group of order n is isomorphic to Z
n
. For instance:
Example 3.7. ( Z
3
, +
3
) is isomorphic to the rotation group (R
3
, ◦) via ϕ(k) = ρ
k (mod 3)
.
It is worth doing this slowly, since the domain is a set of equivalence classes:
Well-definition: If y = x ∈ Z
3
, then y ≡ x ≡ r (mod 3) for some r ∈ {0, 1, 2}. But then
ϕ(y) = ρ
r
= ϕ(x)
Bijection: This is trivial ϕ : {0, 1, 2} → {ρ
0
, ρ
1
, ρ
2
}.
Homomorphism: This is simply the formula for composition of rotations ρ
k
ρ
l
= ρ
k+l (mod 3)
The Roots of Unity
We finish with a third family of cyclic groups, viewed as subgroups of (C
×
, ·).
Aside: Notation Review C = {x + iy : x, y ∈ R} is the vector space R
2
spanned by the basis
{1, i}, where i is a ‘number’ satisfying i
2
= −1. Given z = x + iy ∈ C, we consider several objects:
Complex conjugate: z = x −iy is the reflection of z in the real axis
Modulus (length): r =
|
z
|
=
√
zz =
p
x
2
+ y
2
Argument (angle): θ = arg z is the angle measured counter-clockwise
from the positive real axis to
−→
0z (if z = 0).
Polar form: z = re
iθ
= r cos θ + ir sin θ
The modulus and argument are the usual polar co-ordinates. When
r = 1 we have Euler’s formula:
11
e
iθ
= cos θ + i sin θ
the source of the famous identity e
iπ
= −1. In the picture, S
1
denotes
the unit circle. Note also that
e
iθ
= 1 ⇐⇒ θ = 2πk for some integer k (†)
The polar form behaves nicely with respect to multiplication:
0
0 1 2
z = 1 +
√
3i = 2e
iπ
3
|z| = 2
arg z =
π
3
i
2i
−1 1
S
1
e
iθ
1
θ
i
−i
|
zw
|
=
|
z
||
w
|
and arg(zw) ≡ arg z + arg w (mod 2π)
Definition 3.8. Let n ∈ N. The n
th
roots of unity
12
comprise the cyclic subgroup of C
×
generated by
ζ := e
2πi
n
:
U
n
:=
⟨
ζ
⟩
=
1, ζ, ζ
2
, ··· , ζ
n−1
11
More generally, if x, y ∈ R, then e
x+iy
= e
x
e
iy
= e
x
cos y + ie
x
sin y.
12
In this context, unity is just a pretentious term for the number one!
20
If necessary, write ζ
n
= e
2πi
n
to emphasize n.
The square roots of unity are simply ±1, and we saw the 4
th
roots
±1, ±i in Example 3.1. The n
th
roots are equally spaced round the
unit circle at the vertices of a regular n-gon; this is since
arg ζ
k
= arg e
2πk
n
=
2πk
n
= k arg ζ
We stop listing the elements of U
n
at ζ
n−1
, since ζ
n
= e
2πi
= 1.
Indeed, by (†), we see the relationship with modular arithmetic
ζ
k
= ζ
l
⇐⇒ 1 = ζ
k−l
= e
2πi(k−l)
n
⇐⇒ k ≡ l (mod n)
−1 1
ζ
ζ
2
ζ
3
ζ
4
ζ
5
ζ
6
i
−i
Seventh roots: ζ
7
= e
2πi
7
Theorem 3.9. The n
th
roots of unity are precisely the n (complex) roots of the equation z
n
= 1.
Proof. Plainly (ζ
k
)
n
= (e
2πik
n
)
n
= e
2πik
= 1, so every element of U
n
solves z
n
= 1.
For the converse, suppose z
n
= 1. Take the modulus to obtain
|
z
|
n
= 1. Since
|
z
|
is a non-negative
real number, we see that
|
z
|
= 1, whence its polar form is z = e
iθ
. Now compute:
1 = z
n
= (e
iθ
)
n
= e
inθ
⇐⇒ nθ = 2πk
for some integer k (∗). But then θ =
2πk
n
and so
z = e
iθ
= e
2πi
n
k
=
e
2πi
n
k
= ζ
k
In fact U
n
is just the rotation group R
n
= {ρ
0
, . . . , ρ
n−1
} in disguise!
Lemma 3.10. For any z ∈ C, ζ
k
n
z = ρ
k
( z) is the result of rotating z counter-clockwise by
2πk
n
radians.
Examples 3.11. 1. Observe that ζ
2
6
= (e
2πi
6
)
2
= e
2πi
3
= ζ
3
.
We immediately obtain a subgroup relationship: with ζ = ζ
6
,
U
3
=
1, ζ
2
, ζ
4
< U
6
=
1, ζ, ζ
2
, ζ
3
, ζ
4
, ζ
5
This is essentially trivial by drawing a picture!
S
1
ζζ
2
ζ
3
ζ
4
ζ
5
1
2. The group table for U
n
is trivial to construct. Here is U
3
, where we use the fact that ζ
3
= 1: if
we write the table with 1 = ζ
0
and ζ = ζ
1
, the relationship to (Z
3
, +
3
) and (R
3
, ◦) is glaring:
· 1 ζ ζ
2
1 1 ζ ζ
2
ζ ζ ζ
2
1
ζ
2
ζ
2
1 ζ
· ζ
0
ζ
1
ζ
2
ζ
0
ζ
0
ζ
1
ζ
2
ζ
1
ζ
1
ζ
2
ζ
0
ζ
2
ζ
2
ζ
0
ζ
1
+
3
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
◦ ρ
0
ρ
1
ρ
2
ρ
0
ρ
0
ρ
1
ρ
2
ρ
1
ρ
1
ρ
2
ρ
0
ρ
2
ρ
2
ρ
0
ρ
1
More formally, the groups are isomorphic (U
3
, ·)
∼
=
(Z
3
, +
3
)
∼
=
(R
3
, ◦).
21
Exercises 3.1. Key concepts/definitions:
Generator Order of an element Cyclic (sub)group Z
n
Roots of unity
1. State the Cayley tables for ( Z
5
, +
5
) and (Z
6
, +
6
).
2. List all the generators of each cyclic group.
(a) ( Z, +).
(b) {2
n
3
−n
: n ∈ Z} under multiplication.
(c)
a 0
0 a
,
0 b
−b 0
: a, b = ±1
under multiplication.
3. Revisit Example 1.2. What is the cyclic subgroup of D
3
generated by ρ
1
? Generated by µ
1
?
4. Explicitly compute the cyclic subgroup
ζ
5
8
of U
8
, listing its elements in the order generated.
5. The circle group is the set S
1
= {e
iθ
: θ ∈ [0, 2π)}. Prove that S
1
is a subgroup of C
×
under
multiplication.
6. (a) Prove that (U
3
, ·) is a subgroup of (U
9
, ·).
(b) Complete the sentence and prove your assertion:
U
m
≤ U
n
if and only if (relationship between m and n)
7. (a) Show that the set Z
×
5
= {1, 2, 3, 4} forms a cyclic group under multiplication modulo 5.
(b) What about the set Z
×
8
= {1, 3, 5, 7} under multiplication modulo 8? To what previously
encountered group is this isomorphic?
8. (a) Explain why {1, 2, 3, 4, 5} isn’t a group under multiplication modulo 6.
(b) Hypothesize for which integers n ≥ 2 the set {1, 2, 3, . . . , n −1} is a group under multipli-
cation modulo n. If you want a challenge, try to prove your assertion.
9. Verify that ϕ : C → C
×
: z 7→ e
z
is a homomorphism of abelian groups (C, +), (C
×
, ·) but not
an isomorphism.
(This is in contrast to the real case: Example 2.26.2)
10. (a) Prove Lemma 3.10.
(b) Use the Lemma to prove that (U
n
, ·) and (R
n
, ◦) are isomorphic groups.
22
3.2 The Classification and Structure of Cyclic Groups
In this abstract section, we describe all cyclic groups, their generators, and subgroup structures.
Lemma 3.12. Every cyclic group is abelian.
Proof. Let G =
⟨
g
⟩
. Since any two elements of G can be written g
k
, g
l
for some k, l ∈ Z, we immedi-
ately see that
g
k
g
l
= g
k+l
= g
l+k
= g
l
g
k
Note that the converse is false: the Klein four-group V is abelian but not cyclic.
Theorem 3.13 (Isomorphs). Every cyclic group is isomorphic either to (Z, +) or to some (Z
n
, +
n
).
In either case, if G =
⟨
g
⟩
, then ϕ : x 7→ g
x
defines an isomorphism Z
(n)
∼
=
G.
Proof. To distinguish these cases, consider the set of natural numbers
S = {m ∈ N : g
m
= e}
If S = ∅: Suppose x > y and that g
x
= g
y
. Then g
x−y
= e =⇒ x − y ∈ S: contradiction. It follows
that the elements . . . , g
−2
, g
−1
, e, g, g
2
, g
3
, . . . are distinct and that ϕ : Z → G is a bijection.
If S = ∅: Let
13
n = min S and define ϕ : Z
n
→ G : x 7→ g
x
. We check that this is well-defined:
y = x ∈ Z
n
=⇒ y = x + kn for some k ∈ Z
=⇒ ϕ(y) = g
y
= g
x+kn
= g
x
(g
n
)
k
= g
x
= ϕ(x)
Since the highlighted calculation is valid for all x, k ∈ Z, we also conclude that
G =
⟨
g
⟩
⊆ {e, g, . . . , g
n−1
}
contains finitely many terms. Suppose two of these were equal; if 0 ≤ y ≤ x ≤ n −1, then
g
x
= g
y
=⇒ g
x−y
= e =⇒ x = y
since 0 ≤ x −y < n −1 and n = min S. Thus n is the order of G and G = {e, g, . . . , g
n−1
}.
In both cases, the homomorphism property is simply the exponential law
ϕ(x + y) = g
x+y
= g
x
g
y
= ϕ(x)ϕ(y)
The set S quickly yields an alternative measure for the order of an element.
Corollary 3.14. If G =
⟨
g
⟩
is finite, then its order is the smallest positive integer n such that g
n
= e.
Moreover g
m
= e ⇐⇒ m is a multiple of n (n
m).
13
By the well-ordering property of the natural numbers, any non-empty subset has a minimum element.
23
Examples 3.15. 1. The group of 7
th
roots of unity (U
7
, ·) is isomorphic to (Z
7
, +
7
) via
ϕ : Z
7
→ U
7
: k 7→ ζ
k
7
2. The additive group 5Z = {5z : z ∈ Z} is infinite and cyclic. It is isomorphic to the integers via
ϕ : (Z, +)
∼
=
(5Z, + ) : z 7→ 5z
3. Let ξ = e
2πi
√
2
and consider the cyclic subgroup G :=
⟨
ξ
⟩
< (C
×
, ·). For integers m, observe that
ξ
m
= e
2πim
√
2
= 1 ⇐⇒
m
√
2
∈ Z ⇐⇒ m = 0
We conclude that G is an infinite cyclic group and that ϕ : Z → G : z 7→ ξ
z
is an isomorphism.
We can interpret ξ as performing an irrational fraction (
1
√
2
) of a full rotation.
4. ( R, +) is non-cyclic since its (uncountable) cardinality 2
ℵ
0
is larger than the (countable) car-
dinality ℵ
0
of the integers. This is also straightforward to see directly: if R were cyclic with
generator x, then we’d obtain an immediate contradiction
x
2
/∈ {. . . , −2x, −x, 0, x, 2x, 3x . . .} = R ∋
x
2
The same argument shows that (Q, +) is not cyclic.
Subgroups of Cyclic Groups
We can straightforwardly classify all subgroups of a cyclic group: they’re also cyclic!
Theorem 3.16. Any subgroup of a cyclic group is cyclic.
The motivation for the proof is simple: the subgroup 2Z ≤ Z is generated by 2, the minimal positive
integer in the subgroup. Given a general subgroup H ≤ G, we identify a suitable ‘minimal’ element,
then demonstrate that this generates our subgroup.
Proof. Suppose H ≤ G =
⟨
g
⟩
. If H = {e} is trivial, we are done: H is cyclic!
Otherwise, ∃s ∈ N minimal such that g
s
∈ H. We claim that H =
⟨
g
s
⟩
: i.e. H is generated by g
s
.
⟨
g
s
⟩
⊆ H
This is trivial since g
s
∈ H.
H ⊆
⟨
g
s
⟩
Let g
m
∈ H. By the division algorithm, there exist unique integers q, r such that
m = qs + r and 0 ≤ r < s
But then
g
m
= g
qs+r
= (g
s
)
q
g
r
=⇒ g
r
= (g
s
)
−q
g
m
∈ H
since H is closed under · and inverses. By the minimality of S, this forces r = 0, from which we
conclude that g
m
= (g
s
)
q
∈
⟨
g
s
⟩
.
24
The infinite case is particularly simple; the proof is an exercise.
Corollary 3.17 (Subgroups of infinite cyclic groups). If G is an infinite cyclic group and H ≤ G,
then either H = {e} is trivial, or H
∼
=
G.
Example 3.18. It is helpful to write this out explicitly in additive notation when G = Z. Since every
subgroup is cyclic, there are two cases:
• The trivial subgroup:
⟨
0
⟩
= {0}.
• Every other subgroup:
⟨
s
⟩
= sZ when s = 0. All of these subgroups are isomorphic to Z via
the isomorphism ϕ : Z → sZ : x 7→ sx.
Finite cyclic groups are a little more complicated, so it is worth seeing an example first.
Example 3.19. Consider U
6
= {1, ζ, ζ
2
, ζ
3
, ζ
4
, ζ
5
} under multiplication. Since all subgroups are
cyclic, we need only consider what is generated by each element.
x subgroup
⟨
x
⟩
1 {1}
ζ {1, ζ, ζ
2
, ζ
3
, ζ
4
, ζ
5
}
ζ
2
{1, ζ
2
, ζ
4
}
ζ
3
{1, ζ
3
}
ζ
4
{1, ζ
4
, ζ
2
}
ζ
5
{1, ζ
5
, ζ
4
, ζ
3
, ζ
2
, ζ}
⟨
ζ
⟩
= U
6
ζ
2
= U
3
ζ
3
= U
2
⟨
1
⟩
= U
1
Observe the repetitions:
⟨
ζ
⟩
=
ζ
5
= U
6
and
ζ
2
=
ζ
4
= U
3
.
For comparison, here is the same data for subgroups of the additive group (Z
6
, +
6
).
x subgroup
⟨
x
⟩
0 {0}
1 {0, 1, 2, 3, 4, 5}
2 {0, 2, 4}
3 {0, 3}
4 {0, 4, 2}
5 {0, 5, 4, 3, 2, 1}
⟨
1
⟩
= Z
6
⟨
2
⟩
∼
=
Z
3
⟨
3
⟩
∼
=
Z
2
⟨
0
⟩
∼
=
Z
1
The difference is almost entirely notational, as must be since the groups are isomorphic. Note, how-
ever, in the subgroup diagram that we can’t use equals as we did for U
6
: for instance,
⟨
2
⟩
= {0, 2, 4}
is isomorphic but not equal to Z
3
= {0, 1, 2}.
You should be able to guess two patterns from the example:
• Z
n
has exactly one subgroup of order d for each divisor d of n.
• If d ∈ Z
n
is a divisor of n, then
⟨
d
⟩
∼
=
Z
n
d
.
25
Corollary 3.20 (Subgroups of finite cyclic groups). Let G =
⟨
g
⟩
have order n. Then G has a unique
subgroup of each order dividing n. More precisely,
d = gcd(s, n) =⇒
⟨
g
s
⟩
= ⟨g
d
⟩
∼
=
Z
n
d
Proof. Suppose d = gcd(s, n). We show first that
⟨
g
s
⟩
=
g
d
.
⟨
g
s
⟩
⊆
g
d
Since d |s we have s = kd for some k ∈ Z, and so
(g
s
)
m
= (g
d
)
mk
∈
g
d
=⇒
⟨
g
s
⟩
⊆
g
d
⟨
g
s
⟩
⊇
g
d
By B
´
ezout’s identity (ext. Euclidean alg.), d = κs + λn for some κ, λ ∈ Z, whence
g
d
= (g
s
)
κ
(g
n
)
λ
= (g
s
)
κ
∈
⟨
g
s
⟩
=⇒
g
d
⊆
⟨
g
s
⟩
To finish, we count the number of elements in ⟨g
d
⟩. Since d |n, there are precisely
n
d
of these, namely
⟨g
d
⟩ =
e, g
d
, g
2d
, . . . , g
n−d
The result is worth restating explicitly in the additive group (Z
n
, +
n
):
d = gcd(s, n) =⇒
⟨
s
⟩
=
⟨
d
⟩
∼
=
Z
n
d
In particular: x ∈ Z
n
is a generator if and only if gcd(x, n) = 1.
Example 3.21. We describe all subgroups of Z
30
and construct its subgroup diagram. The first
column lists the subgroup generated by each value x ∈ Z
30
. The second column is the isomorphic
group Z
30
d
. The final column lists the divisors d of 30, and thus the possible values of gcd(x, 30).
Subgroup
⟨
x
⟩
Isomorph Z
30
d
d = gcd(x, 30)
{. . . , 1, . . . , 7, . . . , 11, . . . , 13, . . . , 17, . . . , 19, . . . , 23, . . . , 29} Z
30
1
{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28} Z
15
2
{0, 3, 6, 9, 12, 15, 18, 21, 24, 27} Z
10
3
{0, 5, 10, 15, 20, 25} Z
6
5
{0, 6, 12, 18, 24} Z
5
6
{0, 10, 20} Z
3
10
{0, 15} Z
2
15
{0} Z
1
0 (30)
The subgroup diagram is drawn, with the obvious (minimal)
generator chosen for each subgroup; any of the other gener-
ators in the table could have been chosen instead.
With a little thinking, you should appreciate that the shape of
the subgroup diagram (this one looks a little like a cube. . . )
depends only on the prime factorization 30 = 2 ·3 · 5; namely
that each prime appears exactly once in the decomposition.
⟨
1
⟩
= Z
30
⟨
2
⟩
∼
=
Z
15
⟨
3
⟩
∼
=
Z
10
⟨
5
⟩
∼
=
Z
6
⟨
6
⟩
∼
=
Z
5
⟨
10
⟩
∼
=
Z
3
⟨
15
⟩
∼
=
Z
2
⟨
0
⟩
∼
=
Z
1
26
Exercises 3.2. Key concepts:
Every cyclic group isomorphic to Z or Z
n
⟨
g
⟩
order n =⇒
⟨
g
s
⟩
order
n
gcd(s,n)
Subgroup diagrams for finite cyclic groups
1. For each group: construct the subgroup diagram and give a generator of each subgroup.
(a) ( Z
10
, +
10
) (b) ( Z
42
, +
42
).
2. A generator of the cyclic group U
n
group is known as a primitive n
th
root of unity. For instance,
the primitive 4
th
roots are ±i. Find all the primitive roots when:
(a) n = 5 (b) n = 6 (c) n = 8 (d) n = 15
3. Find the complete subgroup diagram of U
p
2
q
where p, q are distinct primes.
(Hint: try U
12
first if this seems too difficult)
4. If r ∈ N and p is prime, find all subgroups of (Z
p
r
, +
p
r
) and give a generator for each.
5. (a) Suppose ϕ : G → H is an isomorphism of cyclic groups. If g is a generator of G, prove that
ϕ(g) is a generator of H. Do you really need ϕ to be an isomorphism here?
(b) If G is an infinite cyclic group, how many generators has it?
(c) Recall Exercise 3.1.7a. Describe an isomorphism ϕ : Z
4
→ Z
×
5
.
6. True or false: In any group G, if g has order n, then g
s
has order
n
gcd(s,n)
. Explain your answer.
7. Suppose G =
⟨
g
⟩
is infinite and H =
⟨
g
s
⟩
is an infinite subgroup. Prove Corollary 3.17 by
explicitly finding an isomorphism ϕ : G → H.
8. Prove Corollary 3.14: you’ll need the division algorithm for the second part!
9. Let x, y be elements of a group G. If xy has finite order n, prove that yx also has order n.
(Hint: (xy)
m
= x(yx)
m−1
y)
10. Let Z
×
n
=
x ∈ Z
n
: gcd(x, n) = 1
be the set of generators of the additive group (Z
n
, +
n
).
Prove that Z
×
n
is a group under multiplication modulo n.
(Hint: You need B´ezout’s identity. This is the group of units in the ring (Z
n
, +
n
, ·
n
))
11. Let G be a group and X a non-empty subset of G. The subgroup generated by X is the subgroup
created by making all possible combinations of elements and inverses of elements in X.
(a) Explain why ( Z, +) is generated by the set X = {2, 3}.
(b) If m, n ∈ (Z, +), show that the group generated by X = {m, n} is dZ, where d =
gcd(m, n).
(c) The Klein four-group V is not-cyclic, so it cannot be generated by a singleton set. Find a
set of two elements which generates V.
(d) Describe the subgroup of (Q, +) generated by X = {
1
2
,
1
3
}.
(e) (Hard) (Q, +) is plainly generated by the infinite set {
1
n
: n ∈ N}. Explain why (Q, +) is
not finitely generated: i.e. there exists no finite set X generating Q.
(Hint: think about the prime factors of the denominators of elements of X)
27
4 Direct Products & Finitely Generated Abelian Groups
In this short chapter we see a straightforward way to create new groups from old using the Cartesian
product.
Example 4.1. Given Z
2
= {0, 1}, the Cartesian product
Z
2
×Z
2
=
(0, 0), (0, 1), (1, 0), ( 1, 1)
has four elements. This set inherits a group structure in a natural way by adding co-ordinates
(x, y) + (v, w) := (x + v, y + w)
where x + v and y + w are computed in (Z
2
, +
2
). This is a binary operation on Z
2
× Z
2
, with a
familiar-looking table: it has exactly the same structure as the Cayley table for the Klein four-group!
+ (0, 0) (0, 1) (1, 0) (1, 1)
(0, 0) (0, 0) (0, 1) (1, 0) (1, 1)
(0, 1) (0, 1) (0, 0) (1, 1) (1, 0)
(1, 0) (1, 0) (1, 1) (0, 0) (0, 1)
(1, 1) (1, 1) (1, 0) (0, 1) (0, 0)
↭
◦ e a b c
e e a b c
a a e c b
b b c e a
c c b a e
We conclude that Z
2
×Z
2
∼
=
V is indeed a group.
This construction works in general.
Theorem 4.2 (Direct product). The natural component-wise operation on the Cartesian product
n
∏
k=1
G
k
= G
1
×··· × G
n
, (x
1
, . . . , x
n
) ·(y
1
, . . . , y
n
) := (x
1
y
1
, . . . , x
n
y
n
)
defines a group structure: the direct product. This is abelian if each G
k
is abelian.
The proof is a simple exercise. Being a Cartesian product, a direct product has order equal to the
product of the orders of its components
n
∏
k=1
G
k
=
n
∏
k=1
|
G
k
|
Examples 4.3. 1. Consider the direct product of groups (Z
2
, +
2
) and (Z
3
, +
3
):
Z
2
×Z
3
=
(0, 0), (0, 1), (0, 2), ( 1, 0), (1, 1), (1, 2)
This is abelian and has order 6, so we might guess that it is isomorphic to (Z
6
, +
6
). To see this
we need a generator: choose (1, 1) and observe that
⟨
(1, 1)
⟩
=
(1, 1), (0, 2), (1, 0), ( 0, 1), (1, 2), (0, 0)
= Z
2
×Z
3
The map ϕ(x) = (x, x) is therefore an isomorphism ϕ : Z
6
∼
=
Z
2
×Z
3
.
28
2. If each G
k
is abelian, written additively, the direct product can instead be called the direct sum
n
M
k=1
G
k
= G
1
⊕··· ⊕ G
n
We won’t use this notation,
14
though you’ve likely encountered it in linear algebra: the direct
sum of n copies of the real line R is the familiar vector space
R
n
=
n
M
i=1
R = R ⊕ ···⊕R
Orders of Elements in a Direct Product
In Example 4.3.1, we saw that the element (1, 1) ∈ Z
2
×Z
3
had order 6 and thus generated the group.
To help spot the pattern, consider another example.
Example 4.4. What is the order of the element (10, 2) ∈ Z
12
×Z
8
? Recall Corollary 3.20:
• 10 ∈ Z
12
has order 6 =
12
gcd(10,12)
• 2 ∈ Z
8
has order 4 =
8
gcd(2,8)
If we repeatedly add (10, 2), then the first co-ordinate will reset after 6 summations, while the second
resets after 4. For both to reset, we need a common multiple of 6 and 4 summands. We can check this
explicitly:
(10, 2)
=
(10, 2), (8, 4), (6, 6), ( 4, 0), (2, 2), (0, 4), (10, 6), (8, 0), ( 6, 2), (4, 4), (2, 6), (0, 0)
The order of the element (10, 2) is indeed the least common multiple 12 = lcm(6, 4).
Theorem 4.5. Suppose x
k
∈ G
k
has order r
k
. Then (x
1
, . . . , x
n
) ∈
n
∏
k=1
G
k
has order lcm(r
1
, . . . , r
n
).
Proof. Just appeal to Corollary 3.14:
(x
1
, . . . , x
n
)
m
= (x
m
1
, . . . , x
m
n
) = (e
1
, e
2
, . . . , e
n
) ⇐⇒ ∀k, x
m
k
= e
k
⇐⇒ ∀k, r
k
| m
The order is the minimal positive integer m satisfying this, namely m = lcm(r
1
, . . . , r
n
).
Example 4.6. Find the order of (1, 3, 2, 6) ∈ Z
4
×Z
7
×Z
5
×Z
20
.
Again appealing to Corollary 3.20, the element has order
lcm
4
gcd(1,4)
,
7
gcd(3,7)
,
5
gcd(2,5)
,
20
gcd(6,20)
= lcm(4, 7, 5, 10) = 140
14
In this course we will only ever have finitely many terms in a direct product/sum: in such cases these concepts are
identical for abelian groups written additively. When there are infinitely many factors, the concepts are slightly different.
29
When is a direct product of finite cyclic groups cyclic?
Recall that Z
2
×Z
2
∼
=
V is non-cyclic while Z
2
×Z
3
∼
=
Z
6
is cyclic. It is reasonable to hypothesize
that the distinction is whether the orders of the components are relatively prime.
Corollary 4.7. Z
m
×Z
n
is cyclic ⇐⇒ gcd(m, n) = 1, in which case Z
m
×Z
n
∼
=
Z
mn
.
More generally:
• Z
m
1
×··· ×Z
m
k
∼
=
Z
m
1
···m
k
⇐⇒ gcd( m
i
, m
j
) = 1, ∀i = j.
• If n = p
r
1
1
··· p
r
k
k
is the prime factorization, then Z
n
∼
=
Z
p
r
1
1
×··· ×Z
p
r
k
k
Proof. The generalization follows by induction on the first part.
(⇐) If gcd(m, n) = 1, then (1, 1) ∈ Z
m
×Z
n
has order lcm(m, n) =
mn
gcd(m,n)
= mn. Hence (1, 1) is a
generator of Z
m
×Z
n
, which is then cyclic.
(⇒) This is an exercise.
Examples 4.8. 1. (Example 4.6) The group Z
4
×Z
7
×Z
5
×Z
20
is non-cyclic since gcd(4, 20) = 1.
Indeed the maximum order of an element in this group is
lcm( 4, 7, 5, 20) = 140 < 2800 =
|
Z
4
×Z
7
×Z
5
×Z
20
|
2. Is Z
5
×Z
7
×Z
12
cyclic? The Corollary says yes, since none 5, 7, 12 have any common factors.
It is ghastly to write, but there are 12 different ways (up to reordering) of expressing this group!
Z
420
∼
=
Z
3
×Z
140
∼
=
Z
4
×Z
105
∼
=
Z
5
×Z
84
∼
=
Z
7
×Z
60
∼
=
Z
3
×Z
4
×Z
35
∼
=
Z
3
×Z
5
×Z
28
∼
=
Z
3
×Z
7
×Z
20
∼
=
Z
4
×Z
5
×Z
21
∼
=
Z
4
×Z
7
×Z
15
∼
=
Z
5
×Z
7
×Z
12
∼
=
Z
3
×Z
4
×Z
5
×Z
7
We may combine/permute the factors of 420 = 2
2
·3 ·5 ·7, provided we don’t separate 2
2
= 4.
Finite(ly generated) abelian groups
We’ve used the direct product to create finite abelian groups from cyclic building blocks. Our next
result provides a powerful converse.
Theorem 4.9 (Fundamental Theorem of Finitely Generated Abelian Groups).
Every finitely generated
15
abelian group is isomorphic to a group of the form
Z
p
r
1
1
×··· ×Z
p
r
n
n
×Z ×··· ×Z
The p
i
are (not necessarily distinct) primes, each r
k
∈ N, and there are finitely many Z-factors.
A finite abelian group has no factors of Z.
15
Recall Exercise 3.2.11.
30
We won’t develop the technology necessary to prove this, but it is too useful to ignore. Our purpose
is simply to classify finite abelian groups up to isomorphism.
Examples 4.10. 1. Up to isomorphism, there are five abelian groups of order 81 = 3
4
, namely
Z
81
, Z
3
×Z
27
, Z
9
×Z
9
, Z
3
×Z
3
×Z
9
, Z
3
×Z
3
×Z
3
×Z
3
These groups can be distinguished in several ways; for instance, if G is abelian and has order
81, you could show that G
∼
=
Z
3
×Z
27
by demonstrating two facts:
• G contains an element of order 27.
• The maximum order of an element of G is 27.
2. Since 450 = 2 ·3
2
·5
2
is a prime factorization, the fundamental theorem says that every abelian
group of order 450 is isomorphic to one of four groups:
(a) Z
2
×Z
3
2
×Z
5
2
∼
=
Z
450
(cyclic, max order 450)
(b) Z
2
×Z
3
×Z
3
×Z
5
2
(non-cyclic, maximum order 150 = 2 · 3 ·5
2
)
(c) Z
2
×Z
3
2
×Z
5
×Z
5
(non-cyclic, maximum order 90 = 2 · 3
2
·5)
(d) Z
2
×Z
3
×Z
3
×Z
5
×Z
5
(non-cyclic, maximum order 30 = 2 · 3 ·5)
As before, there are multiple isomorphic ways to express each group as a direct product.
We finish by listing all groups of orders 1 through 15 and abelian groups of order 16 up to isomor-
phism. The Fundamental Theorem gives us all the abelian groups.
order abelian non-abelian
1 Z
1
2 Z
2
3 Z
3
4 Z
4
, V
∼
=
Z
2
×Z
2
5 Z
5
6 Z
6
∼
=
Z
2
×Z
3
D
3
∼
=
S
3
7 Z
7
8 Z
8
, Z
2
×Z
4
, Z
2
×Z
2
×Z
2
D
4
, Q
8
9 Z
9
, Z
3
×Z
3
10 Z
10
∼
=
Z
2
×Z
5
D
5
11 Z
11
12 Z
12
∼
=
Z
3
×Z
4
, Z
2
×Z
6
∼
=
Z
2
×Z
2
×Z
3
D
6
, A
4
, Q
12
13 Z
13
14 Z
14
∼
=
Z
2
×Z
7
D
7
15 Z
15
∼
=
Z
3
×Z
5
16 Z
16
, Z
4
×Z
4
, Z
2
×Z
8
, Z
2
×Z
2
×Z
4
, Z
2
×Z
2
×Z
2
×Z
2
Many
The list of non-abelian groups contains some unfamiliarity though we’ve met most already:
• D
n
, S
3
and A
4
will be described properly in the next section.
• Q
8
is the quaternion group (Exercise 2.2.11), and Q
12
a generalized quaternion group: look them up
if interested!
31
There are nine non-isomorphic, non-abelian groups of order 16: D
8
and the direct product Z
2
× Q
8
are explicit examples. The table might make you suspicious that all non-abelian groups have even
order: this is not so, though the smallest counter-example has order 21.
Exercises 4. Key concepts:
Direct product Order of element via lcm Cyclic/gcd criteria Fundamental theorem
1. List the elements of the following direct product groups:
(a) Z
2
×Z
4
.
(b) Z
3
×Z
3
.
(c) Z
2
×Z
2
×Z
2
.
2. Prove Theorem 4.2 by checking each of the axioms of a group.
3. Prove that G × H
∼
=
H ×G.
4. Prove that a direct product
∏
G
k
is abelian if and only if its components G
k
are all abelian.
5. Find the orders of the following elements and write down the cyclic subgroups generated by
each (list all of the elements explicitly):
(a) ( 1, 3) ∈ Z
2
×Z
4
.
(b) ( 4, 2, 1) ∈ Z
6
×Z
4
×Z
3
.
6. Is the group Z
12
×Z
27
×Z
125
cyclic? Explain.
7. Find a generator of the group Z
3
×Z
4
and hence define an isomorphism ϕ : Z
12
∼
=
Z
3
×Z
4
.
(Hint: read the proof of Corollary 4.7)
8. State three non-isomorphic groups of order 50.
9. Suppose p, q are distinct primes. Up to isomorphism, how many abelian groups are there of
order p
2
q
2
?
10. Complete the proof of Corollary 4.7: if Z
m
×Z
n
is cyclic, then gcd(m, n) = 1.
(Hint: if gcd(m, n) ≥ 2, what is the maximum order of an element in Z
m
×Z
n
?)
11. Suppose G is an abelian group of order m, where m is a square-free positive integer (∄k ∈ Z
≥2
such that k
2
|m). Prove that G is cyclic.
12. (a) Let G be a finitely generated abelian group and let H be the subset of G consisting of the
identity e together with all the elements of order 2 in G. Prove that H is a subgroup of G.
(b) In the language of the Fundamental Theorem, to which direct product is H isomorphic?
13. Suppose G is a finite abelian group and that m is a divisor of
|
G
|
. Prove that G has a subgroup
of order m.
(Hint: use the the prime decomposition of m and the fundamental theorem and identify a suitable sub-
group of Z
p
r
1
1
×·×Z
p
r
k
k
)
32
5 Permutations and Orbits
In this chapter we return to the roots of group theory and consider the re-orderings of a set.
5.1 The Symmetric Group & Cycle Notation
Definition 5.1. A permutation of a set A is a bijective/invertible function σ : A → A.
The symmetric group S
A
is the set of all permutations of A under functional composition.
The symmetric group on n-letters
16
S
n
is the group S
A
when A = {1, 2, . . . , n}.
Examples 5.2. 1. If A = {1}, there is only one (bijective) function A → A, namely the identity
function e : 1 7→ 1. Thus S
1
has only one element and is isomorphic to Z
1
.
2. If A = {1, 2}, then there are two bijections e, µ : A → A:
• e(1) = 1 and e(2) = 2 defines the identity function.
• σ(1) = 2 and σ( 2) = 1 swaps the elements of A.
◦ e σ
e e σ
σ σ e
The Cayley table is immediate: plainly S
2
is isomorphic to Z
2
.
3. We met S
3
= S
{1,2,3}
explicitly in Example 1.2; it has six elements and is non-abelian, e.g.
µ
1
◦µ
2
= ρ
1
= ρ
2
= µ
2
◦µ
1
Lemma 5.3. 1. S
A
is indeed a group under composition of functions.
2. If A has at least three elements, then S
A
is non-abelian.
3. The order of S
n
is n! (Warning! The subscript n is not the order of S
n
)
4. S
m
≤ S
n
whenever m ≤ n (strictly S
n
contains a subgroup isomorphic to S
m
)
Proof. 1. Closure: If σ, τ : A → A are bijective, so is the composition
17
σ ◦τ.
Associativity: Composition of functions is associative (Theorem 2.12).
Identity: The identity function e
A
: a 7→ a for all a ∈ A is certainly bijective.
Inverse: If σ is a bijection, then its inverse function σ
−1
is also bijective.
The remaining parts are exercises.
From now on we simply use juxtaposition: στ := σ ◦ τ. Remember that στ is a function A → A, so
evaluation means that we act with τ first:
στ(a) = σ
τ(a)
Similarly, exponentiation will mean self-composition: e.g. σ
3
= σσσ = σ ◦σ ◦ σ.
16
Here we make S
n
an explicit group for clarity. In practice, any set with n elements will do, and any group isomorphic
to this is usually also called S
n
(see Exercise 7).
17
You should have seen this in a previous class. If you are uncomfortable with why this is true, write out the details!
33
Cycle Notation
Computations in S
n
are facilitated by some new notation.
Definition 5.4. Suppose {a
1
, . . . , a
k
} ⊆ {1, . . . , n}. The k-cycle σ = (a
1
a
2
···a
k
) ∈ S
n
is the function
σ :
a
j
7→ a
j+1
if j < k
a
k
7→ a
1
x 7→ x if x ∈ {a
1
, . . . , a
k
}
a
1
a
2
a
3
···
a
k
all other x
Cycles (a
1
···a
k
) and (b
1
···b
l
) are disjoint if {a
1
, . . . , a
k
}∩{b
1
, . . . , b
l
} = ∅.
1-cycles and the 0-cycle () are sometimes helpful in calculations: these are simply the identity e.
Example 5.5. A 4-cycle σ = ( 1 3 4 2) and a 2-cycle τ = (1 4) in S
4
are defined in the table:
x 1 2 3 4
σ(x) 3 1 4 2
τ(x) 4 2 3 1
σ : 1
//
3
//
4
//
2
ww
τ : 1
>>
4
||
2
zz
3
zz
To compose cycles, just remember that each is a function and you won’t go wrong!
x 1 2 3 4
τ(x) 4 2 3 1
στ(x) 2 1 4 3
στ : 1
~
??
2
||
3
??
4
||
The result is a product of disjoint 2-cycles στ = (1 2)(3 4).
Algorithmic Cycle Composition It is impractically slow to compute using tables. Here is an al-
gorithmic approach that, with practice, should prove more efficient. We illustrate by verifying the
previous calculation: at each step you write only a single number or bracket and thus build up the
right column.
• Open a bracket and write 1: στ = (1
• Since 1
τ
7→ 4
σ
7→ 2, write 2 next: στ = (1 2
• 2
τ
7→ 2
σ
7→ 1 starts the cycle; close it and open another with an unused value: στ = (1 2)(3
• 3
τ
7→ 3
σ
7→ 4, so write 4 next: στ = (1 2)(3 4
• 4
τ
7→ 1
σ
7→ 3 starts the current cycle, so close it: στ = (1 2)(3 4)
• All values 1, 2, 3, 4 have appeared so we terminate the algorithm.
It should be clear how to extend the algorithm when composing more cycles. If you obtain any 1-
cycles, delete them. Shortly we’ll prove that the algorithm always terminates in a product of disjoint
cycles. For now, practice the algorithm by verifying the following:
Examples 5.6. 1. ( 1 4)(1 3 4 2) = ( 1 3)(2 4) 2. ( 1 3 5 4)(2 3 4) = (1 3)(2 5 4)
3. ( 1 2 3 4)(1 2 3)(1 2) = (1 4)(2 3) 4. ( 1 2 3 4 5 6)
3
= (1 4)(2 5)(3 6)
34
Geometric Symmetry Groups
Permutations allow us to describe the group of symmetries of a geometric figure: simply label the
vertices (or edges/faces) with numbers 1, 2, 3, . . . and represent each rotation/reflection by how it
permutes these values. Cycle notation makes calculating compositions of symmetries easy!
Examples 5.7. 1. Label the vertices of a rhombus to view the Klein four-group V as a subgroup of
S
4
: the 2-cycles (1 3) and (2 4) are reflections, and their composition is rotation by 180°.
1
2
3
4
V
∼
=
e, (1 3), (2 4), (1 3)(2 4)
2. Label the vertices of a regular hexagon 1 through 6.
• The 2,2-cycle (1 5)(2 4) represents reflection across the axis through
3 and 6.
• The 6-cycle (1 2 3 4 5 6) represents a one-step counter-clockwise ro-
tation.
Both are therefore identified with elements of the dihedral group D
6
.
1
2
3
4
5 6
3. By labelling the vertices of a square as shown, we identify D
4
with a sub-
group of S
4
. All elements and the complete subgroup diagram are given
below, where we follow the convention to denote reflections across diag-
onals (δ
j
) and the midpoints of sides (µ
j
) differently.
Cycle notation makes calculation easy: for instance
(2 4)(1 2)(3 4) = (1 4 3 2) =⇒ δ
1
µ
1
= ρ
3
1
2
3
4
That two reflections make a rotation is geometrically obvious, but identifying which rotation is
harder without the the ability to calculate!
Element Cycle notation
ρ
0
e = ()
Rotations
ρ
1
(1234)
ρ
2
(13)( 24)
ρ
3
(1432)
µ
1
(12)( 34)
Reflections
µ
2
(14)( 23)
δ
1
(24)
δ
2
(13)
Subgroup Isomorph
{ρ
0
} Z
1
{ρ
0
, µ
i
} Z
2
{ρ
0
, δ
i
} Z
2
{ρ
0
, ρ
2
} Z
2
{ρ
0
, ρ
1
, ρ
2
, ρ
3
} Z
4
{ρ
0
, µ
1
, µ
2
, ρ
2
} V
{ρ
0
, δ
1
, δ
2
, ρ
2
} V
D
4
V Z
4
V
Z
2
Z
2
Z
2
Z
2
Z
2
Z
1
You should be able to recognize these subgroups geometrically; e.g. the blue copy of V is pre-
cisely that in the first example. Also try to convince yourself why there are no other subgroups.
The same sort of thing can be done for 3D figures like the tetrahedron (see Section 5.3).
35
Cayley’s Theorem
In mathematics, the word group originally referred to a set of permutations. We finish this section
with a foundational result: every element of a group may be viewed as a permutation of the group
itself, thus linking to the original meaning of the word.
Theorem 5.8 (Cayley). Every group is isomorphic to a group of permutations.
Proof. Let G be a group. For each a ∈ G, let σ
a
: G → G be left multiplication by a, i.e. σ
a
(x) = ax.
We claim that the set of such functions {σ
a
: a ∈ G} forms a subgroup of S
G
isomorphic to G.
First observe that σ
a
has inverse function σ
−1
a
= σ
a
−1
, since
∀x ∈ G, σ
a
−1
σ
a
(x)
= a
−1
ax = x and σ
a
σ
a
−1
(x) = aa
−1
x = x
It follows that each σ
a
is a permutation of G: that is σ
a
∈ S
G
.
We finish by showing that the function ϕ : G → {σ
a
: a ∈ G} defined by ϕ(a) = σ
a
is an isomorphism:
Injectivity: ϕ(a) = ϕ(b) =⇒ σ
a
= σ
b
=⇒ a = σ
a
( e) = σ
b
( e) = b.
Surjectivity: Certainly every function σ
a
is in the range of ϕ!
Homomorphism: For all a, b, x ∈ G,
ϕ(a) ◦ ϕ(b)
(x) = σ
a
σ
b
(x)
= abx = σ
ab
(x) =
ϕ(ab)
(x)
from which ϕ(a) ◦ϕ(b) = ϕ(ab).
Cayley’s Theorem does not say that every group is isomorphic to some symmetric group. It says that
that every group G is isomorphic to a subgroup of S
G
.
Exercises 5.1. Key concepts:
Permutation Symmetric group Cycle notation
1. Which of the following functions are permutations? Explain.
(a) f : Z → Z such that f (x) = x −7.
(b) f : Z → Z such that f (x) = −3x + 4.
(c) f : R → R such that f (x) = x
3
− x.
(d) f : R → R such that f (x) = x
3
+ x.
(e) f : {fish, horse, dog, cat} → {fish, horse, dog, cat} where
f :
fish
horse
dog
cat
=
horse
cat
dog
fish
36
2. Compute the following products of permutations in cycle notation.
(a) ( 1 2)(3 4)(1 2 3) ∈ S
4
(b) ( 1 4)(2 3)(3 4)(1 4) ∈ S
4
(c) ( 1 2 3)(2 3 4)(3 4 1) (4 1 2) ∈ S
4
(d) ( 1 2 4 5)
2
(2 4 5)
2
∈ S
5
3. Consider the dihedral group D
7
of symmetries of the regular
heptagon, viewed as a subgroup of S
7
. Each µ
i
is reflection
across the indicated dashed line, and ρ
j
is rotation j steps
counter-clockwise.
(a) State µ
4
in cycle notation.
(b) Compute µ
3
ρ
1
using cycle notation. What element of
D
7
does this represent?
(c) Calculate (ρ
2
µ
3
ρ
1
)
666
.
µ
1
µ
2
µ
3
µ
4
µ
5
µ
6
µ
7
1
2
3
4
5
6
7
ρ
1
= (1 2 3 4 5 6 7), ρ
j
= ρ
j
1
4. State the elements of the rotation group R
5
in cycle notation when viewed as a subgroup of S
5
.
5. Prove parts 2, 3, and 4 of Lemma 5.3.
6. How many distinct subgroups of S
4
are isomorphic to S
3
. Describe them.
7. Suppose sets A and B have the same cardinality: that is, ∃µ : A → B bijective.
(a) If σ ∈ S
A
is a permutation, show that µσµ
−1
∈ S
B
.
(b) Hence prove that S
A
and S
B
are isomorphic.
8. Cayley’s Theorem says that G is isomorphic to a subgroup of S
G
. What can you say about a
finite group G if G
∼
=
S
G
?
9. In Cayley’s theorem we defined σ
a
: G → G via left multiplication.
(a) Does the argument still work if σ
a
: G → G is right multiplication σ
a
(x) = xa?
(b) (Harder) Suppose we take σ
a
(x) := axa
−1
. Where does the proof of Cayley’s Theorem
fail?
10. Show that the group S
3
is indecomposable: there are no groups G, H of order less than
|
S
3
|
for
which S
3
∼
=
G × H.
(Hint: Assuming S
3
is decomposable, there is only one possible decomposition. Why does this decompo-
sition make no sense?)
11. Let n ≥ 3. Prove that if σ ∈ S
n
commutes with every other element of S
n
(i.e. σρ = ρσ, ∀ρ ∈ S
n
)
then σ is the identity.
(Hint: suppose σ(a) = b = a and consider the cases σ( b) = a and σ(b) = a separately)
37
5.2 Orbits
In this section we begin to consider the idea of a group action; how the elements of a group transform
a set. We’ve already seen examples of this; for instance how rotations transform an object. The
simplest general example is built into the definition of the symmetric group and appears naturally in
cycle notation.
Definition 5.9. The orbit of σ ∈ S
n
containing x ∈ {1, 2, . . . , n} is the set
orb
x
( σ) = {σ
k
(x) : k ∈ Z} ⊆ {1, 2, . . . , n}
Warning! Each orbit is a subset of {1, 2, . . . , n}, not of the group S
n
.
Observe also that orb
σ
k
(x)
( σ) = orb
x
( σ) for any k ∈ Z.
Examples 5.10. If σ ∈ S
n
is written as a product of disjoint cycles, then the cycles are the orbits!
1. The orbits of ( 1 3 4) ∈ S
4
are the disjoint sets {1, 3, 4}, {2}.
2. The orbits of ( 1 2)(4 5) are {1, 2}, {3}, {4, 5}.
3. This is false if the cycles are not disjoint. For instance, σ = (1 3)(2 3 4) ∈ S
4
maps
1 7→ 3 7→ 4 7→ 2 7→ 1
so there is only one orbit: orb
x
( σ) = {1, 2, 3, 4} for any x. This comports with the result σ =
(1 2 3 4) of multiplying out σ using our algorithm.
Given that disjoint cycle notation is so useful for reading orbits, it is natural to ask if any permutation
can be written as a product of disjoint cycles. The answer is yes, and the disjoint cycles turn out to be
precisely the orbits!
Theorem 5.11. The orbits of any σ ∈ S
n
partition X = {1, 2, . . . , n}.
Proof. Define a relation ∼ on X = {1, 2, . . . , n} by x ∼ y ⇐⇒ y ∈ orb
x
( σ). We claim that this is an
equivalence relation.
18
Reflexivity x ∼ x since x = σ
0
(x). ✓
Symmetry x ∼ y =⇒ y = σ
k
(x) for some k ∈ Z. But then x = σ
−k
( y) =⇒ y ∼ x. ✓
Transitivity Suppose that x ∼ y and y ∼ z. Then y = σ
k
(x) and z = σ
l
( y) for some
k, l ∈ Z. But then z = σ
k+l
(x) and so x ∼ z. ✓
The equivalence classes of ∼ are clearly the orbits of σ, which therefore partition X.
18
If ∼ is a relation on a set X and x ∈ X, we may define the set [x] := {y ∈ X : y ∼ x}. In this case [x] = orb
x
(σ).
Theorem: The sets [x] partition X (every y ∈ X lies in precisely one such subset [x]) if and only if ∼ is an equivalence
relation (reflexive, symmetric, transitive). In such a case we call [x] an equivalence class.
Much of the rest of the course requires these crucial ideas. If they’re not familiar, review your notes from a previous class
and ask questions!
38
Theorem 5.12. Every permutation can be written as a product of disjoint cycles.
Proof. We formalize our algorithm from the previous section. Suppose σ ∈ S
n
is given.
1. List the elements of orb
1
( σ) in the order they appear within the orbit:
orb
1
( σ) = {1, σ(1), σ
2
(1), . . .}
If this all of X = {1, . . . , n}, we are finished: σ = (1 σ(1) σ
2
(1) . . . σ
n−1
(1)
is an n-cycle.
2. Otherwise, let x
2
= min{x ∈ X : x ∈ orb
1
( σ)} and construct its orbit:
orb
x
2
( σ) = {x
2
, σ(x
2
), σ
2
(x
2
), . . .}
By Theorem 5.11, orb
x
2
( σ) is disjoint with orb
1
( σ). If orb
1
( σ) ∪ orb
x
2
( σ) = X, we are finished:
σ is the product of two disjoint cycles.
σ =
1 σ(1) σ
2
(1) ···
x
2
σ(x
2
) σ
2
(x
2
) ···
3. Otherwise, we repeat. At stage k, let x
k
= min{x ∈ X : x ∈ orb
1
( σ) ∪ ··· ∪ orb
k−1
( σ)}. By
the Theorem, orb
x
k
( σ) is disjoint with orb
1
( σ) ∪ ··· ∪ orb
k−1
( σ). The process continues until
orb
1
( σ) ∪ ··· ∪orb
k
( σ) = X, which must happen since X is a finite set. The result is a product
of disjoint cycles:
σ =
1 σ(1) σ
2
(1) ···
| {z }
orb
1
(σ)
x
2
σ(x
2
) σ
2
(x
2
) ···
| {z }
orb
x
2
(σ)
··· ···
| {z }
orb
x
3
(σ)
···
··· ···
| {z }
orb
x
k
(σ)
The Theorem explains why our algorithm always results in a product of disjoint cycles! By convec-
tion, we take x
1
= 1 and construct an increasing sequence x
1
≤ x
2
≤ ··· ≤ x
k
, though there is no
need to do so: disjoint cycles can be listed in any order and may start with any element, thus
(1 3)(2 5 4) = (5 4 2)(3 1)
Also, by convention, we delete any orbits of size 1 (1-cycles). If you are still feeling uncomfortable
multiplying cycles, practice until it becomes second-nature!
Orders of Elements in S
n
Recall that the order of an element σ is the least positive integer k for which σ
k
= e.
Example 5.13. If σ = ( 1 2 3 4 5 6) ∈ S
6
, then
σ
2
= (1 3 5)(2 4 6) σ
3
= (1 4)(2 5)(3 6) σ
4
= (1 5 3)(2 6 4)
σ
5
= (1 6 5 4 3 2) σ
6
= e
whence the order of σ is 6. This follows intuitively if we identify σ with a
rotation of a regular hexagon.
1
2
3
4
5 6
By thinking similarly about the regular k-gon, it should be clear that any k-cycle has order k.
39
Things are trickier when you don’t have a single cycle, though this is where our discussion of disjoint
cycles saves us, since disjoint cycles commute.
Examples 5.14. 1. Since (1 2 3) and (4 5) are disjoint cycles, we know that (1 2 3)(4 5) = (4 5)(1 2 3).
We therefore easily compute the following:
(1 2 3)(4 5)
3
= (1 2 3)(4 5)(1 2 3)( 4 5)(1 2 3)( 4 5)
= (1 2 3)
3
(4 5)
3
= e(4 5) = (4 5)
2. Given σ = ( 2 5 3)(1 5 4 3) ∈ S
5
, find σ
8
. It is really tempting to write
σ
8
?
= (2 5 3)
8
(1 5 4 3)
8
=
(2 5 3)
3
2
(2 5 3)
2
(1 5 4 3)
4
2
= e
3
(2 3 5)e
2
= (2 3 5)
but this is incorrect. The cycles don’t commute (2 5 3)(1 5 4 3) = (1 5 4 3)(2 5 3) so we can’t dis-
tribute the exponent. Instead we first write σ as a product of disjoint cycles, then
σ = (1 3)(2 5 4) =⇒ σ
8
= (1 3)
8
(2 5 4)
8
= (2 5 4)
2
= (2 4 5)
The disjoint cycles approach also tells us the order of σ. Observe that
e = σ
k
= (1 3)
k
(2 5 4)
k
⇐⇒ k is divisible by both 2 and 3
The order if σ is therefore 6.
Corollary 5.15. The order of a permutation σ is the least common multiple of the lengths of its
disjoint cycles.
Proof. Write σ = σ
1
···σ
m
as a product of disjoint cycles. Since these commute, we have
σ
k
= σ
k
1
···σ
k
m
Since each factor σ
k
j
permutes disjoint sets, it follows that
σ
k
= e ⇐⇒ ∀j, σ
k
j
= e
If the orbits of σ have lengths r
j
∈ N, it follows that
σ
k
j
= e ⇐⇒ α
j
| k
Thus k must be a multiple of α
j
for all j. The least such k is by definition lcm(α
1
, . . . , α
m
).
Example 5.16. The order of σ = (1 4 5)(3 6 2 7)(8 9) ∈ S
9
is lcm( 3, 4, 2) = 12.
To find σ
3465
, first observe that 3465 = 12 ·288 + 9, whence
σ
3465
= (σ
12
)
288
σ
9
= σ
9
= (1 4 5)
9
(3 6 2 7)
9
(8 9)
9
= (3 6 2 7)( 8 9)
since ( 1 4 5), (3 6 2 7) and (8 9) have orders 3, 4 and 2 respectively.
40
Exercises 5.2. Key concepts:
Orbit Partition Disjoint cycles Order of element via lcm
1. Find the orbits of the following permutations, and their orders:
(a) ρ = (1 4 5)(2 3 4 5) ∈ S
5
.
(b) σ = ( 1 5 4)(2 5 4)(1 2 3 4) ∈ S
5
.
(c) τ = (1 5 7 4)(3 2 4)(3 2 5 6) ∈ S
7
.
2. If σ ∈ S
A
is any permutation, we may define its orbits similarly: orb
a
( σ) = {σ
j
(a) : j ∈ Z}.
What are the orbits of the permutation σ : Z → Z : n 7→ n + 3?
3. Given σ = ( 1 3)(2 4 5) ∈ S
5
, find the elements of the cyclic group
⟨
σ
⟩
≤ S
5
generated by σ.
4. What is the largest possible order of an element of the group S
3
×Z
4
×V? Exhibit one.
5. What is the maximum order of an element in each of the groups S
4
, S
5
, S
6
, S
7
, S
8
? Exhibit a
maximum order element in each case.
6. For which integers n does there exist a subgroup C
n
≤ S
8
where C
n
is cyclic of order n? Explain
your answer.
7. Let σ ∈ S
n
. For each k > 0, prove that each orbit of σ
k
is a subset of an orbit of σ.
8. Consider the permutations σ = ( 1 3 5)(2 7 4 9 6) and τ = (1 5 3 2) (6 9) in S
9
.
(a) Compute στ and τσ in cycle notation.
(b) Find the orders of σ, τ, στ and τσ.
(c) Compute (στ)
432
σ
43
as a product of disjoint cycles.
(d) Construct the subgroup diagram of
⟨
σ
⟩
and give a generator for each subgroup.
41
5.3 Transpositions & the Alternating Group
Instead of breaking a permutation σ into disjoint cycles, we can consider a permutation as con-
structed from only the simplest bijections.
Definition 5.17. A 2-cycle (a
1
a
2
) is also known as a transposition, since it swaps two elements of
{1, 2, . . . , n} and leaves the rest untouched.
Theorem 5.18. Every σ ∈ S
n
(n ≥ 2) is the product of transpositions.
Proof. There are many, many ways to write out a single permutation as a product of transpositions.
One method is first to write σ as a product of disjoint cycles, then write each cycle as follows:
(a
1
··· a
k
) = (a
1
a
k
)(a
1
a
k−1
) ···(a
1
a
2
)
Just read it carefully and you should be convinced this works!
Example 5.19. The method in the proof results in the decomposition
(1 7 6 4 5) = (1 5)(1 4)(1 6)(1 7)
Other decompositions are possible, for instance (1 7)(3 6)(5 7)(4 7)(3 6)(6 7).
While there are many ways to write a permutation as a product of transpositions, there is a simple
commonality which can be observed via a matrix notation for permutations. Consider, for instance,
1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1
2
3
4
=
1
4
3
2
and
0 0 1 0
0 0 0 1
0 1 0 0
1 0 0 0
1
2
3
4
=
3
4
2
1
(∗)
Each 4 ×4 matrix permutes the values 1, 2, 3, 4 when placed in a column vector. These matrices plainly
correspond to the transposition (2 4) and the 4-cycle (1 3 2 4) in S
4
.
Definition 5.20. An n × n permutation matrix is a matrix obtained from the identity matrix by per-
muting its rows. Equivalently, it is zero except for a single 1 in each row and column.
Lemma 5.21. The set of n × n permutation matrices forms a group under multiplication which is
isomorphic to S
n
.
We omit a formal proof, though it relies on essentially one fact from elementary linear algebra; that
row operations preserve the solution set of a system of linear equations. For instance (∗) describes two
systems Ax = b and Cx = d which are identical up to rearrangements of rows (row operations) and
moreover have identical solutions x =
1
2
3
4
.
42
What does this have to do with transpositions? Since a transposition swaps two elements, it corre-
sponds to an elementary matrix which swaps two rows; such a matrix always has determinant −1.
Suppose that a permutation is written as a product of transpositions:
σ = σ
1
···σ
m
Viewing this as a product of matrices, take the determinant of both sides to observe that
det σ = (−1)
m
Notice that this depends only on whether m is even or odd. . .
Definition 5.22. A permutation σ ∈ S
n
is even/odd if it can be written as the product of an even/odd
number of transpositions. By the above discussion, these concepts are well-defined: a permutation
is either even or odd; it cannot be both!
Plainly the composition of even permutations remains even, as does the inverse of such. We may
therefore define a new subgroup of S
n
.
Definition 5.23. The alternating group A
n
(n ≥ 2) is the group of even permutations in S
n
.
Theorem 5.24. A
n
has exactly half the elements of S
n
: that is
|
A
n
|
=
n!
2
.
Proof. Since n ≥ 2, we have (1 2) ∈ S
n
. Define ϕ : S
n
→ S
n
by ϕ(σ) = (1 2) σ. Since
(1 2)(1 2)σ = σ
we see that ϕ is invertible: the inverse of ϕ is ϕ itself! Moreover, ϕ maps even permutations to odd
and vice versa. It follows that there are exactly the same number of odd and even permutations.
Examples 5.25. We describe the small alternating groups up to A
4
.
1. A
2
= {e}
∼
=
Z
1
is extremely boring!
2. A
3
= {e, (1 3) (1 2) , (1 2)(1 3)} = {e, (1 2 3), (1 3 2)}
∼
=
Z
3
is a cyclic group.
3. When n = 4 we obtain the first ‘new’ group in the alternating family; a group of order 12.
A
4
= {e, (1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3),
(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}
A
4
is non-abelian: for example,
(1 2 3)(1 2 4) = (1 3)(2 4) = (1 4)(2 3) = (1 2 4) (1 2 3)
We already know one non-abelian group of order 12: the dihedral
group D
6
. We quickly see that A
4
≇ D
6
: all elements of A
4
have
orders 1, 2 or 3, while D
6
contains a rotation of order 6.
By labelling faces (or vertices), A
4
may be visualized the rotation
group of the tetrahedron: can you see how each element acts?
43
Exercises 5.3. Key concepts:
Transposition (representation by) Odd/even permutations Alternating group
1. Write (1 3 4 6)(2 4 6) as a product of transpositions in two different ways.
2. State σ = (1 3) and τ = (1 3 2) as 3 × 3 permutation matrices S and T. Compute the matrix
product ST and verify that it is the permutation matrix corresponding to στ ∈ S
3
.
3. Give examples of two non-isomorphic non-abelian groups of order 360.
4. Explain why every finite group is isomorphic to a group of matrices under multiplication.
5. S
4
has four distinct subgroups isomorphic to the Klein four-group V; state them. Only one of
these is a subgroup of A
4
; which?
6. We just saw that the rotation group of a regular tetrahedron is isomorphic to A
4
.
(a) What is the order of the rotation group of a cube?
(Hint: each face may be rotated to any of six faces, and then rotated in place. . . )
(b) Repeat the calculation for the remaining three platonic solids (octahedron, dodecahedron,
icosahedron).
(c) By placing a vertex at the center of each face of a cube, argue that the rotation group of an
octahedron is also isomorphic to S
4
.
What happens when you do this for a dodecahedron? A tetrahedron?
(d) Label the four diagonals of a cube 1, 2, 3, 4. Describe geometrically the effect of the per-
mutation (2 3 4) on the cube. What about (2 3)? Hence conclude that the rotation group of
a cube is isomorphic to S
4
.
(The dodecahedral and icosahedral rotation groups are both isomorphic to the alternating group A
5
,
though this is harder to visualize than the cube situation—try researching a proof )
7. (Hard) Find the entire subgroup diagram of A
4
.
8. (Hard) Prove that D
n
is a subgroup of A
n
⇐⇒ n ≡ 1 (mod 4)
(Do this in one shot if you like; otherwise use the following steps to guide your thinking)
(a) Label the corners of a regular n-gon 1 through n counter-clockwise so that every element
of D
n
may be written as a permutation of {1, 2, . . . , n}. Write in a sentence what you are
required to prove: what condition characterizes being in the group A
n
?
(b) Consider the rotation ρ
1
= (1 2 3 ··· n) of the n-gon one step counter-clockwise. Is ρ
1
odd
or even, and how does this depend on n?
(c) Show that every rotation ρ
i
∈ D
n
is generated by ρ
1
. When is the set of rotations in D
n
a
subgroup of A
n
?
(d) A reflection µ ∈ D
n
permutes corners of the n-gon by swapping pairs. How many pairs
of corners does µ swap when n ≡ 1 (mod 4)? Is µ an odd or even permutation? You may
use a picture, provided it is sufficiently general.
(e) Summarize parts (a–d) to argue the ⇐ direction of the theorem.
(f) Prove the ⇒ direction of the theorem by exhibiting an element of D
n
which is not in A
n
whenever n ≡ 1 (mod 4).
44
