Math 120A — Introduction to Group Theory

Neil Donaldson

November 20, 2024

1 Introduction: what is abstract algebra and why study groups?

To abstract something means to remove context and application. Modern mathematics largely in-

volves studying patterns and symmetries (often observed in the real world) abstractly so as to ob-

serve 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 since Kindergarten!

Example 1.1. The integers Z = {. . . , −1, 0, 1, 2, 3, . . .} together with the operation + form a group.

We’ll see a formal deﬁnition 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.

Other 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 (a translation, rotation or reﬂection). More gen-

eral geometries may also be described by their groups of symmetries. Groups may also be

employed to describe geometric properties: 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.

From the point of view of this course, the best reason to study groups is simply that they’re fun!

For example, Z together with the two basic operations of addition and multiplication is a ring, as you’ll study in a later

course.

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/reﬂections of the triangle and permutations (rearrangements) of the set {1, 2, 3}. By con-

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

For instance, (1 2)

is the function which swaps 1 and 2, leaving 3 alone. The function (1 2 3) permutes all three numbers:

(1 2) :











1 7→ 2

2 7→ 1

3 7→ 3

and (1 2 3) :











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, µ

, µ

, ρ

Identity: leave everything alone Swap two numbers Permute all three

e = () µ

= (2 3) ρ

= (1 2 3)

= (1 3) ρ

= (1 3 2)

= (1 2)

Since permutations are functions, we may compose them. For instance (remember to do ρ

ﬁrst!),

◦ρ

= (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) = µ

, whence we write

◦ρ

= µ

This is an algebraic statement: two elements µ

, ρ

have been combined using an operation ◦to produce

a third element µ

. The full list of compositions may be assembled in a table; read the left column

ﬁrst, then the top row.

◦ e ρ

e e ρ

e µ

e ρ

You should verify a few more of these yourself.

We will return to this notation in Chapter 5, so don’t feel you have to be an expert now. The permutation (1 2) is known

as a 2-cycle because it permutes two objects. The permutation (1 2 3) is similarly a 3-cycle.

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: ρ

and ρ

are rotations, while each µ

performs a reﬂection in the altitude

through vertex i.

The two sets of symmetries apply to different objects, but the

structure of their compositions are identical. For example, rotat-

ing the triangle clockwise (ρ

) followed by reﬂecting in the al-

titude through the lower-left corner (µ

), results in the triangle

being ﬂipped upside down as if we had only performed a single

reﬂection (µ

What do we gain from this correspondence? Intuition, for one

thing! There is an obvious qualitative difference between the ro-

tations ρ

, ρ

and the reﬂections µ

, µ

: since reﬂections ﬂip the

triangle upside down, it is completely obvious that composition

of reﬂections produces a rotation! The corresponding idea that

composition of 2-cycles makes a 3-cycle is not so clear.

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

between different part of mathematics are sometimes revealed.

Summary In this introductory example we considered two groups, which we now name.

is the symmetric group on three letters: the permutations of {1, 2, 3}

is the dihedral group of order six: the symmetries of an equilateral triangle

The mathematical way to summarize the relationship between these algebraic structures is to de-

scribe them as isomorphic,

written S

∼

As we progress, we’ll see more examples of relationships between seemingly different structures.

In the ﬁrst half of the course (Chapters 2–5) our primary goal is develop familiarity 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.

We will explain the term isomorphic more concretely, and revisit both examples later. 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.

2 Groups: Axioms and Basic Examples

In this chapter we deﬁne our main objects of study and introduce some of the vocabulary and exam-

ples used throughout the course—the “Key concepts/deﬁnitions” listed at the start of each Exercise

set. Most examples are very simple; their purpose is to help make sense of the abstract ideas. If an

example seems too confusing, feel free to ignore it on ﬁrst reading!

2.1 The Axioms of a Group

Deﬁnition 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 abstract situations (including most theorems) we typically drop the ∗ symbol and use juxtaposition

(x ∗y = xy). However, 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:

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 deﬁnition of integer addition.

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, 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: Z is closed under +.

3. On a small set, it can be convenient to use a table to represent a binary

operation. The given table describes an operation on a set of three elements

{e, a, b}. Read the left column ﬁrst, then the top row: for instance,

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 remaining axioms.

Deﬁnition 2.3 (Associativity). A binary structure (G, ∗) is associative if

∀x, y, z ∈ G, x(yz) = (xy)z

If ∗ is associative, then the expression xyz has unambiguous meaning, as does the usual exponen-

tial/power notation shorthand, e.g. x

= x ···x.

Examples (2.2, 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).



{e, a, b}, ∗



is non-associative: e.g. a(b

) = a

= e = b = eb = (ab)b.

Deﬁnition 2.4 (Identity). A binary structure (G, ∗) has an identity element e ∈ G if

∀x ∈ G, ex = xe = x

Examples (2.2, ver. III). 1. Addition on Z has identity 0, since 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 would depend on x!



{e, a, b}, ∗



has identity e; observe the ﬁrst row and column of the table.

By convention, if G is ﬁnite and has an identity (e.g. Example 2.2.3,) we list it ﬁrst. Indeed, we can

always list it ﬁrst, since. . .

Lemma 2.5 (Uniqueness of identity). A binary structure (G, ∗) has at most one identity.

It is now legitimate to refer to the identity e. Uniqueness proofs in mathematics often follow a stan-

dard 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

Since f = e, there is only one identity.

We used almost nothing about (G, ∗); in particular it need not be associative (e.g. Example 2.2.3).

Deﬁnition 2.6 (Inverse). Let (G, ∗) have identity e. An element x ∈ G has an inverse y ∈ G if

xy = yx = e

Examples (2.2, 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

= a

= 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 2.2.3 shows that this condition is necessary:

a non-associative structure can have non-unique inverses.

Deﬁnition 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 (2.2, ver.V). 1. Addition of integers is commutative: ∀x, y ∈ Z, x + y = y + x.

2. Subtraction of integers is non-commutative: e.g. 2 −3 = 3 −2.

3. The relation is commutative since its table is symmetric across its main ↘ diagonal.

To obtain our main deﬁnition, simply assemble the pieces!

Deﬁnition 2.9 (Group axioms). A group G 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

. Moreover, G is abelian if ∗ is commutative.

Of our examples, only (Z, +) is a group; indeed an abelian, inﬁnite order, additive

group. The same

observations show that ( Q, +), (R, +) and (C, +) are abelian groups.

While it is common practice to refer to a set G as a group, you should do so only if the operation ∗ is

obvious to everyone. Writing “Z is a group under addition,” is much safer than “Z is a group.”

Examples 2.10. 1. The non-zero real numbers R

form 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

is an inverse: x ·

· x = 1

Commutativity If x, y = 0, then xy = yx

As before, we cannot prove these claims since they are part of the deﬁnition of multiplication.

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

Groups of orders 1, 2 and 3 are shown; check this! Note

the magic square property: each row/column contains ev-

ery element exactly once (see Exercise 13).

∗

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

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

in a multiplicative group.

Arthur Cayley (1821–1895) was an early group theorist. Similarly abelian honors Niels Abel (1802–1829).

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

Proof. The ﬁrst two parts are exercises. For the third, multiply out using associativity:

( y

−1

)(xy) = y

−1

x)y = y

−1

ey = y

−1

y = e

Similarly (xy)(y

−1

) = e. Thus y

−1

is the (unique by Lemma 2.7) inverse of xy.

Associativity, Functional Composition & Geometric Symmetry Groups

Of all the group axioms, associativity is the most irritating to verify directly. Thankfully it often

comes for free due to a simple result.

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



By viewing rotations and reﬂections as functions transforming a geometric ﬁgure (recall the triangle,

Example 1.2), the Lemma veriﬁes associativity for the following.

Corollary 2.13. The rotations of a geometric ﬁgure form a group under composition. Moreover, the

symmetries (rotations and reﬂections) form a second group under composition.

Checking the other axioms is an exercise; the identity is considered a rotation (by 0°).

Deﬁnition 2.14. 1. For ﬁxed n ∈ N

≥3

, let ρ

denote rotation counter-clockwise by

2πk

radians. Then

:= {ρ

, . . . , ρ

n−1

} is the rotation group of a regular n-gon.

2. The dihedral group D

is the full symmetry group of a regular n-gon (rotations and reﬂections).

3. The Klein four-group,

denoted V, is the

symmetry group of a rectangle (or a

rhombus): e is the identity, a represents

rotation by 180°, and b, c are reﬂections.

◦ e a b c

e e a b c

a a e c b

b b c e a

c c b a e

Try drawing a smiley face on one side of a piece of paper and rotating/reﬂecting it until you believe

Klein’s example!

From the German Vierergruppe. Felix Klein (1849–1925) was a pioneer in the application of group theory to geometry.

Since multiplication by an n × n matrix amounts to a function (e.g. A ∈ M

(R ) corresponds to a

linear map R

→ R

: 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

(R ) = {A ∈ M

(R ) : det A = 0} (non-abelian when n ≥ 2)

Invertibility is assumed, associativity is the corollary, and closure follows from the familiar result

det AB = det A det B

Finally, the identity is multiplication by (drum roll. . . ) the identity matrix I =







1 0

0 1







Does part 3 of Theorem 2.11 now seem familiar?

Exercises 2.1. Key concepts/deﬁnitions/examples: make sure you can state the formal deﬁnitions

Group (closure, associativity, identity, inverse) Commutativity/abelian Cayley table

Rotation group R

Dihedral group D

Klein 4-group V General linear group GL

(R )

1. Given the binary operation table, calculate

(a) c ∗d (b) a ∗(c ∗b)

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

(e) ( N, ∗), a ∗b = a

(f) ( Q

, ∗), a ∗b = a

, where Q

= {x ∈ Q : x > 0}

(g) ( N, ∗), a ∗b = product of the distinct prime factors of ab. Also deﬁne 1 ∗1 = 1.

(e.g. 42 ∗10 = (2 ·3 ·7) ∗ (2 ·5) = 2 ·3 ·5 ·7 = 210)

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.

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

(R ) : det A = ±1} (b) L = {A ∈ M

(R ) : det A = 7}



a b

0 d



∈ M

(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

)

= (x

)

−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

)

= xy

−1

(b) ∀x ∈ G, (x

−1

)

−1

= x

−1

= x

−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

of a square.

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 satisﬁed by the union operator ∪ on P(U)?

(b) Repeat part (a) for the intersection operator.

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 ﬁnite.

Prove that (G, ∗) is a group if and only if its (multiplication) table satisﬁes two conditions:

i. One row and column (by convention the ﬁrst) is a perfect copy of G itself.

ii. Every element of G appears exactly once in each row and column.

2.2 Subgroups

The preﬁx sub- in mathematics usually indicates a subset that retains whatever structure follows.

Deﬁnition 2.17 (Subgroup). Let G be a group. A subgroup of G is a subset H ⊆ G which remains 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 should be immediate from the deﬁnition.

1. {e} ≤ G and G ≤ G for any G 2. ( Z, +) < (Q, +) < (R, +) < (C, +)

3. ( Q

, ·) < (R

, ·) < (C

, ·) 4. ( R

, +) < (C

, +)

5. ( 2Z, +) < (Z, +) 6. (R

, ◦) ≤ (R

, ◦) (rotation groups)

Thankfully one doesn’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 satisﬁes all the axioms, including closure and inverse.

( ⇐) Since H is a subset of G, the group operation on G is automatically associative

on H. By

assumption, H also satisﬁes 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 of Examples 2.18 can be conﬁrmed 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 satisﬁes 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, +).

Deﬁnition 2.3 makes no claim as to where x(yz) = (xy)z lives!

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

2Z 3Z

where all four are groups under addition. If G has only ﬁnitely 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

(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

(R ) = {A ∈ M

(R ) : A

A = I} forms a subgroup of GL

(R ).

• I ∈ O

(R ) so we have a non-empty set. Moreover, if A ∈ O

(R ), then

1 = det I = det A det A

= (det A)

=⇒ det A = 0 =⇒ A ∈ GL

(R )

• If A, B ∈ O

(R ), then

(AB)

(AB) = B

AB = B

IB = B

B = I, and,

−1

)

−1

= (A

)

= (AA

)

= I

whence AB and A

−1

∈ O

(R ).

We call this the orthogonal group. When n = 2 or 3, its elements may be recognized as rotations and

reﬂections. For instance, the matrix

√



1 −1

1 1



∈ O

(R ) rotates R

counter-clockwise by 45°.

Geometric subgroup proofs Arranging ﬁgures 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

{ρ

, . . . , ρ

, µ

, . . . , µ

} consisting of six rotations and six reﬂections:

• ρ

is rotation counter-clockwise by 60k°; the identity is ρ

• The µ

are reﬂections across ‘diameters’ of the hexagon as in-

dicated in the pictures below.

Now draw two equilateral triangles inside the hexagon. Each of

the six symmetries of the equilateral triangle is also a symmetry

of the hexagon! Since both are groups under the same operation

(composition of functions), it follows that the symmetry group D

of the triangle is a subgroup of D

, indeed in two different ways:

{e, ρ

, ρ

, µ

} < D

and {e, ρ

, ρ

, µ

} < D

The key takeaway here is that subgroup relations are everywhere in mathematics.

Exercises 2.2. Key concepts/deﬁnitions: (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. Describe/explain the relationship between positive integers m and n if (mZ, +) ≤ (nZ, +).

4. Prove or disprove: the set H = {

: a ∈ Z, n ∈ N

} forms a group under addition.

5. Use Theorem 2.19 to explain why the set of rotations of a planar geometric ﬁgure is a subgroup

of the group of its rotations and reﬂections.

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

7. Find the subgroups and subgroup diagram of the rotation group R

= {ρ

, . . . , ρ

}, where ρ

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 each set of matrices forms a group under multiplication (unless you love matrices,

don’t feel you have to memorize these).

(a) Special linear group: SL

(R ) =



A ∈ M

(R ) : det A = 1



(b) Special orthogonal group: SO

(R ) = {A ∈ M

(R ) : A

A = I and det A = 1}



A ∈ M

(R ) : det A ∈ Q



(d) (Harder) Symplectic group: Sp

(R ) =



A ∈ M

(R ) : A

JA = J



, where J =



0 I

−I



a block matrix and I

the n ×n identity matrix.

(e) (Hard) SL

(Z ) =



A ∈ M

(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

(R ), SL

(R ), O

(R ), SO

(R ), Q

, SL

(Z ) (ignore Sp

(R ))

11. (Hard) Q

= {±1, ±i, ±j, ±k} forms a group under ‘multiplication’ subject to the properties:

• 1 is the identity.

• −1 commutes with everything; e.g. (−1)i = −i = i(−1), etc.

• (−1)

= 1, i

= j

= k

= −1 and ij = k.

• Multiplication is associative.

(a) Find the Cayley table of (Q

, ·).

(Hint: You should easily be able to ﬁll in 44 of 64 entries; now use associativity. . . )

(b) Find all subgroups of Q

and draw its subgroup diagram.

2.3 Homomorphisms & Isomorphisms

A key goal of abstract mathematics is the comparison of similar/identical structures with outwardly

different appearances. Our method of comparison is to use functions.

Deﬁnition 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 these notes (certainly after this chapter), all binary structures will be groups.

Examples 2.24. 1. The function ϕ : (N, +) → (R, +) deﬁned 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:

∀v

, v

∈ V, T(v

+ v

) = T(v

) + T(v

)

You’ve been encountering homomorphisms your entire mathematical career, even in calculus:

( f + g) =

d f

is a homomorphism property!

The most useful homomorphisms are bijective, so much so that they get a special name.

Deﬁnition 2.25 (Isomorphism). An isomorphism is a bijective/invertible homomorphism.

We say that G and H are isomorphic, written G

∼

H, if there exists an isomorphism ϕ : G → H.

Why do we care about isomorphisms? Because isomorphic structures are essentially identical: one is

simply a relabelled version of the other!

Here is the standard procedure for showing that binary structures (G, ∗) and (H, ⋆) are isomorphic:

1. (Deﬁnition) Deﬁne ϕ : G → H, if necessary.

2. (Homomorphism) Verify that ϕ(x ∗y) = ϕ(x) ⋆ ϕ(y) for all x, y ∈ G.

3. (Injectivity/1–1) Check ϕ(x) = ϕ(y) =⇒ x = y.

4. (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 can be combined if you exhibit

an explicit inverse function ϕ

−1

: H → G.

The scalar multiplication condition T(λv) = λT(v) of a linear map is not relevant here.

These terms come from ancient Greek: homo- (similar, alike), iso- (equal, identical), and morph(e) (shape, structure).

As we’ll see later (e.g., Theorem 3.11), if G is a set of equivalence classes you might need to check that ϕ is well-deﬁned.

Examples 2.26. 1. We show that ( 2Z, +) and (3Z, +) are isomorphic groups.

Deﬁnition: The obvious function is ϕ(x) =

x. Plainly ϕ(2m) = 3n whence ϕ : 2Z → 3Z.

Homomorphism: ϕ(x + y) =

(x + y) =

x +

y = ϕ(x) + ϕ(y)

Injectivity: ϕ(x) = ϕ(y) =⇒

x =

y =⇒ x = y.

Surjectivity: If z = 3n ∈ 3Z, then z =

z =

(2n) = ϕ(2n) ∈ range ϕ.

The last step is essentially the observation that ϕ

−1

( z) =

More generally, the groups (mZ, +) and (nZ, +) are isomorphic whenever m, n = 0.

2. The function ϕ(x) = e

is an isomorphism of abelian groups ϕ : (R, +)

∼

, ·).

Deﬁnition: 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 (group theory is everywhere!)

ϕ(x + y) = e

x+y

= e

= ϕ(x)ϕ(y)

Bijectivity: ϕ

−1

( z) = ln z is the inverse function of ϕ.

Non-isomorphicity & Structural Properties Unless sets are very small, it is unrealistic to test every

function ϕ : G → H to see that structures are non-isomorphic! Instead we have to be a little more

cunning.

Deﬁnition 2.27 (Structural properties). A structural property is any property which is preserved

under isomorphism: if ϕ : (G, ∗) → (H, ⋆) is an isomorphism then (G, ∗) and (H, ⋆ ) have identical

structural properties.

Suppose ϕ : (G, ∗) → (H, ⋆) is an isomorphism. Here is a non-exhaustive list of structural properties;

we’ll check some 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: If G has identity e, then ϕ(e) is the identity for H. Similarly ϕ maps inverses to

inverses.

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.

Examples 2.28. 1. Since N

= {0, 1, 2, 3, . . .} contains an identity element 0 while N does not, we

conclude that the binary structures (N

, +) and (N, +) are non-isomorphic..

2. The binary structures deﬁned by the two tables are non-isomorphic;

the ﬁrst 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 inﬁnite while R is uncountable.

4. GL

(R ) and (R, +) have the same cardinality. However, since the ﬁrst 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 convert a bijection into an isomorphism simply by impos-

ing the homomorphism property. If (H, ⋆) and a bijection ϕ : G → H are given, we can deﬁne 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 binary structure from

G to H using a bijection:

w ⋆ z := ϕ



−1

( w) ∗ϕ

−1

( z)



Example 2.29. The function ϕ(x) = x

+ 8 is a bijection R → R. If ϕ : (R, ∗) → (R, + ) is an

isomorphism, then the operation ∗ must be

x ∗y := ϕ

−1



ϕ(x) + ϕ(y)



= ϕ

−1

+ y

+ 16) =

+ y

+ 8

Since (R, +) is an abelian group and ϕ

−1

an isomorphism, (R, ∗) must also be an abelian group.

Moreover, its identity must be

−1

(0) =

√

−8 = −2

As a sanity check, observe that

x ∗(−2) =

+ (−2)

+ 8 = x

Up to Isomorphism: a common shorthand This phrase is ubiquitous in abstract

mathematics. For an example of how it is used, recall that if ({e, a}, ∗) is a group with

identity e, then its Cayley table must be as shown (Example 2.10.6). Said formally:

∗ e a

e e a

a a e

Up to isomorphism, there exists 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, for without it the sentence is false: there are inﬁnitely

many distinct groups of order two, but all are isomorphic.

With its focus on functions rather than sets and its long list of unfamiliar words, this last introductory

section likely seems the hardest of the three. Complete ﬂuency with the vocabulary is not required at

this stage. The next few chapters will focus on several standard families of groups, providing plenty

opportunity to reinforce the language introduced in this chapter.

Exercises 2.3. Key concepts/deﬁnitions: 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

x (d) ϕ : (Q, ·) → (Q, ·), ϕ(x) = x

(e) ϕ : (R, ·) → (R, ·), ϕ(x) = x

(f) ϕ : (R, +) → (R, ·), ϕ(x) = 2

(g) ϕ : (M

(R ), ·) → (R, ·), ϕ(A) = det A

(h) ϕ : (M

(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

, +)

∼

, ×) (cross product).

4. ϕ(n) = 2 − n is a bijection of Z with itself. For each of the following, deﬁne 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))

(Hint: read Example 2.29)

5. ϕ(x) = x

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

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 homomor-

phism. Must ϕ(e) be an identity for H? Explain why/why not. Does it matter whether ϕ is a

homomorphism of groups?

9. Let G be the group of rotations of the plane about the origin under composition.

(a) Show that ϕ : (R, +) → G deﬁned 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

(R )



forms a group under matrix addition.

(b) Prove that T = S \{0} (S without the zero matrix) forms a group under matrix multipli-

cation.



a −b

b a



= a + ib. Prove that ϕ : S → C and ϕ

: T → C

are both isomorphisms

ϕ : (S, +)

∼

(C, + ), ϕ

: (T, ·)

∼

, ·)

(In a future class, ϕ will be described as an isomorphism of rings/ﬁelds)

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: ﬁnd 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

(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

= e? Your

answers should look like the Klein four-group V and the rotation group R

13. Prove that isomorphic is an equivalence relation on any collection of groups: that is, for all

groups G, H, K, we have

Reﬂexivity G

∼

Symmetry G

∼

H =⇒ H

∼

Transitivity G

∼

H and H

∼

K =⇒ G

∼

3 Cyclic groups

3.1 Deﬁnitions and Basic Examples

Cyclic groups are a basic family whose complete structure is simple enough to be easily described.

The foundational idea is that a cyclic group is generated by a single element.

Examples 3.1. 1. (Z, +) is generated by 1: all integers may be produced by (repeatedly) combining

1 with itself using only the group operation (+) and inverses (−). For instance,

−4 = −(1 + 1 + 1 + 1)

2. The set of complex numbers U

= {i, −1, −i, 1} = {i, i

, i

}is generated by the single element

i under multiplication. We’ll revisit this example in more generality shortly.

3. The group R

= {ρ

, . . . , ρ

n−1

} of rotations of a regular n-gon (Deﬁnition 2.14) is generated by

the ‘1-step’ rotation ρ

, since any other is just this repeated ρ

= ρ

We formalize this idea by considering the subset of a group G that may be produced starting with a

single element g. Since we work abstractly, we follow the convention of writing G multiplicatively.

Lemma 3.2 (Cyclic subgroup). Let G be a group and g ∈ G. The set

⟨

⟩

:= {g

: n ∈ Z} = {. . . , g

−1

, e, g, g

, . . .}

is a subgroup of G. We call this the cyclic subgroup generated by g.

Proof. We follow the subgroup criterion (Theorem 2.19).

Non-emptiness: Plainly e ∈

⟨

⟩

Closure: Every element of

⟨

⟩

has the form g

for some k ∈ Z. The required condition

follows from standard exponential notation: g

· g

= g

k+l

∈

⟨

⟩

Inverses: This is immediate by Exercise 2.1.8c: (g

)

−1

= g

−k

∈

⟨

⟩

Deﬁnition 3.3 (Cyclic group). A group G is cyclic if it has a generator: ∃g ∈ G such that G =

⟨

⟩

In any group G, the order of an element g is the order (cardinality) of the subgroup

⟨

⟩

≤ G.

Warning! Don’t confuse the order of a group G with the order of an element g ∈ G. Cyclic groups are

precisely those containing elements (generators) whose order equals that of the group!

Examples (3.1 cont). 1. Z =

⟨

⟩

⟨

−1

⟩

is generated by either 1 or −1. As an additive group, the

subgroup generated by 2 is the group of even numbers under addition

⟨

⟩

= {. . . , −2, 0, 2, 4, . . .} = {2m : m ∈ Z} = 2Z

2. U

⟨

⟩

= {1, i, −1, −i} is a cyclic subgroup of (C

, ·). It is also generated by −i.

3. R

⟨

⟩

. This group has other generators, but we’ll delay describing them until the next

section.

Modular Arithmetic

We introduce a family of ﬁnite groups based on the (hopefully familiar!) addition of remainders.

Deﬁnition 3.4. Let n be a positive integer. We denote by Z

the set of equivalence classes of integers

modulo n. These are typically written as remainders

= {0, 1, . . . , n −1}

where x = y ∈ Z

means that the integers x, y have the same remainder

on division by n.

Several notations are available. For instance, here is a calculation in Z

written four ways:

(a) Group/Number Theory style: 4 + 2 = 6 = 1 in Z

(b) Modular arithmetic: 4 + 2 ≡ 6 ≡ 1 (mod 5).

2 = 6 = 1.

(d) Equivalence classes: [4] +

[2] = [ 6] = [1].

Warning! For reasons of brevity we mostly use notation (a),

though feel free to use another if you feel more comfortable.

Regardless of notation, it must be made clear in which Z

you

are working: 4 + 2 = 1 is not acceptable on its own!

[0]

= {. . . , 0, 5, 10, . . .}

[1]

= {

. . . ,

−

4, 1, 6, . . .

}

[2]

= {

. . . ,

−

3, 2, 7, . . .

}

[3]

= {

. . . ,

−

2, 3, 8, . . .

}

[4]

= {

. . . ,

−

1, 4, 9, . . .

}

Adding 1 in Z

Theorem 3.5. Z

forms a cyclic group of order n under addition modulo n.

A rigorous proof is tedious right now and will come for free in Chapter 6 when Z

is properly deﬁned

as a factor group. For the present, note that Z

is cyclic since it is generated by 1: e.g.,

⟨

⟩

= {1, 2, 3, 4, 0} = {1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1}

Examples 3.6. Here are the Cayley tables for Z

, Z

. Compare these to Example 2.10.6.

0 0

0 1

0 0 1

1 1 0

0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

More formally, x = y ∈ Z

means x ≡ y (mod n), or equivalently x = y + λn for some integer λ. The elements of Z

are strictly equivalence classes 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

Addition of equivalence classes is well-deﬁned: if [x] = [w] and [y] = [z], then w = x + κn and z = y + λn, from which

[w] +

[z] = [w + z] =



(x + κn) + (y + λn)





x + y + n(κ + λ)



= [x + y] = [x] +

[y]

The groups Z

are typically those to which other cyclic groups are compared. Indeed in the next

section we’ll see that any cyclic group of order n is isomorphic to Z

Example 3.7. ( Z

, +

) is isomorphic to the rotation group (R

, ◦) via ϕ(k) = ρ

k (mod 3)

It is worth doing this slowly, since the domain is a set of equivalence classes:

Well-deﬁnition: If y = x ∈ Z

, then y ≡ x ≡ r (mod 3) for some r ∈ {0, 1, 2}. But then

ϕ(y) = ρ

= ϕ(x)

Bijection: This is trivial ϕ : {0, 1, 2} → {ρ

, ρ

Homomorphism: This is the formula for composition of rotations ρ

= ρ

k+l (mod 3)

The Roots of Unity

For a ﬁnal family of cyclic groups, we consider subgroups of (C

, ·).

Deﬁnition 3.8. Let n ∈ N. The n

roots of unity form the subgroup of C

generated by ζ := e

2πi

⟨

⟩



1, ζ, ζ

, ··· , ζ

n−1



These are precisely the n complex solutions to the equation z

= 1. To emphasize n, write ζ

= e

2πi

Aside: Notation Review In case you’ve not thought much about complex number notation, here is

a brief review. C = {x + iy : x, y ∈ R} is the vector space R

spanned by the basis {1, i}, where i is a

‘number’ satisfying i

= −1. Given z = x + iy ∈ C, consider several objects:

Complex conjugate: z = x −iy is the reﬂection of z in the real axis.

Modulus (length): r =

√

zz =

+ y

Argument (angle): If z = 0, then θ = arg z is the angle measured

counter-clockwise from the positive real axis to the ray

−→

0z.

Polar form: z = re

iθ

= r cos θ + ir sin θ.

The modulus and argument are simply the usual polar co-ordinates of

a point in R

. When r = 1 we have Euler’s formula:

iθ

= cos θ + i sin θ

the source of the famous identity e

iπ

= −1. In the picture, S

denotes

the unit circle. Note also that

iθ

= 1 ⇐⇒ θ = 2πk for some integer k (†)

The polar form behaves nicely with respect to multiplication:

0 1 2

z = 1 +

√

3i = 2e

iπ

|z| = 2

arg z =

−1 1

iθ

−i

and arg(zw) ≡ arg z + arg w (mod 2π)

The square roots of unity are simply ±1, and we saw the 4

roots

±1, ±i in Example 3.1. More generally, the n

roots are form the

vertices of a regular n-gon centered at the origin; this is since



= 1 and arg ζ

= arg e

2πk

= k arg ζ

We stop listing the elements of U

at ζ

n−1

, since ζ

= e

2πi

= 1. By

( †), we see a simple relationship with modular arithmetic:

= ζ

⇐⇒ 1 = ζ

k−l

= e

2πi(k−l)

⇐⇒ k ≡ l (mod n)

−1 1

−i

Seventh roots: ζ

= e

2πi

Examples 3.9. 1. Observe that ζ

= (e

2πi

)

= e

2πi

= ζ

This immediately results in a subgroup relationship: with ζ = ζ



1, ζ

, ζ



< U



1, ζ, ζ

, ζ



This is essentially trivial from a picture (compare Example 2.22).

ζζ

2. Cayley tables for U

are simple to construct. Here is U

, where we use the fact that ζ

= 1.

Write 1 = ζ

and ζ = ζ

makes the relationship with (Z

, +

) and (R

, ◦) glaring:

· 1 ζ ζ

1 1 ζ ζ

ζ ζ ζ

1 ζ

· ζ

0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

◦ ρ

More formally, the groups are isomorphic (U

, ·)

∼

, +

)

∼

, ◦).

Exercises 3.1. Key concepts: Generator Order of an element Cyclic (sub)group Z

Roots of unity

1. State the Cayley tables for ( Z

, +

) and (Z

, +

2. List all the generators of each cyclic group.

(a) ( Z, +).

(b) {2

−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

generated by ρ

? Generated by µ

4. Explicitly compute the cyclic subgroup





of U

, listing its elements in the order generated.

5. The circle group is the set S

= {e

iθ

: θ ∈ [0, 2π)}. Prove that S

is a subgroup of C

under

multiplication.

6. (a) Prove that (U

, ·) is a subgroup of (U

, ·).

(b) Complete the sentence and prove your assertion:

≤ U

if and only if (relationship between m and n)

7. (a) Show that the set Z

= {1, 2, 3, 4} forms a cyclic group under multiplication modulo 5.

(b) What about the set Z

= {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

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) Let z be a complex number. Explain why ζ

z = ρ

( z) is the result of rotating z counter-

clockwise by

2πk

radians.

(b) Use part (a) to prove that (U

, ·) and (R

, ◦) are isomorphic groups.

11. Give examples of:

(a) A ﬁnite non-cyclic group.

(b) An inﬁnite non-cyclic group.

In both cases, explain how you know that your example is non-cyclic.

3.2 The Classiﬁcation and Structure of Cyclic Groups

We describe all cyclic groups, their generators, and subgroup structures.

Lemma 3.10. Every cyclic group is abelian.

Proof. Let G =

⟨

⟩

. Since any two elements of G can be written g

, g

for some k, l ∈ Z, we see that

= g

k+l

= g

l+k

= g

The converse is false: the Klein four-group V is abelian but not cyclic (is the reason obvious to you?).

The next result is crucial to our classiﬁcation; it is quite hard, so take your time and read carefully.

Theorem 3.11 (Isomorphs). Every cyclic group is isomorphic either to (Z, +) or to some (Z

, +

If G =

⟨

⟩

, then ϕ : x 7→ g

is an isomorphism ϕ : Z

(n)

∼

G: “map generator (1) to generator (g).”

The proof is a little sneaky. To distinguish the two cases, we introduce a useful set of natural numbers

S := {m ∈ N : g

= e} (mg = e if G is additive). To see why, consider a few examples of the theorem.

Examples 3.12. 1. If G = R

⟨

⟩

, then ρ

= e ⇐⇒ 3 | m, whence S = {3, 6, 9, . . .}. Observe that

3 = min S is the order of G. Moreover ϕ(x) = ρ

is an isomorphism Z

∼

(Example 3.9.2).

2. Z

⟨

⟩

is additive, so S = {m ∈ N : m = 0} = {4, 8, 12, . . .} (in Z

, m = 0 means 4 | m!).

Observe that 4 = min S is the order of G =

3. 5Z =

⟨

⟩

is an inﬁnite cyclic group. In this case, S = {m ∈ N : 5m = 0} = ∅ is empty. This is

isomorphic to Z via ϕ : Z → 5Z : x 7→ 5x (map the generator 1 ∈ Z to the generator 5 ∈ 5Z).

As the examples suggest, S distinguishes the ﬁnite/inﬁnite cases and detects the order of G.

Proof. If S = ∅: Suppose x > y and that g

= g

. Then g

x−y

= e =⇒ x −y ∈ S: contradiction. The

elements . . . , g

−2

, g

−1

, e, g, g

, . . . are therefore distinct, whence ϕ : Z → G : x 7→ g

is bijective.

If S = ∅: Let n = min S and deﬁne ϕ : Z

→ G : x 7→ g

. We ﬁrst check this is well-deﬁned:

y = x ∈ Z

=⇒ y = x + kn for some k ∈ Z

=⇒ ϕ(y) = g

= g

x+kn

= g

)

= g

= ϕ(x)

Since the highlighted calculation is valid for all x, k ∈ Z, we also conclude that

G =

⟨

⟩

⊆ {e, g, . . . , g

n−1

} (in particular, G is ﬁnite)

Suppose two of these terms were equal; if 0 ≤ y ≤ x ≤ n −1, then

= g

=⇒ 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)ϕ(y)

Corollary 3.13. If the order of an element g is ﬁnite, then it equals the minimal positive integer n for

which g

= e. Moreover g

= e ⇐⇒ n | m.

Examples 3.14. 1. The group of 7

roots of unity U

is isomorphic to Z

via ϕ : Z

→ U

: k 7→ ζ

As a sanity check, 7 = min{m ∈ N : ζ

= 1} is indeed the order of ζ

2. Let ξ = e

2πi

√

and consider the cyclic subgroup G :=

⟨

⟩

< (C

, ·). For integers m, observe that

= e

2πim

√

= e = 1 ⇐⇒

√

∈ Z ⇐⇒ m = 0

We conclude that G is an inﬁnite cyclic group and that ϕ : Z → G : z 7→ ξ

is an isomorphism.

We can interpret multiplication by ξ as performing an irrational fraction (

√

) of a full rotation.

3. ( R, +) is non-cyclic since its (uncountable) cardinality is larger than the (countable) cardinality

of the integers. This is also straightforward to see directly: if R were cyclic with generator x,

then we’d obtain an immediate contradiction

/∈ {. . . , −2x, −x, 0, x, 2x, 3x . . .} = R ∋

The same argument shows that (Q, +) is not cyclic.

All subgroups of a cyclic group may be straightforwardly described: they’re also cyclic!

Theorem 3.15 (Subgroups of Cyclic Groups). 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 subgroup H ≤ G, we identify a suitable ‘minimal’ element, and

demonstrate that this generates H.

Proof. Suppose H ≤ G =

⟨

⟩

. If H = {e} is trivial, we are done: H is cyclic!

Otherwise, ∃s ∈ N minimal so that g

∈ H. We claim that H is generated by g



⟨

⟩

⊆ H



This is trivial since g

∈ H.



H ⊆

⟨

⟩



Let g

∈ H. By the division algorithm, there exist unique integers q, r such that

m = qs + r and 0 ≤ r < s

But then, since H is closed under · and inverses,

= g

qs+r

= (g

)

=⇒ g

= (g

)

−q

∈ H (∗)

The minimality of s now forces r = 0, from which we conclude that g

= (g

)

∈

⟨

⟩

If the proof seems too hard to follow, try rewriting it carefully when G = Z, H = 2Z and s = 2:

remember that G is additive, so (∗) simply becomes r = −2s + m ∈ H, from which m = 2s. . .

We treat the ﬁnite and inﬁnite cases separately. The inﬁnite case is very simple.

Corollary 3.16 (Subgroups of inﬁnite cyclic groups). If G is an inﬁnite cyclic group and H ≤ G,

then either H = {e} is trivial, or H

∼

We leave the proof as an exercise (just generalize the following example!).

Example 3.17. It is helpful to write things out explicitly in additive notation when G = Z. Since

every subgroup is cyclic, there are two cases:

• The trivial subgroup:

⟨

⟩

= {0}.

• Every other subgroup:

⟨

⟩

= sZ when s = 0. Each of these is isomorphic to Z via an isomor-

phism ϕ : Z → sZ : x 7→ sx.

Finite cyclic groups are a little more complicated so we ﬁrst consider an example.

Example 3.18. Consider U

= {1, ζ, ζ

, ζ

} under multiplication. Since all subgroups are

cyclic, we need only consider the subgroup

⟨

⟩

generated by each element x.

x subgroup

⟨

⟩

1 {1}

ζ {1, ζ, ζ

, ζ

}

{1, ζ

, ζ

}

{1, ζ

}

{1, ζ

, ζ

}

{1, ζ

, ζ

, ζ}

⟨

⟩

= U





= U





= U

⟨

⟩

= U

Observe the repetitions:

⟨

⟩





= U

and









= U

For comparison, here is the same data for subgroups of the additive group (Z

, +

subgroup

⟨

⟩

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}

⟨

⟩

= Z

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

As must be since the groups are isomorphic, the difference is entirely notational! One subtle dif-

ference is that we don’t use equals in the second subgroup diagram: for instance,

⟨

⟩

= {0, 2, 4} is

isomorphic but not equal to Z

= {0, 1, 2}.

You should be able to guess two patterns from the example:

• Z

has exactly one subgroup of order d for each divisor d of n.

• If d ∈ Z

is a divisor of n, then

⟨

⟩

∼

The next result merely asserts these patterns for general ﬁnite cyclic G.

Corollary 3.19 (Subgroups of ﬁnite cyclic groups). Let G =

⟨

⟩

have order n. Then G has a unique

subgroup of each order dividing n and g

is a generator if and only if gcd(s, n) = 1. More precisely,

d = gcd(s, n) =⇒

⟨

⟩

= ⟨g

⟩, where this subgroup has order

Proof. Suppose d = gcd(s, n). Since d divides s we have s = kd for some k ∈ Z, and so

= (g

)

∈





=⇒ (g

)

= (g

)

=⇒

⟨

⟩

⊆





For the reversed set inclusion, apply B

ezout’s identity (extended Euclidean alg.): d = κs + λn for

some κ, λ ∈ Z, whence

= (g

)

= (g

)

∈

⟨

⟩

=⇒





⊆

⟨

⟩

To ﬁnish, consider the elements in ⟨g

⟩. Since d | n, there are precisely

of these, speciﬁcally

⟨g

⟩ =



e, g

, g

, . . . , g

n−d



As before, the result is worth restating for the additive group (Z

, +

d = gcd(s, n) =⇒

⟨

⟩

⟨

⟩

∼

, in particular, s generates Z

⇐⇒ gcd(s, n) = 1

Example 3.20. We describe the subgroups of Z

and construct its subgroup diagram. The ﬁrst

column lists each divisor d of 30 (the possible values of gcd(x, 30)), the second column the isomorphic

group Z

, and the third the subgroup generated by each value x ∈ Z

d = gcd(x, 30) Isomorph Z

Subgroup

⟨

⟩

1 Z

{0, 1, 2, 3, . . . , 7, . . . , 11, 12, 13, . . . , 17, 18, 19, . . . , 23, . . . , 29}

2 Z

{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28}

3 Z

{0, 3, 6, 9, 12, 15, 18, 21, 24, 27}

5 Z

{0, 5, 10, 15, 20, 25}

6 Z

{0, 6, 12, 18, 24}

10 Z

{0, 10, 20}

15 Z

{0, 15}

0 (30) Z

{0}

All generators of each subgroup are red in the table. The sub-

group diagram is drawn, with the obvious (minimal) gener-

ator chosen for each subgroup.

With a little thinking, you should appreciate that the shape

of the subgroup diagram (this one looks something like a

cube) depends only on the fact that in the prime factorization

30 = 2 ·3 ·5, each prime appears exactly once.

⟨

⟩

= Z

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

Exercises 3.2. Key concepts: Every cyclic group isomorphic to Z or Z

⟨

⟩

order n =⇒

⟨

⟩

order

gcd(s,n)

Subgroup diagrams for ﬁnite cyclic groups

1. Construct the subgroup diagram and give a generator of each subgroup:

(a) ( Z

, +

) (b) ( Z

, +

2. A generator of the cyclic group U

group is known as a primitive n

root of unity. For instance,

the primitive 4

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

where p, q are distinct primes.

(Hint: Try U

ﬁrst if this seems too difﬁcult)

4. If r ∈ N and p is prime, ﬁnd all subgroups of (Z

, +

) 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 inﬁnite cyclic group, how many generators has it?

→ Z

6. True or false: In any group G, if g has order n, then g

has order

gcd(s,n)

. Explain.

7. Suppose G =

⟨

⟩

is inﬁnite and H =

⟨

⟩

is an inﬁnite subgroup. Prove Corollary 3.16 by

explicitly ﬁnding an isomorphism ϕ : G → H.

8. Prove Corollary 3.13: you’ll need the division algorithm for the second part!

9. Let x, y be elements of a group G. If xy has ﬁnite order n, prove that yx also has order n.

(Hint: (xy)

= x(yx)

m−1

10. Let Z



x ∈ Z

: gcd(x, n) = 1



be the set of generators of the additive group (Z

, +

Prove that Z

is a group under multiplication modulo n.

(Hint: Use B´ezout’s identity (extended Euclidean Algorithm))

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 X = {m, n} generates dZ, where d = gcd(m, n).

set of two elements which generates V.

(d) Describe the subgroup of (Q, +) generated by X = {

(e) (Hard) (Q, +) is plainly generated by the inﬁnite set {

: n ∈ N }. Explain why (Q, +) is

not ﬁnitely generated: i.e. there exists no ﬁnite set X generating Q.

(Hint: Think about the prime factors of the denominators of elements of X)

4 Direct Products & Finitely Generated Abelian Groups

In this short chapter we discuss a straightforward way to create new groups from old using the

Cartesian product.

Example 4.1. Given Z

= {0, 1}, the Cartesian product

×Z



(0, 0), (0, 1), (1, 0), (1, 1)



has four elements. This set has a natural group structure by via addition of co-ordinates

(x, y) + (v, w) := (x + v, y + w)

where x + v and y + w are both computed in (Z

, +

). This is a binary operation on Z

×Z

, with a

familiar-looking Cayley table: it has exactly the same structure as 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

×Z

∼

V is indeed a group.

This construction works in general.

Theorem 4.2 (Direct product). The natural component-wise operation on the Cartesian product

∏

k=1

= G

×··· × G

, (x

, . . . , x

) ·(y

, . . . , y

) := (x

, . . . , x

)

deﬁnes a group structure: the direct product. This group is abelian if and only if each G

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



∏

k=1



∏

k=1

Examples 4.3. 1. The direct product of the groups (Z

, +

) and (Z

, +

) is

×Z



(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)



This is abelian of order 6, so we might guess it to be isomorphic to (Z

, +

) and thus cyclic.

This is indeed the case: simply observe that (1, 1) is a generator,

⟨

(1, 1)

⟩



(1, 1), (0, 2), (1, 0), (0, 1), (1, 2), (0, 0)



= Z

×Z

The map ϕ(x) = (x, x) is therefore an isomorphism ϕ : Z

∼

×Z

2. If each G

is abelian and written additively, the direct product can instead be called the direct sum

k=1

= G

⊕··· ⊕ G

We won’t use this notation,

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

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

×Z

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

×Z

? Recall Corollary 3.19:

• 10 ∈ Z

has order 6 =

gcd(10,12)

• 2 ∈ Z

has order 4 =

gcd(2,8)

If we repeatedly add (10, 2) to itself, then the ﬁrst co-ordinate resets after 6 summations, while the

second resets after 4. For both to reset simultaneously, we need a common multiple of 6 and 4 sum-

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

∈ G

has order r

. Then (x

, . . . , x

) ∈

∏

k=1

has order lcm(r

, . . . , r

Proof. Simply appeal to Corollary 3.13:

, . . . , x

)

= (x

, . . . , x

) = (e

, e

, . . . , e

) ⇐⇒ ∀k, x

= e

⇐⇒ ∀k, r

| m

The order is the minimal positive integer m satisfying this, namely m = lcm(r

, . . . , r

Example 4.6. Find the order of (1, 3, 2, 6) ∈ Z

×Z

Again with reference to Corollary 3.19, the element has order

lcm



gcd(1,4)

gcd(3,7)

gcd(2,5)

gcd(6,20)



= lcm(4, 7, 5, 10) = 140

In these notes a direct product/sum will only ever have ﬁnitely many terms, in which case the concepts are identical.

There is a slight distinction when there are inﬁnitely many factors.

When is a direct product of ﬁnite cyclic groups cyclic?

Recall that Z

×Z

∼

V is non-cyclic while Z

×Z

∼

is cyclic. It is reasonable to hypothesize

that the distinction is whether the orders of the components are relatively prime.

Corollary 4.7. Z

×Z

is cyclic ⇐⇒ gcd(m, n) = 1, in which case Z

×Z

∼

More generally:

• Z

×··· ×Z

∼

···m

⇐⇒ ∀i = j, gcd(m

, m

) = 1.

• If n = p

··· p

is the prime factorization, then Z

∼

×··· ×Z

Proof. We prove the ﬁrst part; the generalization follows by induction.

(⇐) If gcd(m, n) = 1, then (1, 1) ∈ Z

×Z

has order lcm(m, n) =

gcd(m,n)

= mn. Hence (1, 1) is a

generator of Z

×Z

, which is therefore cyclic.

(⇒) This is Exercise 10.

Examples 4.8. 1. (Example 4.6) The group Z

×Z

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

2. Is Z

×Z

cyclic? The Corollary says yes, since no pair of 5, 7, 12 have common factors.

It is ghastly to write, but there are 12 different ways (up to reordering) of expressing this group!

420

∼

×Z

140

∼

×Z

105

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

We may combine/permute the factors of 420 = 2

·3 ·5 ·7, provided we don’t separate 2

= 4.

The Fundamental Theorem

We used the direct product to create ﬁnite abelian groups from cyclic building blocks. While we don’t

have the technology to prove it, our next result provides a powerful converse.

Theorem 4.9 (Fundamental Theorem of Finitely Generated Abelian Groups).

Every ﬁnitely generated

abelian group is isomorphic to a group of the form

×··· ×Z

×Z ×··· ×Z

The p

are (not necessarily distinct) primes, each r

∈ N, and there are ﬁnitely many Z-factors.

A ﬁnite abelian group has no Z-factors.

Recall Exercise 3.2.11.

Examples 4.10. 1. Up to isomorphism, there are ﬁve distinct abelian groups of order 81 = 3

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

Such groups can often be distinguished by considering the orders of elements. For instance:

G is abelian of order 81 and,

G has an element of order 27 and,

All elements of G have order ≤ 27







=⇒ G

∼

×Z

2. Since 450 = 2 ·3

·5

is a prime factorization, the fundamental theorem says that every abelian

group of order 450 is isomorphic to one of four groups:

(a) Z

×Z

∼

450

(cyclic, maximum order of an element 450)

(b) Z

×Z

(non-cyclic, maximum order 150 = 2 ·3 ·5

)

×Z

(non-cyclic, maximum order 90 = 2 ·3

·5)

(d) Z

×Z

(non-cyclic, maximum order 30 = 2 ·3 ·5)

As previously, there are multiple isomorphic ways to express each group as a direct product.

We ﬁnish by listing, up to isomorphism, all groups of orders ≤ 15 and abelian groups of order 16.

order abelian non-abelian

1 Z

2 Z

3 Z

4 Z

, V

∼

×Z

5 Z

6 Z

∼

×Z

∼

7 Z

8 Z

, Z

×Z

, Z

×Z

, Q

9 Z

, Z

×Z

10 Z

∼

×Z

11 Z

12 Z

∼

×Z

, Z

×Z

∼

×Z

, A

, Q

13 Z

14 Z

∼

×Z

15 Z

∼

×Z

16 Z

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

Many

The list of non-abelian groups contains some unfamiliarity though we’ve met most already:

• The dihedral groups D

are the rotations/reﬂections of a regular n-gon (Deﬁnition 2.14).

• S

is in the introduction, though it and A

will be described properly in Chapter 5.

• Q

is the quaternion group (Exercise 2.2.11). The generalized quaternion group Q

is related.

There are nine non-isomorphic non-abelian groups of order 16: D

and the direct product Z

× Q

being explicit examples. You might suspect from the table 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

×Z

(b) Z

×Z

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

∏

is abelian if and only if its components G

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

×Z

(b) ( 4, 2, 1) ∈ Z

×Z

6. Is the group Z

×Z

125

cyclic? Explain.

7. Find a generator of the group Z

×Z

and hence deﬁne an isomorphism ϕ : Z

∼

×Z

(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

10. Complete the proof of Corollary 4.7: if Z

×Z

is cyclic, then gcd(m, n) = 1.

(Hint: if gcd(m, n) ≥ 2, what is the maximum order of an element in Z

×Z

11. Suppose G is an abelian group of order m, where m is a square-free positive integer (∄k ∈ Z

≥2

such that k

|m). Prove that G is cyclic.

12. (a) Let G be a ﬁnitely 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 ﬁnite abelian group and that m is a divisor of

. Prove that G has a subgroup

of order m.

(Hint: use the prime decomposition of m and the fundamental theorem to identify a suitable subgroup of

×·×Z

)

14. Give a simple explanation as to why D

is not isomorphic to Z

× Q

5 Permutations and Orbits

In this chapter we return to the roots of group theory by considering how a set may be reordered.

5.1 The Symmetric Group & Cycle Notation

Deﬁnition 5.1. A permutation of a set A is a bijective/invertible function σ : A → A.

The symmetric group S

is the set of all permutations of A under functional composition.

The symmetric group on n-letters

is the group S

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

has only one element and is isomorphic to Z

2. If A = {1, 2}, then there are two bijections e, µ : A → A:

• e(1) = 1 and e(2) = 2 deﬁnes the identity function.

• σ(1) = 2 and σ(2) = 1 swaps the elements of A.

◦ e σ

e e σ

σ σ e

The Cayley table is immediate: plainly S

is isomorphic to Z

3. We met S

= S

{1,2,3}

explicitly in Example 1.2; it has six elements and is non-abelian, e.g.

◦µ

= ρ

= ρ

= µ

◦µ

Lemma 5.3. 1. S

is indeed a group under composition of functions.

2. If A has at least three elements, then S

is non-abelian.

3. The order of S

is n! (Warning! The order of S

is not the subscript n)

4. S

≤ S

whenever m ≤ n (Strictly, S

contains a subgroup isomorphic to S

)

Proof. 1. Closure: If σ, τ : A → A are bijective, so is the composition

σ ◦τ.

Associativity: Composition of functions is associative (Lemma 2.12).

Identity: The identity function e

: 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, and

evaluation means that we act with τ ﬁrst:

στ(a) = σ



τ(a)



Similarly, exponentiation mean self-compositions: e.g. σ

= σσσ = σ ◦σ ◦σ.

For clarity we make S

an explicit group. In practice, any set with n elements will do and any group isomorphic to this

is usually also called S

(see Exercise 7).

The details should be familiar. Write them out if you are unsure.

Cycle Notation

Efﬁcient computations in S

are facilitated by some new notation.

Deﬁnition 5.4. Suppose {a

, . . . , a

} ⊆ {1, . . . , n}. The k-cycle σ = (a

···a

) ∈ S

is the function

σ :











7→ a

j+1

if j < k

7→ a

x 7→ x if x ∈ {a

, . . . , a

}

···

all other x

Cycles (a

···a

) and (b

···b

) are disjoint if {a

, . . . , a

}∩{b

, . . . , b

} = ∅.

1-cycles and the 0-cycle () can be helpful in calculations, though both are simply the identity e.

Example 5.5. A 4-cycle σ = (1 3 4 2) and a 2-cycle τ = (1 4) in S

are deﬁned in the table:

x 1 2 3 4

σ(x) 3 1 4 2

τ(x) 4 2 3 1

σ : 1





τ : 1







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







The result is a product of disjoint 2-cycles στ = (1 2)(3 4).

Algorithmic Cycle Composition Computation using tables is impractically slow. Here is an al-

gorithmic approach that, with practice, should prove more efﬁcient. We illustrate by verifying the

previous calculation: at each step you write only a single number or bracket, thus building up the

right column below.

• Open a bracket and write 1. στ = (1

• Since 1

7→ 4

7→ 2, we next write 2. στ = (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 next write 4. στ = (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 the algorithm terminates.

It should be clear how to extend the algorithm when composing more cycles. Simply delete any 1-

cycles if you obtain 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)

= (1 4)(2 5)(3 6)

Geometric Symmetry Groups

Permutations permit an easy description of the group of symmetries of a geometric ﬁgure: simply

label the vertices (or edges/faces) with numbers 1, 2, 3, . . . and represent each rotation/reﬂection by

how it permutes these values. Cycle notation makes calculating compositions easy!

Examples 5.7. 1. Label the vertices of a rhombus to view the Klein four-group V as a subgroup of

: the 2-cycles (1 3) and (2 4) are reﬂections, and their composition is rotation by 180°.

∼



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 reﬂection across the axis through

3 and 6.

• The 6-cycle (1 2 3 4 5 6) represents a one-step counter-clockwise ro-

tation (60°).

5 6

Both functions describe elements of the dihedral group D

. By extension, D

may be identiﬁed

as (is isomorphic to) a subgroup of S

3. By labelling the vertices of a square, we may identify D

with a subgroup

of S

. All elements and the complete subgroup diagram are given be-

low. By convention we denote reﬂections across diagonals (δ

) and the

midpoints of sides (µ

) differently.

Note the ease of computations: e.g.,

(2 4)(1 2)(3 4) = (1 4 3 2) =⇒ δ

= ρ

Element Cycle notation

e = ()

Rotations

(1234)

(13)(24)

(1432)

(12)(34)

Reﬂections

(14)(23)

(24)

(13)

Subgroup Isomorph

{ρ

} Z

{ρ

, µ

} Z

{ρ

, δ

} Z

{ρ

, ρ

} Z

{ρ

, ρ

} Z

{ρ

, µ

, ρ

} V

{ρ

, δ

, ρ

} V

V Z

You should be able to recognize these subgroups geometrically; e.g. the blue copy of V is pre-

cisely that in the ﬁrst example! Try to convince yourself why there are no other subgroups.

The same sort of thing can be done for 3D ﬁgures like the tetrahedron (see Section 5.3).

Cayley’s Theorem

The word group, at least in mathematics, originally referred to a set of permutations. We ﬁnish this

section with a foundational result that links to the original meaning of the word: every element of a

group may be viewed as a permutation—indeed of the group itself!

Theorem 5.8 (Cayley). Every group is isomorphic to a group of permutations.

The proof of Cayley’s Theorem is merely the abstraction of a simple example.

Example 5.9. To each integer g, we may associate the function “add g.” For instance, 1 corresponds

to the function “+1,” etc. The function “add g” is a bijection of the integers: its inverse function is

“add −g.” Each integer is therefore naturally associated to a permutation, an element of the group S

Proof. Let G be a group. For each g ∈ G, consider the function L

: G → G given by left-multiplication:

that is,

∀x ∈ G, L

(x) = gx

Plainly L

is bijective (with inverse (L

)

−1

= L

−1

), whence L

is a permutation of G: that is L

∈ S

Now deﬁne ϕ : G → S

by ϕ(g) = L

. We prove that ϕ is an injective homomorphism.

Injectivity ϕ(g) = ϕ(h) =⇒ L

= L

=⇒ L

( e) = L

( e) =⇒ ge = he =⇒ g = h

Homomorphism We show that ϕ(gh) = ϕ(g)ϕ(h) as functions by evaluating on all x ∈ G:



ϕ(gh)



(x) = L

(x) = (gh)x = g(hx) = L



(x)





ϕ(g)ϕ(h)



(x)

It follows that ϕ is an isomorphism onto its image, range ϕ ≤ S

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 some subgroup of S

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.

− x.

(d) f : R → R such that f (x) = x

+ x.

(e) f : {ﬁsh, horse, dog, cat} → {ﬁsh, horse, dog, cat} where

f (ﬁsh) = horse, f (horse) = cat, f (dog) = dog, f (cat) = ﬁsh

2. Compute the following products (compositions) of permutations in cycle notation.

(a) ( 1 2)(3 4)(1 2 3) ∈ S

(b) ( 1 4)(2 3)(3 4)(1 4) ∈ S

(d) ( 1 2 4 5)

(2 4 5)

∈ S

3. By labelling vertices, view the dihedral group D

of symme-

tries of the regular heptagon as a subgroup of S

. Each µ

reﬂection across the indicated dashed line, while ρ

is rota-

tion j steps counter-clockwise.

(a) State µ

in cycle notation.

(b) Compute µ

using cycle notation. What element of

does this represent?

)

666

= (1 2 3 4 5 6 7), ρ

= ρ

4. State the elements of the rotation group R

in cycle notation when viewed as a subgroup of S

5. Prove parts 2, 3, and 4 of Lemma 5.3.

6. How many distinct subgroups of S

are isomorphic to S

. Describe them.

7. Suppose sets A and B have the same cardinality: that is, ∃µ : A → B bijective.

(a) If σ ∈ S

is a permutation, show that µσµ

−1

∈ S

(b) Hence prove that S

and S

are isomorphic.

8. Cayley’s Theorem says that G is isomorphic to a subgroup of S

. What can you say about a

(ﬁnite) group G if G

∼

9. In Cayley’s Theorem we deﬁned ϕ(g) = L

: G → G via left-multiplication.

(a) Does the argument still work if ϕ(g) = R

: G → G is right-multiplication R

(x) = xg?

(b) (Harder) Suppose we take ϕ(g) = C

: G → G to be the function C

( z) = gxg

−1

. Does

the proof of Cayley’s Theorem work this time? Why/why not?

10. Show that the group S

is indecomposable: there are no groups G, H of order less than

for

which S

∼

G × H.

(Hint: Assuming S

is decomposable, there is only one possible decomposition. Why does this decompo-

sition make no sense?)

11. Let n ≥ 3. Prove that if σ ∈ S

commutes with every other element of S

(i.e. σρ = ρσ, ∀ρ ∈ S

)

then σ is the identity.

(Hint: suppose σ(a) = b = a and consider the cases σ(b) = a and σ(b) = a separately)

5.2 Orbits

Group theory is often applied by allowing the elements of a group to transform a set.

We’ve already

seen several examples: for instance, how rotations transform a geometric ﬁgure. The simplest general

example is built into the deﬁnition of the symmetric group and appears naturally in cycle notation.

Deﬁnition 5.10. The orbit of σ ∈ S

containing x ∈ {1, 2, . . . , n} is the set

orb

( σ) = {σ

(x) : k ∈ Z} ⊆ {1, 2, . . . , n}

Warning! Each orbit is a subset of {1, 2, . . . , n}, not of the group S

Observe also that orb

(x)

( σ) = orb

( σ) for any k ∈ Z.

Examples 5.11. If σ ∈ S

is written as a product of disjoint cycles, then the cycles are the orbits.

1. The orbits of ( 1 3 4) ∈ S

are the disjoint sets {1, 3, 4}, {2}. Note the singleton orbit {2}!

2. The orbits of ( 1 2)(4 5) ∈ S

are {1, 2}, {3}, {4, 5}.

3. Non-disjoint cycles are not orbits. For instance, σ = (1 3)(2 3 4) ∈ S

maps

1 7→ 3 7→ 4 7→ 2 7→ 1

so there is only one orbit: orb

( σ) = {1, 2, 3, 4}for any x. This comports with the result obtained

by multiplying cycles via the usual algorithm: σ = (1 2 3 4).

Given that disjoint cycle notation is so useful for reading orbits, it is natural to ask if any permutation

can be written in such a manner. The answer is yes, as we demonstrate in the next two results.

Lemma 5.12. The orbits of σ ∈ S

partition X = {1, 2, . . . , n}.

Proof. Deﬁne a relation ∼ on X = {1, 2, . . . , n} by x ∼ y ⇐⇒ y ∈ orb

( σ). We claim that this is an

equivalence relation.

Reﬂexivity x ∼ x since x = σ

(x). ✓

Symmetry x ∼ y =⇒ y = σ

(x) for some k ∈ Z. But then x = σ

−k

( y) =⇒ y ∼ x. ✓

Transitivity Suppose that x ∼ y and y ∼ z. Then y = σ

(x) and z = σ

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

The formal deﬁnition of such group actions is postponed until Chapter 8.

The relationship between equivalence relations and partitions underpins several upcoming ideas, and should be famil-

iar from a previous course. Here is a very quick review:

Given x ∈ X and a relation ∼ on X, deﬁne the set [x] := {y ∈ X : y ∼ 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 (reﬂexive, symmetric, transitive). In such a case we call [x] an equivalence class.

In our situation, [x] = orb

(σ); the Lemma simply proves that the orbits of σ are equivalence classes.

Theorem 5.13. Every permutation can be written as a product of disjoint cycles.

Proof. We formalize the algorithm from page 34. Suppose σ ∈ S

is given.

1. List the elements of orb

( σ) in the order they appear within the orbit:

orb

( σ) = {1, σ(1), σ

(1), . . .}

If this all of X = {1, . . . , n}, we are ﬁnished: σ = (1 σ (1) σ

(1) . . . σ

n−1

(1)



is an n-cycle.

2. Otherwise, let x

= min{x ∈ X : x ∈ orb

( σ)} and construct its orbit:

orb

( σ) = {x

, σ(x

), σ

), . . .}

By Lemma 5.12, orb

( σ) is disjoint with orb

( σ). If orb

( σ) ∪ orb

( σ) = X then we are done,

and σ is the product of two disjoint cycles:

σ =



1 σ(1) σ

(1) ···



σ(x

) σ

) ···



3. Otherwise, repeat. At stage k, let x

= min{x ∈ X : x ∈ orb

( σ) ∪ ··· ∪ orb

k−1

( σ)}. By

the Lemma, orb

( σ) is disjoint with orb

( σ) ∪ ··· ∪ orb

k−1

( σ). The process continues until

orb

( σ) ∪··· ∪orb

( σ) = X, which must happen eventually since X is a ﬁnite set. The result is

a product of disjoint cycles:

σ =



1 σ(1) σ

(1) ···

| {z }

orb

(σ)



σ(x

) σ

) ···

| {z }

orb

(σ)



··· ···

| {z }

orb

(σ)



···



··· ···

| {z }

orb

(σ)



The Theorem explains why our cycle algorithm always produces a product of disjoint cycles! By

convention, 1 < x

< ··· < x

, though there is no need to do this: disjoint cycles can be listed in any

order and may start with any element, e.g.,

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

Also, by convention, we delete any orbits of size 1 (1-cycles).

Orders of Elements in S

Recall (Corollary 3.13) that the order of an element σ ∈ S

is the smallest positive integer k for which

= e.

Example 5.14. If σ = (1 2 3 4 5 6) ∈ S

, then

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

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

= (1 5 3)(2 6 4)

= (1 6 5 4 3 2) σ

= e

whence the order of σ is 6. This is intuitive if we identify σ with a counter-

clockwise rotation of a regular hexagon: indeed

⟨

⟩

= {e, σ, . . . , σ

}

∼

5 6

By similarly considering a regular k-gon, it should be clear that every k-cycle has order k.

Things are trickier when you don’t have a single cycle. However, we are again saved by the discus-

sion of disjoint cycles, since disjoint cycles commute.

Examples 5.15. 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



(1 2 3)(4 5)



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

= (1 2 3)

(4 5)

= e(4 5) = (4 5)

2. Given σ = (2 5 3)(1 5 4 3) ∈ S

, we ﬁnd σ

. It is tempting to write

= (2 5 3)

(1 5 4 3)



(2 5 3)



(2 5 3)



(1 5 4 3)



= e

(2 3 5)e

= (2 3 5)

but this would be incorrect: the cycles don’t commute (2 5 3)(1 5 4 3) = (1 5 4 3)(2 5 3) so we can-

not distribute the exponent (8). If instead we ﬁrst ﬁnd σ as a product of disjoint cycles, then the

exponent does distribute and the computation is easy

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

= (1 3)

(2 5 4)

= (2 5 4)

= (2 4 5)

This approach also tells us the order of σ. Observe that

e = σ

= (1 3)

(2 5 4)

⇐⇒ k is divisible by both 2 and 3

The order if σ is therefore 6.

Corollary 5.16. The order of a permutation σ is the least common multiple of the lengths of its

disjoint cycles.

Proof. Write σ = σ

···σ

as a product of disjoint cycles, where the cycle σ

has length α

. Since

disjoint cycles commute,

= σ

···σ

Since each factor σ

permutes disjoint sets, it follows that

= e ⇐⇒ ∀j, σ

= e ⇐⇒ ∀j, α

| k (the order of an α

-cycle is α

)

The order of σ is the smallest k satisfying this condition, namely lcm(α

, . . . , α

Example 5.17. Since σ = (1 4 5)(3 6 2 7)(8 9) ∈ S

is written as a product of disjoint cycles, its order

is lcm( 3, 4, 2) = 12.

To compute σ

3465

, ﬁrst observe that 3465 = 12 ·288 + 9 (division algorithm). From this,

3465

= (σ

)

288

= σ

= (1 4 5)

(3 6 2 7)

(8 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.

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

(b) σ = (1 5 4)(2 5 4)(1 2 3 4) ∈ S

2. If σ ∈ S

is any permutation, we may deﬁne its orbits similarly: orb

( σ) = {σ

(a) : j ∈ Z}.

What are the orbits of the permutation σ : Z → Z : n 7→ n + 3?

3. Given σ = (1 3)(2 4 5) ∈ S

, ﬁnd the elements of the cyclic group

⟨

⟩

≤ S

generated by σ.

4. What is the largest possible order of an element of the group S

×Z

×V? Exhibit one.

5. What is the maximum order of an element in each of the groups S

, S

? Exhibit a

maximum order element in each case.

6. For which integers n does there exist a subgroup C

≤ S

where C

is cyclic of order n? Explain

your answer.

7. Let σ ∈ S

. For each k > 0, prove that each orbit of σ

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

(a) Compute στ and τσ in cycle notation.

(b) Find the orders of σ, τ, στ and τσ.

432

as a product of disjoint cycles.

(d) Construct the subgroup diagram of

⟨

⟩

and give a generator for each subgroup.

5.3 Transpositions & the Alternating Group

In the previous sections we viewed a permutation in terms of its orbits. An alternative approach

involves the construction of permutation from the very simplest bijections.

Deﬁnition 5.18. A 2-cycle (a

) is also known as a transposition, since it swaps two elements of

{1, 2, . . . , n} and leaves the rest untouched.

Theorem 5.19. Every σ ∈ S

(n ≥ 2) may be written as a product of transpositions.

Proof. There are many, many ways to do this. One approach is ﬁrst to write σ as a product of disjoint

cycles, before decomposing each cycle as follows:

··· a

) = (a

)(a

k−1

) ···(a

)

Just read carefully and you should be convinced this works!

Example 5.20. 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 representations as a product of transpositions are non-unique, a simple commonality may

easily be observed via a matrix notation. Consider, for instance,







1 0 0 0

0 0 0 1

0 0 1 0

0 1 0 0































and







0 0 1 0

0 0 0 1

0 1 0 0

1 0 0 0































(∗)

Each of these 4 × 4 matrices permutes the values 1, 2, 3, 4 when placed in a column vector. The

matrices plainly correspond to the transposition (2 4) and the 4-cycle (1 3 2 4) in S

Deﬁnition 5.21. 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.22. The set of n ×n permutation matrices forms a multiplicative group isomorphic to S

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

linear systems Ax = b and Cx = d with identical solutions x, differing only by row operations.

What does this have to do with transpositions? Since a transposition swaps two elements, it corre-

sponds to multiplication by a row-swapping elementary matrix; any such matrix has determinant −1.

Suppose that a permutation is written as a product of transpositions:

σ = σ

···σ

and view this as a product of matrices, taking determinant of both sides shows that

det σ = (−1)

The value of the determinant plainly depends only on whether m is even or odd. . .

Deﬁnition 5.23. A permutation σ ∈ S

is even/odd if it can be written as the product of an even/odd

number of transpositions.

By our matrix/determinant discussion, the parity of a permutation is well-deﬁned: every permuta-

tion 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 deﬁne a new subgroup of S

Deﬁnition 5.24. The alternating group A

(n ≥ 2) is the group of even permutations in S

Theorem 5.25. A

contains exactly half the elements of S

: otherwise said,

Proof. Since n ≥ 2, we have (1 2) ∈ S

. Deﬁne ϕ : S

→ S

by ϕ(σ) = (1 2)σ. Since

(1 2)(1 2)σ = σ

we see that ϕ is invertible (ϕ is its own inverse!). 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.26. We describe the smallest three alternating groups A

1. A

= {e}

∼

is trivial.

2. A

= {e, (1 3)(1 2) , (1 2) (1 3)} = {e, (1 2 3), (1 3 2)}

∼

is a cyclic group.

3. When n = 4 we obtain the ﬁrst ‘new’ group in the alternating family; a group of order 12.

= {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)}

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)

While we’ve already countered one non-abelian group of order

12, the dihedral group D

, we quickly see that A

≇ D

: all ele-

ments of A

have orders 1, 2 or 3, while D

contains a rotation (by

60°) of order 6.

By labelling faces (or vertices), A

may be visualized the 3D-

rotation group of a regular tetrahedron: can you see how each

element acts?

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. Give examples of two non-isomorphic non-abelian groups of order 360.

4. Explain why every ﬁnite group is isomorphic to a group of matrices under multiplication.

5. S

has four distinct subgroups isomorphic to the Klein four-group V; state them. Only one of

these is a subgroup of A

; which?

6. We just saw that the rotation group of a regular tetrahedron is isomorphic to A

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

octahedron is also isomorphic to S

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

(The dodecahedral and icosahedral rotation groups are both isomorphic to the alternating group A

though this is harder to visualize than the cube situation—try researching a proof )

7. (Hard) Find the entire subgroup diagram of A

8. (Hard) Prove that D

is a subgroup of A

⇐⇒ 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

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

(b) Consider the rotation ρ

= (1 2 3 ··· n) of the n-gon one step counter-clockwise. Is ρ

odd

or even, and how does this depend on n?

∈ D

is generated by ρ

. When is the set of rotations in D

subgroup of A

(d) A reﬂection µ ∈ D

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 sufﬁciently 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

which is not in A

whenever n ≡ 1 (mod 4).

6 Cosets & Factor Groups

In this chapter we partition a group in such a way that the set of subsets inherits a natural group

structure. At ﬁrst this will likely feel very abstract and difﬁcult, though it is really nothing new; it

is precisely the idea behind modular arithmetic! Examples like this are the key to understanding

abstract concepts: write everything out by hand until it becomes easy—there is no shortcut!

Example 6.1. In Z

= {0, 1, 2} the elements are really subsets [0], [1], [2] of the integers Z:

[0] = {x ∈ Z : x ≡ 0 (mod 3)} = {. . . , −3, 0, 3, 6, . . .}

[1] = {x ∈ Z : x ≡ 1 (mod 3)} = {. . . , −2, 1, 4, 7, . . .}

[2] = {x ∈ Z : x ≡ 2 (mod 3)} = {. . . , −1, 2, 5, 8, . . .}

When we write 1 +

2 = 0 ∈ Z

, we really mean

∀x ∈ [1], y ∈ [2] we have x + y ∈ [0]

Addition on Z naturally induces addition modulo 3 on the set of subsets Z

= {[0], [1], [2]}.

6.1 Cosets & Normal Subgroups

Our primary goal is to generalize the example. Start by observing that the identity element [0] is a

subgroup of Z from which the sets [1], [2] may be obtained by translation.

Deﬁnition 6.2. Let H be a subgroup of G and g ∈ G. The left coset of H containing g is

gH := {gh : h ∈ H} (x ∈ gH ⇐⇒ ∃h ∈ H such that x = gh)

This is a subset of G. The right coset of H containing g is deﬁned similarly:

Hg := {hg : h ∈ H}

The identity coset H = eH = He is the left & right coset of H containing the identity e.

H is a normal subgroup of G, written H ◁ G, if the left and right cosets containing g are always equal

H ◁ G ⇐⇒ ∀g ∈ G, gH = Hg

If G is written additively, then the left and right cosets of H containing g are instead written

g + H := {g + h : h ∈ H} H + g := {h + g : h ∈ H}

Example (6.1 cont). Let G = Z and H = [0] = 3Z. The left and right cosets of H are precisely the

elements of Z

3Z = 0 + 3Z = 3Z + 0 = [0] = {. . . , −3, 0, 3, 6, . . .}

1 + 3Z = 3Z + 1 = [1] = {. . . , −2, 1, 4, 7, . . .}

2 + 3Z = 3Z + 2 = [2] = {. . . , −1, 2, 5, 8, . . .}

Since the left and right cosets are equal, H = 3Z is a normal subgroup of Z.

The last observation is in fact general—the proof is an exercise.

Lemma 6.3. Every subgroup of an abelian group G is normal.

For non-abelian groups, most subgroups are typically not normal: see Example 6.4.2 below.

Examples 6.4. 1. Consider the subgroup H =

⟨

⟩

= {0, 2, 4} ≤ Z

. The (two) distinct cosets of H

are as follows (left = right since Z

is abelian!):

H = {0, 2, 4}



= 2 + H = 4 + H



1 + H = {1, 3, 5}



= 3 + H = 5 + H



Observe how the cosets partition Z

into equal-sized subsets.

2. By revisiting the multiplication table for D

(Example 1.2) or using cycle notation, we verify

that the left and right cosets of the subgroup H = {e, µ

} are as follows:

Left cosets Right cosets

H = µ

H = {e, µ

} H = Hµ

= {e, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

This time the left and right cosets of H are not all the same: H is not a normal subgroup of

. The partitioning observation still holds: the left cosets partition D

into three equal-sized

subsets; the right cosets also partition into equal-sized subsets, just different ones.

3. Consider a 1-dimensional subspace W ≤ R

. Each coset

u + W = {u + w : w ∈ W}

is a line parallel to W. Note again that the cosets (all lines

parallel to W) partition R

We can be more explicit in the special case when W is the y-

axis: each coset is a vertical line {(x, y) : y ∈ R} (x constant).

More generally, if W is a subspace of some vector space, then

the cosets u + W are the sets parallel to W. Only the zero coset

W = 0 + W is a subspace.

u + W

4. Recall Theorem 5.25. Generalizing the argument, we see that for any α ∈ A

and σ ∈ S

ασ even ⇐⇒ σ even ⇐⇒ σα even

Otherwise said, for any σ ∈ S

the cosets of A

containing σ are

σA

= A

σ =

(

if σ even

if σ odd

where B

is the set of odd permutations in S

. In particular, A

is a normal subgroup of S

As observed in the examples, the cosets of any subgroup H ≤ G seem to partition G.

Theorem 6.5. Let H be a subgroup of G. Then the left cosets of H partition G. Moreover,

y ∈ xH ⇐⇒ x

−1

y ∈ H ⇐⇒ xH = yH

The right cosets also partition G:

y ∈ Hx ⇐⇒ yx

−1

∈ H ⇐⇒ Hx = Hy

The blue criterion is often very easy to check. Before reading the proof, convince yourself that each of

our previous examples satisﬁes the result. When H is non-normal, note that the right cosets partition

G differently to the left cosets (e.g. Example 6.4.2).

Example 6.6. This should seem familiar when G = Z and H = nZ. Then, written additively,

a + H = b + H ⇐⇒ b −a ∈ H ⇐⇒ n | b − a ⇐⇒ a ≡ b (mod n)

The cosets of H are precisely the equivalence classes modulo n. Indeed, in a previous course, you’ve

possibly encountered the following proof in the context of modular arithmetic.

Proof. We start by verifying the ﬁrst connective.

y ∈ xH ⇐⇒ ∃h ∈ H such that y = xh ⇐⇒ x

−1

y = h ∈ H

Now deﬁne a relation ∼ on G via x ∼ y ⇐⇒ y ∈ xH. This is an equivalence relation:

Reﬂexivity: x ∼ x since x

−1

x = e ∈ H.

Symmetry: x ∼ y =⇒ x

−1

y ∈ H =⇒ (x

−1

∈ H, since H is a subgroup. But then

−1

x ∈ H =⇒ y ∼ x

Transitivity: If x ∼ y and y ∼ z then x

−1

y ∈ H and y

−1

z ∈ H. But H is closed, whence

−1

z = (x

−1

y)(y

−1

z) ∈ H =⇒ x ∼ z

The equivalence classes therefore partition G. Since x ∼ y ⇐⇒ y ∈ xH, the equivalence class of x is

indeed the left coset xH, as required.

The subgroup status of H is precisely what guarantees a partition (compare Theorem 2.19):

Reﬂexivity: H contains the identity (and is thus non-empty).

Symmetry: H satisﬁes the inverse axiom.

Transitivity: H is closed under the group operation.

When H is not a subgroup, the coset construction need not produce a partition.

Example 6.7. The subset H = {0, 1} ⊆ Z

is not a subgroup. Its left ‘cosets’ fail to partition Z

H = {0, 1}, 1 + H = {1, 2}, 2 + H = {2, 1}

We ﬁnish with a useful result for identifying when a subgroup is normal without explicitly having to

compute its cosets. The proof is left as an exercise.

Corollary 6.8. Normal subgroups are precisely those which are closed under conjugation:

H ◁ G ⇐⇒ ∀g ∈ G, ∀h ∈ H, we have ghg

−1

∈ H

Since this holds for all g, we may equivalently observe g

−1

hg ∈ H.

Exercises 6.1. Key concepts:

Left/right cosets normal subgroup (left) cosets partition group

1. Find the cosets of each subgroup: since the groups are abelian, left and right cosets are equal.

(a) 2Z ≤ Z (b) 4Z ≤ 2Z (c)

⟨

⟩

≤ Z

(d)

⟨

⟩

≤ Z

(e)

⟨

⟩

≤ Z

2. Find the cosets of H =



(0, 0), (2, 0), (0, 2), (2, 2)



≤ Z

×Z

3. Find the left and right cosets of {ρ

, ρ

} ≤ D

. Is the subgroup normal?

4. (a) Find the left and right cosets of H := {e, (1 2 3), (1 3 2)} ≤ A

. Is the subgroup normal?

(b) Repeat the question for the subgroup V := {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}

5. (a) Find the left and right cosets of H = {ρ

, δ

} ≤ D

. Is the subgroup normal?

(b) Repeat for the subgroup K = {ρ

, ρ

(Hint: Use cycle notation—e.g. Examples 5.7—or look up the Cayley table)

6. Prove Lemma 6.3: every subgroup of an abelian group is normal.

7. Suppose H is a subset of G, but not necessarily a subgroup.

(a) If H has only one element, show that the sets gH = {gh : h ∈ H} do partition G.

(b) Show that the ‘cosets’ of H = {1, 3} also partition Z

, even though H is not a subgroup.

8. Let H = {σ ∈ S

: σ(4) = 4}.

(a) Show that H is a subgroup of S

(in Chapter 8 we’ll call this the stabilizer of 4).

(b) Using Corollary 6.8, or otherwise, determine whether H is a normal subgroup of S

9. Prove Corollary 6.8.

10. (a) Suppose G = H ×K, J ◁ H and let

J = J × {e

}. Prove that

J ◁ G.

(When J = H this is often written H ◁ (H ×K). A similar result holds for K.)

(b) Explain how Example 6.4.3 ﬁts into part (a).

11. Let H, K be subgroups of G. Deﬁne ∼ on G by

a ∼ b ⇐⇒ ∃h ∈ H, k ∈ K such that a = hbk

(a) Prove that ∼ is an equivalence relation on G.

(b) Describe the elements of the equivalence class of a ∈ G; this is a double coset.

. Compute the double cosets.

6.2 Lagrange’s Theorem & Indices

We’ve been inching towards a powerful result; hopefully you’ve hypothesized this already!

Theorem 6.9 (Lagrange). In a ﬁnite group, the order of a subgroup divides the order of the group:

H ≤ G =⇒



Note that the converse is false: e.g. A

has order 12, but no subgroup of order 6 (Exercise 5.3.7). The

argument is merely a generalized version of the proof of Theorem 5.25 (

Proof. Suppose H ≤ G and ﬁx g ∈ G. The function

: H → gH : h 7→ gh

is a bijection (with inverse L

−1

: gh 7→ h). Every left coset of H therefore has the same cardinality as

H. Since the left cosets partition G (Theorem 6.5), we conclude that

= (number of left cosets of H) ·

=⇒



We could instead have proved Lagrange via the right coset partition. Here is an example of its power.

Corollary 6.10. Up to isomorphism, there is a unique group of prime order p, namely Z

Proof. Suppose G is a group with prime order p. Since p ≥ 2, we may choose some element g = e.

The order of the cyclic subgroup

⟨

⟩

≤ G satisﬁes:

•

|⟨

⟩|

≥ 2 since g = e.

•

|⟨

⟩|

= 1 or p by Lagrange, since p is prime.

We conclude that

|⟨

⟩|

= p =⇒ G =

⟨

⟩

is cyclic and thus isomorphic to Z

(Theorem 3.11).

Example 6.11. G = Z

× Z

has order 8 so its non-trivial proper subgroups can only have orders

2 or 4 and are thus isomorphic to Z

, Z

or V. These can be identiﬁed by thinking about all pos-

sible generators; V requires three elements of order 2 which we indeed have! Here is the subgroup

diagram: all proper subgroups are cyclic except V = {(0, 0), (2, 0), (0, 1), (2, 1)}.

generator order subgroup

(1, 0) or (3, 0) 4 {(0, 0), (1, 0), (2, 0), (3, 0)}

(1, 1) or (3, 1) 4 {(0, 0), (1, 1), (2, 0), (3, 1)}

(2, 0) 2 {(0, 0) , (2, 0)}

(0, 1) 2 {(0, 0) , (0, 1)}

(2, 1) 2 {(0, 0) , (2, 1)}

(0, 0) 1 {(0, 0)}

×Z

⟨

(1, 0)

⟩

⟨

(1, 1)

⟩

⟨

(0, 1)

⟩ ⟨

(2, 0)

⟩ ⟨

(2, 1)

⟩

⟨

(0, 0)

⟩

This is often misremembered as ‘the order of an element divides the order of the group,’ which is the special case when

H is a cyclic subgroup of G. Corollary 3.19 is the even more special case when G is cyclic:

⟨

⟩

≤ Z

has order

gcd( s,n)

The proof of Lagrange tells us that the number of left and right cosets of H ≤ G is identical: both equal

the quotient

. This motivates a new concept.

Deﬁnition 6.12. The index (G : H) of a subgroup H ≤ G is the cardinality of the set of (left) cosets:

(G : H) =

{gH : g ∈ G}

The index is also the cardinality of the set of right cosets (Exercise 8). If G is ﬁnite, then (G : H) =

Examples 6.13. 1. If G = Z

and H =

⟨

⟩

, then there are (G : H) =

= 2 cosets:

H =

⟨

⟩

= {0, 2, 4, . . . , 18} and 1 + H = {1, 3, 5, . . . , 19}

2. Recall (Example 2.21 & Exercise 2.2.10 the orthogonal and special orthogonal groups

(R ) = {A ∈ M

(R ) : A

A = I}, SO

(R ) = {A ∈ O

(R ) : det A = 1}

Since every orthogonal matrix has determinant ±1, it feels as if SO

(R ) should be ‘half’ of

(R ). Since both groups are inﬁnite (indeed uncountable), we need the index to conﬁrm this

intuition. Recall Theorem 6.5: given A, B ∈ O

(R ),

A SO

= B SO

(R ) ⇐⇒ B

−1

A ∈ SO

(R ) ⇐⇒ det(B

−1

A) = 1 ⇐⇒ det B = det A

We conclude that there are precisely two cosets



(R ) : SO

(R )



= 2.

Theorem 6.14. If K ≤ H ≤ G is a sequence of subgroups, then

(G : K) = (G : H)(H : K)

If G is a ﬁnite group then the result is essentially trivial:

(G : K) =

= (G : H)(H : K)

Our proof also covers inﬁnite groups and inﬁnite indices. You are strongly encouraged to work

through the following examples, which are written in the language of the proof.

Proof. Choose an element g

from each left coset of H in G and an element h

from each left coset of

K in H. Plainly

(G : H) =

}

and (H : K) =



}



We claim that the left cosets of K in G are precisely the sets (g

)K. Certainly each such is a coset; we

show that these cosets partition G, whence the collection {(g

)K} must comprise all left cosets.

• Every g ∈ G lies in some left coset of H, so ∃g

∈ G such that g ∈ g

−1

g ∈ H lies in some left coset of K in H, so ∃h

∈ H such that g

−1

g ∈ h

But then g ∈ (g

)K so that every g ∈ G lies in at least one set (g

)K.

• Suppose y ∈ g

K ∩ g

K. Since K ≤ H and the left cosets of H partition G, we have

y ∈ g

H ∩ g

H =⇒ g

= g

But then g

−1

y ∈ h

K ∩h

K =⇒ h

= h

similarly, since the left cosets of K in H partition H. It

follows that the sets (g

)K are disjoint.

Since the left cosets of K in G are given by {(g

)K}, it is immediate that

(G : K) =



}



}



}



= (G : H)(H : K)

Examples 6.15. 1. Recall Example 6.13.1: let G = Z

, H =

⟨

⟩

and K =

⟨

⟩

. Plainly

K = {0, 10} ≤ H = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18} ≤ G = {0, 1, 2, 3, . . . , 19}

so we have the required subgroup relationship. Here are the indices and cosets in each case:

• (G : H) = 2 with cosets H and 1 + H. In the language of the proof, g

= 0 and g

= 1.

• (H : K) =

= 5 cosets, with representatives h

= 0, h

= 2, h

= 4, h

= 6, h

= 8:

K = {0, 10}, 2 + K = {2, 12}, 4 + K = {4, 14}, 6 + K = {6, 16}, 8 + K = {8, 18}

• (G : K) =

= 10 = (G : H)(H : K): the cosets are

K = {0, 10}, 1 + K = {1, 11}, 2 + K = {2, 12}, . . . , 9 + K = {9, 19}

In the language of the proof these cosets all have the form (g

+ h

) + K.

2. Consider the sequence of subgroups K ≤ H ≤ S

where

K = {e, (1 2 3), (1 3 2)}

∼

and H = {σ ∈ S

: σ(4) = 4}

∼

The (H : K) =

= 2 left cosets of K in H are

K = eK = {e, (1 2 3), (1 3 2)} and ( 1 2)K = {(1 2), (2 3), (1 3)}

with representatives h

= e and h

= (1 2). The (S

: H) =

= 4 left cosets of H in S

are

H = eH = {e, (1 2 3), (1 3 2), (1 2), (2 3), (1 3)}

(1 4)H = {(1 4), (1 2 3 4), (1 3 2 4), (1 2 4), (1 4)(2 3), (1 3 4)}

(2 4)H = {(2 4), (1 4 2 3), (1 3 4 2), (1 4 2), (2 3 4), (1 3) (2 4)}

(3 4)H = {(3 4), (1 2 4 3), (1 4 3 2), (1 2)(3 4), (2 4 3), (1 4 3)}

with representatives g

= e, g

= (1 4), g

= (2 4), g

= (3 4). The eight left cosets of K in S

are

therefore

eeK = K = {e, (1 2 3), (1 3 2)} e(1 2) K = (1 2)K = {(1 2), (2 3), (1 3)}

(1 4)eK = (1 4)K = {(1 4), (1 2 3 4), (1 3 2 4)} (1 4)(1 2)K = {(1 2 4), (1 4)(2 3), (1 3 4)}

(2 4)eK = (2 4)K = {(2 4), (1 4 2 3), (1 3 4 2)} (2 4)(1 2)K = {(1 4 2), (2 3 4), (1 3) (2 4)}

(3 4)eK = (3 4)K = {(3 4), (1 2 4 3), (1 4 3 2)} (3 4)(1 2)K = {(1 2)(3 4), (2 4 3), (1 4 3)}

Exercises 6.2. Key concepts:

Lagrange’s Theorem index of a subgroup

1. Find the indices of the following subgroups:

(a)

⟨

⟩

≤ Z

(b) 6Z ≤ 2Z (c) ( Q

, ·) ≤ (Q

, ·)

2. Let G = Z

, H =

⟨

⟩

and K =

⟨

⟩

. Write out all the cosets for the three subgroup relations

K ≤ H, H ≤ G and K ≤ G, and verify the index multiplication formula.

3. Let G have order pq where p, q are both prime. Show that every proper subgroup of G is cyclic.

4. Use Lagrange’s Theorem to prove that all proper subgroups of Z

×Z

are cyclic. Hence con-

struct its subgroup diagram.

5. Find the subgroups of Z

×Z

and draw its subgroup diagram.

(Hint: At least one subgroup here is non-cyclic!)

6. Suppose (G : H) = 2. Prove that H is a normal subgroup of G.

7. Prove that {e} and G are both normal subgroups of G: what are the cosets and the indices in

each case?

(Remember that G could be inﬁnite!)

8. For each left coset gH of H in G, choose a representative g

. Prove that the function

Φ : g

H 7→ Hg

−1

deﬁnes an injective function from the set of left cosets to the set of right cosets.

(With the reverse argument this shows that the sets of left and right cosets have the same cardinality)

9. Let G = {a + b

√

2 : a, b ∈ Z}.

(a) Prove that G is a group under addition.

(b) Prove that H = {3m + 2n

√

2 : m, n ∈ Z} is a subgroup of index six in G.

(Hint: what does it mean for a + b

√

2 and c + d

√

2 to lie in the same coset of H?)

10. The sets Q and Z are both groups under addition. Show that there is precisely one coset of Z in

Q for each rational number in the interval [0, 1). Hence conclude that (Q : Z) = ℵ

is countably

inﬁnite.

6.3 Factor Groups

Given H ≤ G, we ask whether the set of left cosets {gH : g ∈ G} has a natural group structure

(inherited from that of G, rather than imposed by some external choice). To see how this might (or

might not) work, we recall some previous examples.

Examples (6.4, cont). 1. The set of (left) cosets for H =

⟨

⟩

= {0, 2, 4} ≤ Z



H, 1 + H



{0, 2, 4}, {1, 3, 5}

We use addition in Z

to deﬁne addition of cosets via

(a + H) ⊕ ( b + H) := (a + b) + H

This seems nice, though consider the computation more carefully:

(a) Choose representatives a and b in the respective cosets.

(b) Add within the original group a + b ∈ Z

If ⊕ is to make sense, the outcome (a + b) + H must be independent

of the choices in step (a). For instance, to properly conclude that

H ⊕(1 + H) = 1 + H we must check nine possibilities:

a ∈ {0, 2, 4}, b ∈ {1, 3, 5} =⇒ a + b ∈ {1, 3, 5} (modulo 6)

0 0

Addition in Z

1+H

1+H1+H

⊕

Addition in {H, 1 + H}

To save time, we verify all possibilities simultaneously. If x ∈ a + H and y ∈ b + H, then

(x + y) −(a + b) = (x −a) + (y −b) ∈ H =⇒ (x + y) + H = (a + b) + H

Addition of cosets is therefore well-deﬁned. The second table above suggests that the set of

cosets forms a group under ⊕; indeed ϕ(x) = x + H deﬁnes an isomorphism of Z

with this

so-called factor group.

2. We repeat the process for the subgroup H = {e, µ

} ≤ D

. The left cosets are

H = µ

H = {e, µ

}, ρ

H = µ

H = {ρ

, µ

}, ρ

H = µ

H = {ρ

, µ

}

As above, we attempt to deﬁne the ‘natural’ operation on the set of left cosets

aH ⊗bH := (ab)H (ab is composition/multiplication within D

)

This time there is a serious problem, as the following two calculations show:

H ⊗ρ

H = (ρ

)H = ρ

H µ

H ⊗µ

H = (µ

)H = eH = H

This is a contradiction: since ρ

H = µ

H, the results of both calculations should be the same.

The freedom of choice (part (a)) in the deﬁnition of ⊗ leads to different outcomes: the natural

operation ⊗ does not exist (and thus cannot produce a group structure!).

Well-deﬁnition of the Factor Group Structure

The examples indicate that only some subgroups H ≤ G behave nicely when trying to view the set

of left cosets as a group. But which subgroups? To answer this question, we repeat some of our

discussion abstractly. Let H be a subgroup of G and deﬁne the natural multiplication of left cosets

aH ·bH := (ab)H (∗)

This is well-deﬁned precisely when

xH = aH, yH = bH =⇒ (xy)H = (ab)H (†)

If the natural multiplication of cosets is well-deﬁned, the fact that hH = H and gH = gH for any

h ∈ H, g ∈ G, tells us that

(hg)H = gH, or equivalently g

−1

hg ∈ H (Theorem 6.5)

Since this holds for all g ∈ G and h ∈ H, Corollary 6.8 says that H is a normal subgroup of G. Not

only is the converse true also, but the resulting structure forms a group under this operation.

Theorem 6.16. Suppose H ≤ G. The natural operation (∗) deﬁnes a group structure on the set of

(left) cosets if and only if H is a normal subgroup of G.

Since this process only works when H is a normal subgroup, the preﬁx ‘left’ is irrelevant.

Deﬁnition 6.17. Given H ◁ G, the set of cosets is termed a factor group, written



(’G mod H’).

The notation for a factor group meshes with the index: if G is ﬁnite, then







= (G : H) =

Proof. The above discussion shows that well-deﬁnition of (∗) implies H ◁ G.

For the converse, assume H ◁ G, and suppose xH = aH and yH = bH. By Theorem 6.5, h := x

−1

and

h := y

−1

b are both in H. But then,

(xy)

−1

(ab) = y

−1

a)b = y

−1

hb = (y

−1

hy)

which lies in H by Corollary 6.8 (y

−1

hy ∈ H). We conclude that (xy)H = (ab)H, justifying well-

deﬁnition (†).

It remains only to check that





, ·



is a group in such cases.

Closure: Given aH, bH ∈



, we see that aH ·bH = (ab)H is also coset.

Associativity: aH · (bH · cH) = aH · (bc)H = a(bc)H. Similarly (aH · bH) · cH = (ab)cH. By the

associativity of (G, ·), these cosets are identical.

Identity: eH · aH = (ea)H = aH = (ae)H = aH ·eH, so the identity coset H is the identity in



Inverse: a

−1

H · aH = (a

−1

a)H = eH = H, etc., therefore (aH)

−1

= a

−1

Since this operation arises naturally from that on G, we use the same notation (here multiplication).

Factor Groups of Z (modular arithmetic done right)

If n is a positive integer, its integer multiples nZ =

⟨

⟩

form a (normal) subgroup of Z. The coset of

nZ containing x ∈ Z is plainly

x + nZ = {x + kn : k ∈ Z} = {y ∈ Z : y ≡ x (mod n)}

This coset is precisely what we have been calling ‘x’ in Z

! Indeed this provides the formal deﬁnition

of Z

, superseding Deﬁnition 3.4 and trivially demonstrating Theorem 3.5.

Deﬁnition 6.18. Let n ∈ N. The group Z

is the factor group



We typically drop the repeated nZ terms when calculating, recovering our familiar notation

4 + 5 = 2 ∈ Z

means (4 + 7Z ) + (5 + 7Z ) = 2 + 7Z ∈



Factor Groups of Finite Cyclic Groups

The ﬁrst example on page 53 shows that



⟨

⟩

∼

. This generalizes in an obvious manner.

Example 6.19.

⟨

⟩

= {0, 5, 10, 15} ≤ Z

has factor group



⟨

⟩



⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩

, 4 +

⟨

⟩



which is isomorphic to Z

via the isomorphism

ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

Theorem 6.20. If d | n, then



⟨

⟩

∼

If s ∤ n, Corollary 3.19 says that

⟨

⟩

⟨

⟩

where d = gcd(s, n), whence



⟨

⟩

∼

gcd(s,n)

Proof. Deﬁne ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

; we prove that this is an isomorphism.

Well-deﬁnition/injectivity:

For any x, y ∈ Z

x = y (∈ Z

) ⇐⇒ x −y ∈

⟨

⟩

⇐⇒ x +

⟨

⟩

= y +

⟨

⟩

⇐⇒ ψ(x) = ψ(y)

Surjectivity: Any coset x +

⟨

⟩

(being ψ(x)) lies in range(ψ).

Homomorphism: For any x, y ∈ Z

ψ(x + y) = (x + y) +

⟨

⟩



x +

⟨

⟩





y +

⟨

⟩



= ψ(x) + ψ(y)

Well-deﬁnition is required since the domain Z

is a set of equivalence classes. That these arguments are mutual converses

should not be a surprise: for a given function µ : A → B, compare the meanings,

• Well-deﬁnition: a = b =⇒ µ(a) = µ (b)

• Injectivity: µ(a) = µ(b) =⇒ a = b

Finite Abelian Examples

If G is ﬁnite abelian, then any subgroup H is normal and



is also a ﬁnite abelian group (exercise).

By the Fundamental Theorem (4.9), there exist positive integers m

, . . . , m

for which



∼

×··· ×Z

and m

···m







= (G : H) =

Our goal in these examples is to identify



as a direct product by ﬁnding suitable integers m

Examples 6.21. Let G = Z

×Z

. We identify the factor group



for three distinct subgroups H.

1. If H =

⟨

(0, 1)

⟩



(0, 0), (0, 1), . . . , (0, 7)



, then the factor group



has order

4·8

= 4,

and is thus isomorphic either to Z

or Z

×Z

. Here are two strategies for deciding which.

(a) Identify a ‘nice’ representative of each coset:

(x, y) + H = (v, w) + H ⇐⇒ (x, y) − (v, w) = (x −v, y −w) ∈ H ⇐⇒ x = v

Each coset therefore contains a unique element (x, 0) where x ∈ Z

, and we may write



H, (1, 0) + H, (2, 0) + H, (3, 0) + H

(b) Consider possible orders of elements (cosets): observe that



(1, 0) + H



= (k, 0) + H = H ⇐⇒ (k, 0) ∈ H ⇐⇒ 4 | k

whence



contains an element ( 1, 0) + H of order 4. Plainly



is cyclic (

∼

Either method essentially proves that ψ : Z

→



: x 7→ (x, 0) + H is an isomorphism.

2. If H =

⟨

(0, 2)

⟩



(0, 0), (0, 2), (0, 4), (0, 6)



, then







= 8: the factor group is isomor-

phic to one of Z

, Z

×Z

or Z

×Z

. We again follow our two strategies.

(a) Identify the cosets:

(x, y) + H = (v, w) + H ⇐⇒ (x −v, y −w) ∈ H ⇐⇒

(

x = v, and

y −w is even

from which the distinct cosets may be written



H, (1, 0) + H, (2, 0) + H, . . . , (3, 1) + H

(x, y) + H : x ∈ Z

, y ∈ Z

In fact ψ : Z

×Z

→



: (x, y) 7→ (x, y) + H is an isomorphism.

(b) Consider possible orders of elements:

•



has an element ( 1, 0) + H of order 4, which rules out Z

×Z

• We rule out Z

by observing that all elements of



have order dividing 4:



(x, y) + H



= (4x, 4y) + H = (0, 4y) + H = 2y



(0, 2) + H



= H

By process of elimination, we conclude that



∼

×Z

3. If H =

⟨

(2, 4)

⟩



(0, 0), (2, 4)



, then the factor group has order







= 16 and we must

consider ﬁve non-isomorphic possibilities:

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

Once again we follow our strategies:

(a) Identify the cosets. This is a little trickier than before.

• If x = 2n is even, then

(x, y) + H = (2n, y) + H = n(2, 4) + (0, y −4n) + H = (0, y −4n) + H

• If x = 2n + 1 is odd, then

(x, y) + H = (2n + 1, y) + H = n(2, 4) + (1, y −4n) + H = (1, y −4n) + H

Each coset contains precisely one representative whose ﬁrst entry is either 0 or 1; we con-

clude that the distinct cosets of H are represented by the sixteen elements

(0, 0), (0, 1), . . . , (0, 7), (1, 0), . . . , (1, 7) ((x, y) where x ∈ Z

, y ∈ Z

)

This suggests



∼

×Z

: while this is true, veriﬁcation isn’t straightforward, for the

obvious ‘function’ ψ : Z

×Z

: (x, y) 7→ (x, y) + H isn’t well-deﬁned (ψ(2, 0) = ψ(0, 0))!

(b) Consider orders of elements. The coset ( 0, 1) + H has order 8 in



, since



(0, 1) + H



= (0, k) + H = H ⇐⇒ 8 | k

This reduces our options to Z

and Z

×Z

. Moreover, any coset has order dividing 8:



(x, y) + H



= (8x, 8y) + H = (0, 0) + H

This rules out Z

, leaving Z

×Z

as the only possibility.

Strategy (b) might seem easier & quicker right now, but it has its drawbacks: for instance, you can-

not easily distinguish between (say) Z

×Z

and Z

×Z

by considering orders of elements.

Moreover, neither method suggests a suitable isomorphism: it can be checked (exercise) that

ψ : Z

×Z

→



→: (x, y) 7→ (x, y −2x) + H

does the job, though cooking up such a function requires some creativity! As we’ll see in Section 7.2,

a related approach offers a better way to tackle these problems. . .

The previous examples may have lulled you into a false sense of security! While H =

⟨

⟩

⟨

⟩

is a direct product just

like G = Z

×Z

, we cannot divide groups in the way you might expect:



≇



⟨

⟩



⟨

⟩

∼

×Z

This non-isomorphicity is obvious since







= 16 = 4 =

×Z

. See Exercise 13 for why the ﬁrst two examples seem

to ﬁt with such a ‘division’ approach.

Inﬁnite or Non-Abelian Examples

For factor groups of inﬁnite or non-abelian groups, more varied strategies may be required.

Examples 6.22. 1. Given W = {(0, y) : y ∈ R} ≤ R

, each coset (vertical line) plainly contains a

unique point (x, 0) on the x-axis. It is easily checked that ψ : R →



: x 7→ (x, 0) + W is an

isomorphism (this is a simpliﬁed version of Example 6.4.3).

2. Since (D

: R

) = 2 (n rotations and n reﬂections!), we see that



has order 2 and is thus

isomorphic to Z

. The function ψ(0) = R

, ψ(1) = {reﬂections} is an isomorphism. Note how

the factor group calculation (µ

)(µ

) = R

(↭ 1 + 1 = 0 ∈ Z

) says that the composition

of two reﬂections is a rotation.

⟨

2π

⟩

= 2πZ = {2πn : n ∈ Z} is a subgroup of (R, +). In any given coset, there is a unique

real number x such that 0 ≤ x < 2π (think ‘take the remainder modulo 2π’). It follows that



2πZ



x + 2πZ : x ∈ [0, 2π)



Moreover, the function

µ :



2πZ

→ S

: x + 2πZ 7→ e

is a well-deﬁned isomorphism. The factor group construction can be visualized as wrapping

the real line inﬁnitely many times around a circle of radius 1 (circumference 2π).

4. By Exercise 6.1.4, the Klein four-group identiﬁed as V =



e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)



is a

normal subgroup of the alternating group A

. The factor group has order (A

: V) =

= 3,

whence



∼

: can you ﬁnd an explicit isomorphism?

It is harder to check, but we’ll see later (Section 7.3) that



∼

5. Consider H =

⟨

(2, 1)

⟩

≤ Z ×Z

= G. Since G and H are inﬁnite, we cannot count cosets using

the index formula. Instead we ﬁnd a representative of each coset similarly to Example 6.21.3.

(x, y) + H =

(

(2n, y) + H = (0, y −n) + H if x = 2n is even

(2n + 1, y) + H = (1, y −n) + H if x = 2n + 1 is odd

There is a unique representative in each coset either of the form (0, z) or (1, z), where z ∈ Z

. We

conclude that there are 2 ·4 = 8 cosets. Since the factor group is abelian (Exercise 6), it must be

isomorphic to one of Z

, Z

×Z

or Z

×Z

. To identify which, compute



(x, y) + H



= (4x, 4y) + H = (0, −2x) + H = H ⇐⇒ 2 | x

Since ( 1, 0) + H has order 8, the factor group is cyclic and we have an explicit isomorphism

ψ : Z

→



: x 7→ (x, 0) + H

6. Let H =

⟨

(1, 2)

⟩

≤ Z ×Z = G. We play a similar trick to before

(x, y) + H = (0, y −2x) + (x, 2x) + H = (0, y −2x) + H

It follows that there is a unique representative of the form (0, z) in each coset and we suspect



∼

Z. Indeed it can be veriﬁed that ψ



(x, y) + H



= y −2x is an isomorphism.

Exercises 6.3. Key concepts:

Factor group



a group ⇐⇒ H ◁ G Z



identifying



1. List the cosets of the subgroup H =

⟨

⟩

in G = Z

. By mimicking the proof of Theorem 6.20,

show that ψ : Z

7→



: x 7→ x + H is a well-deﬁned homomorphism.

2. (Recall Exercise 6.1.2) If H =



(0, 0), (0, 2), (2, 0), (2, 2)



, identify the factor group

×Z



3. Identify the factor group



where H =

⟨

(2, 4)

⟩

≤ G = Z

×Z

4. (a) Let G = Z

× Z

and H =

⟨

(3, 6)

⟩

. Identify



by showing that every element of the

factor group has order at most 9 and that it contains an element of order 9.

(b) Repeat with H =

⟨

⟩

⟨

⟩

(this isn’t a trick question).

5. Let G be any group. To what groups are



{e}

and



isomorphic?

6. (a) If G is abelian and H ≤ G, prove that



is abelian.

(b) If



is abelian, can we conclude that G and/or H is abelian? Explain.

7. (See Examples 6.21) Let G = Z

×Z

. Prove that each ψ is a well-deﬁned homomorphism:

(a) H =

⟨

(0, 1)

⟩

, ψ : Z

→



: x 7→ (x, 0) + H

(b) H =

⟨

(0, 2)

⟩

, ψ : Z

×Z

→



: (x, y) 7→ (x, y) + H

⟨

(2, 4)

⟩

, ψ : Z

×Z

→



: (x, y) 7→ (x, y −2x) + H

(Bijectivity follows from the description of the cosets, though proving injectivity might be instructive.)

8. Revisit Exercise 6.2.9. The factor group



is abelian and of order 6, whence it is cyclic. Prove

this explicitly by ﬁnding a generator and thus an isomorphism ψ : Z

→



9. (a) Let G be a cyclic group with subgroup H. Prove that



is cyclic.

(b) If



is cyclic, does it follow that G is cyclic? Explain.

10. In Example 6.22.4 we saw that Z

∼



. Find an explicit isomorphism.

11. Exercise 6.1.5 showed that {ρ

, ρ

} is a normal subgroup of D

. To what well-known group is

the factor group



{ρ

, ρ

}

isomorphic? Prove your assertion.

12. (a) Identify the factor group



∼

K where K is some well-understood basic group. De-

scribe an explicit isomorphism ψ : K →



and verify that it is such.

(b) Repeat for the factor group

(R)



(R)

13. (Recall Exercise 6.1.10) Suppose G = H ×K, J ◁ H and

J = J ×{e

}. Prove that



×K.

Can you quickly verify Examples 6.21.1, 2, and 6.22.1 in this language?

14. Let H =

⟨

(2, 3)

⟩

≤ G = Z

×Z. Prove that



∼

15. Verify the claim in Example 6.22.6 that ψ



(x, y) + H



= y −2x is an isomorphism.

16. (Hard!) Let G = Z

×Z

×Z and H =

⟨

(4, 2, 3)

⟩

. Identify



as a direct product Z

×Z

(Hint: show that exactly one representative of the coset (x, y, z) + H has z either 0, 1 or 2)

7 Homomorphisms and the First Isomorphism Theorem

In this chapter we further discuss homomorphisms. Of particular importance is the relationship be-

tween normal subgroups, homomorphisms and factor groups, which will lead us (in the next section)

to a superior method for identifying factor groups.

Unless otherwise stated, all homomorphisms in this chapter are between groups.

7.1 Kernels and Images

Deﬁnition 7.1. Let ϕ : G → L be a homomorphism. The kernel and image (or range) of ϕ are the sets

ker ϕ =



g ∈ G : ϕ(g) = e



Im ϕ =



ϕ(g) : g ∈ G



The image is sometimes denoted ϕ(G). Note that ker ϕ ⊆ G while Im ϕ ⊆ L.

Examples 7.2. 1. ϕ(x) = 2x (mod 4) deﬁnes a homomorphism ϕ : Z → Z

, with

ker ϕ = {x ∈ Z : 2x ≡ 0 (mod 4) } = 2Z, Im ϕ = {0, 2}

2. The kernel should feel familiar from linear algebra: if T : V → W is a linear map between vector

spaces, then the kernel is simply the nullspace

ker T = {v ∈ V : T(v) = 0}

Moreover, if T = L

: M

(R ) → M

(R ) is left-multiplication by a matrix A, then Im T is the

column space of A.

Lemma 7.3. Let ϕ : G → L be a homomorphism. Then,

1. ϕ(e

) = e

(ϕ maps identity to identity)

2. ∀g ∈ G,



ϕ(g)



−1

= ϕ(g

−1

) (ϕ maps inverses to inverses)

3. ker ϕ ◁ G (ker ϕ is a normal subgroup of G)

4. Im ϕ ≤ L (Im ϕ is a subgroup of L)

Proof. 1 & 2 were in Exercise 2.3.6 and we leave 4 as an exercise. We prove 3 explicitly.

3. Suppose k

, k

∈ ker ϕ . Then

ϕ(k

) = ϕ(k

) ϕ(k

) = e

=⇒ k

∈ ker ϕ

ϕ(k

−1

) =



ϕ(k

)



−1

= e

=⇒ k

−1

∈ ker ϕ

It follows that ker ϕ is a subgroup of G.

To see that ker ϕ is normal, recall Corollary 6.8: if g ∈ G and k ∈ ker ϕ, then

ϕ(gkg

−1

) = ϕ(g)ϕ(k)ϕ(g)

−1

= ϕ(g)ϕ(g)

−1

= e

=⇒ gkg

−1

∈ ker ϕ

Examples 7.4. 1. For the homomorphism ϕ : Z → Z

: x 7→ 2x, we see that ker ϕ = 2Z is a normal

subgroup of Z, and Im ϕ = {0, 2} =

⟨

⟩

a subgroup of Z

2. The nullspace of a linear map T : V → W is indeed a subspace and thus a subgroup ker T ≤ V:

since V is abelian, this is a normal subgroup. Moreover, Im T is also a subspace/group of W.

3. det : GL

(R ) → R

is a homomorphism, whence we obtain a normal subgroup

ker det = SL

(R ) = {A ∈ GL

(R ) : det A = 1}◁ GL

(R )

4. ϕ : Z → Z

: x 7→ 4x (mod 20) is a homomorphism, as may be checked:

ϕ(x + y) = 4(x + y) = 4x + 4y = ϕ(x) + ϕ(y) ∈ Z

Its kernel and image are ker ϕ = 5Z ≤ Z and Im ϕ =

⟨

⟩

= {0, 4, 8, 12, 16} ≤ Z

Since every kernel is a normal subgroup, it is worth identifying the distinct cosets with a view to

describing the factor group



ker ϕ

Lemma 7.5. Let ϕ : G → L be a homomorphism. Then

ker ϕ = g

ker ϕ ⇐⇒ ϕ(g

) = ϕ(g

)

There is precisely one coset of ker ϕ for each element of Im ϕ; otherwise said (G : ker ϕ) =

Im ϕ

Proof. For all g

, g

∈ G, we have

ker ϕ = g

ker ϕ ⇐⇒ g

−1

∈ ker ϕ (Theorem 6.5)

⇐⇒ ϕ(g

−1

) = e

(Deﬁnition 7.1)

⇐⇒ ϕ(g

)

−1

ϕ(g

) = e

(Lemma 7.3)

⇐⇒ ϕ(g

) = ϕ(g

)

We’ll extend this idea shortly; for the moment we use it to aid in ﬁnding homomorphisms.

Theorem 7.6. Let ϕ : G → L be a homomorphism. If G is ﬁnite, then Im ϕ is a ﬁnite group whose

order divides that of G. The same holds for L. Otherwise said:

< ∞ =⇒

Im ϕ



and

< ∞ =⇒

Im ϕ



If both groups are ﬁnite, then

Im ϕ



gcd



Proof. If G is a ﬁnite group, then ker ϕ ≤ G is ﬁnite. Apply Lemma 7.5 to see that

Im ϕ

= (G : ker ϕ) =

ker ϕ

is a divisor of

. The second situation

Im ϕ



is Lagrange’s Theorem (6.9).

Examples 7.7. 1. If ϕ : Z

→ Z

is a homomorphism, then gcd(17, 13) = 1 =⇒

Im ϕ

= 1. Thus

Im ϕ = {0} is the trivial subgroup of Z

, and ϕ : x 7→ 0 (∀x ∈ Z

) the trivial homomorphism.

More generally, if gcd





= 1, then the trivial homomorphism ϕ : g 7→ e

is the unique

homomorphism ϕ : G → L.

2. We describe all homomorphisms ϕ : Z

→ S

Since Z

is cyclic, we need only describe what ϕ does to a generator (1) to obtain the entire

homomorphism: ϕ(x) =



ϕ(1)



. There are six choices for ϕ(1) ∈ S

, though not all will work.

The Theorem says that

Im ϕ

= 1 or 2; the only common divisors of 4 =

and 6 =

If Im ϕ has one element, we obtain the trivial homomorphism ϕ

(x) = e, ∀x ∈ Z

Im ϕ

= 2, then Im ϕ is a subgroup of order 2, of which S

has exactly three: {e, (2 3)},

{e, (1 3)}, {e, (1 2) }. This results in three further homomorphisms

(x) = (2 3)

, ϕ

(x) = (1 3)

, ϕ

(x) = (1 2)

We now turn to the general question of homomorphisms between ﬁnite cyclic groups ϕ : Z

→ Z

Two facts make this relatively simple:

1. As above, it is enough to deﬁne ϕ(1), for then ϕ(x) = ϕ(1) + ··· + ϕ(1) = ϕ(1) · x.

Im ϕ

must divide d = gcd(m, n). Since Z

has exactly one subgroup of each order dividing n

(Corollary 3.19), Im ϕ must be a subgroup of the unique subgroup of Z

of order d:

Im ϕ ≤



, . . . ,

( d −1)n



It is therefore enough to let ϕ(1) be each element of this group in turn. . .

Corollary 7.8. There are d = gcd(m, n) distinct homomorphisms ϕ : Z

→ Z

, namely

(x) =

x where k = 0, . . . , d −1

Proof. Following the above, it remains only to check that each ϕ

is a well-deﬁned function. For this,

note ﬁrst that x = y ∈ Z

⇐⇒ y = x + λm for some m ∈ Z, from which

( y) = ϕ

(x + λm) =

x + λk

n =

x = ϕ

(x) (in Z

)

where we used the fact that

is an integer.

Example 7.9. We describe all homomorphisms ϕ : Z

→ Z

Since gcd( 12, 20) = 4, we see that Im ϕ ≤

⟨

⟩

= {0, 5, 10, 15} ≤ Z

. There are four choices:

(x) = 0, ϕ

(x) = 5x, ϕ

(x) = 10x, ϕ

(x) = 15x (mod 20)

We similarly see that there are four distinct homomorphisms ψ : Z

→ Z

(x) = 0, ψ

(x) = 3x, ψ

(x) = 6x, ψ

(x) = 9x (mod 12)

Exercises 7.1. Key concepts:

Image kernels are normal subgroups (G : ker ϕ) =

Im ϕ

| |

Im ϕ



gcd





1. Check that you have a homomorphism (use Corollary 7.8) and compute its kernel and image.

(a) ϕ : Z

→ Z

deﬁned by ϕ(x) = 7x (mod 14).

(b) ϕ : Z

→ Z

deﬁned by ϕ(x) = 5x (mod 20).

2. Describe all homomorphisms between the groups:

(a) ϕ : Z

→ Z

(b) ϕ : Z → Z

→ D

(d) ϕ : Z

→ A

3. Find the kernel and image of each homomorphism:

(a) The trace of a matrix tr : M

(R ) → R :



a b

c d



7→ a + d.

(b) T : R

→ R

: x 7→

1 1 −1

0 3 −1

1 4 −2

2 5 −3

4. Explain why the map ϕ is a homomorphism and ﬁnd ker ϕ:

ϕ : S

→



{1, −1}, ·



: σ 7→

(

1 if σ even

−1 if σ odd

5. (a) Prove Part 4 of Lemma 7.3: if ϕ : G → L is a homomorphism, then Im ϕ ≤ L.

(b) If H ≤ G and ϕ : G → L a homomorphism, prove that ϕ(H) := {ϕ(h) : h ∈ H} ≤ Im ϕ.

6. Prove that the number of distinct isomorphisms ϕ : Z

→ Z

equals the cardinality of the group

of units in Z

(see Exercise 3.2.10))



{x ∈ Z

: gcd(x, n) = 1}

7. Prove that ϕ : Z

×Z

→ Z

×Z

is a well-deﬁned homomorphism if and only if there exist

integers a, b, c, d for which

ϕ(x, y) =



ax + by, cx + dy



, m | bn and n | cm

(Hint: let (a, c) = ϕ(1, 0), etc.)

8. Find all homomorphisms ϕ : Z

×Z

→ Z

×Z

. How do you know that there are no more?

9. Consider ϕ : D

→ D

: σ 7→ σ

. Show that ϕ is not a homomorphism.

7.2 The First Isomorphism Theorem

We’ve seen that all kernels of group homomorphisms are normal subgroups. In fact all normal sub-

groups are the kernel of some homomorphism.

Theorem 7.10 (Canonical Homomorphism). Let G be a group and H ◁ G. Then the function

γ : G →



deﬁned by γ(g) = gH

is a homomorphism with ker γ = H.

Proof. Since H is normal,



is a group. By the deﬁnition of multiplication in



γ(g

) γ(g

) = g

H · g

H = (g

)H = γ(g

)

whence γ is a group homomorphism. Moreover, the identity in the factor group is H, whence

ker γ = {g ∈ G : γ (g) = H} = {g ∈ G : gH = H} = H

This might feel a little sneaky and unsatisfying; we’d perhaps have preferred a homomorphism that

doesn’t have a factor group as its image! However, a companion result says that, among all homo-

morphisms with the same kernel, γ’s appearance is unavoidable.

Theorem 7.11 (1

Isomorphism Thm). Let ϕ : G → L be a homomorphism with kernel H. Then

µ :



→ Im ϕ deﬁned by µ(gH) = ϕ(g)

is an isomorphism. Otherwise said,



ker ϕ

∼

Im ϕ.

These results may be summarized in a commutative diagram: a homo-

morphism ϕ : G → L factors as ϕ = µ ◦γ, where γ is the canonical ho-

momorphism with kernel ker ϕ. This theorem is very important, and

has analogues in several other parts of mathematics: e.g., the rank–

nullity theorem from linear algebra is of close kin.

Im ϕ



ker ϕ

;;

Proof. The factor group exists since ker ϕ ◁ G (Lemma 7.3). We check the isomorphism properties:

Well-deﬁnition and Bijectivity: These are immediate from Lemma 7.5 after writing H = ker ϕ:

H = g

H ⇐⇒ ϕ(g

) = ϕ(g

) ⇐⇒ µ(g

H) = µ(g

Homomorphism: For all g

H, g

H ∈



µ(g

H · g

H) = µ(g

H) = ϕ(g

) (deﬁnition of µ)

= ϕ(g

) ϕ(g

) (ϕ is a homomorphism)

= µ(g

H)µ(g

We conclude that µ is an isomorphism.

Examples 7.12. 1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 5x (mod 20) (Example 7.9). Its

kernel and image are

ker ϕ =



x ∈ Z

: 5x ≡ 0 (mod 20)



= {0, 4, 8} =

⟨

⟩

≤ Z

Im ϕ = {5x ∈ Z

: x ∈ Z

} = {0, 5, 10, 15} =

⟨

⟩

≤ Z

The relevant factor group is



ker ϕ

{0, 4, 8}, {1, 5, 9}, {2, 6, 10}, {3, 7, 11}



⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩



The canonical homomorphism γ and the isomorphism µ are

γ(x) = x +

⟨

⟩



⟨

⟩

Im ϕ



x +

⟨

⟩



= 5x x



x +

⟨

⟩



2. (Example 6.22.1) ϕ : R → (C

, ·) : x 7→ e

is a homomorphism with

ker ϕ = {x ∈ R : e

= 1} =

⟨

2π

⟩

= 2πZ ≤ R and Im ϕ = S

is the circle group)

The canonical homomorphism γ and the isomorphism µ from the theorem are

γ : R →



⟨

2π

⟩

: x 7→ x +

⟨

2π

⟩

and µ :



⟨

2π

⟩

→ S

: x +

⟨

2π

⟩

7→ e

Note that µ is precisely the isomorphism we saw previously!

3. ϕ : Z ×Z → Z : (x, y) 7→ 3x −2y is a homomorphism. Moreover

ϕ(x, y) = (0, 0) ⇐⇒ 3x = 2y ⇐⇒ (x, y) = (2n, 3n) for some n ∈ Z

We conclude that ker ϕ =

⟨

(2, 3)

⟩

. The canonical homomorphism is

γ : Z ×Z →

Z ×Z



⟨

(2, 3)

⟩

: (x, y) 7→ (x, y) +

⟨

(2, 3)

⟩

Since ϕ is surjective (e.g., n = ϕ(n, n)), the 1

isomorphism theorem tells us that

Z ×Z



⟨

(2, 3)

⟩

∼

Z via µ



(x, y) +

⟨

(2, 3)

⟩



= 3x −2y

4. ϕ(x, y) = (x, y − x) is a well-deﬁned homomorphism ϕ : Z ×Z

→ Z

×Z

. Moreover,

ϕ(x, y) = (0, 0) ⇐⇒

(

x = 3k, and

y = x = 3k ∈ Z

whence ker ϕ =

⟨

(3, 3)

⟩



. . . , ( −6, 0), (−3, 3), (0, 0), (3, 3), (6, 0), . . .



Plainly ϕ is surjective ((m, n) = ϕ (m, n + m)); we conclude that

Z ×Z



⟨

(3, 3)

⟩

∼

×Z

via

the isomorphism µ



(x, y) +

⟨

(3, 3)

⟩

) = (x, y − x).

With a little creativity, the 1

isomorphism theorem may be applied to the identiﬁcation of factor

groups: given H ◁ G, cook up a homomorphism ϕ : G → L with ker ϕ = H, then



∼

Im ϕ. We

revisit some examples from the previous section in this context.

Examples (6.21, mk.II). Let G = Z

× Z

. For each subgroup H, we describe a homomorphism

ϕ : G → L with ker ϕ = H. While there are often several possible choices for ϕ, ours will line up with

what we saw in the original incarnations. Hopefully you’ll feel that the reasons for our choices are

independent of earlier discussions.

1. Given H =

⟨

(0, 1)

⟩

, we need a homomorphism where ϕ(0, 1) is the identity. A simple way to

do this is to ignore y and deﬁne

ϕ : Z

×Z

→ Z

: (x, y) 7→ x

This indeed has kernel ker ϕ = {(0, y) : y ∈ Z

} = H, whence



∼

Im ϕ = Z

via the isomorphism µ : (x, y) + H 7→ x.

To connect back to the original problem, note that (x, y) + H = (x, 0) + H for all x, y, whence µ

is the inverse of the isomorphism ψ : x 7→ (x, 0) + H stated previously!

2. Given H =

⟨

(0, 2)

⟩

we require ϕ(0, 2) to be the identity. This may be achieved by taking y

modulo 2 and deﬁning

ϕ : Z

×Z

→ Z

×Z

: (x, y) 7→ (x, y)

This is a well-deﬁned (ϕ(x + 4m, y + 8n) = ϕ(x, y), since 2 | 8) homomorphism with the re-

quired kernel = H. Moreover, ϕ is surjective, whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y) . Once again µ is the inverse of ψ(x, y) = (x, y) + H

in the original example.

3. For the last version, ﬁnding a homomorphism with kernel H =

⟨

(2, 4)

⟩

= {(0, 0), (2, 4)}, is

somewhat trickier. One approach is to observe that

(x, y) ∈ H ⇐⇒ x ≡ 0 (mod 2) and y − 2x ≡ 0 (mod 8)

We therefore choose

ϕ : Z

×Z

→ Z

×Z

: (x, y) 7→



x, y −2x



It is worth checking that this is well-deﬁned: the 2x in the second factor is crucial! Certainly ϕ

has the correct kernel. It is moreover surjective, e.g. (m, n) = ϕ(m, n + 2m), whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y −2x).

Exercises 7.2. Key concepts:

Canonical homomorphism γ : G →



isomorphism theorem µ :



ker ϕ

∼

Im ϕ

1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 10x.

(a) Find the kernel of and image of ϕ.

(b) List the elements of the factor group



ker ϕ



ker ϕ

→ Im ϕ.

(d) To what basic group Z

is the factor group isomorphic?

2. Repeat the previous question for the homomorphism ϕ : Z → Z

: x 7→ 8x.

3. For each function ϕ : Z ×Z → Z, ﬁnd the kernel and identify the factor group

Z ×Z



ker ϕ

(a) ϕ(x, y) = 3x + y (b) ϕ(x, y) = 2x −4y

4. (a) If a subgroup H of G = Z

×Z

has order 5, ﬁnd its elements.

(b) Show that ϕ(x, y) = (x, y) is a homomorphism ϕ : G → Z

×Z

with ker ϕ = H.

isomorphism theorem tell us about the factor group



5. Suppose G is a ﬁnite group with normal subgroup H and that ϕ : G → L is a homomorphism

with ker ϕ = H. Prove that (G : H) ≤

with equality if and only if ϕ is surjective.

6. Consider the map ϕ : Z ×Z

→ Z

×Z

deﬁned by

ϕ(x, y) =



2x + y, y



(a) Verify that ϕ is a well-deﬁned homomorphism.

(b) Compute ker ϕ and identify the factor group

Z ×Z



ker ϕ

7. Let H =

⟨

(3, 1)

⟩

≤ G = Z

×Z

. Find an explicit homomorphism ϕ : G → Z

whose kernel is

H, and thus identify the factor group



(Hint: (x, y) ∈ H = {(0, 0), (3, 1), (6, 2)} ⇐⇒ . . .)

8. Consider H =

⟨

(3, 3)

⟩

≤ G = Z

× Z

. Find a surjective homomorphism ϕ : G → Z

× Z

whose kernel is H and hence prove that



∼

×Z

9. Let ϕ : S

→ S

: z 7→ z

(a) Find the kernel of ϕ and describe the canonical homomorphism γ : S

→



ker ϕ

(b) What does the ﬁrst isomorphism theorem say about the factor group



ker ϕ



, where U

is the group of n

roots of unity.

7.3 Conjugation, Cycle Types, Centers and Automorphisms

In this section we consider an important type of homomorphism and some its consequences.

Deﬁnition 7.13. Let G be a group and x, y ∈ G. We say that y is conjugate to x if

∃g ∈ G such that y = gxg

−1

If g ∈ G is ﬁxed, then conjugation by g is the map c

: G → G : x 7→ gxg

−1

We’ve met this notion before: recall that a subgroup H is normal if and only if c

(h) ∈ H for all g ∈ G

(Corollary 6.8). It should also be familiar from linear algebra, in the context of similarity. Recall that

square matrices A, B are similar if B = MAM

−1

for some invertible M. Such matrices have the same

eigenvalues and, essentially, ‘do the same thing’ with respect to different bases. An explicit group

theory analogue of this is Theorem 7.17 below.

Lemma 7.14. Conjugation by g is a isomorphism c

: G

∼

Proof. Conjugation by g

−1

is the inverse function of c

−1



(x)



= g

−1

gxg

−1

)

−1

= x, etc.

We moreover have a homomorphism:

(xy) = g(xy)g

−1



gxg

−1



gyg

−1



= c

(x)c

( y)

Lemma 7.15. Conjugacy is an equivalence relation (x ∼ y ⇐⇒ ∃g ∈ G such that y = gxg

−1

The proof is an exercise. The equivalence classes under conjugacy are termed conjugacy classes.

Examples 7.16. 1. If G is abelian then every conjugacy class contains only one element:

x ∼ y ⇐⇒ ∃g ∈ G such that y = gxg

−1

= xgg

−1

= x

2. The smallest non-abelian group is S

has conjugacy classes

{e}, {(1 2), (1 3), (2 3)}, {(1 2 3), (1 3 2)}

This can be computed directly, but it follows immediately from. . .

Theorem 7.17. The conjugacy classes of S

are the cycle types: elements are conjugate if and only if

they have the same cycle type.

If an element σ ∈ S

is written as a product of disjoint cycles, then its cycle type is clear. For instance:

• ( 1 2 3)(4 5) has the same cycle type as (1 5 6)(2 3): we might call these 3,2-cycles.

• ( 1 2)(3 4) has a different cycle type; 2,2.

Before seeing the proof it is beneﬁcial to try an example.

Example 7.18. If ρ = (2 4 3) and σ = (1 2)(3 4) in S

, then

ρσρ

−1

= (2 4 3)(1 2)(3 4)(2 3 4) = (1 4)(2 3)

Not only does this have the same cycle type as σ , but if may be obtained simply by applying ρ to the

entries of σ!

ρσρ

−1

= (1 4)(2 3) =



ρ(1) ρ(2)



ρ(3) ρ(4)



This also tells us how to reverse the process: given 2,2-cycles σ = (1 2)(3 4)

and τ = (1 4)(2 3) simply place σ on top of τ in a table to deﬁne a suitable

ρ = (2 4 3) for which ρσρ

−1

= τ.

x 1 2 3 4

ρ(x) 1 4 2 3

The proof is nothing more than the example done abstractly!

Proof. (⇒) We consider conjugation by ρ ∈ S

. First let σ = (a

···a

) be a k-cycle and write

A = {a

, . . . , a

}, R = {ρ(a

), . . . , ρ (a

) }

Since ρ is a bijection,

= k are distinct and x ∈ R ⇐⇒ ρ

−1

(x) ∈ A. There are two cases:

If x ∈ R: Let x = ρ(a

), then

ρσρ

−1



ρ(a

)



= ρσ(a

) = ρ(a

j+1

)

where a

k+1

is understood to be a

If x ∈ R: Since ρ

−1

(x) ∈ A it is unmoved by σ, whence

ρσρ

−1

(x) = ρσ(ρ

−1

(x)) = ρρ

−1

(x) = x

We conclude that ρσρ

−1



ρ(a

) ···ρ(a

)



is also a k-cycle!

More generally, if σ = σ

···σ

is a product of disjoint cycles, then

ρσρ

−1

= (ρσ

−1

)(ρσ

−1

) ···(ρσ

−1

)

has the same cycle type as σ.

(⇐) Suppose σ = σ

···σ

and τ = τ

···τ

∈ S

have the same cycle type, written so that the

corresponding orbits have the same length. Moreover, assume we’ve included all necessary

1-cycles so that

= {1, . . . , n} =

. Deﬁne a permutation ρ by writing the orbits of σ and

τ on top each other

··· σ

ρ(x) τ

··· τ

If s

i,j

and t

i,j

are the j

elements of the orbits σ

and τ

, then

ρσρ

−1

( t

i,j

) = ρσ(s

i,j

) = ρ



i,j+1



= t

i,j+1

= τ



i,j



We conclude that ρσρ

−1

= τ, as required.

Examples 7.19. 1. The permutations σ = (1 4 5)(2 7 6) and τ = (1 6 5)(3 4 7) in S

are conjugate: the

table deﬁnes a suitable ρ.

x 1 4 5 2 7 6 3

ρ(x) 1 6 5 3 4 7 2

=⇒ ρ = (2 3)(4 6 7)

Indeed

ρσρ

−1

= (2 3)(4 6 7)(1 4 5)(2 7 6)(2 3)(4 7 6) = (1 6 5)(3 4 7) = τ

There are other possible choices of ρ; just write the orbits of σ, τ in different orders.

2. (Example 6.3.4) We’ve checked previously that V = {e, (1 2)(3 4), (1 3) (2 4), (1 4)(2 3)} is a

normal subgroup of A

. It is moreover a normal subgroup of S

: since V contains the identity

and all 2,2-cycles it is closed under conjugacy and thus a normal subgroup of both A

and S

Automorphisms

We’ve already seen that conjugation c

: G → G by a ﬁxed element is an isomorphism. We now

consider all such maps.

Deﬁnition 7.20. An automorphisms of a group G is an isomorphism of G with itself. The set of such

is denoted Aut G. The inner automorphisms are the conjugations

Inn G = {c

: G → G where c

(x) = gxg

−1

}

Example 7.21. There are four homomorphisms ϕ

: Z

→ Z

(Corollary 7.8);

(x) = 0, ϕ

(x) = x, ϕ

(x) = 2x, ϕ

(x) = 3x

of which two are automorphisms: Aut Z

= {ϕ

, ϕ

}. Observe that ϕ

is the identity function and

that ϕ

◦ ϕ

= ϕ

. The automorphisms therefore comprise a group (necessarily isomorphic to Z

)

under composition of functions.

As for conjugations, observe that for any g ∈ Z

(x) = g + x + (−g) = x

since Z

is abelian. There is only one inner automorphism of Z

, the identity function ϕ

Hunting for automorphisms can be difﬁcult. Here is a helpful observation for narrowing things

down; the proof is an exercise.

Lemma 7.22. If ϕ ∈ Aut G and x ∈ G, then the orders of x and ϕ(x) are identical.

This helps to streamline the previous example: ϕ(1) must have the same order (four) as 1 and so our

only possibilities are ϕ(1) = 1 or ϕ(1) = 3. These possibilities generate the two observed automor-

phisms.

Example 7.23. We describe all automorphisms ϕ of S

. Consider σ = (1 2) and τ = (1 2 3). Since the

order of an element is preserved by ϕ, we conclude that

ϕ(e) = e, ϕ(σ) ∈



(1 2), (1 3), (2 3)



, ϕ(τ) ∈



(1 2 3), (1 3 2)



We therefore have a maximum of six possible automorphism; it is tedious to check, but all really do

deﬁne automorphisms! Indeed all may be explicitly realized as conjugations whence Aut S

= Inn S

Here is the data; verify some of it for yourself:

element g c

( e) c

(1 2) c

(1 3) c

(2 3) c

(1 2 3) c

(1 3 2)

e e (1 2) (1 3) (2 3) (1 2 3) (1 3 2)

(1 2) e (1 2) (2 3) (1 3) (1 3 2) (1 2 3)

(1 3) e (2 3) (1 3) (1 2) (1 3 2) (1 2 3)

(2 3) e (1 3) (1 2) (2 3) (1 3 2) (1 2 3)

(1 2 3) e (2 3) (1 2) (1 3) (1 2 3) (1 3 2)

(1 3 2) e (1 3) (2 3) (1 2) (1 2 3) (1 3 2)

As the next result shows, the automorphisms again form a group under composition, in this case a

group of order 6 which is easily seen to be non-abelian: for instance

(1 2)

(1 3)

= c

(1 3 2)

= c

(1 2 3)

= c

(1 3)

(1 2)

By process of elimination, we conclude that Aut S

∼

Theorem 7.24. Aut G and Inn G are groups under composition. Moreover Inn G ◁ Aut G.

Proof. That Aut G is a group is simply the fact that composition and inverses of isomorphisms are

isomorphisms: you should already have made this argument when answering Exercise 2.3.13. By

Lemma 7.14, every conjugation is an isomorphism, and it is simple to check that c

◦ c

= c

and

−1

= c

−1

: we conclude that Inn G ⊆ Aut G.

For normality, we check that Inn G is closed under conjugation! Let τ ∈ Aut G and c

∈ Inn G. For

any x ∈ G, we have

( τc

−1

)(x) = τ





−1

(x)





(deﬁnition of c

)

= τ





−1

(x)



−1





τ(g)





−1

(x)





τ(g

−1

)



(since τ is a homomorphism)



τ(g)





τ(g)



−1

(again since τ is an homomorphism)

= c

τ(g)

(x)

We conclude that τc

−1

= c

τ(g)

∈ Inn G, from which Inn G ◁ Aut G.

The challenge in reading the proof is simply to keep track of where everything lives. To help, the inverse symbol is

colored: τ

−1

means the inverse function, whereas g

−1

means the inverse of an element in G.

Centers

We say that an element g in a group G commutes with another element x ∈ G if the order of multipli-

cation is irrelevant: i.e. if gx = xg. Otherwise said, if c

(x) = x. It natural to ask whether there are

any elements which commute with all others. There are two very simple cases:

• If G is abelian, then every element commutes with every other element!

• The identity e commutes with everything, regardless of G.

In general, the set of such elements will fall somewhere between these extremes. This subset will

turn out to be another normal subgroup of G.

Deﬁnition 7.25. The center of a group G is the subset of G which commutes with everything in G:

Z(G) := {g ∈ G : ∀h ∈ G, gh = hg}

We will prove that Z(G) ◁ G shortly. First we give a few examples; unless G is abelian, the center is

typically difﬁcult to compute, so we omit more of the details.

Examples 7.26. 1. Z(G) = G ⇐⇒ G is abelian.

2. Z( S

) = {e} if n ≥ 3. This is Exercise 11, though you should also consider Theorem 7.17.

3. Z(D

2n+1

) = {e} and Z(D

) = {e, ρ

n/2

}, where ρ

n/2

is rotation by 180

◦

. For instance, it is easy

to see in D

2n+1

that any rotation and reﬂection fail to commute.

4. Z



(R )



= {λI

: λ ∈ R

}. If you’ve done enough linear algebra, an argument is reason-

ably straightforward (Exercise 12)

Theorem 7.27. For any group G:

1. Z(G) ◁ G



Z(G)

∼

Inn G

Proof. 1. The function ϕ : G → Inn G deﬁned by ϕ(g) = c

is a homomorphism:

(x) = (gh)x(gh)

−1

= g(hxh

−1

= c

( c

(x))

=⇒ ϕ(gh) = ϕ(g)ϕ(h)

Now observe that

g ∈ ker ϕ ⇐⇒ ∀x ∈ G, c

(x) = gxg

−1

= x ⇐⇒ g ∈ Z(G)

from which ker ϕ = Z(G) is a normal subgroup of G.

2. Since ϕ is surjective, the 1

isomorphism theorem tells us that



Z(G)

∼

Im ϕ = Inn G

Exercises 7.3. Key concepts:

Conjugation conjugacy classes cycle types are conjugacy classes in S

(inner) automorphism center of a group

1. Either ﬁnd some ρ ∈ G such that ρσρ

−1

= τ, or explain why no such element exists:

(a) σ = (1 2 3), τ = (1 3 2) where G = S

(b) σ = (1 4 5 6)(2 3)(5 6), τ = (1 2 3 4)(5 6)(2 6) where G = S

2. Recall Example 7.19.1. Find another element ν = ρ for which νσν

−1

= τ.

3. Prove Lemma 7.15. Prove that the relation

x ∼ y ⇐⇒ y is conjugate to x

is an equivalence relation on any group G.

4. (a) Suppose y is conjugate to x in a group G. Prove that the orders of x and y are identical.

(b) Show that the converse to part (a) is false by exhibiting two non-conjugate elements of the

same order in some group.

5. Let H ≤ G, ﬁx a ∈ G and deﬁne the conjugate subgroup K = c

(H) = {aha

−1

: h ∈ H}.

(a) Prove that K is indeed a subgroup of G.

(b) Prove that the function ψ : H → K : h 7→ aha

−1

is an isomorphism of groups.

(H)?

(d) Let H = {e, (1 2)} ≤ S

and a = (1 2 3). Compute the conjugate subgroup K = c

(H).

6. We’ve already seen that V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} is a normal subgroup of S

(a) Show that normal subgroup is not transitive by giving an example of a normal subgroup

K ◁ V which is not normal in S

(b) How many other subgroups does S

have which are isomorphic to V? Why are none of

them normal in S



is a group of order six. Prove that

(1 2)V(1 3)V = (1 3)V(1 2)V

Hence conclude that



∼

(d) Why is it obvious that the following six left cosets are distinct.

V, (1 2) V, (1 3)V, (2 3)V, (1 2 3)V, (1 3 2)V

(Hint: Think about how none of the representatives a of the above cosets move the number 4 and

consider aV = bV ⇐⇒ b

−1

a ∈ V . . .)

(e) Deﬁne an isomorphism µ :



→ S

and prove that it is an isomorphism.

7. Prove Lemma 7.22: if ϕ ∈ Aut G and x ∈ G, then ϕ(x) has the same order as x.

8. Describe all automorphisms of the Klein four-group V.

(Hint: use the previous question!)

9. Recall Exercise 7.1.6. Explain why Aut Z

∼

(Hint: consider ϕ

(x) = kx where gcd(k, n) = 1 and map ψ : k 7→ ϕ

)

10. Let G be a group. Prove directly that Z(G) ◁ G, without using Theorem 7.27. That is:

(a) Prove that Z(G) is closed under the group operation and inverses.

(b) Prove that gZ(G) = Z(G)g for all g ∈ G.

11. Suppose n ≥ 3 and that σ ∈ Z(S

(a) By considering σ(1 2)σ

−1

, prove that {σ(1), σ(2)} = {1, 2}.

(b) If σ(1) = 2, repeat the calculation with σ(1 3)σ

−1

to obtain a contradiction.

) = {e}.

12. We identify the center of the general linear group.

The n ×n matrix A =







0 1 0 ··· ·· · 0

0 0 1 0

0 0 0 0

0 0 0 0 1

0 0 0 ··· 0







has a single one-dimensional eigenspace: Ae

= 0.

(a) Let B ∈ Z



(R )



. Use the fact that AB = BA to prove that Be

= λe

for some λ = 0.

(b) Let x ∈ R

be non-zero and X an invertible matrix for which Xe

= x (e.g. put x in the 1

column of X). Prove that Bx = λx.

, what can we conclude about B?

What is the group Z



(R )



13. (a) Prove that D

has center Z(D

) = {e, ρ

}, where ρ

is rotation by 180

◦

(b) State the cosets of Z(D

). What is the order of each? Determine whether



Z(D

)

isomorphic to Z

or to the Klein four-group V.

→ D

whose kernel is Z(D

(Hint: draw a picture and think about doubling angles of rotation and reﬂection!)

8 Group Actions

8.1 Group Actions, Fixed Sets and Isotropy Subgroups

In this ﬁnal chapter, we revisit a central idea: groups are interesting and useful often because of how

they transform sets. Recall how the symmetric group S

was deﬁned in terms of what its elements do

to the set {1, . . . , n}. This is an example of a general situation.

Deﬁnition 8.1. A group G acts

on a set X via a map · : G × X → X if,

(a) ∀x ∈ X, e ·x = x, and,

(b) ∀x ∈ X, g, h ∈ G, g ·(h ·x) = (gh) · x.

Part (b) says g 7→ g· is a homomorphism of binary structures (the functions X → X needn’t form a

group).

Examples 8.2. 1. The symmetric S

group acts on X = {1, 2, . . . , n}. As a sanity check:

(a) e(x) = x for all x ∈ {1, . . . , n}.

(b) σ



τ(x)



= (στ)(x) is composition of functions!

2. Any group G acts on itself by left multiplication. This is essentially Cayley’s Theorem (5.8). It

also acts on itself by conjugation (c

◦c

= c

is Theorem 7.24).

3. If X is the set of orientations of a regular n-gon such that one vertex is at (1, 0) and the center is

at ( 0, 0), then D

acts on X by rotations and reﬂections. Note that X has cardinality 2n.

4. Matrix groups act on vector spaces by matrix multiplication. For example the orthogonal group

(R ) can be seen to transform vectors via rotations and reﬂections.

(R ) ×R

→ R

: (A, v) 7→ Av

5. A group can act on many different sets. Here are three further actions of the orthogonal group:

i. O

(R ) acts on the set X = {1, −1} via A ·x := ( det A)x.

ii. O

(R ) acts on the set X = R

via A ·v := A(v

i + v

j) + v

iii. O

(R ) acts on the unit circle X = S

⊆ R

via matrix multiplication A ·v := Av.

We often use an action to visualize a group; in this context, some actions are better than others.

Consider the three actions of O

(R ) in part 5 above:

i. The set X is very small. Many matrices act in exactly the same way so the action is an unhelpful

means of visualizing the group.

ii. The set X feels too large. The action leaves any vertical vector untouched.

iii. The circle X = S

is large enough so that the action of distinct matrices can be distinguished

without being inefﬁciently large.

This is really a left action. There is an analogous deﬁnition of a right action. In this course, all actions will be left.

A Goldilocks action, perhaps?

These notions can be formalized.

Deﬁnition 8.3. Let G × X → X be an action.

1. The ﬁxed set of g ∈ G is the set

Fix(g) := {x ∈ X : g ·x = x} (also written X

, though we won’t do this)

2. The isotropy subgroup or stabilizer of x ∈ X is the set

Stab(x) := {g ∈ G : g ·x = x} (also written G

)

3. The action is faithful if the only element of G which ﬁxes everything is the identity. This can be

stated in two equivalent ways:

(a) Fix(g) = X ⇐⇒ g = e (b)

x∈X

Stab(x) = {e}

4. The action is transitive if any element of X may be transformed to any other:

∀x, y ∈ X, ∃g ∈ G such that y = g · x

Examples (8.2 cont). 1. The action of S

on {1, 2, . . . , n} is both faithful and transitive:

Faithful: if σ(x) = x for all x ∈ {1, 2, . . . , n}, then σ = e.

Transitive: if x = y, then the 2-cycle (x y) maps x 7→ y.

2. The action of a group on itself by left multiplication is both faithful and transitive. Conjugation

is more complex: in most situations it is neither.

3. D

acts faithfully and transitively on the orientations of the n-gon.

4. The action of O

(R ) on R

is faithful but not transitive: for instance the zero vector cannot be

transformed into any other vector so Stab(0) = O

(R ).

5. We leave these as exercises.

Lemma 8.4. For each x ∈ X, the stabilizer Stab(x) is indeed a subgroup of G.

Proof. Stab(x) is a non-empty subset of G since e ∈ Stab(x). It sufﬁcient to show that it is closed

under multiplication and inverses. Let g, h ∈ Stab(x), then

(gh) · x = g · (h · x) = g ·x = x =⇒ gh ∈ Stab(x)

Moreover

x = g · x =⇒ g

−1

· x = g

−1

·(g · x) = (g

−1

g) · x = e · x = x

Example 8.5. The dihedral group D

= {e, ρ

, ρ

, µ

} acts on the set X of vertices of an equi-

lateral triangle.

The ﬁxed sets and stabilizers for this action are as follows:

Element g Fix(g)

e {1, 2, 3}

∅

{1}

{2}

{3}

Vertex x Stab(x)

1 {e, µ

}

2 {e, µ

}

3 {e, µ

}

also acts on the set of edges of the triangle Y =



{1, 2}, {1, 3}, {2, 3}



. You needn’t write all these

out since, by the symmetry of the triangle, stabilizing an edge is equivalent to stabilizing its opposite

vertex. Still, here is the data:

Element g Fix(g)



1, 2, 3



∅



{2, 3}





{1, 3}





{1, 2}



Edge {x, y} Stab({x, y})

{1, 2} {e, µ

}

{1, 3} {e, µ

}

{2, 3} {e, µ

}

Exercises 8.1. Key concepts:

(left) action Fix(g) Stab(x) ≤ G faithful/transitive actions

1. For part 5 of Example 8.2, determine whether each action is faithful and/or transitive.

2. Let G =

⟨

⟩

≤ S

where σ = (1 2 3 4 5 6). G acts on the set X = {1, 2, 3, 4, 5, 6} in a natural way.

(a) State the ﬁxed sets and stabilizers for this action.

(b) Is the action of G faithful? Transitive?

3. Repeat the previous question when σ = (1 3)(2 4 6).

4. Mimic Example 8.5 for the actions of D

on X = {vertices} and Y = {edges} of the square.

(Use whatever notation you like; ρ, µ, δ or cycle notation)

5. Suppose G acts on X.

(a) Let Y ⊆ X and deﬁne Stab Y = {g ∈ G : ∀y ∈ Y, g ·y = y}. Prove that Stab Y is a subgroup

of G.

(b) Let G act on itself by conjugation (X = G!). What is another name for the subgroup Stab G?

6. Suppose G has a left action on X. Prove that G acts faithfully on X if and only if no two distinct

elements of G have the same action on every element.

Recall that ρ

rotates 120° counter-clockwise, that ρ

= ρ

and that µ

reﬂects across the altitude through vertex i.

8.2 Orbits & Burnside’s Formula

We ﬁrst encountered orbits in the context of the symmetric groups S

. The same idea applies to any

action.

Deﬁnition 8.6. Let G × X → X be an action. The orbit of x ∈ X under G is the set of elements into

which x may be transformed:

Gx = {g ·x : g ∈ G} ⊆ X

Examples 8.7. 1. If X = {1, 2, . . . n} and G =

⟨

⟩

≤ S

, then

Gx = {σ

(x) : k ∈ Z} = orb

( σ)

The deﬁnition of orbits therefore coincides with that seen earlier in the course.

2. A transitive action

has only one orbit.

3. If O

(R ) acts on R

by matrix multiplication, then the orbits are circles centered at the origin!

Lemma 8.8. The orbits of an action partition X.

Since this is almost identical to the corresponding result for orbits in S

(Lemma 5.12), we leave the

proof as an exercise.

Our next result is analogous to Lemma 7.5, where we counted the number of (left) cosets of ker ϕ.

Lemma 8.9. The cardinality of the orbit Gx is the index of the isotropy subgroup Stab(x):



G : Stab(x)



Proof. Observe that

g · x = h ·x ⇐⇒ h

−1

g · x = x ⇐⇒ h

−1

g ∈ Stab(x) ⇐⇒ g Stab(x) = h Stab(x)

The contrapositive says that distinct elements of the orbit Gx correspond to distinct left cosets.

Example 8.10. Let σ = (1 4)(2 7 3) ∈ S

. Consider X = {1, 2, 3, 4, 5, 6, 7} under the action of the

cyclic group G =

⟨

⟩

. The orbits are precisely the disjoint cycles: {1, 4}, {2, 3, 7}, {5}, {6}. Observe

that G has six elements:

e, σ = (1 4)(2 7 3), σ

= (2 3 7), σ

= (1 4), σ

= (2 7 3), σ

= (1 4)(2 3 7)

The Lemma is easily veriﬁable: for instance if x = 3,

Stab(x) = {τ ∈ G : τ(3) = 3} = {σ

: σ

(3) = 3} = {e, σ

}

=⇒ (G : Stab(x)) =

= 3 =

{2, 3, 7}

Unhelpfully, we now have two distinct meanings of transitive; one for equivalence relations and one for actions.

It is often useful to count the number of orbits of an action. For ﬁnite actions, this turns out to be

possible in two different ways.

Theorem 8.11 (Burnside’s formula). Let G be a ﬁnite group acting on a ﬁnite set X. Then the number

of orbits in X under G satisﬁes

# orbits =

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

Proof. By Lemma 8.9, It follows that

∑

x∈X

Stab(x)

∑

x∈X

Stab(x)

∑

x∈X

(G : Stab(x))

∑

x∈X

(∗)

Consider a ﬁxed orbit Gy. Since

for each x ∈ Gy, we see that

∑

x∈Gy

= 1

The sum (∗) therefore counts 1 for each distinct orbit in X and therefore returns the number of orbits.

For the second equality, observe that

S = {(g, x) ∈ G × X : g ·x = x}

has cardinality

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

Example (8.10 cont). When G =

⟨

⟩

⟨

(1 4)(2 7 3)

⟩

acts on X = {1, 2, 3, 4, 5, 6, 7}, the stabilizers

and ﬁxed sets are as follows:

x ∈ X Stab(x)

1 {e, σ

, σ

}

2 {e, σ

}

3 {e, σ

}

4 {e, σ

, σ

}

5 G = {e, σ, σ

, σ

}

6 G

7 {e, σ

}

g ∈ G Fix(g)

e X = {1, 2, 3, 4, 5, 6, 7}

σ {5, 6}

{1, 4, 5, 6}

{2, 3, 5, 6, 7}

{1, 4, 5, 6}

{5, 6}

Burnside’s formula just sums the number of elements in all of the subsets in the right column of each

table:

4 = # orbits =

∑

x∈X

Stab(x)

(3 + 2 + 2 + 3 + 6 + 6 + 2)

∑

g∈G

Fix(g)

(7 + 2 + 4 + 5 + 4 + 2)

One reason to count the number of orbits of an action is that we often want to consider objects as

equivalent if they differ by the action of some simple group.

Example 8.12. A child’s toy consists of a wooden equilateral triangle where the edges are to be

painted using any choice of colors from the rainbow. How many distinct toys could we create?

There are two problems: we need to describe the variety of possible toys, and we need to know what

distinct means!

We use group actions to address both problems:

• A toy may be considered as a subset of X = {painted triangles} = {ordered color triples}.

Since there are 7 choices for the color of each edge, we see that

= 7

= 343 is a large set!

• Two toys are equivalent if they differ by a rotation in

3-dimensions. This amount to the natural action of

on X: for instance

·(red,green,violet) = (violet,red,green)

The number of orbits is the number of distinct toys, which we may compute using Burnside. Since

it would be time consuming to compute the stabilizer of each element of X, we use the ﬁxed set

approach.

• Identity e: Plainly Fix(e) = X, since e leaves every coloring unchanged.

• Rotations ρ

, ρ

: If a color-scheme is ﬁxed by ρ

, then all pairs of adjacent edges must be the

same color. The only color-schemes ﬁxed by ρ

are those where all sides have the same color,

whence

Fix(ρ

)

= 7.

• Reﬂections µ

, µ

: Since µ

swaps two edges, anything in its ﬁxed set must have these edges

the same. We have 7 choices for the color of the switched edges, and an independent choice of

7 colors for the other edge, whence



Fix(µ

)



= 7

= 49.

The number of distinct toys is therefore

# orbits =

∑

σ∈D

Fix(σ)

+ 7 + 7 + 7

+ 7

)

(49 + 1 + 1 + 7 + 7 + 7) = 84

The question was a little tricky because we are allowed multiple sides to have the same color. A

simpler version would restrict to the situation where all sides had to be different colors. In this case

acts on a set of color schemes with cardinality

= 7 ·6 ·5 = 210. Moreover, only the identity

element has a non-empty ﬁxed set; in this situation the number of distinct toys would be

# orbits =

∑

σ∈D

Fix(g)

(210 + 0 + ··· + 0) =

210

= 35

Of course you could answer these questions by pure combinatorics without any resort to group

theory!

Dice-rolling for Geeks!

Games like Dungeons & Dragons make use of several differently

shaped dice: rather than simply using the standard 6-sided cubic die,

situations might require rolling, say, a 4-sided tetrahedral die or a 20-

sided icosahedral die.

Since dice are designed for rolling, we consider two dice to be the

same if one can be rotated into the other. Play with the two tetrahedral

dice on the right; you should be convinced that you cannot rotate one

to make the other so these dice are distinct.

It is not difﬁcult to see that, up to rotations, these are the only tetrahe-

dral dice just by counting!

• Place face 4 on the table.

• When looking from above, the remaining faces are numbered 1,

2, 3 either clockwise or counter-clockwise.

For larger dice, this approach is not practical! However, with a little

thinking about symmetry groups, Burnside’s formula will ride to the

rescue.

Suppose a regular polyhedron has f faces, each with n sides.

• The faces may be labelled 1 thorough f in f ! distinct ways: the set of distinct labellings is X.

• We may rotate the polyhedron so that any face is mapped to any other, in any orientation. It

follows that the rotation group G has f n elements.

• Each non-identity element of the rotation group moves at least one face, whence

Fix(g)

(

X if g = e

∅ if g = e

• The number of distinct dice for a regular polyhedron is therefore

# orbits =

Fix(e)

f !

f n

( f − 1)!

We don’t need to know what the rotation group is, only its order. For completeness, here are all

the possibilities for the regular platonic solids.

Polyhedron f n Rotation Group # distinct dice

Tetrahedron 4 3 A

Cube 6 4 S

Octahedron 8 3 S

1,680

Dodecahedron 12 5 A

7,983,360

Icosahedron 20 3 A

40,548,366,802,944,000

Subgroups of Prime Order & the Class Equation

We ﬁnish with a taste of where group theory traditionally goes next.

Suppose G acts on a ﬁnite set X, that x

. . . , x

are representatives of the distinct orbits and that

, . . . , x

enumerate the 1-element orbits (Stab(x

) = G ⇐⇒ j ≤ s). Then, by counting elements,

= s +

∑

j=s+1



= s +

∑

j=s+1



G : Stab(x

)



When G acts on itself by conjugation, the 1-element orbits together comprise the center of G and we

obtain the class equation:

Z(G)

∑

j=s+1



G : Stab(x

)



Example 8.13. Since the conjugacy classes in S

are the cycle types, the class equation reads

24 =

{e}

2-cycles

3-cycles

4-cycles

2,2-cycles

= 1 + 6 + 8 + 6 + 3

Here is an example of how the class equation may be applied.

Lemma 8.14. Suppose G is a non-abelian group whose order is divisible by a prime p. Then G has a

proper subgroup whose order is divisible by p.

Proof. Since G is non-abelian, Z(G) is a proper subgroup. Let x be any element not in the center. Then

2 ≤

Stab(x)

=⇒ Stab(x) is a proper subgroup of G

If p divides

Stab(x)

, then we’re done. If not, then p divides



G : Stab(x)



. If this holds for

all non-trivial orbits, the class equation says that

Z(G)

is divisible by p.

Theorem 8.15 (Cauchy). If a prime p divides

, then G contains a subgroup/element of order p.

Proof. 1. A proof when G is abelian is in Exercise 9.

2. If G is non-abelian, apply the Lemma. If the resulting subgroup is abelian, part 1 ﬁnishes

things off. Otherwise repeat. If we never reached an abelian subgroup, then we’d have an

inﬁnite sequence of proper subgroups and thus a decreasing sequence of positive integers;

contradiction.

Haven’t we done this already?! Exercise 4.13 appears to cover abelian groups, but this depends on

the Fundamental Theorem (4.9) whose proof requires Cauchy for abelian groups. . . ! Indeed Cauchy’s

Theorem may be extended to prove that if p

divides G, then G has a subgroup of order p

. This is

the beginning of the Sylow theory of p-subgroups which has applications to group classiﬁcation and

the existence of sequences of normal subgroups.

Exercises 8.2. Key concepts:

Orbits of G partition X Cardinality of orbit

= (G : Stab(x) ) divides

Burnside’s formula for counting number of orbits

1. Determine the orbits of G =

⟨

⟩

on X = {1, 2, 3, 4, 5, 6} for each of Exercises 8.1.2 and 3. In both

cases verify Burnside’s formula.

2. Revisit Example 8.12. How may distinct toys may be created if:

(a) A maximum of two colors can be used?

(b) Exactly two colors must be used?

3. Prove Lemma 8.8: the orbits of a left action partition X.

4. A 10-sided die is shaped so that all faces are congruent kites: ﬁve faces are arranged around the

north pole and ﬁve around the south, so that each face is adjacent to four others.

(a) Argue that the group of rotational symmetries of such a die has ten elements.

(In fact it is non-abelian and is therefore isomorphic to D

(b) Use Burnside’s formula to determine how many distinct 10-sided dice may be produced.

5. A soccer ball is constructed from 20 regular hexagons and 12 regular

pentagons as in the picture.

Suppose the 20 hexagonal patches are all to have different colors, as are

the 12 pentagonal patches. How many distinct balls may be produced?

6. The faces of a cuboid measuring 1 ×1 ×2 in is to be painted using (at

most) two colors. Up to equivalence by rotations, how many ways can

this be done?

7. Repeat the previous question for a regular tetrahedron.

8. Suppose G is a ﬁnite group with order p

where p is a prime. If x ∈ G lies in a conjugacy

class with at least 2 elements, prove that the order of Stab(x) divides p

n−1

. Now use the class

equation to prove that p divides the order of the center Z(G).

9. We prove the abelian part of Cauchy’s Theorem by induction on the order n =

(a) Explain why the base case n =

= 2 is true.

(b) Fix n ≥ 3 and assume p divides the order n of some abelian group G. For the induction

hypothesis, assume that if

< n and p



, then H has a subgroup of order p.

• Let x ∈ G be a non-identity element with order m =

|⟨

⟩|

(necessarily m ≥ 2).

• Choose any prime q dividing m, deﬁne y := x

m/q

and let H :=

⟨

⟩

i. What is the order of H? Explain why are we done if q = p.

ii. If q = p, use the induction hypothesis to explain why there exists a coset zH ∈



order p. Now prove that z

has order p in G.