Math 120A — Introduction to Group Theory

Neil Donaldson

December 1, 2025

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

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

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

serve commonalities between structures in seemingly distinct places.

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

together satisfy a few basic properties. Indeed you’ve been using this structure since Kindergarten!

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

We’ll see a formal deﬁnition shortly, at which point we’ll be able to verify that (Z, +) really is a

group. The simplicity of the group structure means that it is often used as a building block for

more complicated structures.

Other reasons to study groups are their ubiquity and multitudinous

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

Permutations In mathematics, the word group was ﬁrst used to describe the ways in which a set

could be reordered, or permuted. Understanding permutations is of crucial importance to many

areas of mathematics, particularly 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 permutation group of its set of roots.

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

to the other by an element of the Euclidean group (a translation, rotation or reﬂection). More gen-

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

employed to describe geometric properties: for example, the number of holes in an object (a

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

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

substances.

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

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

groups.

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

For instance, the set of integers Z together with the two basic operations of addition and multiplication is a ring, as

you’ll study in a later course.

2 Group Axioms and Basic Examples

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

dard examples used throughout the course. The “Key concepts/deﬁnitions” listed at the start of each

Exercise set summarize these.

2.1 The Axioms of a Group

Deﬁnition 2.1 (Closure). Let G be a set and ∗ a function ∗ : G ×G → G. We describe this arrange-

ment in four different ways, though all mean exactly the same thing:

(a) ∀x, y ∈ G, x ∗y ∈ G (b) G is closed under ∗.

In abstract situations (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:

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

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

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

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

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

On the integers, however, subtraction is a binary operation: Z is closed under −.

3. On a small set, it can be convenient to represent a binary operation in tabular

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

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

a ∗b = e, or simply ab = e

∗ e a b

e e a b

a a e e

b b e a

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

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

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

If ∗ is associative, then the expression xyz has unambiguous meaning, as does exponential notation:

= x ···x (n factors).

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

2. ( Z, −) is non-associative: e.g. (1 −3) −2 = −4, but 1 − (3 −2) = 0.



{e, a, b}, ∗



, described in the table, is non-associative: e.g. a(bb) = aa = e, but (ab)b = eb = b.

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

∀x ∈ G, ex = xe = x

Examples (2.2, ver. III). 1. Addition on Z has identity 0, since 0 + x = x + 0 = x for any integer x.

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



{e, a, b}, ∗



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

If G is ﬁnite and has an identity (e.g. Example 2.2.3), convention dictates that we list it ﬁrst. Indeed,

we can always list it ﬁrst, since. . .

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

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

dard pattern: suppose there are two such objects and show that they are identical.

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

e f =

(

f since e is an identity

e since f is an identity

Since f = e, there is only one identity.

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

Deﬁnition 2.6 (Inverse). Suppose a binary structure (G, ∗) has identity e. An element x ∈ G has an

inverse y ∈ G if

xy = yx = e

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

2. Since ( Z, −) has no identity, the question of inverses is irrelevant.

3. Since ee = aa = ab = ba = e, we see that every element has an

inverse; indeed a has two inverses!

Element e a b

Inverses e a, b a

Lemma 2.7 (Uniqueness of inverses). Suppose a binary structure (G, ∗) is associative and has an

identity. If an element x ∈ G has an inverse, then said inverse is unique.

Proof. Suppose x has inverses y, z ∈ G. By associativity,

z(xy) = (zx)y =⇒ ze = ey =⇒ z = y

In such a situation it is legitimate to write x

−1

(or −x) for the inverse of x. Example 2.2.3 shows that

associativity is necessary: a non-associative binary structure can have non-unique inverses.

Deﬁnition 2.8 (Commutativity). Let (G, ∗) be a binary structure. Elements x, y ∈ G commute if

xy = yx. We say that ∗ is commutative if all elements commute:

∀x, y ∈ G, xy = yx

Examples (2.2, ver.V). 1. Addition of integers is commutative: ∀x, y ∈ Z, x + y = y + x.

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

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

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

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

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

Closure, Associativity, Identity, Inverse

The order of a group is the cardinality (size)

of the underlying set.

In addition, a group G is said to be abelian if the operation ∗ is commutative.

In a multiplicative group, the operation is written multiplicatively or using juxtaposition (includes

composition of functions). A group is additive

if the operation is addition. Abstract groups are

almost always written multiplicatively.

Examples (2.2, ver.VI). 1. (Z, +) is an inﬁnite, abelian, additive group. Precisely the same observa-

tions show that ( Q, +), (R, +) and (C, +) are also.

2. ( Z, −) is not a group since subtraction is neither associative, nor has an identity (nor inverses).

3. This binary relation is non-associative and so does not deﬁne a group.

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

obvious to everyone. Writing “Z is a group under addition,” is safer than “Z is a group:” it might be a

group under many different operations!

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

form an abelian group under multiplication.

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

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

Identity 1 ∈ R

is the identity since, for any x = 0, we have 1 · x = x ·1 = x

Inverse Given x = 0, observe that x

−1

is an inverse: x ·

· x = 1

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

As with addition of integers, we cannot prove these claims since they are part of the deﬁnition

of multiplication. Similarly, (Q

, ·) and (C

, ·) are abelian groups.

A ﬁnite group has ﬁnite order, while an inﬁnite group has inﬁnite order; unless absolutely necessary, it is rare to be

speciﬁc about inﬁnite cardinalities (countable, uncountable, etc.).

These are distinctions only of notation. For instance x + x + x = 3x in an additive group corresponds to xxx = x

in a

multiplicative group.

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

3. The set of odd integers 1 + 2Z = {1 + 2n : n ∈ Z} does 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. A Cayley table

is a tabular representation of a (small)

group. Groups of orders 1, 2 and 3 are shown. The one-

element group {e} is often called the trivial group.

Note the magic square (sudoku) property: each row/column

contains every element exactly once (see Exercise 11).

∗ 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

Theorem 2.11 (Cancellation laws & inverses). Suppose G is a group and that x, y, z ∈ G. Then

1. xy = xz =⇒ y = z 2. xz = yz =⇒ x = y 3. (xy)

−1

= y

−1

Part 3 should remind you of matrix multiplication.

Proof. Parts 1 & 2 are exercises. For part 3, multiply out using associativity:

−1

)(xy) = y

−1

x)y = y

−1

ey = y

−1

y = e

Similarly (xy)(y

−1

) = e. Thus y

−1

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

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

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

1. Given the binary operation table, calculate

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

∗ a b c d

a c d c b

b d c b a

c a d c d

d b a b c

2. The table for a binary operation on the set {a, b, c}is given. Compute

a ∗ (b ∗ c) and (a ∗ b) ∗ c. Does the expression a ∗ b ∗ c make sense?

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 (without writing 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?)

Englishman Arthur Cayley (1821–95) was an early group theorist. Similarly abelian honors the Norwegian Niels Abel

(1802–29), after whom the Abel Prize is named (often considered the Nobel Prize in Mathematics).

5. Which are binary structures? For those that are, which are commutative and which associative?

Give brief arguments in each case.

(a) ( Z, ∗), a ∗b = a + b + 1 (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. Verify the axioms of an abelian group; if any are false, provide a counter-example.

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

···x

−1

| {z }

n times

For any n ∈ N and x ∈ G, prove that (x

−1

)

= (x

)

−1

. By convention, this object is

denoted x

−n

. How would we write this in an additive group (Footnote 3)?

8. Let G be a group. Prove:

(a) ∀x, y ∈ G, (xyx

−1

)

= xy

−1

(b) ∀x ∈ G, (x

−1

)

−1

= x

−1

= x

−1

9. Prove or disprove:



R \ {1}, ∗



is an abelian group, where x ∗y := x + y −xy.

10. Let U be a set and P(U) its power set (the set of subsets of X).

(a) Which of the group axioms are 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.

11. (Magic Square) Suppose (G, ∗) is associative and that G is ﬁnite.

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

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

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

2.2 Subgroups

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

Deﬁnition 2.12 (Subgroup). Let G be a group. A subgroup of G is a non-empty subset H ⊆ G which

remains a group with respect to the same binary operation. We write H ≤ G.

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

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

Examples 2.13. The following should be immediate from the deﬁnition: all you need is a non-empty

subset that remains a group!

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

3. ( Q

, ·) < (R

, ·) < (C

, ·) 4. (R

, +) < (C

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

4. ( R

, +) ≤ (R

, +) if m ≤ n. For instance, with respect to the standard basis, R

consists of all

column vectors in R

whose last n −m entries are zero.

5. (C(R), +) < (C

(R ), +) . Think back to calculus: the sub of any two continuous functions is

continuous; every differentiable function is continuous; etc., etc.

Thankfully one doesn’t have to check all the group axioms to see that a subset is a subgroup.

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

and only if it is closed and has inverses in H (with respect to the group operation on G):

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

(⇐) By assumption, H satisﬁes the closure axiom. Moreover, the group operation on G is automati-

cally associative on any subset,

including H. It remains to verify that the identity element e (of

G) lies in H, for then our assumption (h

−1

∈ H) says that that inverse axiom is also satisﬁed.

Since H = ∅, we may choose some (any!) h ∈ H. By (∗), h

−1

∈ H. A second application of (∗)

ﬁnishes things off:

e = hh

−1

∈ H

Examples 2.15. 1. All of Examples 2.13 can be conﬁrmed using the theorem. For instance, part 5:

Non-empty subset: plainly 2Z = {. . . , −2, 0, 2, 4, . . .} = {2z : z ∈ Z} is such (of Z).

Closure: 2m, 2n ∈ 2Z =⇒ 2m + 2n = 2(m + n) ∈ 2Z.

Inverses: 2m ∈ 2Z has inverse −( 2m) = 2(−m) ∈ 2Z.

2. The positive integers N are closed under addition but do not satisfy the inverse axiom (for

instance, no x ∈ N satisﬁes x + 2 = 0). Thus (N, +) is not a subgroup of (Z, +).

Associativity does not care where x(yz) = (xy)z lives: “∈ G” does not appear in Deﬁnition 2.3!

3. Denote by 1 + 3Z 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, +).

4. The circle group S



iθ

: θ ∈ [0, 2π)



is plainly a non-empty subset of (C

, ·). The standard

exponential laws and the fact that e

2πi

= 1 verify that S

is in fact a subgroup.

Closure: e

iθ

iψ

= e

i(θ+ψ)

∈ S

(equals e

(θ+ψ−2π)i

if you feel it necessary).

Inverses: (e

iθ

)

−1

= e

−iθ

= e

(2π−θ)i

Subgroup Diagrams It can be helpful to represent subgroup relations pictorially,

using descending lines. For instance, the diagram on the right summarizes the sub-

group relations

6Z < 2Z < Z, 6Z < 3Z < Z, 6Z < Z

2Z 3Z

where all four groups under addition. If G has only ﬁnitely many subgroups, then its subgroup

diagram is the complete depiction of all subgroups.

Exercises 2.2. Key concepts: (Proper/trivial/non-trivial) Subgroup

Subgroup criterion (non-empty subset, closure, inverses) Subgroup diagram

1. Use the subgroup criterion to verify that Q

is a subgroup of R

under multiplication.

2. Give two reasons why the non-zero integers do not form a subgroup of Z under addition.

3. Describe/explain the relationship between positive integers m and n if (mZ, +) ≤ (nZ, + ).

4. Prove or disprove: the set H = {

: a ∈ Z, n ∈ N

} forms a group under addition.

5. Brieﬂy explain why “subgroup” is transitive: that is, if K ≤ H and H ≤ G, then K ≤ G.

6. Suppose H and K are subgroups of G. Prove that H ∩K is also a subgroup of G.

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

8. (Hard) On an abstract set Q

= {±1, ±i, ±j, ±k} of eight elements, we deﬁne an operation

(’multiplication’) using several properties:

• 1 is the identity.

• −1 commutes with everything in the expected way: e.g. −i = (−1)i = i(−1), etc.

• (−1)

= 1, i

= j

= k

= −1 and ij = k.

• Multiplication is associative.

(a) Prove that (Q

, ·) is a non-abelian group by completing its Cayley table.

(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 Modular Arithmetic

Many commonly encountered examples in abstract algebra make use of modular arithmetic: the ad-

dition and multiplication of remainders. Such arithmetic should be at least somewhat familiar so we

offer only a brief refresher. At present, these groups are very informal and are introduced primarily

to supply examples; more rigorous discussions will be given in Chapters 3 & 5.

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

the set of equivalence classes of integers

modulo n. These are typically written as remainders (i.e., as integers),

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

where x = y ∈ Z

means that the integers x, y have the same remainder on division by n.

More formally,

x = y ∈ Z

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

Example 2.17. In the most commonly used notation, we write Z

= {0, 1, 2, 3, 4}. Several other

notations are available. For instance, here is a calculation written in four different ways (note that

6 = 1 in Z

because they both have the same remainder 1 on division by 5):

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

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

2 = 6 = 1.

(d) Equivalence classes: [4] +

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

For reasons of brevity we mostly use notation (a), though feel

free to use another if it makes you more comfortable. Regard-

less of notation, you must make it clear in which Z

you are

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

[0]

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

[1]

= {

. . . ,

−

4, 1, 6, . . .

}

[2]

= {

. . . ,

−

3, 2, 7, . . .

}

[3]

= {

. . . ,

−

2, 3, 8, . . .

}

[4]

= {

. . . ,

−

1, 4, 9, . . .

}

Theorem 2.18. Z

forms an abelian group of order n under addition modulo n.

A rigorous proof (in the language of Footnote 6) is tedious, but will come for free in Chapter 5 when

is properly deﬁned as a factor group. These groups are so common that we usually just state “The

group Z

,” rather than (Z

, +

). In the exercises, we’ll also consider how multiplication modulo n

can be used to create groups of remainders.

An element of Z

is strictly an equivalence class: for instance, [x] ∈ Z

denotes the class of all integers with the same

remainder as the representative x ∈ Z:

[x] =



z ∈ Z : x ≡ z (mod n)





. . . , x −n, x, x + n, x + 2n . . .



= {x + kn : k ∈ Z} = x + nZ

Addition of equivalence classes is well-deﬁned (multiplication similarly): if [ x] = [w] and [y] = [z], then w = x + κn and

z = y + λn, from which

[w] +

[z] = [w + z] =



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





x + y + n(κ + λ)



= [x + y] = [x] +

[y]

While it is important to appreciate that the elements of Z

are not really numbers, the tediousness of this formal language

means that it is usually avoided. Equivalence classes and well-deﬁnition are not critical right now, but will become so later.

Examples 2.19. Here are the Cayley tables for Z

, Z

and 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

In each case 0 is the identity element. If you compare these to the the tables in Example 2.10.6, the

patterns should look familiar (we will explore this further in Section 2.5).

Subgroups of Z

It is easy to spot certain subgroups of Z

— just think about divisors of n!

Example 2.20. Plainly 2 is a divisor of 4. By covering up the rows/columns corresponding to 1 and

3, we obtain the Cayley table for the subgroup H = {0, 2} of Z

0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

−→

0 2

0 0 2

2 2 0

Hopefully it is obvious why H is a subgroup (think about the subgroup criterion Theorem 2.14!).

Now suppose 1 were in some subgroup K ≤ Z

and consider what the group axioms tell us:

Closure =⇒ 2 = 1 + 1 ∈ K

Inverse =⇒ 3 = −1 ∈ K

Identity =⇒ 0 ∈ K







=⇒ K = {0, 1, 2, 3} = Z

The same thing happens if a subgroup contains 3. The upshot is that Z

has precisely three

subgroups: itself, {0, 2} and the trivial subgroup {0}. The full subgroup diagram is drawn.

{0, 2}

{0}

Here is a more general version. Suppose d is a divisor of n, write n = dk, and consider the subset of

multiples of d in Z

⟨

⟩



0, d, 2d, . . . , (k −1)d



In the language of the subgroup criterion (Theorem 2.14), this set is:

Non-empty: Plainly 0 ∈

⟨

⟩

Closed under addition: κd + λd = (κ + λ)d ∈

⟨

⟩

Closed under inverses: The inverse of λd is −λd = (k −λ)d ∈

⟨

⟩

We have therefore proved:

Lemma 2.21. If d is a divisor of n, then the set of multiples

⟨

⟩

in Z

is a subgroup of order

As in Example 2.20, in Chapter 3 we’ll see that these are in fact the only subgroups of Z

Exercises 2.3. Key concepts: Z

, Multiples as subgroups: d | n =⇒

⟨

⟩

≤ Z

1. Refresh your memory of modular arithmetic by evaluating the following:

(a) 17 + 22 in Z

(b) 31 ·4 in Z

in Z

, (d) 19

−42 ·13 in Z

2. State the Cayley tables for the groups Z

and Z

(more formally (Z

, +

) and (Z

, +

)).

3. State the Cayley tables for all proper subgroups of Z

. Now draw the full subgroup diagram

for Z

(Hint: consider Lemma 2.21 and the remark that follows)

4. Draw the subgroup diagram for Z

5. Suppose n is a positive integer ≥ 2.

(a) Explain why Z

is not a group under multiplication. If you’re unsure what to do, consider

an example: what is the multiplication table for (Z

, ·)?

(b) Explain why {1, 2, 3, 4, 5} isn’t a group under multiplication modulo 6.

multiplication modulo n. If you want a challenge, try to prove your assertion.

6. The set Z

denotes the units in Z

, those elements which are relatively prime to n:



x ∈ Z

: gcd(x, n) = 1



In part (d), we verify that Z

is an abelian group under multiplication modulo n.

(a) Construct the Cayley tables for the groups Z

= {1, 2} and Z

= {1, 3}.

(b) Construct the Cayley table for the group Z

= {1, 2, 3, 4}. Now identify its subgroups.

and Z

. What is the order of each group?

(d) (Hard) Prove that Z

forms an abelian group under multiplication modulo n by verifying

the group axioms.

(Hint: Recall B´ezout’s identity gcd(x, n) = 1 ⇐⇒ ∃κ, λ ∈ Z such that κx + λn = 1)

(e) i. Compare the orders of the groups Z

, Z

and Z

. What do you observe?

ii. What about the orders of Z

, Z

and Z

? What is going on?

iii. The order of Z

is the value of Euler’s totient function ϕ(n). Research some of the prop-

erties of this function: can you ﬁnd something that helps explain your observations in

parts i and ii? Better still, take a course in Number Theory!

2.4 Geometric Symmetries & Matrix Groups

Geometric symmetries an matrices provide further large families of groups.

Now consider any geometric ﬁgure that has some symmetry (typically viewed as rotational or re-

ﬂective), such as a triangle, square, or tetrahedron. Each symmetry corresponds to a function that

transforms the original ﬁgure in such a way that the result occupies the same location as the original.

Example 2.22 (Klein four-group). The pictured rectangle has three obvious symmetries:

(a) Rotation by 180°.

(b) Vertical reﬂection.

Each symmetry may be viewed as a function transforming the rectangle (or permuting its ver-

tices/edges if you prefer). Group Theorists also consider the identity function e as a symmetry: it

simply leaves the rectangle alone.

It should be clear that the set V := {e, a, b, c} comprises every symmetry of the rectangle. We claim

that V forms a group whose binary operation is composition of functions.

Closure After applying any two symmetries in sequence, the rectangle still occu-

pies the same location on the page, the result of applying a single symmetry.

The composition table is shown and is easily be veriﬁed by, for instance,

drawing a smiley face on one side of a sheet of paper.

◦ e a b c

e e a b c

a a e c b

b b c e a

c c b a e

Original Face on back

Face up

The pictures conﬁrm b ◦ c = a: remember that the right side comes ﬁrst when composing

functions! The diagonal symmetry of the table shows that the operation is commutative.

Associativity Composition of functions is always associative (Exercise 9).

Identity The function e leaves the rectangle alone. Plainly e ◦ f = f ◦e = f for any symmetry f .

Inverse To ﬁnd the inverse of a symmetry, simply undo what you just did! In the case of the rectan-

gle, every symmetry is its own inverse.

The symmetries of the rectangle thus form an abelian group of order 4. This is named the Klein

four-group in honor of Felix Klein, a 19

century German mathematician whose application of group

theory transformed modern geometry. The letter V comes from the original German: vierergruppe.

There is little beneﬁt to being explicit, but if you choose co-ordinates with the origin at the center of the rectangle, these

functions can be written formulaically:

e(x, y) = (x, y), a(x, y) = (−x, −y), b(x, y) = (x, −y), c(x, y) = (−x, y)

A similar discussion applies to any geometric ﬁgure.

Theorem 2.23. The symmetries of any geometric ﬁgure form a group under composition.

The orientation-preserving symmetries form a subgroup, often called the rotation group.

Example (2.15.4, cont.). Since the complex function z 7→ e

iθ

z rotates counter-clockwise by θ around

the origin, the circle group S

may be viewed as the group of rotations of the plane (or the circle).

Deﬁnition 2.24. A regular n-gon has two commonly associated symmetry groups.

Dihedral Group The full symmetry group D

has order 2n. It splits into two subsets of size n:

Rotations Labelled e, ρ

, . . . , ρ

n−1

where ρ

rotates counter-clockwise by

2πk

radians (

360k

°). The

identity e = ρ

is considered a rotation (by 0°).

Reﬂections These are typically labelled µ

or δ

Rotation group Denoted R

= {e, ρ

, . . . , ρ

n−1

}. This group is abelian, which follows because com-

position of rotations simply sums angles:

◦ρ

= ρ

j+k (mod n)

= ρ

k+j ( mod n)

= ρ

◦ρ

Example 2.25. Denote the elements of the dihedral group D

as in the picture, where labeling the

vertices 1, 2, 3 helps to keep track of things:



e, ρ

, ρ

, µ



Its Cayley table is below. Constructing the table from scratch is a lot

of work and is not worth memorizing!

The highlighted computation is µ

◦ ρ

= µ

(remember to ’do’ ρ

to the triangle ﬁrst!). To verify, we could again try the smiley face

trick, or alternatively consider the movement of a vertex:

moves vertex 1 to vertex 3; µ

moves this to vertex 2.

Since the composition of a rotation and a reﬂection is a

reﬂection (the triangle has been ﬂipped over once!), the

result must be the reﬂection mapping 1 7→ 2, namely µ

The lack of symmetry in the Cayley table shows that D

is a non-

abelian group: indeed

◦µ

= µ

= µ

= µ

◦ρ

◦ e ρ

e e ρ

e µ

e ρ

The Cayley table for the (abelian) rotation group R

= {e, ρ

, ρ

} is visible in the top left corner.

In low dimensions, orientation-preserving means that a transformation doesn’t change the usual right-hand rule (e.g.,

cross products). In two dimensions these are precisely the planar rotations. In three dimensions a general orientation-

preserving symmetry is the composition of two pure rotations (recall spherical polar co-ordinates).

Geometric Subgroup Relations

These are often straightforward to observe by drawing two shapes in such a way that all the symme-

tries of one are also symmetries of the other. Since the symmetries of both shapes form a group, this

pictorial approach justiﬁes the only necessary condition in Deﬁnition 2.12: the subset property.

Examples 2.26. 1. For any n, we see that R

< S

: every rotation of a regular n-gon is also a rotation

of a circle (with the same center).

2. Consider a regular hexagon, inside which have been drawn two equilateral triangles. Every

symmetry of either triangle is also a symmetry the hexagon. We conclude:

(a) R

< R

. Be careful with notation! With respect to the hexagon, ρ

is rotation counter-

clockwise by 60k°, whence the subgroup relation should be written

= {e, ρ

, ρ

} < R

= {e, ρ

, ρ

}

Also note that both triangles have the same rotation group.

(b) D

< D

. This is a little more complicated. Labeling the reﬂections µ

, . . . , µ

as in the

picture, we see that the two triangles actually have different (full) symmetry groups:

= {e, ρ

, ρ

, µ

} < D

and D

= {e, ρ

, ρ

, µ

} < D

Otherwise said, D

has two distinct subgroups that look like D

Matrix Groups

As observed in any elementary linear algebra course (see also Exercise 10), matrix multiplication is

associative. This quickly yields several examples.

Example 2.27. The general linear group comprises the invertible n × n matrices under multiplication.

For this course, only such matrices with real number entries will be encountered:

(R ) =



A ∈ M

(R ) : det A = 0



(non-abelian when n ≥ 2)

Since associativity holds in general, we need only verify the other three axioms.

Closure follows from the familiar result det AB = det A det B.

The identity (drum roll. . . ) is the identity matrix I.

Finally, invertibility is assumed. Part 3 of Theorem 2.11 should now seem very

familiar: (xy)

−1

= y

−1

I =







1 0

0 1







Matrix subgroups

The general linear group GL

(R ) has many subgroups. Here is one; some others are in the Exercises.

Example 2.28. The orthogonal group O

(R ) = {A ∈ M

(R ) : A

A = I} consists of those matrices

whose inverse equals their transpose (A

−1

= A

). We verify that this is a subgroup of GL

(R ) using

the subgroup criterion (Theorem 2.14) and simple matrix properties.

Non-empty subset Every orthogonal matrix is invertible, whence O

(R ) ⊆ GL

(R ). This is imme-

diate in two ways: if A ∈ O

(R ), then,

A = I =⇒ A

−1

= A

exists, or,

1 = det I = det A det A

= (det A)

=⇒ det A = 0

Moreover, I

I = I

= I, so I ∈ O

(R ): we have non-emptiness.

Closure Suppose A, B ∈ O

(R ). Then

(AB)

(AB) = B

AB = B

IB = B

B = I =⇒ AB ∈ O

(R )

Inverses Suppose A ∈ O

(R ). Then

−1

)

−1

= (A

)

= (AA

)

= I

= I =⇒ A

−1

∈ O

(R )

The 2 ×2 orthogonal matrices can be interpreted as rotations and reﬂections.

For instance, the matrix

√



1 −1

1 1



∈ O

(R ) rotates the plane counter-clockwise by 45°.

Exercises 2.4. Key concepts: Klein 4-group V Dihedral group D

Rotation group R

Geometric subgroup relations General linear group GL

(R )

1. Use Theorem 2.14 to explain why the set of rotations of a planar ﬁgure is a subgroup of its full

symmetry group (rotations and reﬂections).

2. Explicitly state the Cayley table for the rotation group R

of a square.

3. Find the subgroup diagram of the Klein four-group. Explain how you know you are correct.

4. Repeat the previous question for the rotation group R

5. (a) Find all subgroups and the subgroup diagram for the group D

(Don’t worry about being rigorous as to how you know you’ve found them all.)

(b) Describe the symmetry group and Cayley table of a non-equilateral isosceles triangle. What

about a scalene triangle?

You might have seen this in another course. Left-multiplication by:

•



cos θ −sin θ

sin θ cos θ



rotates vectors counter-clockwise by θ radians.

•



cos θ sin θ

sin θ −cos θ



reﬂects across the line making angle θ/2 with the positive real axis.

This interpretation allows us to view D

as a subgroup of O

(R).

6. (a) Represent the elements of the Klein four-group V (as in Footnote 7) using matrix notation

(i.e. a is left-multiplication by what matrix). As such, identify V as a subgroup of O

(R ).

(b) Modeling Example 2.26, draw three pictures which describe different ways in which V

may be viewed as a subgroup of D

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. Prove that each set of matrices forms a group under multiplication (don’t memorize these un-

less you really love matrices. . . ).

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

(Z ) =



A ∈ M

(Z ) : det A = 1



: all entries in these matrices are integers.

(Hint: look up the classical adjoint adj A of a square matrix)

Now construct a diagram showing the subgroup relationships between the groups

(R ), SL

(R ), O

(R ), SO

(R ), Q

, SL

(Z )

9. (a) Let X be any set. Prove that composition of functions f : X → X is associative.

(Hint: ( f ◦ g) ◦h = f ◦(g ◦h) means that both functions do the same thing to the same input. . . )

(b) Suppose X contains at least two distinct elements a = b. Prove that there exist functions

f , g : X → X for which f ◦ g = g ◦ f .

10. (a) Prove that matrix multiplication of (real square) matrices is associative.

(Hint: If A has entries (a

), etc., what are the pq

entries of the matrices A(BC) and (AB)C?)

(b) Show that multiplication of (invertible) n ×n matrices is non-commutative when n ≥ 2.

11. Prove that D

is non-abelian (n ≥ 3).

(Hint: label vertices and proceed as is Example 2.25)

12. Consider rotating (in 3D) a regular tetrahedron. Any face (equilat-

eral triangle) may be rotated to its desired location (four options),

in which it has three possible orientations. The rotation group of

the tetrahedron therefore has 4 ×3 = 12 elements.

(a) Find the order of the rotation group of a cube.

(b) Repeat for a regular octahedron. Give a geometric reason

why your answer is the same as part (a).

(Hint: Try joining the midpoints of each face. . . ).

Common polyhedral dice

In case you don’t recognize it, the pictured red die is not one of the ﬁve Platonic solids: it has

ten kite-shaped faces, and its rotation group has order 10. We’ll return to these examples in

later sections.

2.5 Homomorphisms & Isomorphisms

In the previous sections, you should have felt like you were encountering similar examples in dif-

ferent contexts. A key goal of abstract mathematics is the comparison of similar/identical structures

with outwardly different appearances. The standard approach to such comparison is uses functions.

Example 2.29. Compare the rotation group R

of an equilateral triangle to the modular arithmetic

group Z

. Their Cayley tables look almost identical, particularly if we write ρ

for the identity in R

To a mathematician, the groups have the same structure; they are merely labelled differently.

Relabelling means deﬁning an invertible function µ : R

→ Z

the obvious choice from looking at the tables is µ(ρ

) = k.

Since the tables describe all possible interactions between the

elements of each group, it is clear that µ satisﬁes

∀ρ

, ρ

∈ R

, µ(ρ

◦ρ

) = µ(ρ

) +

µ(ρ

)

◦ ρ

0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

, ◦) (Z

, +

)

Indeed, both sides simply equal j +

k! This is a critical formula. To see why, suppose we are given

remainders x, y ∈ Z

and consider two courses of action:

1. First combine the remainders x +

y in Z

, then map to R

using the function to obtain µ(x +

y).

2. First map both remainders to R

using µ, then combine in R

to obtain µ(x) ◦µ(y).

Regardless of the order (combine/map or map/combine) we always obtain the same result! Such

structure-preserving functions are at the heart of abstract algebra.

Deﬁnition 2.30 (Homo- & Isomorphisms). 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)

An isomorphism

of binary structures G, H is a bijective/invertible homomorphism µ : G → H.

Binary structures G, H are isomorphic, written G

∼

H, if there exists some isomorphism µ : G → H.

The notation is typical: µ (rather than ϕ) is often used when we know we have an isomorphism. For

most of these notes (certainly after this chapter), all binary structures will be groups.

Examples 2.31. 1. (2.29 cont.) We have isomorphic groups R

∼

. Indeed the function µ : R

→ Z

is an isomorphism of groups (or group isomorphism).

2. The function ϕ : (N, +) → (R, +) deﬁned by ϕ(x) =

√

2x is a homomorphism (of binary

structures: (N, +) is not a group!),

ϕ(x + y) =

√

2(x + y) =

√

2x +

√

2y = ϕ(x) + ϕ(y)

As before, it is worth spelling this out:

Sum then map ϕ(x + y) gives the same result as map then sum ϕ(x) + ϕ(y).

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

3. If V, W are vector spaces then every linear map T : V → W is a group homomorphism:

∀v

, v

∈ V, T(v

+ v

) = T(v

) + T(v

)

You’ve been encountering homomorphisms your entire mathematical career: for instance, both

the calculus identity

( f + g) =

d f

and the distributive law of matrix multiplication

A(x + y) = Ax + Ay are homomorphism properties!

4. (Trivial homomorphism) If G and L are any groups, then the function ϕ : G → L deﬁned by

ϕ(g) = e

(the identity in L) is a homomorphism:

∀x, y ∈ G, ϕ (xy) = e

= (e

)

= ϕ(x)ϕ (y)

5. (Inclusion map) If H is a subgroup of G, then ϕ(x) = x deﬁnes a homomorphism ϕ : H → G:

∀x, y ∈ G, ϕ (xy) = xy = ϕ(x)ϕ(y)

6. The function ϕ(ρ

) = ρ

2k (mod 4)

is a homomorphism ϕ : R

→ R

ϕ(ρ

◦ρ

) = ϕ(ρ

j+k (mod 4)

) = ρ

2(j+k) (mod 4)

= ρ

2j (mod 4)

◦ρ

2k (mod 4)

= ϕ(ρ

) ◦ϕ(ρ

)

Establishing Isomorphicity

We must do four things if we suspect binary structures (G, ∗) and (H, ⋆) to be isomorphic:

Deﬁnition: Deﬁne µ : G → H and, if necessary, verify that it is a function.

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

Injectivity/1–1: Check that µ(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, and injectivity/surjectivity can be combined if you

manage to exhibit an explicit inverse function µ

−1

: H → G. If you are unsure how to start, often the

best thing is to play with the homomorphism property itself.

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

Deﬁnition: The obvious candidate

is ϕ(x) =

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

Homomorphism: ϕ(x + y) =

(x + y) =

x +

y = ϕ(x) + ϕ(y)

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

x =

y =⇒ x = y.

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

z =

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

The last steps are essentially the observation that ϕ

−1

(z) =

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

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

If G is a set of equivalence classes, we also need to check that ϕ is well-deﬁned. This subtlety is why we haven’t (yet)

had an example where Z

is the domain of a homomorphism. We will do so later (Example 3.5.2, Theorem 3.7, etc.).

2. We prove that (R, +)

∼

, ·): these are isomorphic abelian groups (recall that R

= (0, ∞)

is the set of positive real numbers).

Deﬁnition/Homomorphism: We need a bijective function µ : R → R

which converts addi-

tion to multiplication µ(x + y) = µ(x)µ(y). But exponentiation does exactly this: deﬁning

µ(x) = e

, we see that the homomorphism property is the familiar exponential law!

µ(x + y) = e

x+y

= e

= µ(x)µ (y)

Bijectivity: µ

−1

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

Other exponential functions also provide suitable isomorphisms: e.g. 2

, 10

, etc.

Demonstrating Non-Isomorphicity (Structural Properties)

Suppose we suspect that binary structures (G, ∗) and (H, ⋆ ) are non-isomorphic. Unless G, H are very

small, individually verifying that every possible function µ : G → H is a non-isomorphism would

be unrealistic! Instead we consider structural properties: properties that isomorphic structures must

share. If any such is held by one structure but not the other, then the structures are non-isomorphic.

Here is a non-exhaustive list of structural properties; we’ll check some in Exercise 11. Throughout,

we assume that µ : (G, ∗) → (H, ⋆) is an isomorphism.

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

Commutativity & Associativity: Suppose (G, ∗) is commutative and let X, Y ∈ H. Since µ is surjec-

tive, we may write X = µ(x) and Y = µ(y) for some x, y ∈ G. The homomorphism property

now shows that (H, ⋆) is commutative:

X ⋆ Y = µ(x) ⋆ µ(y) = µ(x ∗y) = µ(y ∗ x) = µ(y) ⋆ µ(x) = Y ⋆ X

The argument for associativity is similar, though more tedious.

Identities & Inverses: If (G, ∗) has identity e, then µ(e) is the identity for (H, ⋆). Similarly µ maps

inverses to inverses.

Solutions to equations: Related equations have the same number of solutions. For instance,

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

says that the equations x ∗x = x (in G) and z ⋆ z = z (in H) have the same number of solutions.

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

Examples 2.33. 1. Recall that N

= {0, 1, 2, 3, . . .}. Since (N

, +) contains the identity element 0

whereas (N, +) has no identity, we conclude that these binary structures are non-isomorphic.

2. Z

is not isomorphic to D

since the two groups have different orders (5 and 6).

You might think, “How can I turn an even number into a multiple of three?” Of perhaps you start by thinking about

the homomorphism property: multiplication by a constant certainly satisﬁes ϕ(x + y) = ϕ(x) + ϕ(y).

Such solutions are called idempotents; thus existence of idempotents is itself a structural property.

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

For instance, the ﬁrst is commutative while the second is not.

4. GL

(R ) and (R, +) are non-isomorphic for the same reason: the ﬁrst

is non-abelian and the second abelian.

∗ a b

a a b

b b a

⋆ c d

c c d

d c d

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

6. The groups (Z, +) and (Q, +) have the same (countably inﬁnite) order, and are both abelian. To

see that they are non-isomorphic, consider the equation x + x = 1 which has no solutions in Z.

If µ : Z → Q were an isomorphism, then the equation µ(x) + µ(x) = µ(1) does have a solution

y = µ(x) =

µ(1) in Q. But then x = µ

−1

(y) solves the original equation: contradiction!

7. (S

, ·) and (R, +) are non-isomorphic: consider the equations x ∗x = e. . .

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

Suppose µ : G → H is a bijection of sets, where one of G, H has a binary structure. A binary structure

may be deﬁned on the other by insisting that µ be an isomorphism.

Example 2.34. The function µ(x) = x

+ 8 is a bijection R → R. Starting with the binary (group)

structure (R, +) and treating µ as an isomorphism, we may create a new isomorphic structure. There

are two ways to do this:

Pull-back: Suppose µ : (R, ∗) → (R, +). Since µ(x ∗y) = µ(x) + µ(y), the new operation ∗ must be

x ∗y := µ

−1



µ(x) + µ(y)



= µ

−1

+ y

+ 16) =

+ y

+ 8

All structural properties transfer from (R, +) to (R, ∗): for instance, (R, ∗) is an abelian group

with identity element

−1

(0) =

√

−8 = −2

As a sanity check, observe that we really do have x ∗(−2) =

+ (−2)

+ 8 = x!

Push-forward: View µ : (R, +) → (R, ∗) as an isomorphism. Computation of ∗ is an exercise.

“Up to Isomorphism”

This phrase is ubiquitous in group theory. To illustrate, consider that if



{e, a}, ∗



is a group with identity e, then its Cayley table must be as shown (Example 2.10.6).

Otherwise said: there may be inﬁnitely many distinct groups of order two, but all are

isomorphic to each other. This is too wordy, so a mathematician might instead say:

∗ e a

e e a

a a e

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

Make sure you include the snippet “up to isomorphism,” for otherwise the sentence is false!

The start of group theory can feel very challenging. With its focus on functions and its unfamiliar

words, this last introductory section likely seems particularly so. Complete ﬂuency with the vocab-

ulary is not required at this stage. The remaining chapters provide plenty opportunity to reinforce the

language introduced in this chapter.

For the same reason, several of the following Exercises (particularly number 11 onwards) will likely

seem difﬁcult. Try these (and discuss them) now, even if you aren’t sure what to do; return later

when you feel more comfortable. Learning abstract concepts isn’t quick; give the ideas a chance to

sink in. By the end of the course, these Exercises should seem much easier!

Exercises 2.5. Key concepts: Homomorphism Isomorphism Injective/surjective/bijective

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

(a) µ : (Z, ∗) → (Z, +) (b) µ : (Z, ∗) → (Z, ·) (c) µ : (Z, ∗) → (Z, max(a, b))

5. Finish Example 2.34 by computing the push-forward X ∗Y for any X, Y ∈ R.

6. µ(x) = x

is a bijection µ : R

→ R

. Find x ∗y if µ is to be an isomorphism.

(a) µ : (R

, ∗) → (R

, +) (b) µ : (R

, +) → (R

, ∗) (c) µ : (R

, ∗) → (R

, ·)

7. Show that x ∗y = x + y −xy is the pull-back of (R

, ·) to R \ {1} by µ(x) = 1 − x. Use this to

provide an alternative quick argument for Exercise 2.1.9.

8. Recall Exercise 2.3.6c. Prove that the Klein four-group and Z

are isomorphic.

9. (a) Prove that S :=



a −b

b a



∈ M

(R )



forms a group under matrix addition.

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

cation.



a −b

b a



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

: T → C

are both isomorphisms

ϕ : (S, +)

∼

(C, +), ϕ

: (T, ·)

∼

, ·)

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

10. (Recall Exercise 2.4.8 and Footnote 9) Prove that S

∼

(R ) via an isomorphism

µ(e

iθ

) =



cos θ −sin θ

sin θ cos θ



11. Suppose µ : (G, ∗) → (H, ⋆) is an isomorphism of binary structures. Prove:

(a) If e is the identity for G, then µ(e) is the identity for H.

(b) If x ∈ G has an inverse y, then µ(y) is an inverse to µ(x) (in H).

) = e

and ϕ(x

−1

) =



ϕ(x)



−1

For a challenge: What happens if ϕ is merely a homomorphism of binary structures?

12. Given a group homomorphism ϕ : G → H , deﬁne the image ϕ(G) and kernel ker ϕ as follows:

ϕ(G) = Im ϕ =



ϕ(x) : x ∈ G



, ker ϕ :=



x ∈ G : ϕ(x) = e



(a) Compute the image and kernel of ϕ : (R

, ·) → (R

, ·) where ϕ(x) = x

(b) Prove that ϕ(G) is a subgroup of H (in general, not just for the example in (a)!).

(We’ll return to these important concepts later)

13. The groups (Q, +) and (Q

, ·) are both abelian and both have the same cardinality: nonethe-

less, we prove that they are non-isomorphic.

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 the number of solutions to the equations in part (a), obtain a contradiction

and hence conclude that ( Q, +) ≇ (Q

, ·).

(Extra challenge) Suppose ϕ : (Q, +) → (R, ·) is a homomorphism (of binary structures) and that

ϕ(1) = a: ﬁnd a formula for ϕ(x).

14. Recall the magic square property (Exercise 2.1.11).

(a) Up to isomorphism, explain why there is a unique group of order three.

(This is another reason the groups in Example 2.29 must be isomorphic!)

(b) Show that, up to isomorphism, there are precisely two groups of order four.

(Hint: 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 group Z

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

groups G, H, K:

Reﬂexivity: G

∼

Symmetry: G

∼

H =⇒ H

∼

Transitivity: G

∼

H and H

∼

K =⇒ G

∼

3 Cyclic & Finite Abelian Groups

In this chapter we consider a general family of groups and see how to combine these to describe any

ﬁnite abelian group.

3.1 Deﬁnitions and Basic Examples

The foundational idea of a cyclic group is that it may be generated from a single element.

Examples 3.1. 1. The integers (Z, +) are generated by the element 1: all integers may be produced

by repeatedly combining 1 using only the group operation (+) and inverses (−). For instance,

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

2. The modular arithmetic groups (Z

, +

) (Section 2.3) are also generated by (the remainder) 1.

Since the group is ﬁnite, inverses are not necessary. For instance,

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

3. The group R

of rotations of a regular n-gon (Deﬁnition 2.24) is generated by the ‘1-step’ rota-

tion ρ

: that is, ρ

= ρ

We formalize this idea by considering the subset of a group that may be produced from a single

element, the group operation, and inverses.

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

⟨

⟩

:= {g

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

−1

, e, g, g

, . . .}

is a subgroup of G. We call this the cyclic subgroup

generated by g.

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

Non-emptiness: Plainly g ∈

⟨

⟩

Closure: Every element of

⟨

⟩

has the form g

for some k ∈ Z. The required condition

follows from standard exponential notation (Deﬁnition 2.3): g

· g

= g

k+l

∈

⟨

⟩

Inverses: This is Exercise 2.1.7c: (g

)

−1

= g

−k

∈

⟨

⟩

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

⟨

⟩

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

⟨

⟩

≤ G.

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

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

Since this is an abstract result, the lemma is written multiplicatively. If G is an additive group, then cyclic subgroups

are written

⟨

⟩

= {ng : n ∈ Z} = {. . . , −2g, −g, 0, g, 2g, 3g, . . .}. As in Example 3.1.2, for ﬁnite cyclic groups convention

dictates that the identity element is written ﬁrst, e.g.

⟨

⟩

= {e, g, g

, . . . , g

n−1

Examples (3.1 cont). 1. Z =

⟨

⟩

⟨

−1

⟩

is generated by either 1 or −1. The cyclic subgroup

generated by 2 is the group of even numbers under addition

⟨

⟩

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

2. Z

is generated by both 1 and −1 = n −1, but may have other generators (we’ll consider how

to ﬁnd them all shortly). For instance, Z

is generated also by 2:

⟨

⟩

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

3. R

⟨

⟩

= {e, ρ

, ρ

, . . . , ρ

n−1

}. As with Z

, this group typically has other generators.

Another commonly encountered family of cyclic groups arise as subgroups of (C

, ·) (or (S

, ·)).

Deﬁnition 3.4 (Roots of Unity). Let n ∈ N. The group of n

roots of unity U

is the cyclic subgroup

of (S

, ·) generated by ζ := e

2πi

⟨

⟩



1, ζ, ζ

, ··· , ζ

n−1



These are precisely the n complex solutions to the equation z

= 1. To emphasize n, write ζ

= e

2πi

For instance U

⟨

−1

⟩

= {1, −1} and U

⟨

⟩

= {1, i, −1, −i}. In general,

the n

roots are the vertices of a regular n-gon centered at 0 with radius 1:



= 1 and arg ζ

= arg e

2πk

= k arg ζ

We stop listing the elements at ζ

n−1

since ζ

= e

2πi

= 1. The periodicity of

the complex exponential (e

iθ

= 1 ⇐⇒ θ ∈ 2πZ) results in a simple tie-in

with modular arithmetic:

= ζ

⇐⇒ 1 = ζ

k−l

= e

2πi(k−l)

⇐⇒ k ≡ l (mod n)

−1 1

−i

Seventh roots: ζ

= e

2πi

Examples 3.5. 1. Observe that ζ

= (e

2πi

)

= e

2πi

= ζ

This produces a subgroup relationship: writing ζ = ζ

, we have



1, ζ

, ζ



< U



1, ζ, ζ

, ζ



The picture makes this geometrically trivial (compare Example 2.26.2).

ζζ

2. (Example 2.29, cont.) Below is the Cayley table for U

. Writing 1 = ζ

and ζ = ζ

makes the

isomorphic relationship with (Z

, +

) and (R

, ◦) obvious: (U

, ·)

∼

, +

)

∼

, ◦).

· 1 ζ ζ

1 1 ζ ζ

ζ ζ ζ

1 ζ

· ζ

0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

◦ ρ

For a little practice here is a formal argument that Z

∼

: we show explicitly that

µ : Z

→ U

: x 7→ ζ

is an isomorphism. Since the domain Z

consists of equivalence classes, this requires a little care.

Well-deﬁnition: We must prove that if x = y in Z

, then µ(x) = µ(y).

Given x = y ∈ Z

, then (as integers) x = y + 3k for some integer k. But then

µ(x) = ζ

= ζ

x+3k

= ζ

(ζ

)

= ζ

= µ(y)

Homomorphism: µ(x + y) = ζ

x+y

= ζ

= µ(x)µ (y)

Injectivity: µ(x) = µ(y) =⇒ ζ

= ζ

=⇒ ζ

x−y

= 1 =⇒ x ≡ y (mod 3) =⇒ x = y in Z

(Notice how injectivity is the converse of well-deﬁnition!)

Surjectivity: range µ = {ζ

: x ∈ Z} = {1, ζ, ζ

} = U

, since ζ

x+3k

= ζ

In the next section we’ll essentially repeat this discussion in the abstract, so make sure this

example makes sense before moving on.

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

1. Compute the cyclic subgroup

⟨

⟩

of Z

(write the elements in the order generated).

2. Find/describe all the generators of each cyclic group.

(a) ( Z, +) (b) {2

−n

: n ∈ Z} under multiplication

, +

) (d)



a 0

0 a





0 b

−b 0



: a, b = ±1



under multiplication

3. State all cyclic subgroups of Z

. What is the order of each element?

4. Recall Example 2.25. What is the cyclic subgroup of D

generated by ρ

? Generated by µ

5. (a) Find all cyclic subgroups of the Klein four-group V. What is the order of each element?

(b) V is a ﬁnite non-cyclic group. Give an example of an inﬁnite non-cyclic group, and explain

how you know you are correct.

6. Compute the cyclic subgroup





of U

, listing its elements in the order generated.

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

8. (a) Show that Z

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

(b) What about Z

= {1, 3, 5, 7} under multiplication modulo 8? To what well-known group

is this isomorphic?

9. Suppose that a cyclic group G has order

≥ 3. Explain why it has at least two generators.

10. Modeling Example 3.5.2, prove explicitly that Z

∼

for any n ∈ N.

11. In contrast to the real case (Example 2.32.2), verify that ϕ : C → C

: z 7→ e

is a homomorphism

(C, +)

∼

, ·) but not an isomorphism.

3.2 The Classiﬁcation and Structure of Cyclic Groups

This section is signiﬁcantly more abstract that what has come before: take your time, read carefully,

and use the examples to help. Our goal is to describe general properties of all cyclic groups, including

their generators and subgroup structures. The ﬁrst result is, mercifully, very simple.

Lemma 3.6. Every cyclic group is abelian.

Proof. Let G =

⟨

⟩

. Any two elements of G can be written g

, g

for some k, l ∈ Z. The result follows

from standard exponential notation and the fact that addition of integers is commutative:

= g

k+l

= g

l+k

= g

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

Our major classiﬁcation theorem proves a pattern you’ve likely already guessed.

Theorem 3.7 (Isomorphs). Every cyclic group G =

⟨

⟩

is isomorphic either to Z or to some Z

• If G is inﬁnite, then G

∼

• If G is ﬁnite with order n, then G

∼

In either case, µ : Z

(n)

→ G : x 7→ g

is an explicit isomorphism.

To help understand the theorem and set up the proof, some remarks and examples are helpful.

Map Generator to Generator The isomorphism maps the generator 1 ∈ Z

(n)

to the generator g of G.

Together with the homomorphism property, this idea deﬁnes µ

µ(1) = g =⇒ µ(x) = µ(x + ···+ x) =



µ(1)



= g

This observation makes it easy to ﬁnd suitable isomorphisms in examples.

The Cyclic Group of Order n? The theorem says that, up to isomorphism, there is a unique cyclic

group of order n. For this reason, many algebraists use the symbol Z

(or C

for ‘cyclic’) to

refer to any example of a cyclic group of order n (e.g. R

, U

, etc.). For clarity, in these notes,

will always be the explicit group of remainders under addition modulo n.

The Order of G =

⟨

⟩

It is helpful to introduce a set of positive integers

S := {m ∈ N : g

= e} (mg = e if G is additive)

This set plays a crucial role in the proof, distinguishing the ﬁnite/inﬁnite cases and detecting

the order of G. . .

Examples 3.8. 1. Z

⟨

⟩

is additive, so S = {m ∈ N : m = 0 ∈ Z

} = {4, 8, 12, . . .}. The minimal

element 4 is plainly the order of

2. (Example 3.5.2) In U

⟨

⟩

, we have ζ

= 1 ⇐⇒ 3 | m, whence S = {3, 6, 9, . . .}. Plainly 3 is

the order of U

. Moreover µ(x) = ζ

is the isomorphism µ : Z

→ U

seen previously!

3. 5Z =

⟨

⟩

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

an isomorphism µ : Z → 5Z : x 7→ 5x (map the generator 1 of Z to the generator 5 of 5Z).

Proof. We ﬁrst establish that µ is a bijection. The generic cases depend on the minimal element of S.

Case 1: S = ∅. Suppose x > y and that g

= g

. Then g

x−y

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

elements . . . , g

−2

, g

−1

, e, g, g

, . . . are distinct, and so µ : Z → G : x 7→ g

is bijective.

Case 2: min S = n. We ﬁrst check that µ : Z

→ G : x 7→ g

is well-deﬁned:

y = x ∈ Z

=⇒ y = x + kn for some k ∈ Z (as integers)

=⇒ µ(y) = g

= g

x+kn

= g

)

= g

= µ(x) (n ∈ S, so g

= e)

This moreover tells us that G is ﬁnite (there are at most n distinct elements of G)

G =

⟨

⟩

= {. . . , g

−2

, g

−1

, e, g, g

, . . .} = {e, g, . . . , g

n−1

}

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

= g

=⇒ g

x−y

= e =⇒ x = y (0 ≤ x −y ≤ n −1 < n = min S)

We conclude that G = {e, g, . . . , g

n−1

} has order n, and that µ is a bijection.

Finally, note that the homomorphism property in both cases is merely standard exponential notation

µ(x + y) = g

x+y

= g

= µ(x)µ (y)

As advertised, the use of S in the proof yields a useful alternative notion for the order of an element.

Corollary 3.9 (Order of an element). If ﬁnite, the order of g equals the minimal positive integer n

for which g

= e. Moreover g

= e ⇐⇒ n | m.

Otherwise said, if g has order n, then S = {m ∈ N : g

= e} = {kn : k ∈ N} is the set of positive

multiples of n.

Examples 3.10. 1. The group of 7

roots of unity U

is isomorphic to Z

via µ : Z

→ U

: k 7→ ζ

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

= 1} is indeed the order of ζ

= e

2πi

2. ( R, +) is non-cyclic since its (uncountable) cardinality is larger than that of the integers. This is

also straightforward directly: if R =

⟨

⟩

were cyclic (x = 0), then we obtain the contradiction

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

⟨

⟩

= R ∋

The same argument shows that, for instance, that (Q, +) is non-cyclic.

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.

Multiplication by ξ essentially performs an irrational fraction (

√

) of a full rotation.

Subgroups of Cyclic Groups are also Cyclic!

For the remainder of this section we describe the complete subgroup structure of all cyclic groups.

Our approach is motivated by a simple example.

Example 3.11. The cyclic subgroup 2Z ≤ Z is generated by 2: the minimal positive integer in the

subgroup.

For an abstract subgroup H of a cyclic group G =

⟨

⟩

, our goal is to identify a suitable ‘minimal

element’ of H and then demonstrate that this generates H.

Theorem 3.12 (Subgroups of Cyclic Groups). Every subgroup of a cyclic group is cyclic.

Proof. Suppose H is a subgroup of G =

⟨

⟩

. Let s be the smallest positive integer

such that g

∈ H.

We prove that H is generated by g

by establishing the set equality H =

⟨

⟩

(⊇) Since H is a group, the closure and inverse axioms force (g

)

∈ H for all k ∈ Z.

(⊆) Let g

∈ H. We must prove that g

∈

⟨

⟩

. By the division algorithm, there exist unique

integers q, r such that

m = qs + r and 0 ≤ r < s

Since H satisﬁes the closure and inverse axioms,

= g

qs+r

= (g

)

=⇒ g

= (g

)

−q

∈ H (∗)

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

= (g

)

∈

⟨

⟩

If the proof seems hard, try rewriting it for our motivational example, where G = Z, H = 2Z and

s = 2; remember that G is additive, so (∗) is simply r = −2s + m ∈ 2Z!

We ﬁnish by considering the ﬁnite and inﬁnite cases separately. The latter is very simple.

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

∼

The proof as an exercise—just generalize the following generic example!

Example 3.14. We write things out explicitly in additive notation when G = Z. By Theorem 3.12,

every subgroup has the form

⟨

⟩

= sZ (the multiples of s ∈ Z). There are two generic situations:

• If s = 0 we have the trivial subgroup:

⟨

⟩

= {0}.

• If s = 0, then sZ is isomorphic to Z via the isomorphism µ : Z → sZ : x 7→ sx.

This exists for two reasons:

1. H is a non-empty subset of G =

⟨

⟩

and so must contain some element g

. We may assume k ≥ 1 since the subgroup

also contains g

−k

(inverse axiom).

2. The set of natural numbers {k ∈ N : g

∈ H} is non-empty and so (well-ordering) has a minimal element s.

Note that s = 1 ⇐⇒ H =

⟨

⟩

is the trivial subgroup (g

= e

= e ∈ H). In this special case the division algorithm argument

is trivial: every m = q · 1 + 0 is immediately a multiple of 1, and g

= e for all m.

Finite cyclic groups are more complicated, so we ﬁrst illustrate the main result with an example.

Example 3.15. Consider the 6

roots of unity U

= {1, ζ, ζ

, ζ

}. Since every subgroup of U

necessarily cyclic (Theorem 3.12), it is enough to consider each cyclic subgroup

⟨

⟩

in turn (for each

z ∈ U

). We obtain three proper subgroups, as arranged in the subgroup diagram below.

z subgroup

⟨

⟩

1 {1}

ζ {1, ζ, ζ

, ζ

}

{1, ζ

, ζ

}

{1, ζ

}

{1, ζ

, ζ

}

{1, ζ

, ζ

, ζ}

⟨

⟩

= U





= U





= U

⟨

⟩

= U

Observe the repetitions:

⟨

⟩





= U

and









= U

. Note also that we really do have

equality of groups here: for instance, ζ

= (e

2πi

)

= e

2πi

is a generator of 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

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

Since U

∼

, differences are entirely notational. One subtle distinction is that we don’t use equals in

the second subgroup diagram: for instance,

⟨

⟩

= {0, 2, 4} is isomorphic but not equal to Z

= {0, 1, 2}.

The Example should suggest a pattern (previewed in Lemma 2.21): the subgroups of Z

are precisely

those generated by the divisors of n, with one subgroup for each divisor:

d | n =⇒

⟨

⟩

∼

, moreover gcd(s, n) = d =⇒

⟨

⟩

⟨

⟩

Our ﬁnal result merely asserts this for general ﬁnite cyclic groups.

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

⟨

⟩

have order n. For each divisor of n,

G has a unique subgroup with this order; these are moreover the only subgroups of G.

More precisely,

d = gcd(s, n) =⇒

⟨

⟩

= ⟨g

⟩, where this subgroup has order

(isomorphic to Z

)

In particular: g

has order

gcd(s,n)

and generates G if and only if gcd(s, n) = 1.

As with Theorem 3.12, if the proof seems hard, try rewriting it when G = Z

Proof. Suppose d = gcd(s, n). We prove set inclusion in both directions.

(⊆) Since d divides s, we have s = kd for some k ∈ Z. But then

= (g

)

∈





=⇒ (g

)

= (g

)

=⇒

⟨

⟩

⊆





(⊇) Apply B

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

= (g

)

= (g

)

∈

⟨

⟩

=⇒





⊆

⟨

⟩

To ﬁnish, note that since d | n, there are precisely

elements of





⟨g

⟩ =



e, g

, g

, . . . , g

n−d



Example 3.17. 1. Z

is generated by 1, 3, 5 and 7: precisely the elements for which gcd(s, 8) = 1. For

example,

⟨

⟩

= {5, 2, 7, 4, 1, 6, 3, 0} = Z

Similarly, the subgroup

⟨

⟩

= {6, 4, 2, 0} has order 4 =

gcd(6,8)

. The complete

collection of subgroups is in the table: the ﬁrst column lists each divisor d of 8 (the

possible values of gcd(x, 8)), while the second column has the explicit subgroup

generated by each x, and the group isomorph Z

. The ‘smallest’ generator is used

for each subgroup in the subgroup diagram.

d = gcd(x, 8) Subgroup

⟨

⟩

∼

1 {0, 1, 2, 3, 4, 5, 6, 7}= Z

2 {0, 2, 4, 6}

∼

4 {0, 4}

∼

8 {0}

∼

⟨

⟩

= Z

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

2. We repeat the discussion for Z

d = gcd(x, 30) Subgroup

⟨

⟩

∼

1 {0, 1, 2, 3, . . . , 7, . . . , 11, 12, 13, . . .

17, 18, 19, . . . , 23, . . . , 29}= Z

2 {0, 2, 4, 6, 8, 10, 12, 14, 16,

18, 20, 22, 24, 26, 28}

∼

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

∼

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

∼

{0, 6, 12, 18, 24}

∼

10 {0, 10, 20}

∼

15 {0, 15}

∼

30 {0}

∼

⟨

⟩

= Z

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

⟨

⟩

∼

You should consider how the shape of the subgroup diagram for Z

depends on the prime decomposi-

tion of n: for instance, each prime appears exactly once in 30 = 2 · 3 ·5.

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

= e ⇐⇒ (ord g) | m

⟨

⟩

∼

=⇒

⟨

⟩

∼

gcd(s,n)

Subgroup diagrams for ﬁnite cyclic groups

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

(a) ( Z

, +

) (b) (Z

, +

2. A generator of the cyclic group U

group is known as a primitive n

root of unity. For instance,

the primitive 4

roots are ±i. Find all the primitive roots when:

(a) n = 5 (b) n = 6 (c) n = 8 (d) n = 15

3. Find the complete subgroup diagram of U

where p, q are distinct primes.

(Hint: Try U

ﬁrst if this seems too difﬁcult)

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

, +

) and give a generator for each.

5. (a) Suppose µ : G → H is an isomorphism of cyclic groups. If g is a generator of G, prove that

µ(g) is a generator of H. Do you really need µ to be an isomorphism here?

(b) If G is an inﬁnite cyclic group, how many generators has it got?

→ Z

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

has order

gcd(s,n)

. Explain.

7. Suppose G =

⟨

⟩

is inﬁnite and H =

⟨

⟩

is an inﬁnite subgroup. Prove Corollary 3.13 by

describing an isomorphism µ : G → H.

8. Prove Corollary 3.9: 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. For which real numbers θ is the multiplicative cyclic group G =



2πiθ



≤ C

ﬁnite? Describe

the order of G in terms of θ.

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

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

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

(b) If m, n ∈ (Z, +), show X = {m, n} generates dZ, where d = gcd( m, n).

set of two elements which generates V.

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

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

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

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

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

3.3 Direct Products & Finite Abelian Groups

In this section we discuss a straightforward way to create new groups from old using the Cartesian

product. In the abstract, this discussion applies to any groups, though the ingredients in most of our

examples will be cyclic.

Example 3.18. Given Z

= {0, 1}, the Cartesian product

×Z



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



has four elements. This set inherits a binary structure via addition of co-ordinates

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

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

, +

). This binary operation has an addition table

that should looks very familiar: it has exactly the same structure as the Klein four-group!

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

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

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

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

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

↭

◦ e a b c

e e a b c

a a e c b

b b c e a

c c b a e

We conclude that Z

×Z

∼

V is indeed a group.

This type of construction works in general.

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

∏

k=1

= G

×···× G

, (x

, . . . , x

) ·(y

, . . . , y

) := (x

, . . . , x

)

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

is abelian.

The proof is a simple exercise. Being a Cartesian product, a direct product has order equal to the

product of the orders of its components



∏

k=1



∏

k=1

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

, +

) and (Z

, +

) is

×Z



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



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

, +

) and thus cyclic.

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

⟨

(1, 1)

⟩



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



= Z

×Z

In accordance with Theorem 3.7, µ(x) = (x, x) deﬁnes an isomorphism µ : Z

∼

×Z

2. If each G

is abelian and written additively, the direct product is sometimes called a direct sum,

k=1

= G

⊕···⊕ G

We won’t use this notation, though you’ve likely encountered it in linear algebra: for instance,

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 3.20.1, we saw that the element (1, 1) ∈ Z

× Z

had order 6 and thus generated the

group. There is another general pattern here; to help spot it, consider another example.

Example 3.21. We ﬁnd the order of the element (10, 2) ∈ Z

×Z

? Recall Corollary 3.16:

• 10 ∈ Z

has order 6 =

gcd(10,12)

• 2 ∈ Z

has order 4 =

gcd(2,8)

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

the second resets after 4. For both to reset simultaneously, 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 3.22. Suppose x

∈ G

has order r

. Then (x

, . . . , x

) ∈

∏

k=1

has order lcm(r

, . . . , r

Proof. We appeal to Corollary 3.9:

, . . . , 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 3.23. Find the order of (1, 3, 2, 6) ∈ Z

×Z

Again with reference to Corollary 3.16, the element has order

lcm



gcd(1,4)

gcd(3,7)

gcd(2,5)

gcd(6,20)



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

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

The slight difference in the concepts when there are inﬁnitely many factors is not worth discussing here.

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

Recall that Z

×Z

∼

is cyclic, whereas Z

×Z

∼

V is non-cyclic. It is reasonable to hypothesize

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

Corollary 3.24. Z

×Z

is cyclic ⇐⇒ gcd(m, n) = 1. In such a case Z

×Z

∼

More generally:

• Z

×···× Z

∼

···m

⇐⇒ ∀i = j, gcd(m

, m

) = 1.

• If n = p

··· p

is written in its prime factorization, then Z

∼

×···× Z

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

(⇐) Suppose gcd(m, n) = 1. We claim that (1, 1) is a generator of Z

× Z

. But this element has

order lcm(m, n) =

gcd(m,n)

= mn =

×Z

, so we’re done.

(⇒) This is Exercise 11.

Examples 3.25. 1. (Example 3.23) The group Z

×Z

is non-cyclic since, for instance,

gcd( 4, 20) = 1. The maximum order of an element in this group is

lcm( 4, 7, 5, 20) = 140 < 2800 =

×Z

2. Is Z

×Z

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

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

as a direct product!

420

∼

×Z

140

∼

×Z

105

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

∼

×Z

We may combine/permute the factors of 420 = 2

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

= 4.

The Fundamental Theorem of Finite(ly Generated) Abelian Groups

Direct products create ﬁnite abelian groups from cyclic building blocks. Our ﬁnal result provides a

powerful converse, though we don’t have the technology to prove it (yet—though see Section 7.3).

Theorem 3.26. Every ﬁnite abelian group is isomorphic to a group of the form

×···× Z

where each r

∈ N and the p

are primes (not necessarily distinct). More generally, every ﬁnitely

generated abelian group (see Exercise 3.2.11) is isomorphic to some

×···× Z

×Z ×···× Z

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

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

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

G is abelian of order 81 and,

G has an element of order 27 and,

All elements of G have order ≤ 27







=⇒ G

∼

×Z

2. Since 450 = 2 ·3

·5

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

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

(a) Z

×Z

∼

450

(cyclic, maximum order of an element 450)

(b) Z

×Z

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

)

×Z

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

·5)

(d) Z

×Z

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

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

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

order abelian non-abelian

1 Z

2 Z

3 Z

4 Z

, V

∼

×Z

5 Z

6 Z

∼

×Z

∼

7 Z

8 Z

, Z

×Z

, Z

×Z

, Q

9 Z

, Z

×Z

10 Z

∼

×Z

11 Z

12 Z

∼

×Z

, Z

×Z

∼

×Z

, A

, Q

13 Z

14 Z

∼

×Z

15 Z

∼

×Z

16 Z

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

(nine)

The Fundamental Theorem & Corollary 3.24 supply the abelian groups. In the non-abelian column:

• The dihedral groups D

are the familiar symmetries of a regular n-gon (Deﬁnition 2.24).

• S

and A

will be described in Chapter 4 (symmetric and alternating groups).

• Q

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

is related.

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

and the direct product Z

× Q

are explicit examples. You might suspect from the table that all non-abelian groups have even order:

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

Exercises 3.3. Key concepts: Direct product Order of an element via lcm Cyclic/gcd criteria

Fundamental theorem of ﬁnitely generated abelian groups

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

(a) Z

×Z

(b) Z

×Z

2. Prove Theorem 3.19 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 3.24)

8. State three non-isomorphic groups of order 50.

9. Let p, q be distinct primes. Up to isomorphism, how many abelian groups have order p

10. Give a simple explanation for why D

is not isomorphic to Z

× Q

11. Complete the proof of Corollary 3.24: 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

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

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

14. Suppose G is ﬁnite abelian and that m divides

. Prove that G has a subgroup of order m.

(Hint: use the prime decomposition of m and the Fundamental Theorem)

15. Suppose G is an abelian group and let T ⊆ G be the subset of elements with ﬁnite order.

(a) Prove that T is a subgroup of G.

(Your proof shouldn’t use the Fundamental Theorem—why not?)

(b) Compute T when:

i. G = (R

, ·) ii. G = (S

, ·)

4 Permutations and Orbits

In this chapter we return to the origins of group theory by considering the ways in which a set may

be reordered.

4.1 The Symmetric Group, Cycle Notation & Cayley’s Theorem

Deﬁnition 4.1. Let A be a set. A permutation of 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 4.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. S

= S

{1,2,3}

has six elements and is non-abelian. We have met this group before: note how every

rotation/reﬂection of the triangle in Example 2.25 corresponds to a permutation of the three

vertices 1, 2, 3. Otherwise said, S

is isomorphic to the dihedral group D

Lemma 4.3. 1. S

is a group under composition of functions.

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

is non-abelian.

3. The order of S

is n! (Warning! The order of S

is not the subscript n)

4. S

≤ S

whenever m ≤ n (Strictly, S

contains a subgroup isomorphic to S

)

Proof. 1. The axioms follow from familiar function properties. Write out the details if you’re unsure.

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

Associativity: Composition of functions is associative (Exercise 2.4.9).

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 use juxtaposition: στ := σ ◦ τ. Exponentiation therefore means self-composition:

e.g. σ

= σσσ = σ ◦ σ ◦ σ. Remember also that στ is a function A → A, and that evaluation means

that we act with τ ﬁrst:

∀a ∈ A, στ(a) = σ



τ(a)



This choice of A makes S

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

usually also called S

(see Exercise 8 and the remark regarding “up to isomorphism” on Page 20).

Cycle Notation

Efﬁcient computation in S

is facilitated by some new notation.

Deﬁnition 4.4. Suppose {a

, . . . , a

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

···a

) ∈ S

is the function

σ :











7→ a

j+1

if j < k

7→ a

x 7→ x if x ∈ {a

, . . . , a

}

···

all other x

Cycles (a

···a

) and (b

···b

) are disjoint if {a

, . . . , a

}∩{b

, . . . , b

} = ∅.

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

Example 4.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, remember that both are functions and you won’t go wrong!

x 1 2 3 4

τ(x) 4 2 3 1

στ(x) 2 1 4 3

στ : 1







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

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

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

previous calculation: at each stage we write only a single number or bracket, building up the right

column below.

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

• Since 1

7→ 4

7→ 2, we next write 2. = (1 2

• 2

7→ 2

7→ 1 restarts the cycle; close it and start another with an unused value. = (1 2)(3

• 3

7→ 3

7→ 4, so next write 4. = (1 2)(3 4

• 4

7→ 1

7→ 3 restarts the current cycle, so close it. = (1 2)(3 4)

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

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

should be deleted. Shortly we’ll prove that the algorithm always terminates in a product of disjoint

cycles (Theorem 4.13). For now, practice it by verifying the following:

Examples 4.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 (Section 2.4 revisited)

We’ve already seen (Example 4.2.3) how the symmetry group D

of an equilateral triangle is iso-

morphic to the symmetric group S

. The same trick applies more generally: label the vertices (or

edges/faces) of a ﬁgure with numbers 1, 2, 3, . . . and represent each rotation/reﬂection by how it

permutes these values. Cycle notation makes calculating compositions easy!

Examples 4.7. 1. Label the edges of a rectangle to view the Klein four-group V as a subgroup of S

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)



Alternative descriptions of V can be obtained by using different labellings (Exercise 3).

2. Label the vertices of a regular hexagon 1 through 6.

• The 2,2-cycle (1 5)( 2 4) represents reﬂection across the line through

3 and 6.

• The 6-cycle ( 1 2 3 4 5 6) represents 60° counter-clockwise rotation.

5 6

Both functions describe elements of the dihedral group D

. By extension, D

may be identiﬁed

as (is isomorphic to) a subgroup of S

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

with a subgroup

of S

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

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

) and the

midpoints of sides (µ

) differently.

Note the ease of computations: e.g.,

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

= ρ

Element Cycle notation

e = ()

Rotations

(1234)

(13)(24)

(1432)

(12)(34)

Reﬂections

(14)(23)

(24)

(13)

Subgroup Isomorph

{ρ

} Z

{ρ

, µ

} Z

{ρ

, δ

} Z

{ρ

, ρ

} Z

{ρ

, ρ

} Z

{ρ

, µ

, ρ

} V

{ρ

, δ

, ρ

} V

V Z

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

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

The same thing can be done for 3D ﬁgures like the tetrahedron (Example 4.26.3).

Cayley’s Theorem

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

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

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

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

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

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

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

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

Proof. Let G be a group. For each g ∈ G, deﬁne left-multiplication by g to be the function L

: G → G

where,

∀x ∈ G, L

(x) = gx

This is bijective (inverse function (L

)

−1

= L

−1

), and therefore a permutation of G: that is L

∈ S

Now deﬁne a function ϕ : G → S

by ϕ(g) = L

. We prove that ϕ is an injective homomorphism.

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

= L

=⇒ L

(e) = L

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

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



ϕ(gh)



(x) = L

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



(x)





ϕ(g)ϕ(h)



(x)

By Exercise 2.5.12, ϕ is an isomorphism onto its image/range. Otherwise said, G is isomorphic to the

subgroup ϕ(G) of the symmetric group S

Be careful! Cayley’s Theorem does not say that every group is isomorphic to some symmetric group.

It says that that every group G is isomorphic to some subgroup of S

Exercises 4.1. Key concepts: Permutation Symmetric group Cycle notation

1. Which of the following functions are permutations? Explain.

(a) f : Z → Z such that f (x) = x −7.

(b) f : Z → Z such that f (x) = −3x + 4.

− x.

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

+ x.

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

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

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

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

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

(d) ( 1 2 4 5)

(2 4 5)

∈ S

3. (Example 4.7.1, cont.) Use different labellings of the edges of the rectangle to ﬁnd another two

subgroups of S

isomorphic to V. What happens if you instead label the rectangle’s vertices?

4. By labelling vertices, view the dihedral group D

of symmetries

of the regular heptagon as a subgroup of S

. Each µ

is reﬂec-

tion across the indicated dashed line, while ρ

is rotation j steps

counter-clockwise.

(a) State µ

in cycle notation.

(b) Compute µ

using cycle notation. What element of D

does

this represent?

)

666

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

= ρ

5. State the elements of the rotation group R

in cycle notation when viewed as a subgroup of S

6. Prove parts 2, 3, and 4 of Lemma 4.3.

7. How many distinct subgroups of S

are isomorphic to S

. Describe them.

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

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

. What can you say about a

(ﬁnite) group G if G

∼

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

: G → G via left-multiplication.

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

: G → G is right-multiplication R

(x) = xg?

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

: G → G to be the function C

(z) = gxg

−1

. Does

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

11. Show that the group S

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

= 6

for which S

∼

G × H.

(Hint: If S

is decomposable, there is only one possibility; why does this decomposition make no sense?)

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

13. (a) Let µ ∈ D

be a reﬂection and ρ the one-step counter-clockwise rotation. Prove that

µρ = ρ

n−1

µ and more generally that µρ

= ρ

n−k

µ.

(b) Deﬁne a group G abstractly as the elements generated by objects ρ, µ with the properties:

ρ has order n, µ ∈

⟨

⟩

has order 2, and µρ = ρ

n−1

Prove that G = {e, . . . , ρ

n−1

, µ, . . . , ρ

n−1

µ} has order 2n, and that each ρ

µ has order 2.

(In many textbooks this is the deﬁnition of D

4.2 Orbits

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

We’ve already

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

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

Deﬁnition 4.10. The orbit of σ ∈ S

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

orb

(σ) = {σ

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

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

Observe also that orb

(x)

(σ) = orb

(σ) for any k ∈ Z.

Examples 4.11. If σ ∈ S

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

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

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

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

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

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

maps

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

so there is only one orbit: orb

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

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

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

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

Lemma 4.12. The orbits of σ ∈ S

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

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

(σ). We claim that this is an

equivalence relation.

Reﬂexivity x ∼ x since x = σ

(x). ✓

Symmetry x ∼ y =⇒ y = σ

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

−k

(y) =⇒ y ∼ x. ✓

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

(x) and z = σ

(y) for some

k, l ∈ Z. But then z = σ

k+l

(x) and so x ∼ z. ✓

The equivalence classes of ∼ are clearly the orbits of σ, which therefore partition X.

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

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

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

Given x ∈ X and a relation ∼ on X, deﬁne the set [x] := {y ∈ X : y ∼ x}.

Theorem: The sets [x] partition X (every y ∈ X lies in precisely one such subset [x]) if and only if ∼ is an equivalence

relation (reﬂexive, symmetric, transitive). In such a case we call [x] an equivalence class.

In our situation, [x] = orb

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

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

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

is given.

1. List the elements of orb

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

orb

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

(1), . . .}

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

(1) . . . σ

n−1

(1)



is an n-cycle.

2. Otherwise, let x

= min{x ∈ X : x ∈ orb

(σ)} and construct its orbit:

orb

(σ) = {x

, σ(x

), σ

), . . .}

By Lemma 4.12, orb

(σ) is disjoint with orb

(σ). If orb

(σ) ∪ orb

(σ) = X then we are done,

and σ is the product of two disjoint cycles:

σ =



1 σ(1) σ

(1) ···



σ(x

) σ

) ···



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

= min{x ∈ X : x ∈ orb

(σ) ∪ ··· ∪ orb

k−1

(σ)}. By

the Lemma, orb

(σ) is disjoint with orb

(σ) ∪ ··· ∪ orb

k−1

(σ). The process continues until

orb

(σ) ∪···∪orb

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

a product of disjoint cycles:

σ =



1 σ(1) σ

(1) ···

| {z }

orb

(σ)



σ(x

) σ

) ···

| {z }

orb

(σ)



··· ···

| {z }

orb

(σ)



···



··· ···

| {z }

orb

(σ)



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

convention, 1 < x

< ··· < x

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

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

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

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

Orders of Elements in S

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

is the smallest positive integer k for which

= e.

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

, then

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

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

= (1 5 3)(2 6 4)

= (1 6 5 4 3 2) σ

= e

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

clockwise rotation of a regular hexagon: indeed

⟨

⟩

= {e, σ, . . . , σ

}

∼

5 6

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

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

sion of disjoint cycles, since disjoint cycles commute.

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

We therefore easily compute



(1 2 3)(4 5)



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

= (1 2 3)

(4 5)

= e(4 5) = (4 5)

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

, we ﬁnd σ

. It is tempting to write

= (2 5 3)

(1 5 4 3)



(2 5 3)



(2 5 3)



(1 5 4 3)



= e

(2 3 5)e

= (2 3 5)

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

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

exponent does distribute and the computation is easy

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

= (1 3)

(2 5 4)

= (2 5 4)

= (2 4 5)

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

e = σ

= (1 3)

(2 5 4)

⇐⇒ k is divisible by both 2 and 3

The order if σ is therefore 6.

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

disjoint cycles.

Proof. Write σ = σ

···σ

as a product of disjoint cycles, where the cycle σ

has length α

. Since

disjoint cycles commute,

= σ

···σ

Since each factor σ

permutes disjoint sets, it follows that

= e ⇐⇒ ∀j, σ

= e ⇐⇒ ∀j, α

| k (the order of an α

-cycle is α

)

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

, . . . , α

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

is written as a product of disjoint cycles, its order

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

To compute σ

3465

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

3465

= (σ

)

288

= σ

= (1 4 5)

(3 6 2 7)

(8 9)

= (3 6 2 7)(8 9)

since ( 1 4 5), (3 6 2 7) and (8 9) have orders 3, 4 and 2 respectively.

Exercises 4.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.

4.3 Transpositions & the Alternating Group

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

involves the construction of permutation from the very simplest bijections.

Deﬁnition 4.18. A 2-cycle (a

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

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

Theorem 4.19. Every σ ∈ S

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

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

cycles, before decomposing each cycle as follows:

··· a

) = (a

)(a

k−1

) ···(a

)

Just read carefully and you should be convinced this works!

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

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

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

While representations as a product of transpositions are non-unique, a simple commonality may be

observed via matrix notation. Consider, for instance,







1 0 0 0

0 0 0 1

0 0 1 0

0 1 0 0































and







0 0 1 0

0 0 0 1

0 1 0 0

1 0 0 0































Each of these 4 × 4 matrices permutes the rows of any 4 × k matrix following it. These matrices

correspond naturally to two elements of S

• The transposition ( 2 4) (swap rows 2 and 4).

• The 4-cycle ( 1 4 2 3) (map row 1 to row 4, row 4 to row 2, etc.)

Deﬁnition 4.21. A permutation matrix is square matrix which is zero except for a single 1 in each row

and column. Equivalently, it is obtained by permuting the rows of the identity matrix.

Lemma 4.22. The set of n ×n permutation matrices forms a multiplicative group isomorphic to S

We omit a formal proof, though the rough idea is hopefully clear: replace each σ ∈ S

with its corre-

sponding permutation matrix and observe that composition corresponds to matrix multiplication.

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

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

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

σ = σ

···σ

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

det σ = (−1)

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

Deﬁnition 4.23. A permutation σ ∈ S

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

number of transpositions.

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

tion is either even or odd; it cannot be both!

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

therefore deﬁne a new subgroup of S

Deﬁnition 4.24. The alternating group A

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

Theorem 4.25. A

contains exactly half the elements of S

: otherwise said,

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

. Deﬁne ϕ : S

→ S

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

(1 2)(1 2)σ = σ

we see that ϕ is invertible (ϕ is its own inverse!). Moreover, ϕ maps even permutations to odd and

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

Examples 4.26. We describe the smallest three alternating groups A

1. A

= {e}

∼

is trivial.

2. A

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

∼

is a cyclic group.

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

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

(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}

is non-abelian: for example,

(1 2 3)(1 2 4) = (1 3)(2 4) = (1 4)(2 3) = ( 1 2 4)(1 2 3)

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

12, the dihedral group D

, we quickly see that A

≇ D

: all ele-

ments of A

have orders 1, 2 or 3, while D

contains a rotation (by

60°) of order 6.

By labelling faces (or vertices), A

may be visualized the 3D-

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

element acts?

Exercises 4.3. Key concepts: Transposition (representation of elements) Odd/even permutations A

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

5 Cosets & Factor Groups

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

group structure. This is a long and abstract story, though the essentials aren’t new; this is precisely

what happens with modular arithmetic (itself a generalization of even and odd).

Example 5.1. In Z

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

[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

, what we really mean is

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

The group operation (addition) on Z naturally induces the group operation (addition modulo 3) on

the set of subsets Z

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

5.1 Cosets & Normal Subgroups

Our main goal is to generalize Example 5.1. Start by observing that the identity element [0] ∈ Z

in fact a subgroup (3Z) of Z from which the other subsets [1], [2] are obtained by translation.

Deﬁnition 5.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

Example (5.1 cont). Since G = Z is written additively, the left and right cosets of H = [0] = 3Z

containing g are written

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

These cosets are precisely the elements of Z

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

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

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

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

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

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

A subgroup of a non-abelian group might be normal, but is more likely not to be (see Example 5.4.2).

Examples 5.4. 1. The subgroup H =

⟨

⟩

= {0, 2, 4} ≤ Z

has two distinct cosets (left = right since

is abelian):

H = {0, 2, 4}



= 2 + H = 4 + H



1 + H = {1, 3, 5}



= 3 + H = 5 + H



Observe how the cosets partition Z

into equal-sized subsets.

2. The left and right cosets of the subgroup H = {e, µ

} ≤ D

are as follows:

Left cosets Right cosets

H = µ

H = {e, µ

} H = Hµ

= {e, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

To verify this, either revisit the multiplication table for D

(Example 2.25) or use cycle notation

(e.g. Example 4.7). This time the left and right cosets of H are not the same: H is not a normal

subgroup of D

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

into three

equal-sized subsets; the right cosets also partition D

into equal-sized (but different) subsets.

3. Consider a 1-dimensional subspace W ≤ R

. Each coset

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

is a line parallel to W. Once again, the cosets (all lines parallel

to W) partition R

If this feels too abstract, consider the special case where W is

the y-axis: each coset is a vertical line (same x-co-ordinate).

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

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

W = 0 + W is a subspace.

u + W

4. Consider the alternating group A

as a subgroup of S

. Generalizing the argument from Theo-

rem 4.25, 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 partition G.

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

y ∈ xH ⇐⇒ x

−1

y ∈ H ⇐⇒ xH = yH

The right cosets also partition G:

y ∈ Hx ⇐⇒ yx

−1

∈ H ⇐⇒ Hx = Hy

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

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

differently to the left cosets (e.g. Example 5.4.2).

Example 5.6. This should seem familiar when G = Z and H = nZ. Written additively,

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

The cosets of H are precisely the equivalence classes modulo n. Indeed you’ve likely encountered

the main proof in the context of modular arithmetic.

Proof. We start by verifying the ﬁrst connective.

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

−1

y = h ∈ H

Now deﬁne a relation ∼ on G via x ∼ y ⇐⇒ x

−1

y ∈ H. We claim that this is an equivalence relation:

Reﬂexivity: x ∼ x since x

−1

x = e ∈ H.

Symmetry: x ∼ y =⇒ x

−1

y ∈ H =⇒ y

−1

x = (x

−1

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

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

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

Symmetry: H satisﬁes the inverse axiom.

Transitivity: H is closed under the group operation.

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

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

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

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

By combining the criteria in Theorem 5.5, we obtain a useful result for identifying when a subgroup

is normal without explicitly having to compute its cosets. The proof is an exercise.

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

H ◁ G ⇐⇒ H ≤ G and ∀g ∈ G, ∀h ∈ H, ghg

−1

∈ H

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

−1

hg ∈ H.

Exercises 5.1. Key concepts: left/right cosets & partitioning normal subgroup kernels are normal

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

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

⟨

⟩

≤ Z

(d)

⟨

⟩

≤ Z

(e)

⟨

⟩

≤ Z

2. Find the cosets of H =



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



≤ Z

×Z

3. Find the left and right cosets of {ρ

, ρ

} ≤ D

. Is the subgroup normal?

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

. Is the subgroup normal?

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

5. Revisit Examples 4.7, particularly its use of cycle notation.

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

, δ

} ≤ D

. Is H normal?

(b) Repeat for the subgroup K = {ρ

, ρ

6. Prove Lemma 5.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}. Show that H is a subgroup of S

. Is it normal?

9. Prove Corollary 5.8.

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

J = J × {e

}. Prove that

J ◁ G.

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

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

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

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

(a) Prove that ∼ is an equivalence relation on G and describe the elements of the equivalence

class of a ∈ G; this is called a double coset.

(b) Compute the double cosets of H = {e, (1 2)} and K = {e, (1 3)} as subgroups of S

5.2 Lagrange’s Theorem & Indices

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

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

H ≤ G =⇒



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

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

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

Proof. Suppose H ≤ G and ﬁx g ∈ G. The function left-multiplication by g

: H → gH : h 7→ gh

is a bijection (inverse function (L

)

−1

= L

−1

). Every left coset of H therefore has the same cardinality

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

= (number of left cosets of H) ·

=⇒



We could instead have used the right coset partition. Here is an example of Lagrange’s power.

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

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

The order of the cyclic subgroup

⟨

⟩

≤ G satisﬁes:

•

|⟨

⟩|

≥ 2 since g = e.

•

|⟨

⟩|

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

We conclude that

|⟨

⟩|

= p. But then G =

⟨

⟩

is cyclic and so isomorphic to Z

(Theorem 3.7).

Example 5.11. G = Z

× Z

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

2 or 4 and are thus isomorphic to Z

, Z

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

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

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

generator order subgroup

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

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

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

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

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

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

×Z

⟨

(1, 0)

⟩

⟨

(1, 1)

⟩

⟨

(0, 1)

⟩ ⟨

(2, 0)

⟩ ⟨

(2, 1)

⟩

⟨

(0, 0)

⟩

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

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

⟨

⟩

≤ Z

has order

gcd( s,n)

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

the quotient

. This motivates a new concept.

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

(G : H) =

{gH : g ∈ G}

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

Examples 5.13. 1. If G = Z

and H =

⟨

⟩

= {0, 2, 4, . . . , 18}, then there are (G : H) =

= 2

cosets (left and right are equal here):

H =

⟨

⟩

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

2. Recall the orthogonal and special orthogonal groups (Example 2.28 & Exercise 2.2.8):

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

Since determinant can take only two possible values in O

(R ), we conclude that there are pre-

cisely two cosets



(R ) : SO

(R )



= 2.

3. The integers form an (additive) subgroup of the real numbers R. Observe that

xZ = yZ ⇐⇒ y − x ∈ Z

It follows that there is exactly one coset for every real number in the half-open interval [0, 1);

otherwise said, ψ(x) = xZ deﬁnes a bijection of the interval [0, 1) with the set of cosets {xZ}.

We conclude that there are uncountably many cosets!

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

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

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

(G : K) =

= (G : H)(H : K)

Our proof also covers inﬁnite groups (and even inﬁnite indices, if multiplication of such makes sense

to you!). To help understand how it works, ﬁrst consider a straightforward example.

Example (5.13.1, cont.). If G = Z

, H =

⟨

⟩

and K =

⟨

⟩

, then

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 (left) cosets in each case:

• (G : H) = 2 with cosets H and 1 + H. Each coset has the form g

+ H with either g

= 0 or

= 1: these values are representatives of the two cosets.

• (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 this time are

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

with representatives 0, 1, . . . , 9. The crucial observation for the proof is that representatives are

formed by summing those above: the cosets of K in G are precisely (g

+ h

) + K.

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 of these is a coset;

we show that these 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 with g ∈ g

Now g

−1

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

∈ H with g

−1

g ∈ h

But then g ∈ (g

)K, whence 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)

Exercises 5.2. Key concepts: Lagrange’s Theorem index of a subgroup (counting cosets)

1. Find the indices of the following subgroups:

(a)

⟨

⟩

≤ Z

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

, ·) ≤ (Q

, ·)

2. Let G = Z

, H =

⟨

⟩

= {0, 2, 4, 6} and K =

⟨

⟩

= {0, 4}. Write out all the cosets for the three

subgroup relations K ≤ H, H ≤ G and K ≤ G, and verify the index multiplication formula

(Theorem 5.14).

3. Let G = S

and consider the subgroup tower K ≤ H ≤ G where

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

∼

and H = {σ ∈ S

: σ(4) = 4}

∼

(a) Write out the elements of the two left cosets K ≤ H, namely K = eK and (1 2)K with

representatives h

= e and h

= (1 2).

(b) Repeat part (a) for the four cosets of H in G = S

: observe that g

= e, g

= (1 4),

= (2 4), g

= (3 4) are representatives.

and verify that they are (g

)K in accordance with

the proof of Theorem 5.14.

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

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

×Z

are cyclic. Hence con-

struct its subgroup diagram.

6. Find the subgroups of Z

×Z

and draw its subgroup diagram.

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

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

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

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

. Prove that the function

Φ : g

H 7→ Hg

−1

is injective 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)

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

11. We modify Example 5.13.3.

(a) The sets Q and Z are both groups under addition. Show that there is exactly one coset of

Z in Q for each rational q ∈ [0, 1). Hence conclude that (Q : Z) = ℵ

is countably inﬁnite.

(b) Describe the index of U

roots of unity) as a subgroup of the circle group S

5.3 Factor Groups

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

inherited from that of G. In our motivating Example (5.1) this is precisely how Z

was created from

the integers, by ‘squashing’ all elements of each coset down to a single object. We simply want to do

this in general. To see how this might (or might not) work, recall some previous examples.

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

⟨

⟩

= {0, 2, 4} ≤ Z



H, 1 + H



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

We use addition in Z

to deﬁne addition of cosets via

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

This seems nice, though consider the steps of the computation

more carefully:

(a) First choose representatives a and b of the two cosets.

(b) Then add within the original group a + b ∈ Z

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

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

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

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

0 0

Addition in Z

1+H

1+H1+H

⊕

Addition in {H, 1 + H}

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

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

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

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

with this

so-called factor group.

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

} ≤ D

. The left cosets are

H = µ

H = {e, µ

}, ρ

H = µ

H = {ρ

, µ

}, ρ

H = µ

H = {ρ

, µ

}

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

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

)

This time there is a serious problem: note that ρ

H = µ

H, however,

H ⊗ρ

H = (ρ

)H = ρ

H µ

H ⊗µ

H = (µ

)H = eH = H

This is a contradiction: ρ

H = H, but the result of both calculations should be the same. The

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

operation ⊗ does not exist (is not well-deﬁned), and thus cannot produce a group structure.

Well-deﬁnition of the Factor Group Structure

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

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

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

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

This is well-deﬁned precisely when

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

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

h ∈ H, g ∈ G, tells us that

(hg)H = gH, or equivalently g

−1

hg ∈ H (Theorem 5.5)

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

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

Theorem 5.15. Suppose H ≤ G and consider the natural operation (∗) on the set of (left) cosets.

1. (∗) is well-deﬁned if and only if H is a normal subgroup of G.

2. In such cases, (∗) deﬁnes a group structure on the set of cosets.

Since this process only works when H is a normal subgroup, the preﬁx ‘left’ is irrelevant.

Deﬁnition 5.16. Suppose H ◁ G. The group of cosets





gH : g ∈ G



(read ’G mod H’) under

the natural operation (∗) is termed a factor group (or quotient group).

Factor group notation looks like division in part because if G is ﬁnite, then







= (G : H) =

Proof. 1. (⇒) The above discussion shows that well-deﬁnition of (∗) implies H ◁ G.

(⇐) Assume H ◁ G, and suppose xH = aH and yH = bH. By Theorem 5.5, h := x

−1

a and

h := y

−1

b are both in H. But then,

(xy)

−1

(ab) = y

−1

a)b = y

−1

hb = (y

−1

hy)

which lies in H by Corollary 5.8 (y

−1

hy ∈ H). We conclude that (xy)H = (ab)H (†).

2. Since the natural operation is well-deﬁned, we need only verify the group axioms for





, ·



Closure: Given aH, bH ∈



, we see that aH · bH = (ab)H is also coset.

Associativity: aH ·(bH ·cH) = aH ·(bc)H = a(bc)H. Similarly (aH ·bH) ·cH = (ab)cH. By the

associativity of (G, ·), these cosets are identical.

Identity: The identity coset H = eH does the job: eH · aH = (ea)H = aH = (ae)H = aH · eH.

Inverse: a

−1

H · aH = (a

−1

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

−1

= a

−1

Since this operation arises naturally from that on G, we use the same notation (here multiplication).

’Identifying’ Factor Groups

The ﬁrst goal when faced with a factor group



is often to identify it by recognizing some well-

understood group to which it is isomorphic. In Section 6.2 we’ll develop the main piece of abstract

machinery for doing this. Since this upcoming approach can be difﬁcult to apply, it is worth ﬁrst

spending a little time with some basic examples. In particular, we can straightforwardly describe the

factor groups of every cyclic group: by Theorem 3.7, we need only do this for Z and Z

. . .

Factor Groups of Z (modular arithmetic done right) If n is a positive integer, its integer multiples

nZ =

⟨

⟩

form a (normal) subgroup of Z. The coset of nZ containing x ∈ Z is plainly

x + nZ = {x + kn : k ∈ Z} =



y ∈ Z : y ≡ x (mod n)



This coset is what we have been calling ‘x’ in Z

! This provides the formal deﬁnition of Z

(super-

seding Deﬁnition 2.16) and trivially demonstrating that Z

is an abelian group.

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

is the factor group



We typically drop the repeated nZ terms when calculating, recovering our familiar notation: e.g.

4 + 5 = 2 ∈ Z

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



Factor Groups of Finite Cyclic Groups The ﬁrst example on page 57 shows that



⟨

⟩

∼

. This

generalizes straightforwardly.

Example 5.18.

⟨

⟩

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

has factor group



⟨

⟩



⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩

, 4 +

⟨

⟩



which is isomorphic to Z

via the isomorphism

ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

Theorem 5.19. If d | n, then



⟨

⟩

∼

. More generally,



⟨

⟩

∼

gcd(s,n)

Proof. Deﬁne ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

. We prove that this is an isomorphism.

Well-deﬁnition/injectivity: For any x, y ∈ Z

x = y (∈ Z

) ⇐⇒ x −y ∈

⟨

⟩

⇐⇒ x +

⟨

⟩

= y +

⟨

⟩

⇐⇒ ψ(x) = ψ(y)

Surjectivity: Any coset x +

⟨

⟩

(being ψ(x)) lies in range(ψ).

Homomorphism: For any x, y ∈ Z

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

⟨

⟩



x +

⟨

⟩





y +

⟨

⟩



= ψ(x) + ψ(y)

The general case follows by Corollary 3.16: if d = gcd(s, n), then

⟨

⟩

⟨

⟩

Further Examples Na

ıve identiﬁcation of factor groups often boils down to a two-step hack.

1. Find the order of the factor group



by computing the index (G : H).

2. Determine which group of order ( G : H) is correct.



is abelian, the Fundamental Theorem (3.26) might supply candidates. Step 2 can often be

accomplished by considering orders of elements (cosets). The simple observation can help with this.

Lemma 5.20. Let



be a factor group. Then (gH)

= H ⇐⇒ g

∈ H (mg ∈ H if G additive).

By Corollary 3.9, the order of the element gH ∈



is the smallest m ∈ N for which g

∈ H.

Moreover, this number min{m ∈ N : g

∈ H} divides the order of g (in G).

Examples 5.21. Let G = Z

×Z

. We identify the factor group



for three subgroups H.

1. The subgroup H =

⟨

(0, 1)

⟩



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



has 8 elements, so the factor group



has order

4·8

= 4. By the Fundamental Theorem,



is isomorphic to Z

or Z

×Z

We can decide which by considering the orders of elements in



×Z

: Every element has order at most 2.

: There exists a generator with order 4.

Start playing with elements (cosets)! It doesn’t take long to observe that

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

Otherwise said, (1, 0) + H ∈



has order 4: we conclude that



∼

. Since (1, 0) + H is a

generator, this approach provides an explicit isomorphism ψ : Z

∼



ψ(x) = (x, 0) + H





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





2. The subgroup H =

⟨

(0, 2)

⟩



(0, 0), (0, 2), (0, 4), (0, 6)



has 4 elements, so







= 8.

The factor group is isomorphic to one of Z

, Z

×Z

or Z

×Z

• Exactly as in (†), (1, 0) + H ∈



has order 4. This rules out Z

×Z

as a candidate.

• Z

is ruled out since every (x, y) + H has order at most 4: for any (x, y),

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

By process of elimination, we conclude that



∼

×Z

3. The subgroup H =

⟨

(2, 4)

⟩



(0, 0), (2, 4)



produces a factor group of order







= 16,

so we must consider ﬁve non-isomorphic possibilities:

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

• The coset ( 0, 1) + H ∈



has order 8, since



(0, 1) + H



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

• Every (x, y) + H has order dividing 8, since

8(x, y) = (8x, 8y) = (0, 0) ∈ H

The only candidate satisfying both properties is Z

×Z

For factor groups of inﬁnite or non-abelian groups, more creative strategies might be required.

Examples 5.22. 1. As seen in Exercise 5.2.7, every index-2 subgroup H ≤ G is normal. Since there is

only one group of order 2 up to isomorphism, in such a case



∼

For instance, R

◁ D

has index (D

: R

) = 2. The two cosets are,

Rotations: R



, . . . , ρ

n−1



Reﬂections: µR



, . . . , µ



, where µ is any reﬂection.

◦ R

µR

The Cayley table for the factor group



= {R

, µR

} is shown. Consider how the calcula-

tion (µR

)(µR

) = R

says that the composition of two reﬂections is a rotation!

2. In Exercise 5.1.4, we saw that the alternating group A

has the Klein four-group identiﬁed as

V =



e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)



as a normal subgroup. Since the factor group has order (A

: V) =

= 3 and there is only one

group of order 3 up to isomorphism, we conclude that



∼

3. (Example 5.4.3, simpliﬁed) Given W = {(0, y) : y ∈ R} ≤ R

, each coset (vertical line)



(x, y) : y ∈ R

 

= (x, 0) + W



intersects the x-axis at a unique point (x, 0). Otherwise said, we have a bijection,

ψ : R →



: x 7→ (x, 0) + W

This is moreover an isomorphism, since

ψ(x

+ x

) = (x

+ x

) + W = (x

+ W) + (x

+ W) = ψ(x

) + ψ(x

)

4. (Hard) Let G = Z ×Z

and consider the subgroup

H =

⟨

(2, 1)

⟩



. . . , (−4, 2), (−2, 3), (0, 0), (2, 1), (4, 2), (6, 3), (8, 0), (10, 1), . . .



We cannot count cosets using the index formula. Instead we ﬁnd a simple representative of

each coset:

If x = 2n is even: (x, y) + H = (2n, y) + H = (0, y −n) + H

If x = 2n + 1 is odd: (x, y) + H = (2n + 1, y) + H = (1, y −n) + H

In any coset, there is a unique representative either of the form (0, z) or (1, z), where z ∈ Z

: it

follows that there are 8 cosets. To ﬁnish things off, observe that

k(1, 0) = (k, 0) ∈ H ⇐⇒ 8 | k

whence ( 1, 0) + H ∈



has order 8: we conclude that



∼

We’ll see more examples, and revisit others, in Section 6.2 once we’ve developed more machinery.

Exercises 5.3. Key concepts:

Factor group



a group ⇐⇒ H ◁ G Z



identifying



1. List the cosets of the subgroup H =

⟨

⟩

in G = Z

. By mimicking the proof of Theorem 5.19,

show that ψ : Z

7→



: x 7→ x + H is a well-deﬁned isomorphism.

2. (Exercise 5.1.2 cont.) If H =



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



, identify the factor group

×Z



3. Identify the factor group



where H =

⟨

(2, 4)

⟩

≤ G = Z

×Z

4. Let G = Z

×Z

(a) State the elements of the subgroup H =

⟨

(3, 6)

⟩

. Now 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. (a) Let G be a cyclic group with subgroup H. Prove that



is cyclic.

(b) If



is cyclic, does it follow that G is cyclic? Explain.

8. (Exercise 5.2.10, cont.) The factor group



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

this explicitly by ﬁnding a generator and thus an isomorphism ψ : Z

→



9. (Example 5.22.2, cont.) Find an explicit isomorphism ψ : Z

∼



10. Exercise 5.1.5 showed that {ρ

, ρ

} is a normal subgroup of D

. To what well-known group is

the factor group



{ρ

, ρ

}

isomorphic? Prove your assertion.

11. If H ◁ G has index (G : H) = 2, then the factor group



is necessarily isomorphic to Z

(a) Prove that ψ : Z

→



deﬁned by ψ(x) = (1 2)

is an isomorphism.

(b) Find an explicit isomorphism ψ : Z

→

(R)



(R)

12. (Exercise 5.1.10, cont.) Suppose G = H ×K, J ◁ H and

J = J × {e

}. Prove that



×K.

Can you quickly verify Examples 5.21.1, 2, and 5.22.3 in this language?

13. Complete the proof of Lemma 5.20 by showing that the order of the element/coset gH ∈



divides the order of the element g ∈ G.

(Hint: Use the division algorithm similarly to the proof of Theorem 3.12)

14. (Hard) Let H =

⟨

(2, 3)

⟩

≤ G = Z

×Z. Prove that



∼

15. (Hard!!) If G = Z

×Z

×Z and H =

⟨

(4, 2, 3)

⟩

, identify



as a direct product Z

×Z

(Hint: show that exactly one representative of the coset (x, y, z) + H has z = 0, 1 or 2)

6 Homomorphisms & The First Isomorphism Theorem

The main goal of this chapter is to discuss the link between homomorphisms, normal subgroups and

factor groups. The key result is the subject of Section 6.2: the First Isomorphism Theorem.

6.1 Kernels, Images and Normal Subgroups

In Section 2.5 we established several important facts that are worth refreshing and summarizing here.

Deﬁnition 6.1. The kernel and image of a homomorphism

ϕ : G → L are the sets

ker ϕ =



g ∈ G : ϕ(g) = e



, Im ϕ =



ϕ(g) : g ∈ G



Lemma 6.2. Suppose ϕ : G → L is a homomorphism.

1. (Exercise 2.5.11c) ϕ maps identity to identity and inverse to inverse:

ϕ(e

) = ϕ(e

) and ∀g ∈ G,



ϕ(g)



−1

= ϕ(g

−1

)

2. (Exercise 2.5.12) ker ϕ is a subgroup of G and Im ϕ is a subgroup of L.

Do these exercises now, even if you did them earlier!

Examples 6.3. 1. The function ϕ(x) = 2x (mod 4) deﬁnes a homomorphism ϕ : Z → Z

with

ker ϕ = {x ∈ Z : 2x ≡ 0 (mod 4)} = 2Z, Im ϕ = {0, 2}

Plainly ker ϕ is a subgroup of Z and Im ϕ is a subgroup of Z

2. Every linear map T : V → W between vector spaces is a homomorphism. In linear algebra its

kernel is better known as its nullspace

ker T = N(T) =



v ∈ V : T(v) = 0



If T = L

: R

→ R

is left-multiplication by a matrix A, then Im T is the column space of A.

Since the groups in these examples are abelian, all subgroups are automatically normal. In fact the

kernel of every homomorphism is a normal subgroup, though the same cannot be said for images.

Lemma 6.4. If ϕ : G → L is a homomorphism, then ker ϕ ◁ G.

Proof. The kernel is a subgroup by part 2 of Lemma 6.2, so we need only check normality. For this

we appeal to the conjugation criterion (Corollary 5.8). If g ∈ G and k ∈ ker ϕ, then



gkg

−1



= ϕ(g)ϕ(k)ϕ(g)

−1

= ϕ(g)ϕ(g)

−1

= e

=⇒ gkg

−1

∈ ker ϕ

Note how the ﬁrst equality used the homomorphism property and part 1 of the Lemma.

All homomorphisms in this chapter (indeed outside of Section 2.5) are between groups.

Examples 6.5. 1. (Recall Exercises 2.4.8a & 2.5.1g) We’ve seen that det : GL

(R ) → R

is a homo-

morphism. We therefore obtain a normal subgroup

ker det = {A ∈ GL

(R ) : det A = 1}◁ GL

(R )

Otherwise said, SL

(R ) is a normal subgroup of GL

(R ).

2. (Example 5.4.2, cont.) ϕ : Z

→ D

deﬁned by ϕ(x) = µ

is a homomorphism. Certainly

ker ϕ = {0} ◁ Z

, however Im ϕ = {e, µ

} is not a normal subgroup of S

Kernels, Images and Describing Homomorphisms

Since every kernel is a normal subgroup, it makes sense to ask how its cosets may be counted and

distinguished.

Lemma 6.6. Let ϕ : G → L be a homomorphism. There is precisely one coset of ker ϕ for each

element of Im ϕ:

ker ϕ = g

ker ϕ ⇐⇒ ϕ(g

) = ϕ(g

)

Otherwise said, the index equals the order of the image: (G : ker ϕ) =

Im ϕ

The proof is an abstraction of Example 5.13.2 (where ϕ = det : O

(R ) → R

Proof. For all g

, g

∈ G, we have

ker ϕ = g

ker ϕ ⇐⇒ g

−1

∈ ker ϕ (Theorem 5.5)

⇐⇒ ϕ(g

−1

) = e

(Deﬁnition of ker ϕ)

⇐⇒ ϕ(g

)

−1

ϕ(g

) = e

(Homomorphism properties)

⇐⇒ ϕ(g

) = ϕ(g

)

The Lemma is really part of the upcoming punchline in Section 6.2. For the moment we apply it to

help describe and count homomorphisms.

Theorem 6.7. Let ϕ : G → L be a homomorphism. If G is ﬁnite, then Im ϕ is a ﬁnite group whose

order divides that of G. The same holds for L. Otherwise said,

< ∞ =⇒

Im ϕ



and

< ∞ =⇒

Im ϕ



If both groups are ﬁnite, then

Im ϕ



gcd



Proof. If G is a ﬁnite group, then ker ϕ ≤ G is ﬁnite. Apply Lemma 6.6 to see that

Im ϕ

= (G : ker ϕ) =

ker ϕ

is a divisor of

. The second situation

Im ϕ



is Lagrange’s Theorem (5.9).

Examples 6.8. 1. If ϕ : G → L is a homomorphism and gcd





= 1, then we have

Im ϕ

= 1.

The image is necessarily the trivial subgroup Im ϕ = {e

} and there is exactly one homomor-

phism, namely the trivial homomorphism (∀g ∈ G, ϕ(g) = e

2. Consider all homomorphisms ϕ : Z

→ S

. Since the domain is cyclic, describing ϕ( 1) is

enough to obtain ϕ(x) =



ϕ(1)



. Since gcd(

) = 2, we have

Im ϕ

= 1 or 2. Either:

• Im ϕ = {e} and we obtain the trivial homomorphism ϕ

(x) = e.

• Im ϕ is a subgroup of order 2, of which S

has exactly three: {e, (2 3)}, {e, (1 3)}, {e, (1 2) }.

This results in three further homomorphisms (for a total of four)

(x) = (2 3)

, ϕ

(x) = (1 3)

, ϕ

(x) = (1 2)

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

→ Z

Two facts make this relatively simple:

1. As above, choosing ϕ(1) deﬁnes the homomorphism: ϕ(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.16), Im ϕ must be a subgroup of the unique subgroup





≤ Z

of order d:

Im ϕ ≤



, . . . ,

(d −1)n



It is enough to see what happens if we let ϕ(1) be each element of this subgroup in turn. . .

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

→ Z

, namely

(x) =

x where k = 0, . . . , d −1

Proof. We check that each ϕ

is well-deﬁned; the calculation uses the fact that

is an integer.

x = y ∈ Z

=⇒ y = x + λm for some m ∈ Z

=⇒ ϕ

(y) = ϕ

(x + λm) =

x + λk

n =

= ϕ

(x)

(in Z

)

By observation 1, each ϕ

is a homomorphism. Observation 2 says there are no other candidates.

Example 6.10. We describe all homomorphisms ϕ : Z

→ Z

Since gcd( 12, 20) = 4, we see that Im ϕ ≤

⟨

⟩

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

. There are four choices:

(x) = 0, ϕ

(x) = 5x, ϕ

(x) = 10x, ϕ

(x) = 15x (mod 20)

We similarly see that there are four distinct homomorphisms ψ : Z

→ Z

(x) = 0, ψ

(x) = 3x, ψ

(x) = 6x, ψ

(x) = 9x (mod 12)

Most of these examples rely on the domain of a homomorphism being cyclic (observation 1). It is

typically much harder to ﬁnd and describe homomorphisms when the domain is non-cyclic.

Exercises 6.1. Key concepts: (G : ker ϕ) =

Im ϕ

| |

Im ϕ



gcd





1. Check that you have a homomorphism (use Corollary 6.9) 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. State a linear map T : R

→ R

whose kernel is the y-axis (a normal subgroup of R

). What

type of linear map is the function T?

4. Find the kernel and image of each homomorphism and verify that ker ϕ is normal:

(a) The trace of a matrix tr : M

(R ) → R :



a b

c d



7→ a + d.

(b) T : R

→ R

: x 7→

1 1 −1

0 3 −1

1 4 −2

2 5 −3

5. Explain why the map ϕ is a homomorphism and ﬁnd ker ϕ:

ϕ : S

→



{1, −1}, ·



: σ 7→

(

1 if σ even

−1 if σ odd

6. Suppose ϕ : G → L is a homomorphism, and that H ≤ G and K ≤ L are subgroups.

(a) Prove that ϕ(H) := {ϕ(h) : h ∈ H} is a subgroup of Im ϕ.

(b) Give an example to show that Im ϕ need not be a normal subgroup of L.

−1

(K) = {g ∈ G : ϕ(g) ∈ K} is a subgroup of G.

7. (Exercise 3.2.6, cont.) Prove that the number of distinct isomorphisms ϕ : Z

→ Z

equals the

order of the multiplicative group of units (Z

, ·

8. (a) Suppose ϕ : Z

(m)

× Z

(n)

→ L is a well-deﬁned homomorphism.

Prove that ϕ(x, y) =

ax + by, where a = ϕ(1, 0) and b = ϕ(0, 1).

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

9. Find all homomorphisms ϕ : Z

×Z

→ Z

×Z

. How do you know that there are no more?

10. Consider ϕ : D

→ D

: σ 7→ σ

. Explain why ϕ is not a homomorphism.

As in Theorem 3.7, Z

(m)

is a generic additive cyclic group: either Z or Z

6.2 The First Isomorphism Theorem

Lemma 6.4 says that every kernel is a normal subgroup. In fact all normal subgroups arise this way.

Theorem 6.11 (Canonical Homomorphism). Let G be a group and H ◁ G. The function

γ : G →



deﬁned by γ(g) = gH

is a homomorphism with ker γ = H.

Proof. Since H is normal,



is a factor 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

g ∈ ker γ ⇐⇒ γ(g) = H ⇐⇒ g ∈ H

This might feel a little sneaky, and we’d have preferred a codomain that wasn’t a factor group! Our

hope is vain however, for the next result—arguably the most important in elementary group theory—

shows that every homomorphism with the same kernel is essentially γ in disguise.

Theorem 6.12 (1

Isomorphism). Let ϕ : G → L be a homomorphism with kernel H. Then

µ :



→ Im ϕ deﬁned by µ(gH) = ϕ(g)

is an isomorphism. Otherwise said: ϕ = µ ◦ γ and



ker ϕ

∼

Im ϕ.

A commutative diagram provides a helpful summary: ϕ = µ ◦ γ means

we get the same result by following arrows from G to Im ϕ regardless

of the path.

The 1

isomorphism theorem has analogues in several other parts of

mathematics: at the very least you should have met its close kin from

linear algebra, the rank–nullity theorem.

Im ϕ



ker ϕ

;;

Proof. The factor group exists since ker ϕ ◁ G (Lemma 6.4). We check the isomorphism properties:

Well-deﬁnition and Bijectivity: These are immediate after writing H = ker ϕ:

H = g

Lemma

⇐⇒

6.6

ϕ(g

) = ϕ(g

) ⇐⇒ µ(g

H) = µ(g

Homomorphism: For all g

H, g

H ∈



µ(g

H · g

H) = µ(g

H) = ϕ(g

) (coset multiplication & deﬁnition of µ)

= ϕ(g

)ϕ(g

) (ϕ is a homomorphism)

= µ(g

H)µ(g

Examples 6.13. 1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 5x (mod 20) (Example 6.10). 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. The homomorphism ϕ : R → (C

, ·) : x 7→ e

2πix

has

ker ϕ =



x ∈ R : e

2πix

= 1



= Z and Im ϕ = S

is the circle group)

The canonical homomorphism γ and the isomorphism µ from the theorem are

γ : R →



: x 7→ x + Z and µ :



→ S

: x + Z 7→ e

2πix

Think about how this relates to Example 5.13.3.

3. The homomorphism ϕ : Z ×Z → Z : (x, y) 7→ 3x −2y satisﬁes

ϕ(x, y) = (0, 0) ⇐⇒ 3x = 2y ⇐⇒ (x, y) = (2n, 3n) for some n ∈ Z

We conclude that ker ϕ =

⟨

(2, 3)

⟩

. The canonical homomorphism is therefore

γ : Z ×Z →

Z ×Z



⟨

(2, 3)

⟩

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

⟨

(2, 3)

⟩

Since n = ϕ(n, n), the homomorphism is surjective: Im ϕ = Z. By the 1

isomorphism theorem,

Z ×Z



⟨

(2, 3)

⟩

∼

Z via µ



(x, y) +

⟨

(2, 3)

⟩



= 3x −2y

4. ϕ(x, y) = (x, y − x) is a well-deﬁned homomorphism ϕ : Z ×Z

→ Z

×Z

. Moreover,

ϕ(x, y) = (0, 0) ⇐⇒

(

x = 3k, and

y = x = 3k ∈ Z

whence ker ϕ =

⟨

(3, 3)

⟩



. . . , (−6, 0), (−3, 3), (0, 0), (3, 3), (6, 0), . . .



Moreover, ϕ is surjective: e.g. (m, n) = ϕ(m, n + m). We conclude that

Z ×Z



⟨

(3, 3)

⟩

∼

×Z

via µ



(x, y) +

⟨

(3, 3)

⟩

) = (x, y − x)

Identifying Factor Groups (revisited)

The 1

isomorphism theorem may be applied to the identiﬁcation of factor groups. Given H ◁ G, we

cook up a homomorphism ϕ : G → L with ker ϕ = H and conclude that



∼

Im ϕ. This typically

requires some creativity: there are many options, and both L and a formula for ϕ need to be found

simultaneously! We ﬁrst revisit some examples from the previous section in this context.

Examples (5.21, mk.II). For each subgroup H of G = Z

× Z

, we hunt for a suitable homomor-

phism with ker ϕ = H.

1. Given H =

⟨

(0, 1)

⟩

, we need a homomorphism for which ϕ(0, 1) is the identity. This is very

simple: just ignore y! Deﬁne

ϕ : Z

×Z

→ Z

: (x, y) 7→ x

This indeed has kernel ker ϕ = {(0, y) : y ∈ Z

} = H. By the 1

isomorphism theorem,



∼

Im ϕ = Z

via the isomorphism µ



(x, y) + H



= x. Note that (x, y) + H = (x, 0) + H, whence µ is the

inverse of the isomorphism ψ : x 7→ (x, 0) + H stated previously!

2. Given H =

⟨

(0, 2)

⟩

we require ϕ(0, 2) to be the identity. This may be achieved by taking y

modulo 2 and deﬁning

ϕ : Z

×Z

→ Z

×Z

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

This is well-deﬁned

ϕ(x + 4m, y + 8n) = (x + 4m, y + 8n) = (x, y) = ϕ (x, y) (since 2 | 8)

and a homomorphism with required kernel H. Moreover, ϕ is surjective, whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y). Once again µ is the inverse of ψ(x, y) = (x, y) + H

in the original example.

3. Finding a homomorphism with kernel H =

⟨

(2, 4)

⟩



(0, 0), (2, 4)



is somewhat trickier. One

approach is to observe that

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

This suggests

ϕ : 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 co-ordinate is crucial! Cer-

tainly ϕ has the correct kernel. It is moreover surjective: (m, n) = ϕ(m, n + 2m). In conclusion,



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y − 2x).

Examples 6.14. Two ﬁnal examples follow a similar theme, though with inﬁnite groups. We’ll

generalize these in Exercise 10.

1. We identify the factor group



Z ×Z



⟨

(1, −1)

⟩

We require a homomorphism where (1, −1) ∈ ker ϕ. An obvious candidate is

ϕ : Z ×Z → Z : (x, y) 7→ x + y

Certainly (x, y) ∈ ker ϕ ⇐⇒ x + y = 0 ⇐⇒ y = −x ⇐⇒ (x, y) ∈

⟨

(1, −1)

⟩

. Moreover,

x = ϕ(x, 0) for any x ∈ Z, so this is a surjective homomorphism. We conclude that

Z ×Z



⟨

(1, −1)

⟩

∼

Im ϕ = Z

2. We identify the factor group



Z ×Z



⟨

(4, 6)

⟩

It is tempting to try a homomorphism ψ(x, y) = 6x −4y or ψ(x, y) = 3x −2y. These certainly

satisfy ψ(4, 6) = 0, but they also have ψ(2, 3) = 0 which we don’t want!

As a hint for how to proceed, note that the element/coset (2, 3) + H ∈



has order 2:

2( 2, 3) = (4, 6) ∈ H

We’d therefore like a homomorphism that maps (2, 3) to an element of order 2: the simple

function ξ : Z ×Z → Z

: (x, y) 7→ y −x certainly does this! We try combining these functions:

ϕ : Z ×Z → Z ×Z

: (x, y) 7→ (3x −2y, y −x)

Let’s compute the kernel:

ϕ(3x −2y, y − x) = (0, 0) =⇒ 3x = 2y ∈ Z =⇒ (x, y) = (2m, 3m) : m ∈ Z

Substitute this into the second factor: y − x = m = 0 ∈ Z

=⇒ m = 2n is even, from which

(x, y) = (4n, 6n). It is trivially veriﬁed that all such pairs lie in the kernel, whence ker ϕ =

⟨

(4, 6)

⟩

, as required. Finally,

ϕ(1, 1) = (1, 0), ϕ(2, 3) = (0, 1) =⇒ (u, v) = ϕ(u + 2v, u + 3v)

says that ϕ is surjective. We conclude that



∼

Z ×Z

Exercises 6.2. Key concepts:

Canonical homomorphism γ : G →



isomorphism theorem µ :



ker ϕ

∼

Im ϕ

1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 10x.

(a) Find the kernel of and image of ϕ.

(b) List the elements of the factor group



ker ϕ



ker ϕ

→ Im ϕ.

(d) To what basic group Z

is the factor group isomorphic?

2. Repeat the previous question for the homomorphism ϕ : Z → Z

: x 7→ 8x.

3. For each function ϕ : Z ×Z → Z, ﬁnd the kernel and identify the factor group

Z ×Z



ker ϕ

(a) ϕ(x, y) = 3x + y (b) ϕ(x, y) = 2x −4y

4. (a) If a subgroup H of G = Z

×Z

has order 5, ﬁnd its elements.

(b) Show that ϕ(x, y) = (x, y) is a homomorphism ϕ : G → Z

×Z

with ker ϕ = H.

isomorphism theorem tell us about the factor group



5. Suppose G is a ﬁnite group with normal subgroup H and that ϕ : G → L is a homomorphism

with ker ϕ = H. Prove that (G : H) ≤

with equality if and only if ϕ is surjective.

6. Consider the map ϕ : Z ×Z

→ Z

×Z

deﬁned by

ϕ(x, y) =



2x + y, y



(a) Verify that ϕ is a well-deﬁned homomorphism.

(b) Compute ker ϕ and identify the factor group

Z ×Z



ker ϕ

7. Let H =

⟨

(3, 1)

⟩

≤ G = Z

×Z

. Find an explicit homomorphism ϕ : G → Z

whose kernel is

H, and thus identify the factor group



(Hint: (x, y) ∈ H = {(0, 0), (3, 1), (6, 2)} ⇐⇒ . . .)

8. Consider H =

⟨

(3, 3)

⟩

≤ G = Z

× Z

. Find a surjective homomorphism ϕ : G → Z

× Z

whose kernel is H and hence prove that



∼

×Z

9. Let ϕ : S

→ S

: z 7→ z

(a) Find the kernel of ϕ and describe the canonical homomorphism γ : S

→



ker ϕ

(b) What does the ﬁrst isomorphism theorem say about the factor group



ker ϕ



, where U

is the group of n

roots of unity.

10. We identify



Z ×Z



⟨

(a, b)

⟩

. Suppose d = gcd(a, b) where a, b are not both zero.

(a) Let ψ(x, y) =

x −

y be the homomorphism ψ : Z ×Z → Z. Find ker ψ.

(b) Show that



contains an element of order d, namely (

) + H.

ezout’s identity says ∃κ, λ ∈ Z for which κa + λb = d. The function

ξ : Z ×Z → Z

: (x, y) 7→ κx + λy

plainly maps (

) to the generator 1 ∈ Z

. Compute ker ϕ for the combined map

ϕ : Z ×Z → Z ×Z

: (x, y) 7→



x −

y, κx + λy



(d) Identify the factor group

Z ×Z



⟨

(a, b)

⟩

(e) Find an explicit isomorphism µ :

Z ×Z



⟨

(21, 35)

⟩

→ Z ×Z

6.3 Conjugation, Cycle Types, Centers and Automorphisms

In this section we consider an important type of homomorphism and some its consequences.

Deﬁnition 6.15. 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 5.8). It should also be familiar from linear algebra, in the context of similarity. Recall that

square matrices A, B are similar if B = MAM

−1

for some invertible M. Such matrices have the same

eigenvalues and, essentially, ‘do the same thing’ with respect to different bases. An explicit group

theory analogue of this is Theorem 6.19 below.

Lemma 6.16. 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 6.17. 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 6.18. 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 6.19. 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 cycle-type 2,2.

Before seeing a proof it is beneﬁcial to try an example.

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

This plainly has the same cycle-type as σ. Moreover, it may be obtained by applying ρ to the entries

of σ!

ρσρ

−1

= (1 4)(2 3) =



ρ(1) ρ(2)



ρ(3) ρ(4)



(∗)

This 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 a notational horror, but it amounts to nothing more than the example done abstractly:

our goal is to recognize ρσρ

−1

in exactly the form (∗), taking ρ of each entry in each cycle.

Proof. (⇒) First consider conjugation of a k-cycle σ = (a

···a

) by ρ ∈ S

. We claim that

ρσρ

−1



ρ(a

) ···ρ(a

)



is also a k-cycle. Since this is an equality of functions, we verify by evaluating on all elements

of X = {1, 2, . . . , n}. There are two cases, which correspond to partitioning X = A ∪(X \ A)

where A = {a

, . . . , a

}. First observe that ρ bijectively maps A → A and X \ A → X \ A.

1. Suppose x ∈ A. Since A = ρ(A), we may uniquely write x = ρ(a

). But then

ρσρ

−1

(x) = ρσρ

−1



ρ(a

)



= ρσ(a

) = ρ(a

j+1

)

where a

k+1

is understood to equal a

2. Suppose x ∈ A. We know that ρ

−1

(x) ∈ A is unmoved by σ, whence

ρσρ

−1

(x) = ρσ(ρ

−1

(x)) = ρρ

−1

(x) = x

We conclude that ρσρ

−1



ρ(a

) ···ρ(a

)



is as claimed. 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 corre-

sponding orbits have the same length. Assume we’ve all single-element orbits are included so

that

= {1, . . . , n} =

. Deﬁne ρ ∈ S

by writing the orbits of σ and τ on top each other

x σ

··· σ

ρ(x) τ

··· τ

Since the orbits of σ, & τ partition X = {1, . . . , n}, this is plainly deﬁnes a permutation. Finally,

if s

i,j

and t

i,j

are the j

elements of the orbits σ

and τ

, then

ρσρ

−1

i,j

) = ρσ(s

i,j

) = ρ



i,j+1



= t

i,j+1

= τ



i,j



We conclude that ρσρ

−1

= τ, as required.

Examples 6.21. 1. The permutations σ = (1 4 5)(2 7 6) and τ = (1 6 5)(3 4 7) in S

have the same

cycle-type and are thus 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)

It is worth making a sanity check:

ρσρ

−1

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

Other choices of ρ are available: just write the orbits of σ, τ in different orders. Can you ﬁgure

out how many distinct choice of ρ will work?

2. (Example 5.3.2) We checked previously that V =



e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)



is a normal

subgroup of A

. 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 g ∈ G is an isomorphism. We

now consider all such maps.

Deﬁnition 6.22. An automorphism 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 6.23. There are four homomorphisms ϕ

: Z

→ Z

(Corollary 6.9);

(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 (isomorphic to Z

) under composition

of functions.

As for conjugations, since Z

is abelian these are uninteresting:

g, x ∈ Z

=⇒ c

(x) = g + x + (−g) = x =⇒ c

= ϕ

There is only one inner automorphism of Z

, namely the identity function ϕ

. This indeed holds in

general: if G is abelian, then Inn(G)

∼

is trivial.

In general, hunting for automorphisms is difﬁcult. Here is a simple observation that helps to narrow

things down. The proof is an exercise.

Lemma 6.24. 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 generate the two observed automorphisms.

Example 6.25. 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 automorphisms; it is tedious to check, but all in fact

deﬁne automorphisms! Indeed all are conjugations, from which 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 always form a group under composition; in this case

Aut S

is a group of order 6 which is easily seen to be non-abelian,

(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 6.26. 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.5.15. By

Lemma 6.16, 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 itself closed under conjugation! Let τ ∈ Aut G and c

∈ Inn G.

For any x ∈ G, we have

(τc

−1

)(x) = τ





−1

(x)





= τ





−1

(x)



−1



(deﬁnition of c

)



τ(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 keeping track of where everything lives. To help, the inverse symbol is colored:

−1

(in red) means the inverse function, whereas g

−1

(in blue) means the inverse of an element in G.

Centers

We say that an element g ∈ G commutes with another element x ∈ G if the order of multiplication

is irrelevant: gx = xg. Otherwise said, g conjugates x to itself: 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 everything!

• The identity e commutes with everything, regardless of G.

In general, the set of such elements falls somewhere between these extremes. This subset will turn

out to be yet another normal subgroup of G.

Deﬁnition 6.27. 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 6.28. 1. Z(G) = G ⇐⇒ G is abelian.

2. Z(S

) = {e} if n ≥ 3. This is Exercise 4.1.12.

3. Z(D

2n+1

) = {e} and Z(D

) = {e, ρ

n/2

}, where ρ

n/2

is rotation by 180°. Part of this is in

Exercise 12: more generally, this follows from Exercise 4.1.13.

4. Z



(R )



= {λI

: λ ∈ R

}. If you’ve done enough linear algebra to be familiar with

eigenvectors, an argument is reasonably straightforward (Exercise 11)

Theorem 6.29. Let G be any group. Then:

1. Z(G) ◁ G 2.



Z(G)

∼

Inn G

Proof. Everything follows from deﬁning a suitable homomorphism with the correct kernel!

Deﬁne ϕ : G → Inn G by ϕ(g) = c

. This is indeed a homomorphism (ϕ(gh) = ϕ(g)ϕ(h)):



ϕ(gh)



(x) = c

(x) = (gh)x(gh)

−1

= g(hxh

−1

= c

(x))



ϕ(g)ϕ(h)



(x)

Now observe that

g ∈ ker ϕ ⇐⇒ ∀x ∈ G, c

(x) = gxg

−1

= x

⇐⇒ g ∈ Z(G)

By Lemma 6.4, ker ϕ = Z(G) is a normal subgroup of G.

To ﬁnish, observe that ϕ is surjective (deﬁnition of Inn G). The 1

isomorphism theorem tells us that



Z(G)

∼

Im ϕ = Inn G

Exercises 6.3. Key concepts: Conjugation Conjugacy Classes Cycle Types are Conjugacy Classes (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 6.21.1. Find another element ν = ρ for which νσν

−1

= τ. Now determine how

many distinct such ν exist: that is, how many ways can we conjugate σ to get τ?

3. Prove Lemma 6.17. 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. In Example 6.21.2 we saw that V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} ◁ 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 6.24: 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 6.1.7. 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 6.29. 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. 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 (i.e. x is the 1

column of X). Prove that Bx = λx.

, what can we conclude about B?

What is the group Z



(R )



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

13. The centralizer of an element x ∈ G is the set of elements which conjugate x to itself:

C(x) =



g ∈ G : gxg

−1

= x



(a) Prove directly that C(x) is a subgroup of G.

(b) We compute a few centralizers directly. The centralizer of σ = (1 2 3) ∈ S

is the set of all

ρ for which

(1 2 3) = ρσρ

−1



ρ(1) ρ(2) ρ(3)



Otherwise said, ρ must permute the elements {1, 2, 3} in order. We conclude that

C(σ) =



e, (1 2 3), (1 3 2)



= {e, σ, σ

}

∼

In similar fashion, compute the centralizers of the following elements and identify the

group C(σ):

i. σ = (1 2) ∈ S

ii. σ = (1 2 3 4 5) in both S

and A

iii. σ = (1 2)(3 4) in both S

and A

14. Prove that if



Z(G)

is cyclic, then G is abelian. What is the group



Z(G)

in such a situation?

7 Group Actions

7.1 Group Actions, Fixed Sets and Isotropy Subgroups

You may feel by now that groups are worthy of study purely in their own right—if so great! For

many, however, the fundamental reason to care about groups is because of how they transform sets.

Recall how the symmetric group S

(Section 4) 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 7.1. An action

of a group G on a set X is a function · : G × X → X for which,

(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 (G, ·) →



{f : X → X}, ◦



Examples 7.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 simply composition of functions!

2. If X is the set of orientations of a regular n-gon centered at the origin and with one vertex at

(1, 0), then D

acts on X by rotations and reﬂections. This is essentially our deﬁnition of D

3. Any group G acts on itself by left multiplication (X = G). This is essentially the proof of

Cayley’s Theorem (4.8). G also acts on itself by conjugation (c

◦c

= c

is Theorem 6.26).

4. Matrix groups act on vector spaces by matrix multiplication. For example the orthogonal group

(R ) transforms 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 X = {1, −1} via A ·x := (det A)x.

ii. O

(R ) acts on 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 actions to help visualize a group (or even deﬁne it!); in this context, some actions are

better than others. Consider the three actions of O

(R ) in part 5 above.

i. X = {1, −1} is too small to provide a detailed picture of the group since many matrices act in

the same way: e.g.



1 0

0 1



and



−1 0

0 −1



both “multiply by 1 (= det A)”.

ii. X = R

is unnecessarily large. The action leaves any vertical vector untouched.

iii. X = S

is large enough that the action of distinct matrices can be distinguished without being

inefﬁciently large (a Goldilocks action, perhaps?).

This is strictly a left action. There is an analogous deﬁnition of a right action. In these notes, all actions will be left.

These notions can be formalized.

Deﬁnition 7.3. Let G × X → X be an action.

1. The ﬁxed set of g ∈ G is the set (subset of X)

Fix(g) := {x ∈ X : g ·x = x} (also written X

)

2. The isotropy subgroup or stabilizer of x ∈ X is the set (subset of G)

Stab(x) := {g ∈ G : g ·x = x} (also written G

)

3. The action is faithful (or effective) if the only element of G ﬁxing everything is e. Equivalently:

(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

Very loosely, an action that is both faithful and transitive is likely reasonable for visualizing a group.

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

acts faithfully and transitively on the orientations of the n-gon.

3. The action of a group on itself by left multiplication is both faithful and transitive. Conjugation

is more complex: in this context, the stabilizer of x ∈ G is called its centralizer C(x) = Stab(x).

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 7.4. For each x ∈ X, the stabilizer Stab(x) is indeed a subgroup of G.

Proof. We use the subgroup criterion:

Non-emptiness Part (a) of Deﬁnition 7.1 says that e ∈ Stab(x).

Closure This is part (b) of the Deﬁnition. Let g, h ∈ Stab(x), then

(gh) · x = g ·(h ·x) = g ·x = x =⇒ gh ∈ Stab(x)

Closure This relies on both parts of the Deﬁnition. If g ∈ Stab(x), then

x = g · x =⇒ g

−1

· x = g

−1

·(g · x) = (g

−1

g) · x = e · x = x

=⇒ g

−1

∈ Stab(x)

Example 7.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 E =



{1, 2}, {1, 3}, {2, 3}



. You needn’t write all these

out since stabilizing an edge is equivalent to stabilizing its opposite vertex. Still, here is the data:

Element g

Fix(g)

e E

∅



{2, 3}





{1, 3}





{1, 2}



Edge {x, y} Stab({x, y})

{1, 2} {e, µ

}

{1, 3} {e, µ

}

{2, 3} {e, µ

}

Exercises 7.1. Key concepts: (left) action Fix(g) Stab(x) ≤ G faithful & transitive actions

1. For part 5 of Example 7.2, determine whether each action is faithful and/or transitive.

2. Consider the cyclic subgroup G =

⟨

⟩

of S

generated by the 6-cycle σ = (1 2 3 4 5 6).

(a) State the ﬁxed sets and stabilizers for the natural action of G on the set X = {1, 2, 3, 4, 5, 6}.

(b) Is the action of G faithful? Transitive?

3. Repeat the previous question when σ = (1 3)(2 4 6).

4. Mimic Example 7.5 for the actions of D

on X = {vertices} and E = {edges} of the square.

(Use whatever notation you like; ρ, µ, δ or cycle notation)

5. Prove that left multiplication of G on itself g ·x = gx is:

(a) Free: ∃x ∈ G, g · x = x =⇒ g = e (this is stronger than faithfulness [∀ versus ∃]).

(b) Transitive.

6. Suppose that G acts on itself (X = G) by conjugation g · x = gxg

−1

(a) Prove that conjugation is faithful if and only if the center is trivial: Z(G) = {e}.

(b) If G is abelian, is conjugation faithful? Transitive? Explain.

, is conjugation faithful? Transitive? Explain.

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

7.2 Orbits & Burnside’s Formula

We ﬁrst met orbits in the context of the symmetric groups S

. The same idea applies to any action.

Deﬁnition 7.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 (also written G · x)

Examples 7.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 in Section 4.2.

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 7.8. The orbits of an action partition X.

We omit the proof: compare the special case where S

acts on X = {1, . . . , n} (Lemma 4.12).

Our next result is analogous to Lemma 6.6 where we counted the number of (left) cosets of ker ϕ.

Lemma 7.9. The cardinality of the orbit Gx is the index of the isotropy subgroup Stab(x):



G : Stab(x)



For a ﬁnite group

, the size of the orbit necessarily divides the order of the group

Proof. Observe that

g · x = h ·x ⇐⇒ h

−1

g · x = x ⇐⇒ h

−1

g ∈ Stab(x)

⇐⇒ g Stab(x) = h Stab(x)

Otherwise said (contrapositive) distinct elements of Gx correspond to distinct left cosets.

Examples 7.10. 1. 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,

Stab( 3) = {τ ∈ G : τ(3) = 3} = {σ

: σ

(3) = 3} = {e, σ

}

=⇒



G : Stab(3)



= 3 =

{2, 3, 7}

We now have two meanings of transitive; one for equivalence relations and one for actions. Be careful!

2. In Exercise 6.3.13 we computed several centralizers (stabilizers under conjugation). Notice

what the Lemma says about the size of the orbit of the 3-cycle σ = (1 2 3) under conjugation:

(σ)

C(σ)

= 2

As it should be, this is precisely the size of the conjugacy class of 2-cycles!

Burnside’s Formula

It can be useful to count the number of orbits of an action. For ﬁnite actions, this can be done in two

different ways, which leads to an interesting formula. We start by observing that

S =



(g, x) ∈ G ×X : g · x = x



has cardinality

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

We now count the elements of S in a different way. Since (G : Stab(x)) =

Stab(x)

, we see that

∑

x∈X

Stab(x)

∑

x∈X

(G : Stab(x))

∑

x∈X

(∗)

where we used Lemma 7.9 for the last equality. Consider a ﬁxed orbit Gy. Since

constant for each x ∈ Gy, we conclude that

∑

x∈Gy

= 1

The summation (∗) therefore counts 1 for each distinct orbit. In concludsion:

Theorem 7.11 (Burnside’s formula). Let G be a ﬁnite group acting on a ﬁnite set X. Then

# orbits =

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

Example (7.10.1 cont). Here is the data when G =

⟨

⟩

⟨

(1 4)(2 7 3)

⟩

acts on X = {1, 2, 3, 4, 5, 6, 7}:

x ∈ X Stab(x)

1, 4 {e, σ

, σ

}

2, 3, 7 {e, σ

}

5, 6 G = {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}

Burnside’s formula merely sums the cardinalities of all 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 group.

Example 7.12. A child’s toy consists of a wooden equilateral triangle whose edges are painted using

any choice of colors of the rainbow. How many distinct toys could we create?

This might feel like an imprecisely-posed problem, but think for a moment like a child: wouldn’t

they likely consider the two pictured triangles below to be the same? The language of group actions

can help make this precise.

• If we orient each triangle the same way, then a single toy may be considered as an element of

X = {ordered color triples}. Since there are 7 choices for the color of each edge, we see that

= 7

= 343 (a large set!).

• Two toys are equivalent if they differ only by a ro-

tation in 3-dimensions. This amounts to the natural

action of D

on X: for instance, taking ρ

to rotate

120° counter-clockwise,

·(red,green,violet) = (violet,red,green)

The number of distinct toys is therefore the number of orbits of D

on X, which we may compute

using Burnside. Since it would be time consuming to ﬁnd the stabilizer of each element of X, we use

the ﬁxed set approach.

Identity e: For any action Fix(e) = X.

Rotations ρ

, ρ

: If a color-scheme is ﬁxed by ρ

, then all pairs of adjacent edges must be the same

color. Since there are seven colors in the rainbow, we see that

Fix(ρ

)

= 7.

Reﬂections µ

, µ

: Since µ

swaps two edges, any color-scheme in its ﬁxed set must have these

edges the same color. We have 7 choices for the color of the switched edges, and an independent

choice of 7 colors for the other edge. It follows that



Fix(µ

)



= 7

= 49.

The number of distinct toys is therefore

# orbits =

∑

σ∈D

Fix(σ)

+ 7 + 7

|{z}

rotations

+ 7

| {z }

reﬂections

)

(49 + 1 + 1 + 7 + 7 + 7) = 84

For simpler version of the problem, consider the situation where all sides must be different colors. In

this case D

acts on a set of color-schemes with cardinality

= 7 · 6 ·5 = 210. Moreover, only the

identity element has a non-empty ﬁxed set. The number of distinct three-colored toys is therefore

# orbits =

∑

σ∈D

Fix(g)

(210 + 0 + ··· + 0) =

210

= 35

Of course you are welcome to answer questions like these using pure combinatorics without any

resort to group theory!

Example 7.13 (Dice-rolling for Geeks). Various games (such as Dungeons & Dragons) make use of

polyhedral dice beyond merely the cube (see, for instance, Exercise 2.4.12).

Since dice are for rolling, we consider two such to be equivalent if one can be rotated into the other. It

shouldn’t be hard to convince yourself that the pictured tetrahedral dice are distinct (non-equivalent):

the ﬁrst cannot be rotated to make the second.

Indeed, it is not difﬁcult to see that these are the only tetrahe-

dral dice: if you place 4 on the table, then the remaining faces

must be numbered 1, 2, 3 either counter-clockwise or clockwise.

For larger dice, such a counting approach is impractical.

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. Denote the set of distinct labellings

by X.

• We may rotate the polyhedron so that any face is mapped to any other, in any orientation. For

instance, the face labelled 1 may be rotated to any of the f faces, before rotating the polyhedron

around that face in any of n orientations. The rotation group G of the polyhedron therefore has

f n elements.

• Each non-identity element of the rotation group G moves at least one face, whence

Fix(g)

(

X if g = e

∅ if g = e

• By Burnside’s formula, the number of distinct dice for a regular polyhedron is therefore

# orbits =

Fix(e)

f !

f n

( f −1)!

Here is the complete data for all the regular platonic solids.

Polyhedron f n Rotation Group # distinct dice (orbits)

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

Note that we don’t need an explicit description of the rotation group, only its order

. We saw

that the rotation group of regular tetrahedron was A

in Example 4.26.3. Proving that the remaining

groups are as claimed is somewhat trickier. . .

Exercises 7.2. Key concepts: Orbits partition X

= (G : Stab(x)) Burnside’s formula

1. Determine the orbits of G =

⟨

⟩

on X = {1, 2, 3, 4, 5, 6} for each of Exercises 7.1.2 and 3. In both

cases verify Burnside’s formula.

2. Revisit Example 7.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 7.8: the orbits of a (left) action partition X.

4. Revisit Exercise 6.3.13 and Example 7.10.2. Prove that there are two distinct conjugacy classes

of 5-cycles in A

. Provide an example of two 5-cycles which are not conjugate in A

5. A 10-sided die (see Exercise 2.4.12) is shaped so that all faces are congruent kites: ﬁve faces are

arranged around the north pole and ﬁve around the south.

(a) Argue that the group of rotational symmetries of such a die has ten elements, and that it

is isomorphic to D

(b) Use Burnside’s formula to determine how many distinct 10-sided dice (faces numbered 1

to 10) may be produced.

6. 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?

7. The faces of a cuboid measuring 1 ×1 ×2 in are to be painted using (at

most) two colors. Up to equivalence by rotations, how many ways can

this be done?

8. Repeat the previous question for a regular tetrahedron.

9. (Hard) A cube has four diagonals: a, b, c, d, which are permuted by

its rotation group. For instance, we might rotate by 180° around

an axis through the midpoints of the sides a

and a

. This

switches diagonals a and b, but leaves c and d alone and therefore

acts as the 2-cycle (a b) on {a, b, c, d}. As a function on vertices,

(a b) :





7→





(a) Describe as best you can how to rotate the cube in a way that corresponds to each of the

following rotations (written in cycle notation):

(a b c), (a b c d), (a b) (c d)

Hence argue that the rotation group of the cube is isomorphic to S

(b) A cube can operate as a “3-sided” die by labelling two each of its faces using the numbers

1, 2, 3. In how many distinct ways can this be done?

7.3 The Class Equation, p-groups, and the Theorems of Cauchy and Sylow

The toolkit provided by group actions is central to an enormous topic: the classiﬁcation of groups

and their internal structure. This ﬁnal section offers a small taste of this discussion.

Suppose G acts on a ﬁnite set X. Denote the set of 1-element orbits by

g∈G

Fix(g) = {x ∈ X : ∀g ∈ G, g ·x = x}

Let x

, . . . , x

be representatives of the remaining (larger) orbits. Since the orbits partition X,

∑

j=1



∑

j=1



G : Stab(x

)



∑

j=1



Stab(x

)



(∗)

We focus on the special case when G acts on itself (X = G) by conjugation g · x = gxg

−1

• The 1-element orbits comprise the group center: X

= Z(G).

• In this context the stabilizer of an element x ∈ G is known as its centralizer:

C(x) = Stab(x) = {g ∈ G : gxg

−1

= x} = {g ∈ G : gx = xg}

• Equation (∗) is called the class equation:

Z(G)

∑

j=1



conjugacy class of x



Z(G)

∑

j=1



C(x

)



Example 7.14. The conjugacy classes in S

are the cycle-types, so the class equation is easily veriﬁed:

24 =

{e}

+ #



2-cycles



+ #



3-cycles



+ #



4-cycles



+ #



2,2-cycles



= 1 + 6 + 8 + 6 + 3

Our next result applies the class equation to obtain a partial converse to Lagrange’s Theorem.

Theorem 7.15 (Cauchy). If a prime p divides

, then G contains a subgroup/element of order p.

Proof. 1. Exercise 9 supplies an inductive proof that abelian G have such subgroups.

2. If G is non-abelian, then the center Z(G) is a proper (abelian) subgroup.

Let x ∈ Z(G). Plainly C(x) is a proper subgroup of G. If p does not divide

C(x)

, then p divides



G : C(x)



C(x)

. If this holds for all non-trivial orbits, the class equation says that

Z(G)

is divisible by p. Either way, G has a proper subgroup H whose order is divisible by p.

If H is abelian, apply case 1. Otherwise, repeat starting with H to ﬁnd an even smaller subgroup

whose order is divisible by p. If this process never reached an abelian subgroup, then we’d have

an inﬁnite descending sequence of proper subgroups: contradiction.

The resulting subgroup is cyclic (Corollary 5.10), whence an element of order p also exists.

Example 7.16. If G has order 60 = 2

· 3 ·5, then it has subgroups of orders 2, 3 and 5. It also has

subgroups of other orders (at the very least 1, 60 and 4 — this last by the 1

Sylow Theorem below).

Haven’t we done this already? Exercise 3.3.14 appears to cover abelian groups, but this depends on

the Fundamental Theorem (3.26), the standard proof of which in fact relies on Cauchy (Exercise 10)!

Deﬁnition 7.17. Let p be a prime. A group G is a p-group if all its elements have order a power of p.

Examples 7.18. 1. G = Z

is a 2-group.

2. G =

⟨

⟩

(

∼

) is a 3-subgroup of Z

(this last is not a 3-group).

3. Z

⟨

⟩

is a 3-subgroup of Z

×Z

4. V =



e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)



is a 2-subgroup of S

The proofs of the next result are exercises.

Theorem 7.19. 1. A ﬁnite group G is a p-group if and only if

= p

for some n.

2. If G is a p-group, then its center Z(G) is non-trivial.

Corollary 7.20. Let p be prime. If G has order p

, then it is abelian.

Proof. By the Theorem, we know that

Z(G)

= p or p

. In the second case we are done: Z(G) = G

says that G is abelian. In the ﬁrst case the factor group is cyclic:





Z(G)



= p =⇒



Z(G)

∼

Exercise 6.3.14 says G is abelian, though really it’s a contradiction: Z(G) = G =⇒



Z(G)

∼

Our ﬁnal results go some way towards establishing the existence and number of certain subgroups.

We omit the proofs: a typical approach uses induction with Cauchy’s Theorem as the base case, and

the application of various ingenious group actions. If you are interested, look them up!

Theorem 7.21 (Sylow). Let G be ﬁnite and write

= p

m, where p is prime and gcd(p, m) = 1.

1. G contains a subgroup H

of order p

for each i = 1, . . . , n. Moreover, any such subgroup with

i < n is a normal subgroup of some subgroup of order p

i+1

{e} ◁ H

◁ H

◁ ···◁ H

≤ G (†)

2. Any two maximal p-subgroups H

(called Sylow p-subgroups) are conjugate.

3. The number of Sylow p-subgroups divides

and is congruent to 1 modulo p.

Only the last inclusion in (†) can be non-normal. For a given example, the 3

Theorem might show

that there is a unique Sylow p-subgroup H

: by Exercise 6.3.5, such a subgroup is necessarily normal.

Examples 7.22. 1. Suppose

= 15 = 3 ·5. By the 1

Sylow Theorem, G has at least one Sylow

3-subgroup (isomorphic to Z

) and at least one Sylow 5-subgroup (isomorphic to Z

The divisors of 15 are listed, along with whether each is con-

gruent to 1 modulo 3 or 5. By the 2

and 3

Theorems, G has

exactly one subgroup isomorphic to Z

and one to Z

: being

self-conjugate, both subgroups are normal.

Divisor d 1 3 5 15

d ≡ 1 (mod 2)? ✓

d ≡ 1 (mod 3)? ✓

By Lagrange, the orders of elements in G can only be 1, 3, 5 or 15. Since an order 3 element

generates a subgroup isomorphic to Z

(the unique Sylow 3-subgroup), only two elements in

G have order 3. Similarly only four elements in G have order 5 (each being a generator of the

unique Sylow 5-subgroup). Since only the identity has order 1, the remaining 8 = 15 −1 −2 −4

elements must have order 15, and thus generate G.

In conclusion: if

= 15, then G

∼

is cyclic. Exercise 5 extends this analysis to when

= pq, where p < q are primes for which q −1 is not divisible by p: in such a case G

∼

2. Suppose

= 100 = 2

·5

. By the 1

Sylow Theorem, G has at least one Sylow 5-subgroup of

order 5

= 25, and at least one Sylow 2-subgroup of order 4 = 2

. We can be more precise by

applying the other results.

The full list of divisors of

= 100 is: 1, 2, 4, 5, 10, 20, 25, 50, 100.

• The only divisor congruent to 1 modulo 5 is 1 itself! By the 3

Theorem, there is precisely

one Sylow 5-subgroup H

of G. Since this is the only subgroup of order 25, it must be

normal: H

◁ G. By Corollary 7.20, H

is abelian. The Fundamental Theorem says that

either H

∼

or H

∼

×Z

• The divisors 1, 5 and 25 are congruent to 1 modulo 2, so there might be 1, 5 or 25 distinct

Sylow 2-subgroups of G.

We give several sub-examples where the Sylow p-subgroups can be seen explicitly.

(a) G = Z

100

has one Sylow 5-subgroup

⟨

⟩

∼

, and one Sylow 2-subgroup

⟨

⟩

∼

(b) G = Z

× Z

has one Sylow 5-subgroup

⟨

(2, 0)

⟩

∼

, and one Sylow 2-subgroup

⟨

⟩

×Z

∼

×Z

has one Sylow 5-subgroup Z

⟨

⟩

∼

×Z

, and one Sylow 2-subgroup

⟨

(0, 5)

⟩

∼

(d) G = D

has one Sylow 5-subgroup consisting of half the 50 rotations:

⟨

⟩

= {ρ

, ρ

, . . . , ρ

}

∼

There are 25 distinct Sylow 2-subgroups, each of which is isomorphic to the Klein 4-group

V. These may be described explicitly if we label the reﬂections µ

, . . . , µ

= {ρ

, ρ

, µ

i+25

}, i = 1, . . . , 25

Note that D

has no subgroups isomorphic to Z

(reﬂections have order 2 and rotations

have orders 1, 5 or 25). This is also clear from the 2

Theorem: all Sylow 2-subgroups are

conjugate and thus isomorphic (to V).

Exercises 7.3. 1. State all the 3-subgroups of Z

2. Let p be a prime of your choice. In contrast to Corollary 7.20, give an example of a non-abelian

group of order p

3. Suppose

= 225 = 3

·5

. Prove that G has a normal subgroup of order 25.

4. Suppose

= 20 = 2

·5.

(a) Determine how many distinct Sylow 2- and Sylow 5-subgroups G can have. Must they be

normal subgroups?

(b) Similarly to Example 7.22.2, state the Sylow subgroups when

i. G = Z

, ii. G = D

5. Let G have order pq, where p < q are distinct primes (≥ 3). Then all proper subgroups of G are

cyclic (isomorphic to Z

, Z

or Z

(a) If pq = 2 ·3 = 6, then G

∼

. State all the Sylow 2- and 3-subgroups in each case.

(b) Returning to the general case, prove that there is a unique Sylow q-subgroup H

∼

(which is therefore normal) by showing that p ≡ 1 (mod q) is a contradiction.

subgroup K

∼

(which is also normal). Extending the analysis of Example 7.22.1, prove

that G

∼

(d) If

= 21 (p = 3, q = 7), show that there are either one or seven Sylow 3-subgroups. In

the former case, argue that G

∼

(The latter case [seven 3-subgroups] results in a new non-abelian group not seen in these notes.)

6. Prove Theorem 7.19, part 1.

(Hints: one direction uses Lagrange’s Theorem, the other Cauchy)

7. Suppose G is a p-group which acts on a ﬁnite set X.

(a) Prove that

≡

(mod p).

(Hint: what can you say about

if x lies in a non-trivial orbit?)

(b) Prove part 2 or Theorem 7.19, that p divides the order of the center Z(G).

8. The alternating group A

has order 60 = 2

· 3 · 5 and comprises the identity, all 3-cycles, 5-

cycles, and 2,2-cycles in S

(a) Describe all the Sylow 2-, 3-, and 5-subgroups of A

and verify that the number of each is

in line with the 3

Theorem.

(b) Extending Exercise 7.2.4, ﬁnd the sizes of all conjugacy classes in A

. Hence prove that A

is a simple group: if N is a normal subgroup of A

, then N = {e} or A

(Simple groups are very important and have applications throughout mathematics. Their full

classiﬁcation was completed in 2004—an enormous undertaking: look it up. . . )

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.

Fix n ≥ 3, let G be abelian of order n and assume p divides n. For the induction hypothesis,

assume that if K is any abelian group of order

< n where p divides

, then K has a

subgroup of order p.

• Let x ∈ G be a non-identity element with order m =

|⟨

⟩|

(necessarily m ≥ 2).

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

m/q

and let H :=

⟨

⟩

(b) What is the order of H? Explain why are we done if q = p.



order p. Now prove that z

has order p in G.

10. We sketch part of the proof of the Fundamental Theorem of Finite Abelian Groups (3.26).

Suppose G is abelian and that

= p

m where p does not divide m. Deﬁne

H = {x ∈ G : x

= e}, K = {x ∈ G : x

= e}

(a) Show that H is a p-group.

(b) Since gcd(m, p

) = 1, we may write 1 = κm + λp

for some κ, λ ∈ Z.

i. For any x ∈ G, prove that x

κm

∈ H and x

λp

∈ K.

ii. Prove that the following function is an isomorphism:

ψ : G → H × K : x 7→



κm

, x

λp



(Hint: try evaluating ψ(hk). . . ).

= p

by applying Cauchy’s Theorem to show that p does not divide

(Inducting on this shows that G

∼

×···× H

where each H

is a p

-group of maximal order. A

little more work is needed to show that each H

is itself a direct product of cyclic groups and thus

complete the proof.)