Math 120A — Introduction to Group Theory

Neil Donaldson

Fall 2023

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

To be abstract means to remove context and application. A large part of modern mathematics in-

volves studying patterns and symmetries (often those observed in the real world) from an abstract

viewpoint so as to see commonalities between structures in seemingly distinct places.

One reason to study groups is that they are relatively simple: a set and a single operation which

together satisfy a few basic properties. Indeed you’ve been using this structure almost since Kinder-

garten!

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

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

Better reasons to study groups are their ubiquity and multitudinous

applications. Here are just a few of the places where the language of group theory is essential.

Permutations The original use of group was to describe the ways in which a set could be reordered.

Understanding permutations is of crucial importance to many areas of mathematics, particu-

larly combinatorics, probability and Galois Theory: this last, the crown jewel of undergraduate

algebra, develops a deep relationship between the solvability of a polynomial and the permuta-

tion group of its set of roots.

Geometry Figures in Euclidean geometry (e.g. triangles) are congruent if one may be transformed to

the other by an element of the Euclidean group (translations, rotations & reﬂections). More general

geometries are also be described by their groups of symmetries. Geometric properties may also

be encoded by various groups: for example, the number of holes in an object (a sphere has

none, a torus one, etc.) is related to the structure of its fundamental group.

Chemistry Group Theory may be applied to describe the symmetries of molecules and of crystalline

substances.

Physics Materials science sees group theory similarly to chemistry. Modern theories of the nature of

the universe and fundamental particles/forces (e.g. gauge/string theories) also rely heavily on

groups.

Of course, the best reason to study groups is simply that they’re fun!

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

future 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 of the set {1, 2, 3}. By considering compositions

of these symmetries, we shall see that the sets of such are essentially identical.

Permutations of {1, 2, 3} These can be written as functions using cycle notation.

For instance, the

cycle (1 2) is the function which swaps 1 and 2 and leaves 3 alone, while (1 2 3) permutes all three

numbers:

(1 2) :











1 7→ 2

2 7→ 1

3 7→ 3

and (123) :











1 7→ 2

2 7→ 3

3 7→ 1

It is not hard to convince yourself that there are six distinct permutations of {1, 2, 3}; for brevity, we

use the symbols e, µ

, µ

, ρ

Identity: leave everything alone Swap two numbers Permute all three

e = () µ

= (2 3) ρ

= (1 2 3)

= (1 3) ρ

= (1 3 2)

= (1 2)

Since the 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

◦ρ

= µ

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 ρ

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

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

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 the i

vertex.

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

structure of their compositions are identical.

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

thing! There is a qualitative difference between the rotations

, ρ

and the reﬂections µ

, µ

of the triangle: since reﬂections

ﬂip the triangle upside down, it is completely obvious that com-

position 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

are sometimes revealed.

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

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

is the dihedral group of order six (symmetries of the equilateral triangle)

The formal way to say that the resulting group structures are identical is to call them isomorphic,

and

we’ll write S

∼

As we progress, we’ll see more examples of such relationships between seemingly different struc-

tures. In the ﬁrst half of the course (Chapters 2–5) the primary goal is to become familiar with the

most commonly encountered examples of groups so that they may quickly be recognized, even when

well-disguised. The second half of the course is more abstract, with relatively few new examples of

groups; comfort with the standard examples will be crucial in making sense of this harder material.

We will explain the term isomorphic more concretely in Section 2.3 and revisit both examples in Chapter 5. For the

present, observe the use of the congruence symbol

∼

; given your understanding of congruent objects in geometry, think

about why the use of this symbol isn’t unreasonable.

2 Groups: Axioms and Basic Examples

In this chapter we deﬁne our main objects of study and introduce some of the common language

that will be used throughout the course. Most of the examples are very simple and many should be

familiar. We start by individually considering the axioms of a group.

2.1 The Axioms of a Group

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 the abstract, including most theorems, we typically drop the symbol and use juxtaposition (x ∗y =

xy). In explicit examples this might be a bad idea, say if ∗ is addition. . .

Examples 2.2. 1. Addition (+) is a binary operation on the set of integers Z: explicitly,

Given x, y ∈ Z, we know that x + y ∈ Z

This isn’t a claim you can prove since it is really part of the deﬁnition of addition on the integers.

2. Subtraction (−) is not a binary operation on the positive integers N = {1, 2, 3, 4, . . .}. This you

can prove; to show that (†) is false, simply exhibit a counter-example

1 −7 = −6 ∈ N (∃x, y ∈ N such that x −y ∈ N)

On the integers, however, subtraction is a binary operation.

3. It can be convenient to use a table to represent a binary operation on a

small set; for instance the example describes an operation on a set of three

elements {e, a, b}. Read the left column ﬁrst, then the top row; thus

ab = e

∗ e a b

e e a b

a a e e

b b e a

We’ll continue checking these examples for each of the group axioms.

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

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

Associativity means that the expression xyz has unambiguous meaning, as does the usual exponen-

tial/power notation shorthand, e.g. x

= x ···x.

Examples (ver. II). 1. Addition is associative: x + (y + z) = (x + y) + z for any integers.

2. ( Z, −) is non-associative: e.g. (1 −1) −2 = −2 = 2 = 1 − (1 −2).



{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 (ver. III). 1. Addition has identity 0: that is 0 + x = x + 0 = x for any integer x.

2. ( Z, −) does not have an identity: e.g. if e − x = x, then e = −2x depends on x!



{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 3,) we list it ﬁrst. Indeed, we can always

list it ﬁrst, since. . .

Lemma 2.5 (Uniqueness of identity). If a binary structure (G, ∗) has an identity, then it is unique.

It is now legitimate to refer to the identity e using the deﬁnite article. Uniqueness proofs in mathematics

typically follow a pattern: suppose there are two such objects and show that they are identical.

Proof. Suppose e, f ∈ G are identities. Then

e f =

(

f since e is an identity

e since f is an identity

We conclude that f = e.

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

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

xy = yx = e

Examples (ver. IV). 1. Every integer x has an inverse under addition: x + (−x) = (−x) + x = 0.

2. Since ( Z, −) has no identity, the question of inverses makes no sense.

3. Since e

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

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

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

We simply assemble the pieces to obtain our main deﬁnition.

Deﬁnition 2.9 (Group axioms). A group is a binary structure (G, ∗) satisfying the associativity and

identity axioms, and for which all elements have inverses. This is summarized by the mnemonic

Closure, Associativity, Identity, Inverse

The order of G is its cardinality

. Moreover, G abelian if ∗ is commutative.

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

group (the oper-

ation is addition). The same observations show that (Q, +), (R, +) and (C, +) are abelian groups.

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

forms an abelian group under multiplication.

Closure If x, y = 0, then xy = 0

Associativity ∀x, y, z, x(yz) = (xy)z

Identity If x = 0, then 1 · x = x ·1 = x, so 1 ∈ R

is an identity

Inverse Given x = 0, observe that x

−1

is an inverse: x ·

· x = 1

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

Similarly, (Q

, ·) and (C

, ·) are abelian groups.

2. The even integers 2Z = {2z : z ∈ Z} form an abelian group under addition.

3. The odd integers 1 + 2Z = {1 + 2n : n ∈ Z} do not form a group under addition since they are

not closed: for instance, 1 + 1 = 2 ∈ 1 + 2Z.

4. Every vector space is an abelian group under addition.

5. ( R, ·) is not a group, since 0 has no multiplicative inverse. Similarly (Q, ·), (C, ·) are not groups.

6. Groups of small order may be depicted in Cayley tables

Groups of orders 1, 2 and 3 are shown: you should check

that these are groups.

Note the magic square property: each row/column con-

tains every element exactly once (see Exercise 13).

∗ e

e e

∗ e a

e e a

a a e

∗ e a b

e e a b

a a b e

b b e a

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.

Englishman Arthur Cayley (1821–1895) was a pioneer of group theory. Abelian similarly honors the Norwegian math-

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

−1

(xy) = y

−1

x) y = y

−1

ey = y

−1

y = e

Thus y

−1

is an inverse of xy. Since inverses are unique, (Lemma 2.7) we are done.

Associativity and Functional Composition

Theorem 2.12. Let X be a set. Composition of functions f : X → X is associative.

Proof. Let f , g, h : X → X. We have equality ( f ◦ g) ◦ h = f ◦ (g ◦h) if and only if these functions do

the same thing to every element x ∈ X. But this is trivial:



( f ◦ g) ◦ h



(x) = ( f ◦ g)



h(x)



= f



g(h(x))



and,



f ◦(g ◦h)



(x) = f



(g ◦h)(x)



= f



g(h(x))



It follows that ◦ is associative.

By viewing rotations and reﬂections as functions, the theorem veriﬁes associativity for the following.

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

The symmetries (rotations and reﬂections) of a geometric ﬁgure form a group under composition.

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

Deﬁnition 2.14. 1. If ρ

is rotation counter-clockwise by

2πk

radians, then R

= {ρ

, . . . , ρ

n−1

} is the

rotation group of a regular n-gon.

2. The dihedral group D

is the symmetry group of a regular n-gon.

3. The Klein four-group

(denoted V) is the symmetry group of a rectangle (or a rhombus), where

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

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}

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

det AB = det A det B

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







1 0

0 1







This group is non-abelian (when n ≥ 2).

Look again at part 3 of Theorem 2.11: seem familiar?

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

Group (closure, associativity, identity, inverse) Commutativity/abelian Cayley table V 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

In mathematics, the preﬁx sub- 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 is a group

with respect to the same binary operation; we write H ≤ G.

A subgroup H is a proper subgroup if H = G; this is written H < G.

The trivial subgroup is the 1-element set {e}; all other subgroups are non-trivial.

Examples 2.18. The following are immediate from the 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 you don’t have to check all the group axioms to see that a subset is a subgroup.

Theorem 2.19 (Subgroup criterion). Let G be a group. A non-empty subset H ⊆ G is a subgroup if

and only if it is closed under the group operation and inverses. Otherwise said,

∀h, k ∈ H, hk ∈ H and h

−1

∈ H

Proof. (⇒) H is a group and therefore 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 as-

sumption, 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 the above examples 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ﬂec-

tions:

• ρ

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

• The µ

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

indicated in the pictures below.

Now draw two equilateral triangles inside the hexagon.

Each of the six symmetries of the equilateral triangle is also a sym-

metry of the hexagon! It follows that the symmetry group D

the triangle is a subgroup of D

in two different ways:

{e, ρ

, ρ

, µ

} < D

and {e, ρ

, ρ

, µ

} < D

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. Explain the relationship between positive integers m and n whenever (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 the following sets of matrices are groups under multiplication.

(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) Symplectic group: Sp

(R ) =



A ∈ M

(R ) : A

JA = J



, where J =



0 I

−I



is a block

matrix and I

the n ×n identity matrix.

(e) 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. The set Q

= {±1, ±i, ±j, ±k} forms a group of order eight under ‘multiplication’ subject to

the following properties:

• 1 is the identity.

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

• (−1)

= 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. We describe such comparisons using 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 this course (certainly after this chapter), the 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

)

This shows that 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: these 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? It is because isomorphic groups have exactly the same struc-

ture; one is simply a relabelled version of the other!

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

Deﬁnition: Deﬁne ϕ : G → H (if necessary). As we’ll see starting in Chapter 3, if G is a set

of equivalence classes you might need to check that ϕ is well-deﬁned.

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

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

Surjectivity/onto: Check range ϕ = H. Equivalently ∀h ∈ H, ∃g ∈ G such that h = ϕ(g).

The last three steps can be done in any order. Injectivity/surjectivity might also be combined by

exhibiting an explicit inverse function ϕ

−1

: H → G.

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

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

In the last step we essentially observed that the inverse function is ϕ

−1

( z) =

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

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!

ϕ(x + y) = e

x+y

= e

= ϕ(x)ϕ(y)

Bijectivity: ϕ

−1

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

Non-isomorphicity & Structural Properties

Unless you have very small sets, you cannot realistically test every function ϕ : G → H to see that

structures are non-isomorphic! Instead we have to be a little more cunning.

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

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

structural properties.

The following is a non-exhaustive list of structural properties: we’ll check a few in Exercise 6.

Cardinality/order: Since G and H are bijectively paired, their cardinalities are the same.

Commutativity & Associativity: For instance, if ∗ is commutative, then

∀x, y ∈ G, ϕ(x) ⋆ ϕ(y) = ϕ(x ∗y) = ϕ(y ∗ x) = ϕ(y) ⋆ ϕ(x)

Since ϕ is bijective, this says that ⋆ is commutative on H.

Identities & Inverses: For instance, if G has identity e, then ϕ(e) is the identity for H.

Solutions to equations: Related equations in G and H have the same number of solutions: e.g.

x ∗x = x ⇐⇒ ϕ(x) ⋆ ϕ(x) = ϕ(x)

The equations x ∗x = x and z ⋆ z = z therefore have the same number of solutions.

Being a group If G is a group, so also is H.

Examples 2.28. 1. The binary structures (N

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

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

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 turn a bijection into an isomorphism by imposing 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 structure from G to H:

w ⋆ z := ϕ



−1

( w) ∗ϕ

−1

( z)



Example 2.29. ϕ(x) = x

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

x ∗y := ϕ

−1



ϕ(x) + ϕ(y)



= ϕ

−1

+ y

+ 16) =

+ y

+ 8

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

−1

an isomorphism, it follows that (R, ∗) is also an abelian

group. Moreover, its identity must be

−1

(0) =

√

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

note that if ({e, a}, ∗) is a group with identity e, then its Cayley table must be as shown

(recall Example 2.10.6). This might be summarized by the phrase:

∗ e a

e e a

a a e

Up to isomorphism, there is a unique group of order two.

More precisely: if G is any group of order two, then there exists an isomorphism ϕ : {e, a} → G. The

expression ‘up to isomorphism’ is essential; without it, the sentence is false, since there are inﬁnitely

many distinct groups of order two!

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, ·)

∼

(Z, max(a, b))

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

morphism. 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 except the zero matrix) forms a group under matrix multiplica-

tion.



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 of groups whose complete structure can be easily described. The

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

Examples 3.1. 1. The group of integers (Z, +) is generated by 1. Otherwise said, all integers may be

produced simply by combining 1 with itself using only the group operation (+) and inverses

(−). Indeed, if n is a positive integer, then

n = 1 + 1 + ··· + 1

The inverse operation produces −n, and the identity is 0 = 1 + (−1).

2. Recall the group R

= {ρ

, . . . , ρ

n−1

} of rotations of a regular n-gon (Deﬁnition 2.14). Since

= ρ

, the group is generated by ρ

, the ‘1-step’ counter-clockwise rotation by

2π

radians.

We formalize this idea by considering a subset of a group G that is produced starting with a single

element g. Since this is abstract, we follow the convention of writing G multiplicatively.

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

⟨

⟩

:= {g

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

−1

, e, g, g

, . . .}

is a subgroup of G.

Proof. Non-emptiness: Plainly e ∈

⟨

⟩

Closure: Every element of

⟨

⟩

has the form g

for some k ∈ Z. The required condition is

nothing more than standard exponential notation:

· g

= g

k+l

∈

⟨

⟩

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

)

−1

= g

−k

∈

⟨

⟩

Deﬁnition 3.3 (Cyclic group). The subgroup

⟨

⟩

is the cyclic subgroup of G generated by g.

The order of an element g ∈ G is the order (cardinality)

|⟨

⟩|

of the subgroup generated by g.

G is a cyclic group if ∃g ∈ G such that G =

⟨

⟩

: we call g a generator of G.

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

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

Examples (3.1 cont). 1. Z =

⟨

⟩

⟨

−1

⟩

is generated by either 1 or −1. Note that this is an additive

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

⟨

⟩

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

2. R

⟨

⟩

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

Modular Arithmetic

It is now time we introduced the most commonly encountered family of ﬁnite groups.

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

the set of equivalence classes modulo n.

It is most common to denote the elements of Z

as remainders,

that is

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

You should be familiar with addition and multiplication modulo n, and you have several options for

notation. For instance, here is a calculation in Z

written four ways:

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

(b) Equivalence classes: [4]

+ [2]

= [6]

= [1]

2 = 6 = 1.

(d) Drop almost all notation: 4 + 2 = 6 = 1 in Z

Warning! If you choose version (d), you must make clear

that you are working in Z

. If the distinction between num-

bers and equivalence classes is confusing, use one of the

other notations!

[0]

= {. . . , −5, 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, abelian group under addition modulo n.

A direct rigorous proof is tedious right now. It will come for free in Chapter 6 when we properly

deﬁne Z

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

is cyclic since it is generated by 1.

Examples 3.6. Here are the Cayley tables for Z

, Z

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

Compare these to Example 2.10.6.

It is crucial to appreciate that these aren’t numbers but equivalence classes. Thus Z



[0], [1], . . . , [n −1]



where the

equivalence class [x] of x ∈ Z is the set of integers with the same remainder as x:

[x] = {z ∈ Z : x ≡ z (mod n)} = {. . . , x −n, x, x + n, x + 2n . . .} = {x + kn : k ∈ Z} = x + nZ

Modular addition and multiplication of equivalence classes are well-deﬁned. For addition: if [x] = [w] and [y] = [z], then

w = x + kn and z = y + ln for some k, l ∈ Z, from which

[w] +

[z] = [w + z] =



(x + kn) + (y + ln)





x + y + n(k + l)



= [x + y] = [x] +

[y]

All this should be familiar from a previous course. We’ll revisit this in Chapter 6 when we deﬁne Z

as a factor group.

These groups are typically the cyclic groups to which others are compared. Indeed, as we’ll see

shortly, any cyclic group of order n is isomorphic to Z

. For instance:

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 simply the formula for composition of rotations ρ

= ρ

k+l (mod 3)

The Roots of Unity

We ﬁnish with a third family of cyclic groups, viewed as subgroups of (C

, ·).

Aside: Notation Review C = {x + iy : x, y ∈ R} is the vector space R

spanned by the basis

{1, i}, where i is a ‘number’ satisfying i

= −1. Given z = x + iy ∈ C, we 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): θ = arg z is the angle measured counter-clockwise

from the positive real axis to

−→

0z (if z = 0).

Polar form: z = re

iθ

= r cos θ + ir sin θ

The modulus and argument are the usual polar co-ordinates. When

r = 1 we have Euler’s formula:

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

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

roots of unity

comprise the cyclic subgroup of C

generated by

ζ := e

2πi

⟨

⟩



1, ζ, ζ

, ··· , ζ

n−1



More generally, if x, y ∈ R, then e

x+iy

= e

cos y + ie

sin y.

In this context, unity is just a pretentious term for the number one!

If necessary, write ζ

= e

2πi

to emphasize n.

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

roots

±1, ±i in Example 3.1. The n

roots are equally spaced round the

unit circle at the vertices of a regular n-gon; this is since

arg ζ

= arg e

2πk

= k arg ζ

We stop listing the elements of U

at ζ

n−1

, since ζ

= e

2πi

= 1.

Indeed, by (†), we see the relationship with modular arithmetic

= ζ

⇐⇒ 1 = ζ

k−l

= e

2πi(k−l)

⇐⇒ k ≡ l (mod n)

−1 1

−i

Seventh roots: ζ

= e

2πi

Theorem 3.9. The n

roots of unity are precisely the n (complex) roots of the equation z

= 1.

Proof. Plainly (ζ

)

= (e

2πik

)

= e

2πik

= 1, so every element of U

solves z

= 1.

For the converse, suppose z

= 1. Take the modulus to obtain

= 1. Since

is a non-negative

real number, we see that

= 1, whence its polar form is z = e

iθ

. Now compute:

1 = z

= (e

iθ

)

= e

inθ

⇐⇒ nθ = 2πk

for some integer k (∗). But then θ =

2πk

and so

z = e

iθ

= e

2πi



2πi



= ζ

In fact U

is just the rotation group R

= {ρ

, . . . , ρ

n−1

} in disguise!

Lemma 3.10. For any z ∈ C, ζ

z = ρ

( z) is the result of rotating z counter-clockwise by

2πk

radians.

Examples 3.11. 1. Observe that ζ

= (e

2πi

)

= e

2πi

= ζ

We immediately obtain a subgroup relationship: with ζ = ζ



1, ζ

, ζ



< U



1, ζ, ζ

, ζ



This is essentially trivial by drawing a picture!

ζζ

2. The group table for U

is trivial to construct. Here is U

, where we use the fact that ζ

= 1: if

we write the table with 1 = ζ

and ζ = ζ

, the relationship to (Z

, +

) and (R

, ◦) is 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/deﬁnitions:

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) Prove Lemma 3.10.

(b) Use the Lemma to prove that (U

, ·) and (R

, ◦) are isomorphic groups.

3.2 The Classiﬁcation and Structure of Cyclic Groups

In this abstract section, we describe all cyclic groups, their generators, and subgroup structures.

Lemma 3.12. Every cyclic group is abelian.

Proof. Let G =

⟨

⟩

. Since any two elements of G can be written g

, g

for some k, l ∈ Z, we immedi-

ately see that

= g

k+l

= g

l+k

= g

Note that the converse is false: the Klein four-group V is abelian but not cyclic.

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

, +

In either case, if G =

⟨

⟩

, then ϕ : x 7→ g

deﬁnes an isomorphism Z

(n)

∼

Proof. To distinguish these cases, consider the set of natural numbers

S = {m ∈ N : g

= e}

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

= g

. Then g

x−y

= e =⇒ x − y ∈ S: contradiction. It follows

that the elements . . . , g

−2

, g

−1

, e, g, g

, g

, . . . are distinct and that ϕ : Z → G is a bijection.

If S = ∅: Let

n = min S and deﬁne ϕ : Z

→ G : x 7→ g

. We check that 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

}

contains ﬁnitely many terms. Suppose two of these 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)

The set S quickly yields an alternative measure for the order of an element.

Corollary 3.14. If G =

⟨

⟩

is ﬁnite, then its order is the smallest positive integer n such that g

= e.

Moreover g

= e ⇐⇒ m is a multiple of n (n



m).

By the well-ordering property of the natural numbers, any non-empty subset has a minimum element.

Examples 3.15. 1. The group of 7

roots of unity (U

, ·) is isomorphic to (Z

, +

) via

ϕ : Z

→ U

: k 7→ ζ

2. The additive group 5Z = {5z : z ∈ Z} is inﬁnite and cyclic. It is isomorphic to the integers via

ϕ : (Z, +)

∼

(5Z, + ) : z 7→ 5z

3. Let ξ = e

2πi

√

and consider the cyclic subgroup G :=

⟨

⟩

< (C

, ·). For integers m, observe that

= e

2πim

√

= 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 ξ as performing an irrational fraction (

√

) of a full rotation.

4. ( R, +) is non-cyclic since its (uncountable) cardinality 2

ℵ

is larger than the (countable) car-

dinality ℵ

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.

Subgroups of Cyclic Groups

We can straightforwardly classify all subgroups of a cyclic group: they’re also cyclic!

Theorem 3.16. Any subgroup of a cyclic group is cyclic.

The motivation for the proof is simple: the subgroup 2Z ≤ Z is generated by 2, the minimal positive

integer in the subgroup. Given a general subgroup H ≤ G, we identify a suitable ‘minimal’ element,

then demonstrate that this generates our subgroup.

Proof. Suppose H ≤ G =

⟨

⟩

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

Otherwise, ∃s ∈ N minimal such that g

∈ H. We claim that H =

⟨

⟩

: i.e. 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

= g

qs+r

= (g

)

=⇒ g

= (g

)

−q

∈ H

since H is closed under · and inverses. By the minimality of S, this forces r = 0, from which we

conclude that g

= (g

)

∈

⟨

⟩

The inﬁnite case is particularly simple; the proof is an exercise.

Corollary 3.17 (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

∼

Example 3.18. It is helpful to write this out explicitly in additive notation when G = Z. Since every

subgroup is cyclic, there are two cases:

• The trivial subgroup:

⟨

⟩

= {0}.

• Every other subgroup:

⟨

⟩

= sZ when s = 0. All of these subgroups are isomorphic to Z via

the isomorphism ϕ : Z → sZ : x 7→ sx.

Finite cyclic groups are a little more complicated, so it is worth seeing an example ﬁrst.

Example 3.19. Consider U

= {1, ζ, ζ

, ζ

} under multiplication. Since all subgroups are

cyclic, we need only consider what is generated by each element.

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

, +

x 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

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

The difference is almost entirely notational, as must be since the groups are isomorphic. Note, how-

ever, in the subgroup diagram that we can’t use equals as we did for U

: 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

⟨

⟩

∼

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

⟨

⟩

have order n. Then G has a unique

subgroup of each order dividing n. More precisely,

d = gcd(s, n) =⇒

⟨

⟩

= ⟨g

⟩

∼

Proof. Suppose d = gcd(s, n). We show ﬁrst that

⟨

⟩







⟨

⟩

⊆





Since d |s we have s = kd for some k ∈ Z, and so

)

= (g

)

∈





=⇒

⟨

⟩

⊆







⟨

⟩

⊇





By B

ezout’s identity (ext. Euclidean alg.), d = κs + λn for some κ, λ ∈ Z, whence

= (g

)

= (g

)

∈

⟨

⟩

=⇒





⊆

⟨

⟩

To ﬁnish, we count the number of elements in ⟨g

⟩. Since d |n, there are precisely

of these, namely

⟨g

⟩ =



e, g

, g

, . . . , g

n−d



The result is worth restating explicitly in the additive group (Z

, +

d = gcd(s, n) =⇒

⟨

⟩

⟨

⟩

∼

In particular: x ∈ Z

is a generator if and only if gcd(x, n) = 1.

Example 3.21. We describe all subgroups of Z

and construct its subgroup diagram. The ﬁrst

column lists the subgroup generated by each value x ∈ Z

. The second column is the isomorphic

group Z

. The ﬁnal column lists the divisors d of 30, and thus the possible values of gcd(x, 30).

Subgroup

⟨

⟩

Isomorph Z

d = gcd(x, 30)

{. . . , 1, . . . , 7, . . . , 11, . . . , 13, . . . , 17, . . . , 19, . . . , 23, . . . , 29} Z

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

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

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

{0, 6, 12, 18, 24} Z

{0, 10, 20} Z

{0, 15} Z

{0} Z

0 (30)

The subgroup diagram is drawn, with the obvious (minimal)

generator chosen for each subgroup; any of the other gener-

ators in the table could have been chosen instead.

With a little thinking, you should appreciate that the shape of

the subgroup diagram (this one looks a little like a cube. . . )

depends only on the prime factorization 30 = 2 ·3 · 5; namely

that each prime appears exactly once in the decomposition.

⟨

⟩

= 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. For each group: 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 your answer.

7. Suppose G =

⟨

⟩

is inﬁnite and H =

⟨

⟩

is an inﬁnite subgroup. Prove Corollary 3.17 by

explicitly ﬁnding an isomorphism ϕ : G → H.

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

9. Let x, y be elements of a group G. If xy has ﬁ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: You need B´ezout’s identity. This is the group of units in the ring (Z

, +

, ·

))

11. Let G be a group and X a non-empty subset of G. The subgroup generated by X is the subgroup

created by making all possible combinations of elements and inverses of elements in X.

(a) Explain why ( Z, +) is generated by the set X = {2, 3}.

(b) If m, n ∈ (Z, +), show that the group generated by X = {m, n} is dZ, where d =

gcd(m, n).

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 see 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 inherits a group structure in a natural way by adding co-ordinates

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

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

, +

). This is a binary operation on Z

× Z

, with a

familiar-looking table: it has exactly the same structure as the Cayley table for the Klein four-group!

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

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

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

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

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

↭

◦ e a b c

e e a b c

a a e c b

b b c e a

c c b a e

We conclude that Z

×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 is abelian 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. Consider the direct product of groups (Z

, +

) and (Z

, +

×Z



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



This is abelian and has order 6, so we might guess that it is isomorphic to (Z

, +

). To see this

we need a generator: choose (1, 1) and observe that

⟨

(1, 1)

⟩



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



= Z

×Z

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

∼

×Z

2. If each G

is abelian, 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.20:

• 10 ∈ Z

has order 6 =

gcd(10,12)

• 2 ∈ Z

has order 4 =

gcd(2,8)

If we repeatedly add (10, 2), then the ﬁrst co-ordinate will reset after 6 summations, while the second

resets after 4. For both to reset, we need a common multiple of 6 and 4 summands. We can check this

explicitly:



(10, 2)





(10, 2), (8, 4), (6, 6), ( 4, 0), (2, 2), (0, 4), (10, 6), (8, 0), ( 6, 2), (4, 4), (2, 6), (0, 0)



The order of the element (10, 2) is indeed the least common multiple 12 = lcm(6, 4).

Theorem 4.5. Suppose x

∈ G

has order r

. Then (x

, . . . , x

) ∈

∏

k=1

has order lcm(r

, . . . , r

Proof. Just appeal to Corollary 3.14:

, . . . , 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 appealing to Corollary 3.20, the element has order

lcm



gcd(1,4)

gcd(3,7)

gcd(2,5)

gcd(6,20)



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

In this course we will only ever have ﬁnitely many terms in a direct product/sum: in such cases these concepts are

identical for abelian groups written additively. When there are inﬁnitely many factors, the concepts are slightly different.

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

⇐⇒ gcd( m

, m

) = 1, ∀i = j.

• If n = p

··· p

is the prime factorization, then Z

∼

×··· ×Z

Proof. The generalization follows by induction on the ﬁrst part.

(⇐) 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 then cyclic.

(⇒) This is an exercise.

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 none 5, 7, 12 have any common factors.

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

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.

Finite(ly generated) abelian groups

We’ve used the direct product to create ﬁnite abelian groups from cyclic building blocks. 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 factors of Z.

Recall Exercise 3.2.11.

We won’t develop the technology necessary to prove this, but it is too useful to ignore. Our purpose

is simply to classify ﬁnite abelian groups up to isomorphism.

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

, namely

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

These groups can be distinguished in several ways; for instance, if G is abelian and has order

81, you could show that G

∼

×Z

by demonstrating two facts:

• G contains an element of order 27.

• The maximum order of an element of G is 27.

2. Since 450 = 2 ·3

·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, max order 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 before, there are multiple isomorphic ways to express each group as a direct product.

We ﬁnish by listing all groups of orders 1 through 15 and abelian groups of order 16 up to isomor-

phism. The Fundamental Theorem gives us all the abelian groups.

order abelian non-abelian

1 Z

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:

• D

, S

and A

will be described properly in the next section.

• Q

is the quaternion group (Exercise 2.2.11), and Q

a generalized quaternion group: look them up

if interested!

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

and the direct product Z

× Q

are explicit examples. The table might make you suspicious that all non-abelian groups have even

order: this is not so, though the smallest counter-example has order 21.

Exercises 4. Key concepts:

Direct product Order of element via lcm Cyclic/gcd criteria Fundamental theorem

1. List the elements of the following direct product groups:

(a) Z

×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 the prime decomposition of m and the fundamental theorem and identify a suitable sub-

group of Z

×·×Z

)

5 Permutations and Orbits

In this chapter we return to the roots of group theory and consider the re-orderings of a set.

5.1 The Symmetric Group & Cycle Notation

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 subscript n is not the order of S

)

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 (Theorem 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, so

evaluation means that we act with τ ﬁrst:

στ(a) = σ



τ(a)



Similarly, exponentiation will mean self-composition: e.g. σ

= σσσ = σ ◦σ ◦ σ.

Here we make S

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

to this is usually also called S

(see Exercise 7).

You should have seen this in a previous class. If you are uncomfortable with why this is true, write out the details!

Cycle Notation

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 () are sometimes helpful in calculations: these are simply the identity e.

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

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 It is impractically slow to compute using tables. 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 and thus build up the

right column.

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

• Since 1

7→ 4

7→ 2, write 2 next: στ = (1 2

• 2

7→ 2

7→ 1 starts the cycle; close it and open another with an unused value: στ = (1 2)(3

• 3

7→ 3

7→ 4, so write 4 next: στ = (1 2)(3 4

• 4

7→ 1

7→ 3 starts the current cycle, so close it: στ = (1 2)(3 4)

• All values 1, 2, 3, 4 have appeared so we terminate the algorithm.

It should be clear how to extend the algorithm when composing more cycles. If you obtain any 1-

cycles, delete them. Shortly we’ll prove that the algorithm always terminates in a product of disjoint

cycles. For now, practice the algorithm by verifying the following:

Examples 5.6. 1. ( 1 4)(1 3 4 2) = ( 1 3)(2 4) 2. ( 1 3 5 4)(2 3 4) = (1 3)(2 5 4)

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

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

Geometric Symmetry Groups

Permutations allow us to describe 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 of symmetries 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.

Both are therefore identiﬁed with elements of the dihedral group D

5 6

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

with a sub-

group of S

. All elements and the complete subgroup diagram are given

below, where we follow the convention to denote reﬂections across diag-

onals (δ

) and the midpoints of sides (µ

) differently.

Cycle notation makes calculation easy: for instance

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

= ρ

That two reﬂections make a rotation is geometrically obvious, but identifying which rotation is

harder without the the ability to calculate!

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

In mathematics, the word group originally referred to a set of permutations. We ﬁnish this section

with a foundational result: every element of a group may be viewed as a permutation of the group

itself, thus linking to the original meaning of the word.

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

Proof. Let G be a group. For each a ∈ G, let σ

: G → G be left multiplication by a, i.e. σ

(x) = ax.

We claim that the set of such functions {σ

: a ∈ G} forms a subgroup of S

isomorphic to G.

First observe that σ

has inverse function σ

−1

= σ

−1

, since

∀x ∈ G, σ

−1



(x)



= a

−1

ax = x and σ



−1



(x) = aa

−1

x = x

It follows that each σ

is a permutation of G: that is σ

∈ S

We ﬁnish by showing that the function ϕ : G → {σ

: a ∈ G} deﬁned by ϕ(a) = σ

is an isomorphism:

Injectivity: ϕ(a) = ϕ(b) =⇒ σ

= σ

=⇒ a = σ

( e) = σ

( e) = b.

Surjectivity: Certainly every function σ

is in the range of ϕ!

Homomorphism: For all a, b, x ∈ G,



ϕ(a) ◦ ϕ(b)



(x) = σ



(x)



= abx = σ

(x) =



ϕ(ab)



(x)

from which ϕ(a) ◦ϕ(b) = ϕ(ab).

Cayley’s Theorem does not say that every group is isomorphic to some symmetric group. It says that

that every group G is isomorphic to a subgroup of S

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

dog

cat













horse

cat

dog

ﬁsh







2. Compute the following products 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. Consider the dihedral group D

of symmetries of the regular

heptagon, viewed as a subgroup of S

. Each µ

is reﬂection

across the indicated dashed line, and ρ

is rotation 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 → G via left multiplication.

(a) Does the argument still work if σ

: G → G is right multiplication σ

(x) = xa?

(b) (Harder) Suppose we take σ

(x) := axa

−1

. Where does the proof of Cayley’s Theorem

fail?

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

In this section we begin to consider the idea of a group action; how the elements of a group transform

a set. We’ve already seen examples of this; for instance how rotations transform an object. The

simplest general example is built into the deﬁnition of the symmetric group and appears naturally in

cycle notation.

Deﬁnition 5.9. 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.10. 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}.

2. The orbits of ( 1 2)(4 5) are {1, 2}, {3}, {4, 5}.

3. This is false if the cycles are not disjoint. For instance, σ = (1 3)(2 3 4) ∈ S

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

(1 2 3 4) of multiplying out σ using our algorithm.

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

can be written as a product of disjoint cycles. The answer is yes, and the disjoint cycles turn out to be

precisely the orbits!

Theorem 5.11. The orbits of any σ ∈ S

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.

If ∼ is a relation on a set X and x ∈ X, we may deﬁne the set [x] := {y ∈ X : y ∼ x}. In this case [x] = orb

(σ).

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.

Much of the rest of the course requires these crucial ideas. If they’re not familiar, review your notes from a previous class

and ask questions!

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

Proof. We formalize our algorithm from the previous section. Suppose σ ∈ S

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 Theorem 5.11, orb

( σ) is disjoint with orb

( σ). If orb

( σ) ∪ orb

( σ) = X, we are ﬁnished:

σ is the product of two disjoint cycles.

σ =



1 σ(1) σ

(1) ···



σ(x

) σ

) ···



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

= min{x ∈ X : x ∈ orb

( σ) ∪ ··· ∪ orb

k−1

( σ)}. By

the Theorem, orb

( σ) is disjoint with orb

( σ) ∪ ··· ∪ orb

k−1

( σ). The process continues until

orb

( σ) ∪ ··· ∪orb

( σ) = X, which must happen 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 algorithm always results in a product of disjoint cycles! By convec-

tion, we take x

= 1 and construct an increasing sequence x

≤ x

≤ ··· ≤ x

, though there is no

need to do so: disjoint cycles can be listed in any order and may start with any element, thus

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

Also, by convention, we delete any orbits of size 1 (1-cycles). If you are still feeling uncomfortable

multiplying cycles, practice until it becomes second-nature!

Orders of Elements in S

Recall that the order of an element σ is the least positive integer k for which σ

= e.

Example 5.13. 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 follows intuitively if we identify σ with a

rotation of a regular hexagon.

5 6

By thinking similarly about the regular k-gon, it should be clear that any k-cycle has order k.

Things are trickier when you don’t have a single cycle, though this is where our discussion of disjoint

cycles saves us, since disjoint cycles commute.

Examples 5.14. 1. Since (1 2 3) and (4 5) are disjoint cycles, we know that (1 2 3)(4 5) = (4 5)(1 2 3).

We therefore easily compute the following:



(1 2 3)(4 5)



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

, ﬁnd σ

. It is really 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 is incorrect. The cycles don’t commute (2 5 3)(1 5 4 3) = (1 5 4 3)(2 5 3) so we can’t dis-

tribute the exponent. Instead we ﬁrst write σ as a product of disjoint cycles, then

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

= (1 3)

(2 5 4)

= (2 5 4)

= (2 4 5)

The disjoint cycles 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.15. 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. Since these commute, we have

= σ

···σ

Since each factor σ

permutes disjoint sets, it follows that

= e ⇐⇒ ∀j, σ

= e

If the orbits of σ have lengths r

∈ N, it follows that

= e ⇐⇒ α

| k

Thus k must be a multiple of α

for all j. The least such k is by deﬁnition lcm(α

, . . . , α

Example 5.16. The order of σ = (1 4 5)(3 6 2 7)(8 9) ∈ S

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

To ﬁnd σ

3465

, ﬁrst observe that 3465 = 12 ·288 + 9, whence

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

Instead of breaking a permutation σ into disjoint cycles, we can consider a permutation as con-

structed from only the simplest bijections.

Deﬁnition 5.17. 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.18. Every σ ∈ S

(n ≥ 2) is the product of transpositions.

Proof. There are many, many ways to write out a single permutation as a product of transpositions.

One method is ﬁrst to write σ as a product of disjoint cycles, then write each cycle as follows:

··· a

) = (a

)(a

k−1

) ···(a

)

Just read it carefully and you should be convinced this works!

Example 5.19. The method in the proof results in the decomposition

(1 7 6 4 5) = (1 5)(1 4)(1 6)(1 7)

Other decompositions are possible, for instance (1 7)(3 6)(5 7)(4 7)(3 6)(6 7).

While there are many ways to write a permutation as a product of transpositions, there is a simple

commonality which can be observed via a matrix notation for permutations. Consider, for instance,







1 0 0 0

0 0 0 1

0 0 1 0

0 1 0 0































and







0 0 1 0

0 0 0 1

0 1 0 0

1 0 0 0































(∗)

Each 4 ×4 matrix permutes the values 1, 2, 3, 4 when placed in a column vector. These matrices plainly

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

Deﬁnition 5.20. An n × n permutation matrix is a matrix obtained from the identity matrix by per-

muting its rows. Equivalently, it is zero except for a single 1 in each row and column.

Lemma 5.21. The set of n × n permutation matrices forms a group under multiplication which is

isomorphic to S

We omit a formal proof, though it relies on essentially one fact from elementary linear algebra; that

row operations preserve the solution set of a system of linear equations. For instance (∗) describes two

systems Ax = b and Cx = d which are identical up to rearrangements of rows (row operations) and

moreover have identical solutions x =





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

sponds to an elementary matrix which swaps two rows; such a matrix always has determinant −1.

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

σ = σ

···σ

Viewing this as a product of matrices, take the determinant of both sides to observe that

det σ = (−1)

Notice that this depends only on whether m is even or odd. . .

Deﬁnition 5.22. A permutation σ ∈ S

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

number of transpositions. By the above discussion, these concepts are well-deﬁned: a permutation

is either even or odd; it cannot be both!

Plainly the composition of even permutations remains even, as does the inverse of such. We may

therefore deﬁne a new subgroup of S

Deﬁnition 5.23. The alternating group A

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

Theorem 5.24. A

has exactly half the elements of S

: that is

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: the inverse of ϕ is ϕ itself! Moreover, ϕ maps even permutations to odd

and vice versa. It follows that there are exactly the same number of odd and even permutations.

Examples 5.25. We describe the small alternating groups up to A

1. A

= {e}

∼

is extremely boring!

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)

We already know one non-abelian group of order 12: the dihedral

group D

. We quickly see that A

≇ D

: all elements of A

have

orders 1, 2 or 3, while D

contains a rotation of order 6.

By labelling faces (or vertices), A

may be visualized the rotation

group of the 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 into subsets so that the set of subsets inherits a natural group

structure. This will likely feel extremely abstract and difﬁcult. However, it is really nothing new; it is

precisely the idea behind modular arithmetic.

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 main 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 examples are everything in this chapter: write everything out by hand until it becomes easy—there is no shortcut!

The last observation is in fact general—we leave the proof as a straightforward 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, 4, 8} ≤ Z

. This is cyclic with order 3. The

distinct cosets of

⟨

⟩

are as follows (left = right since Z

is abelian!):

⟨

⟩

= {0, 4, 8}



= 4 +

⟨

⟩

= 8 +

⟨

⟩



1 +

⟨

⟩

= {1, 5, 9}



= 5 +

⟨

⟩

= 9 +

⟨

⟩



2 +

⟨

⟩

= {2, 6, 10}



= 6 +

⟨

⟩

= 10 +

⟨

⟩



3 +

⟨

⟩

= {3, 7, 11}



= 7 +

⟨

⟩

= 11 +

⟨

⟩



Observe that 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

; this is a line

through the origin. The coset

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

is a line parallel to W. The cosets thus comprise all lines

parallel to W. Note again that these partition R

: every

point in R

lies in precisely one coset.

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

the cosets v + W are the sets parallel to W. Only the zero

coset W = 0 + W is a subspace.

v + W

4. Recall Theorem 5.24. If we generalize 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 partition G similarly: indeed

y ∈ Hx ⇐⇒ yx

−1

∈ H ⇐⇒ Hx = Hy

The blue criterion is particularly useful as it is often very easy to check. Before reading the proof, con-

vince yourself that each previous example satisﬁes the result. When H is non-normal (e.g. Example

2), the right cosets partition G in a different way to the left cosets!

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. We claim 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.

It is precisely the fact that H is a subgroup which 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 is unlikely to produce a partition.

Example 6.6. 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 this section with a technical result which will be useful in future sections.

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

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

−1

∈ H

Proof. Start by using the above criteria to observe:

(a) gH ⊆ Hg ⇐⇒ ∀h ∈ H, gh ∈ Hg ⇐⇒ ∀h ∈ H, ghg

−1

∈ H

(b) Hg ⊆ gH ⇐⇒ ∀h ∈ H, hg ∈ gH ⇐⇒ ∀h ∈ H, g

−1

hg ∈ H

We may now complete the proof in two parts:

( ⇒) H ◁ G =⇒ part (a) for all g ∈ G.

( ⇐) If ghg

−1

∈ H for all g, h, then this is also true for g

−1

: that is g

−1

hg ∈ H. We now have the right

side of both (a) and (b). Otherwise said, gH = Hg for all g ∈ G, whence H is normal in G.

Exercises 6.1. Key concepts:

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

1. Find the cosets of the following subgroups: since the groups are abelian, left and right cosets

are identical.

(a) 4Z ≤ 2Z (b)

⟨

⟩

≤ Z

(c)

⟨

⟩

≤ Z

(d)

⟨

⟩

≤ 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 the subgroup {ρ

, δ

} ≤ D

. Is the subgroup normal?

(b) Repeat part (a) for the subgroup {ρ

, ρ

(Hint: use cycle notation (Exercises 5.1.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

: we call this the stabilizer of 4.

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

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

a ∼ b ⇐⇒ a = hbk for some h ∈ H, k ∈ K.

(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 up to a powerful result; with luck you’ve hypothesized this already!

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

Otherwise said

H ≤ G =⇒



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

: H → gH : h 7→ gh

is a bijection (with inverse ϕ

−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 similarly have proved this using the right coset partition. Here is an example of its power.

Corollary 6.9. 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.13).

Example 6.10. 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 sometimes misremembered as ‘the order of an element divides the order of the group.’ This is the special case

when H is a cyclic subgroup of G. The even more special case when G is cyclic is Corollary 3.20:

⟨

⟩

≤ Z

has order

gcd( s,n)

(certainly divides n). The converse to Lagrange is false: e.g. A

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

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.11. 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.12. 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.13. 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.14. 1. Recall Example 6.12.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 a subgroup H ≤ G, we ask whether the set of left cosets {gH : g ∈ G} can be viewed as a group

in a natural way. By this, we mean that the group structure on should be inherited from that of G. To

see how this works (or doesn’t!), recall Examples 6.1.

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

⟨

⟩

= {0, 4, 8} ≤ Z

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

{0, 4, 8}, {1, 5, 9}, {2, 6, 10}, {3, 7, 11}

It feels like we have the cyclic group Z

in disguise! To see this we need a binary operation: the

natural approach is to use the addition we already have in Z

and deﬁne addition of cosets via

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

The process for computing (a + H) ⊕(b + H) contains a potential snag:

(a) Choose representatives: Make a choice of elements a and b in the respective cosets.

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

If ⊕ is to make sense, the outcome must be independent of the choices made in step (a). In this

case there is no problem, as you can tediously check for yourself: for example, to verify

(2 + H) ⊕(3 + H) = 1 + H

there are nine possibilities, of which one is

6 +

11 = 17 = 5 ∈ 1 + H

Rather than verify these independently, we proceed in general. If x ∈ a + H and y ∈ b + H,

then x −a and y −b ∈ H, whence

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

The operation is well-deﬁned and we’ll shortly see that the set of left cosets forms a group

under ⊕. Indeed ϕ(x) = x + H deﬁnes an isomorphism of Z

with this factor group.

2. Unfortunately, this sort of behavior isn’t universal. Let us repeat the process with the subgroup

H = {e, µ

} ≤ D

, whose left cosets are

H = µ

H = {e, µ

}, ρ

H = µ

H = {ρ

, µ

}, ρ

H = µ

H = {ρ

, µ

}

This time, if we attempt to deﬁne the ‘natural’ operation on the set {σH} of left cosets via

aH ⊗bH := (ab)H

then the problem is real. There are four choices for how to compute ρ

H ⊗ ρ

H, of which two

sufﬁce for a contradiction:

H = ρ

H and µ

H = H

The freedom of choice (part (a)) in the deﬁnition of ⊗ leads to different outcomes, whence ⊗ is

not well-deﬁned, and the set of left cosets does not form a group in a natural way.

Well-deﬁnition of the Factor Group Structure

As the examples show, some subgroups H ≤ G behave better than others when trying to view the

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

in the abstract.

Let H be a subgroup of G and deﬁne the natural operation on the set of left cosets:

aH ·bH := (ab)H

This is well-deﬁned if and only if

∀a, b ∈ G, ∀x ∈ aH, y ∈ bH, we have (ab)H = (xy)H

Let us trace through what this means for the subgroup H, using the fact that

x ∈ aH ⇐⇒ ∃h ∈ H such that x = ah

The natural operation is well-deﬁned if and only if

∀a, b ∈ G, h, h

∈ H, (ab)H = (ahbh

)H = (ahb)H

⇐⇒ ∀a, b ∈ G, h ∈ H, (ab)

−1

(ahb) ∈ H (Theorem 6.5)

⇐⇒ ∀b ∈ G, h ∈ H, b

−1

hb ∈ H

⇐⇒ H ◁ G (Corollary 6.7)

We have proved the critical part of an amazing result!

Theorem 6.15. Suppose H ≤ G. The set of left cosets forms a group under the natural operation

aH ·bH := (ab)H

if and only if H is a normal subgroup of G.

Deﬁnition 6.16. If H ◁ G, then the set of (left) cosets is a factor group, written



(’G mod H’).

Since the group structure on



arises naturally from that on G, we typically use the same notation

for the operation. The notation meshes with the index: if G is ﬁnite, then







= (G : H) =

Proof. The above discussion shows that the natural operation on



is well-deﬁned if and only if H

is normal in G. It remains only to check that



is a group in such cases.

Closure: aH ·bH = (ab)H is a coset, whence





, ·



is closed.

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 therefore the identity coset eH = H is the identity.

Inverse: a

−1

H · aH = (a

−1

a)H = eH = H, etc., therefore (aH)

−1

= a

−1

Factor Groups of Z: modular arithmetic done right!

For each positive integer n, the integer multiples nZ =

⟨

⟩

form a normal subgroup of Z. The coset

of nZ containing x ∈ Z is therefore

x + nZ = {x + kn : k ∈ Z} = {y ∈ Z : y ≡ x (mod n)}

This is precisely what we are used to calling ‘x’ in Z

! Indeed this is the formal deﬁnition, supersed-

ing Deﬁnition 3.4 and trivially proving Theorem 3.5.

Deﬁnition 6.17. Let n ∈ N. The group Z

is the factor group



Since remainders are so familiar, we typically drop nZ when calculating, thus

4 + 5 = 2 ∈ Z

means (4 + 7Z ) + (5 + 7Z ) = 2 + 7Z ∈



Factor Groups of Finite Cyclic Groups

Our ﬁrst example in this section showed that



⟨

⟩

∼

. Here is another.

Example 6.18.

⟨

⟩

= {0, 5, 10, 15} ≤ Z

has factor group



⟨

⟩



0 +

⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩

, 4 +

⟨

⟩



This is isomorphic to Z

via the isomorphism

ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

Theorem 6.19. If d | n, then



⟨

⟩

∼

If s is not a divisor of n, recall that

⟨

⟩

⟨

⟩

where d = gcd(s, n), whence



⟨

⟩

∼

gcd(s,n)

Proof. Deﬁne ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

: our goal is to see that this is an isomorphism.

Well-deﬁnition/injectivity:

The former is required since the domain is a set of equivalence classes!

x = y ∈ Z

⇐⇒ x −y ∈

⟨

⟩

⇐⇒ x +

⟨

⟩

= y +

⟨

⟩

⇐⇒ ψ(x) = ψ(y)

Surjectivity: Any coset x +

⟨

⟩

= ψ(x) ∈ Im(ψ).

Homomorphism: For any x, y ∈ Z

ψ(x + y) = (x + y) +

⟨

⟩



x +

⟨

⟩





y +

⟨

⟩



= ψ(x) + ψ(y)

That these arguments are converses is typical: for a given function µ : A → B,

• Well-deﬁnition means: a = b =⇒ µ(a) = µ(b)

• Injectivity means: µ(a) = µ(b) =⇒ a = b

Finite Abelian Examples

If G is a ﬁnite abelian group, 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.20. For G = Z

×Z

and three subgroups H, we identify the factor group



1. If H =

⟨

(0, 1)

⟩

= {(0, 0), (0, 1), (0, 2), . . . , (0, 7)}, then the index of H in G is (G : H) =

4·8

= 4.

The factor group is abelian with order four and thus isomorphic to either Z

or Z

×Z

Here are two strategies for deciding which.

(a) Identify the cosets:

(x, y) + H = (v, w) + H ⇐⇒ (x, y) −(v, w) = (x −v, y −w) ∈ H ⇐⇒ x = v

Each coset contains a unique element (x, 0) where x ∈ Z

, whence,



H, (1, 0) + H, (2, 0) + H, (3, 0) + H

It can be checked that this is isomorphic to Z

via ψ : Z

→



: x 7→ (x, 0) + H.

(b) Observe that there exists an element in



with order 4. If k ∈ N, then



(1, 0) + H



= (k, 0) + H = H ⇐⇒ (k, 0) ∈ H ⇐⇒ 4 | k

This identiﬁes



∼

by elimination: every element of Z

×Z

has order at most 2.

2. H =

⟨

(0, 2)

⟩

= {(0, 0), (0, 2), (0, 4), (0, 6)} has order 4 with index (G : H) =

4·8

= 8. The factor

group is abelian with order 8 and thus isomorphic to one of Z

, Z

×Z

or Z

×Z

We again follow our strategies:

(a) Identify the cosets:

(x, y) + H = (v, w) + H ⇐⇒ (x −v, y −w) ∈ H ⇐⇒

(

x = v, and

y −w = 2k 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

We have an isomorphism ψ : Z

×Z

→



: (x, y) 7→ (x, y) + H.

(b) Alternatively, consider orders of elements:

•



contains an element ( 1, 0) + H of order 4.

• All elements of



have order dividing 4:



(x, y) + H



= (4x, 4y) + H = (0, 4y) + H = 2y



(0, 2) + H



= H

By elimination,



∼

× Z

has an element of order 8, while elements of Z

×Z

have maximum order 2).

3. Consider H =

⟨

(2, 4)

⟩

= {(0, 0), (2, 4)}. The previous examples may have lulled you into a

false sense of security:



is not



⟨

⟩



⟨

⟩

∼

×Z

The fact that there are (G : H) =

4·8

= 16 cosets immediately rules out this na

ıve possibility!

The Fundamental Theorem gives ﬁve non-isomorphic options for the factor group:

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

We again 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

There is precisely one representative of each coset whose ﬁrst entry is either 0 or 1, whence

the sixteen elements

(0, 0), (0, 1), . . . , (0, 7), (1, 0), . . . , (1, 7)

lie in distinct cosets of H. It seems reasonable to claim that the factor group is isomorphic

to Z

×Z

. Indeed

ψ : Z

×Z

→



→: (x, y) 7→ (x, y −2x) + H

is an explicit isomorphism. We leave it as an exercise to verify this. It requires some

creativity to invent such a function from nothing, particularly at the moment!

(b) The coset ( 0, 1) + H has order 8 in



, since



(0, 1) + H



= (0, k) + H = H ⇐⇒ 8 | k

which 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 right now, but it has some drawbacks; for instance, it cannot distin-

guish between groups such as Z

×Z

and Z

×Z

: both groups contain an element of order

4, and the maximum order of an element is also 4.

Other Examples

There are many other examples of factor groups, with varied strategies required for their identiﬁca-

tion. Here are just a few, and we’ll see more in later chapters.

Examples 6.21. 1.

⟨

2π

⟩

= 2πZ = {2πn : n ∈ Z} is a subgroup of the abelian group (R, +).

In any given coset x + 2πZ, there is a unique x such that 0 ≤ x < 2π (this is like taking the

remainder of x 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 an isomorphism of groups. The factor group construction therefore corresponds to wrapping

the real line inﬁnitely many times around a circle of circumference 2π.

2. Exercise 6.1.4, tells us that the Klein four-group

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

and so



∼

: can you ﬁnd an explicit isomorphism?

It’s a lot harder to prove, but we’ll see later that



∼

3. Consider H =

⟨

(2, 1)

⟩

≤ Z × Z

= G. Since G and H are inﬁnite, we cannot simply apply

the index formula to count cosets. Instead we use the 2 in the subgroup H to ﬁnd a simple

representative of each coset.

(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



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

We conclude that ( 1, 0) + H has order 8, whence



∼

4. Let H =

⟨

(1, 2)

⟩

≤ Z ×Z = G. We play a similar trick as above

(x, y) + H = (0, y −2x) + H

Since the choice of y is free, we see that there is a unique representative in each coset of the form

(0, z). We conclude that



∼

Z. In fact it can be checked that ψ



(x, y) + H



= y −2x deﬁnes

an isomorphism.

Exercises 6.3. Key concepts:

Factor group well-deﬁnition ⇐⇒ H ◁ G Z



identifying



1. List the cosets of the subgroup H =

⟨

⟩

in G = Z

. Verify directly that the function

ψ : Z

7→



: x 7→ x + H

is a well-deﬁned homomorphism (mimic the proof of Theorem 6.19!).

2. Identify the factor group

×Z



, where H = {(0, 0), (0, 2), (2, 0), (2, 2)} (Exercise 6.1.2).

3. (a) Identify the factor group



where H =

⟨

(2, 4)

⟩

≤ G = Z

×Z

(b) Repeat with the subgroup H =

⟨

⟩

⟨

⟩

(this is a trick question!)

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. Let G = Z

×Z

. Prove that each function in Examples 6.20 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. Recall Exercise 6.2.9. The factor group



is abelian and of order 6, whence it is cyclic. Prove

this explicitly by ﬁnding a generator.

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? Prove or disprove.

10. In Example 6.21.2 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. Let H =

⟨

(2, 3)

⟩

≤ G = Z

×Z. Prove that



∼

13. Verify the claim in Example 6.21.4 that ψ



(x, y) + H



= y −2x is an isomorphism.

14. (Hard!) Let G = Z

×Z

×Z and H =

⟨

(4, 2, 3)

⟩

. Identify the factor group



as a direct

product Z

×Z

(Hint: use the division algorithm z = 3q + r to show that there is exactly one representative of each coset

(x, y, z) + H where z is 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

between normal subgroups, homomorphisms and factor groups.

Unless otherwise stated, in this chapter all homomorphisms 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.7: 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 (or L) is ﬁnite, then Im ϕ is a ﬁnite group

whose order divides that of G (or L). Otherwise said:

< ∞ =⇒

Im ϕ



and

< ∞ =⇒

Im ϕ



Proof. If G is a ﬁnite group, then ker ϕ ≤ G is ﬁnite. Now apply Lemma 7.5:

Im ϕ

= (G : ker ϕ) =

ker ϕ

is a divisor of

. The second case

Im ϕ



is Lagrange’s Theorem (6.8).

Examples 7.7. 1. How many distinct homomorphisms are there ϕ : Z

→ Z

If ϕ is such a homomorphism, the Theorem says that

Im ϕ

divides both 17 and 13. The only

such positive integer is 1. Since Im ϕ must contain the identity, we conclude that there is only

one homomorphism!

∀x ∈ Z

, ϕ(x) = 0

More generally, if gcd(

) = 1, then the only homomorphism ϕ : G → L is the trivial

function ϕ : g 7→ e

2. Describe all homomorphisms ϕ : Z

→ S

Since the domain Z

is cyclic, we need only describe what happens to a generator (e.g. 1) to

obtain the entire homomorphism ϕ(x) =



ϕ(1)



. There are at most six homomorphisms; one

for each possible element ϕ(1) ∈ S

. Not all of these cases are however possible.

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

contains exactly three: {e, (2 3)},

{e, (1 3)}, {e, (1 2)}. We therefore have three further homomorphisms

(x) = (2 3)

, ϕ

(x) = (1 3)

, ϕ

(x) = (1 2)

for a grand total of four distinct homomorphisms.

We now consider the general question of homomorphisms between ﬁnite cyclic groups ϕ : Z

→ Z

Two facts make this relatively simple:

1. 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.20), Im ϕ must be a subgroup of the unique subgroup of Z

of order d:

Im ϕ ≤



, . . . ,

( d −1)n



We need only try letting ϕ(1) be each element of this group in turn. . .

Corollary 7.8. There are d = gcd(m, n) distinct homomorphisms ϕ : Z

→ Z

, deﬁned by

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

Reversing the argument, we see that there are also 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 deﬁned by tr



a b

c d



= a + d = a + d

(b) T : R

→ R

: x 7→

1 1 −1

0 3 −1

1 4 −2

2 5 −3

(Hint: remember row operations. . . )

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, the following companion result says that, among

homomorphisms with the same kernel, γ 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 ϕ.

The results may be summarized in a commutative diagram: any ho-

momorphism ϕ : G → L factors as ϕ = µ ◦γ where γ is the canon-

ical homomorphism with kernel ker ϕ. There are analogues in

several other parts of mathematics; in particular, 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

) = ϕ(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.21.1) Let H =

⟨

2π

⟩

≤ R and deﬁne ϕ : R → (C

, ·) by ϕ(x) = e

. This is a

homomorphism with

ker ϕ = {x ∈ R : e

= 1} = H and Im ϕ = S

The canonical homomorphism is

γ : R →



: x 7→ x +

⟨

2π

⟩

while the isomorphism we saw previously

µ :



→ S

: x +

⟨

2π

⟩

7→ e

is precisely that arising from the 1

isomorphism theorem.

3. The map ϕ : Z ×Z → Z deﬁned by ϕ(x, y) = 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, we see that

Z ×Z



⟨

(2, 3)

⟩

∼

Z via µ



(x, y) +

⟨

(2, 3)

⟩



= 3x −2y

With a little creativity, the theorem can 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.20, mk.II). Let G = Z

× Z

. For each subgroup H, we describe a homomorphism

ϕ : G → L with ker ϕ = H. There are many possible choices for ϕ; while ours will line up with what

we saw in the original incarnation of these examples, hopefully you’ll feel that the reasons for such

choices are independent of our earlier discussion.

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.

Note that µ is precisely the inverse of the isomorphism ψ : x 7→ (x, 0) + H stated in the original

version of this example; (x, y) + H = (x, 0) + H for this subgroup!

2. Given H =

⟨

(0, 2)

⟩

we require ϕ(0, 2) to be the identity. We may easily do this by taking y

modulo 2 and deﬁning

ϕ : Z

×Z

→ Z

×Z

: (x, y) 7→ (x, y)

This is a homomorphism with the correct kernel ker ϕ = H. Indeed ϕ is also 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. If H =

⟨

(2, 4)

⟩

= {(0, 0), (2, 4)}, it is signiﬁcantly trickier to ﬁnd a suitable homomorphism.

One approach is to observe that

(x, y) ∈ H ⇐⇒ x ≡ 0 (mod 2) and y −2x ≡ 0 (mod 8)

We therefore choose the homomorphism

ϕ : 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. (p, q) = ϕ(p, q + 2p), whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y −2x).

Other homomorphisms are possible in all the above examples. This approach requires a little creativ-

ity! In general, it can be very difﬁcult to construct a simple homomorphism with the correct kernel.

Exercises 7.2. Key concepts:

Canonical homomorphism γ : G →



isomorphism theorem µ :



∼

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.7). It should also be familiar from linear algebra, in the form 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.2) 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 straightforward to check when n = 3 since there are only six

elements. In general, think about the proof of 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

(Theorem 5.11), 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 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.

It might feel as if we’ve done this already; Exercise 4.13 covers abelian groups, but this depends on

the fundamental theorem, which ﬁrst requires Cauchy for abelian groups!

Proof. 1. A proof for when G is abelian is in the exercises.

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 reach an abelian subgroup, then we have an inﬁnite sequence

of proper subgroups and thus a decreasing sequence of positive integers; contradiction.

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ﬁca-

tion and the existence of sequences of normal subgroups.

The two are equivalent: if y has order p, then

⟨

⟩

is a subgroup of order p. If H ≤ G has order p, then H

∼

is cyclic.

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 of G.

(a) Explain why the base case

= 2 is true.

(b) Suppose p divides

≥ 3 and assume the result holds for all abelian groups of order

• Choose any x = e; denote its order by m =

|⟨

⟩|

(necessarily m ≥ 2).

• Choose a prime q dividing m, deﬁne y := x

m/q

and let H :=

⟨

⟩

Why are we done if q = p?



of order p.

(d) Prove that z

has order p in G.