6 Cosets & Factor Groups

In this chapter

we partition a group into subsets so that the set of subsets inherits a natural group

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

precisely the idea behind modular arithmetic.

Example 6.1. In Z

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

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

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

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

When we write 1 +

2 = 0 ∈ Z

, we really mean

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

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

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

6.1 Cosets & Normal Subgroups

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

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

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

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

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

Hg := {hg : h ∈ H}

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

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

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

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

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

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

elements of Z

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

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

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

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

The examples are everything in this chapter: write everything out by hand until it becomes easy—there is no shortcut!

The last observation is in fact general—we leave the proof as a straightforward exercise.

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

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

Examples 6.4. 1. Consider the subgroup H =

⟨

⟩

= {0, 4, 8} ≤ Z

. This is cyclic with order 3. The

distinct cosets of

⟨

⟩

are as follows (left = right since Z

is abelian!):

⟨

⟩

= {0, 4, 8}



= 4 +

⟨

⟩

= 8 +

⟨

⟩



1 +

⟨

⟩

= {1, 5, 9}



= 5 +

⟨

⟩

= 9 +

⟨

⟩



2 +

⟨

⟩

= {2, 6, 10}



= 6 +

⟨

⟩

= 10 +

⟨

⟩



3 +

⟨

⟩

= {3, 7, 11}



= 7 +

⟨

⟩

= 11 +

⟨

⟩



Observe that the cosets partition Z

into equal-sized subsets.

2. By revisiting the multiplication table for D

(Example 1.2) or using cycle notation, we verify

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

} are as follows:

Left cosets Right cosets

H = µ

H = {e, µ

} H = Hµ

= {e, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

H = µ

H = {ρ

, µ

} Hρ

= Hµ

= {ρ

, µ

}

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

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

into three equal-sized

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

3. Consider a 1-dimensional subspace W ≤ R

; this is a line

through the origin. The coset

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

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

parallel to W. Note again that these partition R

: every

point in R

lies in precisely one coset.

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

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

coset W = 0 + W is a subspace.

v + W

4. Recall Theorem 5.24. If we generalize the argument, we see that, for any α ∈ A

and σ ∈ S

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

Otherwise said, for any σ ∈ S

, the cosets of A

containing σ are

σA

= A

σ =

(

if σ even

if σ odd

where B

is the set of odd permutations in S

. In particular, A

is a normal subgroup of S

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

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

y ∈ xH ⇐⇒ x

−1

y ∈ H ⇐⇒ xH = yH

The right cosets partition G similarly: indeed

y ∈ Hx ⇐⇒ yx

−1

∈ H ⇐⇒ Hx = Hy

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

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

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

Proof. We start by verifying the ﬁrst connective.

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

−1

y = h ∈ H

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

Reﬂexivity: x ∼ x since x

−1

x = e ∈ H.

Symmetry: x ∼ y =⇒ x

−1

y ∈ H =⇒ (x

−1

∈ H, since H is a subgroup. But then

−1

x ∈ H =⇒ y ∼ x

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

−1

y ∈ H and y

−1

z ∈ H. But H is closed, whence

−1

z = (x

−1

y) (y

−1

z) ∈ H =⇒ x ∼ z

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

indeed the left coset xH, as required.

It is precisely the fact that H is a subgroup which guarantees a partition (compare Theorem 2.19)!

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

Symmetry: H satisﬁes the inverse axiom.

Transitivity: H is closed under the group operation.

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

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

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

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

We ﬁnish this section with a technical result which will be useful in future sections.

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

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

−1

∈ H

Proof. Start by using the above criteria to observe:

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

−1

∈ H

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

−1

hg ∈ H

We may now complete the proof in two parts:

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

( ⇐) If ghg

−1

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

−1

: that is g

−1

hg ∈ H. We now have the right

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

Exercises 6.1. Key concepts:

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

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

are identical.

(a) 4Z ≤ 2Z (b)

⟨

⟩

≤ Z

(c)

⟨

⟩

≤ Z

(d)

⟨

⟩

≤ Z

2. Find the cosets of H =



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



≤ Z

×Z

3. Find the left and right cosets of {ρ

, ρ

} ≤ D

. Is the subgroup normal?

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

. Is the subgroup normal?

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

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

, δ

} ≤ D

. Is the subgroup normal?

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

, ρ

(Hint: use cycle notation (Exercises 5.1.5.7), or look up the Cayley table)

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

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

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

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

, even though H is not a subgroup.

8. Let H = {σ ∈ S

: σ(4) = 4}.

(a) Show that H is a subgroup of S

: we call this the stabilizer of 4.

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

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

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

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

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

. Compute the double cosets.

6.2 Lagrange’s Theorem & Indices

We’ve been inching up to a powerful result; with luck you’ve hypothesized this already!

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

Otherwise said

H ≤ G =⇒



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

: H → gH : h 7→ gh

is a bijection (with inverse ϕ

−1

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

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

= (number of left cosets of H) ·

=⇒



We could similarly have proved this using the right coset partition. Here is an example of its power.

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

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

The order of the cyclic subgroup

⟨

⟩

≤ G satisﬁes:

•

|⟨

⟩|

≥ 2 since g = e.

•

|⟨

⟩|

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

We conclude that

|⟨

⟩|

= p =⇒ G =

⟨

⟩

is cyclic and thus isomorphic to Z

(Theorem 3.13).

Example 6.10. G = Z

× Z

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

2 or 4 and are thus isomorphic to Z

, Z

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

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

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

generator order subgroup

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

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

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

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

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

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

×Z

⟨

(1, 0)

⟩

⟨

(1, 1)

⟩

⟨

(0, 1)

⟩ ⟨

(2, 0)

⟩ ⟨

(2, 1)

⟩

⟨

(0, 0)

⟩

This is sometimes misremembered as ‘the order of an element divides the order of the group.’ This is the special case

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

⟨

⟩

≤ Z

has order

gcd( s,n)

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

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

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

the quotient

. This motivates a new concept.

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

(G : H) =

{gH : g ∈ G}

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

Examples 6.12. 1. If G = Z

and H =

⟨

⟩

, then there are (G : H) =

= 2 cosets:

H =

⟨

⟩

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

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

(R ) = {A ∈ M

(R ) : A

A = I}, SO

(R ) = {A ∈ O

(R ) : det A = 1}

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

(R ) should be ‘half’ of

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

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

(R ),

A SO

= B SO

(R ) ⇐⇒ B

−1

A ∈ SO

(R ) ⇐⇒ det(B

−1

A) = 1 ⇐⇒ det B = det A

We conclude that there are precisely two cosets



(R ) : SO

(R )



= 2.

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

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

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

(G : K) =

= (G : H)(H : K)

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

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

Proof. Choose an element g

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

from each left coset of

K in H. Plainly

(G : H) =

}

and (H : K) =



}



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

)K. Certainly each such is a coset; we

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

)K} must comprise all left cosets.

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

∈ G such that g ∈ g

−1

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

∈ H such that g

−1

g ∈ h

But then g ∈ (g

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

)K.

• Suppose y ∈ g

K ∩ g

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

y ∈ g

H ∩ g

H =⇒ g

= g

But then g

−1

y ∈ h

K ∩h

K =⇒ h

= h

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

follows that the sets (g

)K are disjoint.

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

)K}, it is immediate that

(G : K) =



}



}



}



= (G : H)(H : K)

Examples 6.14. 1. Recall Example 6.12.1: let G = Z

, H =

⟨

⟩

and K =

⟨

⟩

. Plainly

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

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

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

= 0 and g

= 1.

• (H : K) =

= 5 cosets, with representatives h

= 0, h

= 2, h

= 4, h

= 6, h

= 8:

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

• (G : K) =

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

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

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

+ h

) + K.

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

where

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

∼

and H = {σ ∈ S

: σ(4) = 4}

∼

The (H : K) =

= 2 left cosets of K in H are

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

with representatives h

= e and h

= (1 2). The (S

: H) =

= 4 left cosets of H in S

are

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

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

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

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

with representatives g

= e, g

= (1 4), g

= (2 4), g

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

are

therefore

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

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

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

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

Exercises 6.2. Key concepts:

Lagrange’s Theorem index of a subgroup

1. Find the indices of the following subgroups:

(a)

⟨

⟩

≤ Z

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

, ·) ≤ (Q

, ·)

2. Let G = Z

, H =

⟨

⟩

and K =

⟨

⟩

. Write out all the cosets for the three subgroup relations

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

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

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

×Z

are cyclic. Hence con-

struct its subgroup diagram.

5. Find the subgroups of Z

×Z

and draw its subgroup diagram.

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

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

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

each case?

(Remember that G could be inﬁnite!)

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

. Prove that the function

Φ : g

H 7→ Hg

−1

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

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

9. Let G = {a + b

√

2 : a, b ∈ Z}.

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

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

√

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

(Hint: what does it mean for a + b

√

2 and c + d

√

2 to lie in the same coset of H?)

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

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

is countably

inﬁnite.

6.3 Factor Groups

Given a subgroup H ≤ G, we ask whether the set of left cosets {gH : g ∈ G} can be viewed as a group

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

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

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

⟨

⟩

= {0, 4, 8} ≤ Z

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

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

It feels like we have the cyclic group Z

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

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

and deﬁne addition of cosets via

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

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

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

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

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

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

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

there are nine possibilities, of which one is

6 +

11 = 17 = 5 ∈ 1 + H

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

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

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

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

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

with this factor group.

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

H = {e, µ

} ≤ D

, whose left cosets are

H = µ

H = {e, µ

}, ρ

H = µ

H = {ρ

, µ

}, ρ

H = µ

H = {ρ

, µ

}

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

aH ⊗bH := (ab)H

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

H ⊗ ρ

H, of which two

sufﬁce for a contradiction:

H = ρ

H and µ

H = H

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

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

Well-deﬁnition of the Factor Group Structure

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

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

in the abstract.

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

aH ·bH := (ab)H

This is well-deﬁned if and only if

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

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

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

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

∀a, b ∈ G, h, h

∈ H, (ab)H = (ahbh

)H = (ahb)H

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

−1

(ahb) ∈ H (Theorem 6.5)

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

−1

hb ∈ H

⇐⇒ H ◁ G (Corollary 6.7)

We have proved the critical part of an amazing result!

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

aH ·bH := (ab)H

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

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



(’G mod H’).

Since the group structure on



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

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







= (G : H) =

Proof. The above discussion shows that the natural operation on



is well-deﬁned if and only if H

is normal in G. It remains only to check that



is a group in such cases.

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





, ·



is closed.

Associativity: aH · (bH · cH) = aH · (bc)H = a(bc)H. Similarly (aH · bH) · cH = ( ab)cH. By the

associativity of G these cosets are identical.

Identity: eH ·aH = (ea)H = aH = (ae)H = aH ·eH therefore the identity coset eH = H is the identity.

Inverse: a

−1

H · aH = (a

−1

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

−1

= a

−1

Factor Groups of Z: modular arithmetic done right!

For each positive integer n, the integer multiples nZ =

⟨

⟩

form a normal subgroup of Z. The coset

of nZ containing x ∈ Z is therefore

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

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

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

ing Deﬁnition 3.4 and trivially proving Theorem 3.5.

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

is the factor group



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

4 + 5 = 2 ∈ Z

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



Factor Groups of Finite Cyclic Groups

Our ﬁrst example in this section showed that



⟨

⟩

∼

. Here is another.

Example 6.18.

⟨

⟩

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

has factor group



⟨

⟩



0 +

⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩

, 4 +

⟨

⟩



This is isomorphic to Z

via the isomorphism

ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

Theorem 6.19. If d | n, then



⟨

⟩

∼

If s is not a divisor of n, recall that

⟨

⟩

⟨

⟩

where d = gcd(s, n), whence



⟨

⟩

∼

gcd(s,n)

Proof. Deﬁne ψ : Z

→



⟨

⟩

: x 7→ x +

⟨

⟩

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

Well-deﬁnition/injectivity:

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

x = y ∈ Z

⇐⇒ x −y ∈

⟨

⟩

⇐⇒ x +

⟨

⟩

= y +

⟨

⟩

⇐⇒ ψ(x) = ψ(y)

Surjectivity: Any coset x +

⟨

⟩

= ψ(x) ∈ Im( ψ).

Homomorphism: For any x, y ∈ Z

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

⟨

⟩



x +

⟨

⟩





y +

⟨

⟩



= ψ(x) + ψ(y)

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

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

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

Finite Abelian Examples

If G is a ﬁnite abelian group, then any subgroup H is normal and



is also a ﬁnite abelian group

(exercise). By the Fundamental Theorem (4.9) there exist positive integers m

, . . . , m

for which



∼

×··· ×Z

and m

···m

= (G : H) =

Our goal in these examples is to identify



as a direct product by ﬁnding suitable integers m

Examples 6.20. For G = Z

×Z

and three subgroups H, we identify the factor group



1. If H =

⟨

(0, 1)

⟩

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

4·8

= 4.

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

or Z

×Z

Here are two strategies for deciding which.

(a) Identify the cosets:

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

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

, whence,



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

It can be checked that this is isomorphic to Z

via ψ : Z

→



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

(b) Observe that there exists an element in



with order 4. If k ∈ N, then



(1, 0) + H



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

This identiﬁes



∼

by elimination: every element of Z

×Z

has order at most 2.

2. H =

⟨

(0, 2)

⟩

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

4·8

= 8. The factor

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

, Z

×Z

or Z

×Z

We again follow our strategies:

(a) Identify the cosets:

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

(

x = v, and

y − w = 2k is even

from which the distinct cosets may be written



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

(x, y) + H : x ∈ Z

, y ∈ Z

We have an isomorphism ψ : Z

×Z

→



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

(b) Alternatively, consider orders of elements:

•



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

• All elements of



have order dividing 4:



(x, y) + H



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



(0, 2) + H



= H

By elimination,



∼

× Z

has an element of order 8, while elements of Z

×Z

have maximum order 2).

3. Consider H =

⟨

(2, 4)

⟩

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

false sense of security:



is not



⟨

⟩



⟨

⟩

∼

×Z

The fact that there are (G : H) =

4·8

= 16 cosets immediately rules out this na

ıve possibility!

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

, Z

×Z

, Z

×Z

, Z

×Z

, Z

×Z

We again follow our strategies:

(a) Identify the cosets. This is a little trickier than before.

• If x = 2n is even, then

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

• If x = 2n + 1 is odd, then

(x, y) + H = (2n + 1, y) + H = n(2, 4) + (1, y −4n) + H = (1, y −4n) + H

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

the sixteen elements

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

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

to Z

×Z

. Indeed

ψ : Z

×Z

→



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

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

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

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



, since



(0, 1) + H



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

which reduces our options to Z

and Z

×Z

. Moreover, any coset has order dividing 8:



(x, y) + H



= (8x, 8y) + H = (0, 0) + H

This rules out Z

, leaving Z

×Z

as the only possibility.

Strategy (b) might seem easier right now, but it has some drawbacks; for instance, it cannot distin-

guish between groups such as Z

×Z

and Z

×Z

: both groups contain an element of order

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

Other Examples

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

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

Examples 6.21. 1.

⟨

2π

⟩

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

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

remainder of x modulo 2π!). It follows that



2πZ



x + 2πZ : x ∈ [ 0, 2π)



Moreover, the function

µ :



2πZ

→ S

: x + 2πZ 7→ e

is an isomorphism of groups. The factor group construction therefore corresponds to wrapping

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

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

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

is a normal subgroup of the alternating group A

. The factor group has order (A

: V) =

= 3

and so



∼

: can you ﬁnd an explicit isomorphism?

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



∼

3. Consider H =

⟨

(2, 1)

⟩

≤ Z × Z

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

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

representative of each coset.

(x, y) + H =

(

(2n, y) + H = (0, y − n) + H if x = 2n is even

(2n + 1, y) + H = (1, y −n) + H if x = 2n + 1 is odd

There is a unique representative in each coset either of the form (0, z) or (1, z), where z ∈ Z

. We

conclude that there are 2 ·4 = 8 cosets. Since



is abelian (Exercise 6), it must be isomorphic

to one of Z

, Z

×Z

or Z

×Z

. To identify which, compute



(x, y) + H



= (4x, 4y) + H = (0, −2x) + H = H ⇐⇒ 2 | x

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



∼

4. Let H =

⟨

(1, 2)

⟩

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

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

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

(0, z). We conclude that



∼

Z. In fact it can be checked that ψ



(x, y) + H



= y −2x deﬁnes

an isomorphism.

Exercises 6.3. Key concepts:

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



identifying



1. List the cosets of the subgroup H =

⟨

⟩

in G = Z

. Verify directly that the function

ψ : Z

7→



: x 7→ x + H

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

2. Identify the factor group

×Z



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

3. (a) Identify the factor group



where H =

⟨

(2, 4)

⟩

≤ G = Z

×Z

(b) Repeat with the subgroup H =

⟨

⟩

⟨

⟩

(this is a trick question!)

4. (a) Let G = Z

× Z

and H =

⟨

(3, 6)

⟩

. Identify



by showing that every element of the

factor group has order at most 9 and that it contains an element of order 9.

(b) Repeat with H =

⟨

⟩

⟨

⟩

(this isn’t a trick question!)

5. Let G be any group. To what groups are



{e}

and



isomorphic?

6. (a) If G is abelian and H ≤ G, prove that



is abelian.

(b) If



is abelian, can we conclude that G and/or H is abelian? Explain.

7. Let G = Z

×Z

. Prove that each function in Examples 6.20 is a well-deﬁned homomorphism.

(a) H =

⟨

(0, 1)

⟩

, ψ : Z

→



: x 7→ (x, 0) + H

(b) H =

⟨

(0, 2)

⟩

, ψ : Z

×Z

→



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

⟨

(2, 4)

⟩

, ψ : Z

×Z

→



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

(Bijectivity follows from the description of the cosets, though proving injectivity might be instructive.)

8. Recall Exercise 6.2.9. The factor group



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

this explicitly by ﬁnding a generator.

9. (a) Let G be a cyclic group with subgroup H. Prove that



is cyclic.

(b) If



is cyclic, does it follow that G is cyclic? Prove or disprove.

10. In Example 6.21.2 we saw that Z

∼



. Find an explicit isomorphism.

11. Exercise 6.1.5 showed that {ρ

, ρ

} is a normal subgroup of D

. To what well-known group is

the factor group



{ρ

, ρ

}

isomorphic? Prove your assertion.

12. Let H =

⟨

(2, 3)

⟩

≤ G = Z

×Z. Prove that



∼

13. Verify the claim in Example 6.21.4 that ψ



(x, y) + H



= y −2x is an isomorphism.

14. (Hard!) Let G = Z

× Z

× Z and H =

⟨

(4, 2, 3)

⟩

. Identify the factor group



as a direct

product Z

×Z

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

(x, y, z) + H where z is either 0, 1 or 2.)

7 Homomorphisms and the First Isomorphism Theorem

In this chapter we further discuss homomorphisms. Of particular importance is the relationship

between normal subgroups, homomorphisms and factor groups.

Unless otherwise stated, in this chapter all homomorphisms are between groups.

7.1 Kernels and Images

Deﬁnition 7.1. Let ϕ : G → L be a homomorphism. The kernel and image (or range) of ϕ are the sets

ker ϕ =



g ∈ G : ϕ(g) = e



Im ϕ =



ϕ(g) : g ∈ G



The image is sometimes denoted ϕ(G). Note that ker ϕ ⊆ G while Im ϕ ⊆ L.

Examples 7.2. 1. ϕ(x) = 2x (mod 4) deﬁnes a homomorphism ϕ : Z → Z

, with

ker ϕ = {x ∈ Z : 2x ≡ 0 (mod 4)} = 2Z, Im ϕ = {0, 2}

2. The kernel should feel familiar from linear algebra: if T : V → W is a linear map between vector

spaces, then the kernel is simply the nullspace

ker T = {v ∈ V : T( v) = 0}

Moreover, if T = L

: M

(R ) → M

(R ) is left-multiplication by a matrix A, then Im T is the

column space of A.

Lemma 7.3. Let ϕ : G → L be a homomorphism. Then,

1. ϕ( e

) = e

(ϕ maps identity to identity)

2. ∀g ∈ G,



ϕ(g)



−1

= ϕ(g

−1

) (ϕ maps inverses to inverses)

3. ker ϕ ◁ G (ker ϕ is a normal subgroup of G)

4. Im ϕ ≤ L (Im ϕ is a subgroup of L)

Proof. 1 & 2 were in Exercise 2.3.6 and we leave 4 as an exercise. We prove 3 explicitly.

3. Suppose k

, k

∈ ker ϕ. Then

ϕ( k

) = ϕ(k

) ϕ(k

) = e

=⇒ k

∈ ker ϕ

ϕ( k

−1

) =



ϕ( k

)



−1

= e

=⇒ k

−1

∈ ker ϕ

It follows that ker ϕ is a subgroup of G.

To see that ker ϕ is normal, recall Corollary 6.7: if g ∈ G and k ∈ ker ϕ, then

ϕ(gkg

−1

) = ϕ(g)ϕ(k)ϕ(g)

−1

= ϕ(g)ϕ(g)

−1

= e

=⇒ gkg

−1

∈ ker ϕ

Examples 7.4. 1. For the homomorphism ϕ : Z → Z

: x 7→ 2x, we see that ker ϕ = 2Z is a normal

subgroup of Z, and Im ϕ = {0, 2} =

⟨

⟩

a subgroup of Z

2. The nullspace of a linear map T : V → W is indeed a subspace and thus a subgroup ker T ≤ V:

since V is abelian, this is a normal subgroup. Moreover, Im T is also a subspace/group of W.

3. det : GL

(R ) → R

is a homomorphism, whence we obtain a normal subgroup

ker det = SL

(R ) = {A ∈ GL

(R ) : det A = 1} ◁ GL

(R )

4. ϕ : Z → Z

: x 7→ 4x (mod 20) is a homomorphism, as may be checked:

ϕ(x + y) = 4(x + y) = 4x + 4y = ϕ(x) + ϕ(y) ∈ Z

Its kernel and image are ker ϕ = 5Z ≤ Z and Im ϕ =

⟨

⟩

= {0, 4, 8, 12, 16} ≤ Z

Since every kernel is a normal subgroup, it is worth identifying the distinct cosets with a view to

describing the factor group



ker ϕ

Lemma 7.5. Let ϕ : G → L be a homomorphism. Then

ker ϕ = g

ker ϕ ⇐⇒ ϕ(g

) = ϕ(g

)

There is precisely one coset of ker ϕ for each element of Im ϕ; otherwise said (G : ker ϕ) =

Im ϕ

Proof. For all g

, g

∈ G, we have

ker ϕ = g

ker ϕ ⇐⇒ g

−1

∈ ker ϕ (Theorem 6.5)

⇐⇒ ϕ(g

−1

) = e

(Deﬁnition 7.1)

⇐⇒ ϕ(g

)

−1

ϕ(g

) = e

(Lemma 7.3)

⇐⇒ ϕ(g

) = ϕ(g

)

We’ll extend this idea shortly; for the moment we use it to aid in ﬁnding homomorphisms.

Theorem 7.6. Let ϕ : G → L be a homomorphism. If G (or L) is ﬁnite, then Im ϕ is a ﬁnite group

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

< ∞ =⇒

Im ϕ



and

< ∞ =⇒

Im ϕ



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

Im ϕ

= (G : ker ϕ) =

ker ϕ

is a divisor of

. The second case

Im ϕ



is Lagrange’s Theorem (6.8).

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

→ Z

If ϕ is such a homomorphism, the Theorem says that

Im ϕ

divides both 17 and 13. The only

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

one homomorphism!

∀x ∈ Z

, ϕ(x) = 0

More generally, if gcd(

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

function ϕ : g 7→ e

2. Describe all homomorphisms ϕ : Z

→ S

Since the domain Z

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

obtain the entire homomorphism ϕ(x) =



ϕ(1)



. There are at most six homomorphisms; one

for each possible element ϕ(1) ∈ S

. Not all of these cases are however possible.

The Theorem says that

Im ϕ

= 1 or 2; the only common divisors of 4 =

and 6 =

If Im ϕ has one element, we obtain the trivial homomorphism ϕ

(

x) = e, ∀x ∈ Z

Im ϕ

= 2, then Im ϕ is a subgroup of order 2 of which S

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

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

(x) = (2 3)

, ϕ

(x) = (1 3)

, ϕ

(x) = (1 2)

for a grand total of four distinct homomorphisms.

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

→ Z

Two facts make this relatively simple:

1. It is enough to deﬁne ϕ(1), for then ϕ(x) = ϕ(1) + ··· + ϕ(1) = ϕ(1) · x.

Im ϕ

must divide d := gcd( m, n). Since Z

has exactly one subgroup of each order dividing n

(Corollary 3.20), Im ϕ must be a subgroup of the unique subgroup of Z

of order d:

Im ϕ ≤



, . . . ,

( d −1)n



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

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

→ Z

, deﬁned by

(x) =

x where k = 0, . . . , d −1

Proof. Following the above, it remains only to check that each ϕ

is a well-deﬁned function. For this,

note ﬁrst that x = y ∈ Z

⇐⇒ y = x + λm for some m ∈ Z, from which

( y) = ϕ

(x + λm) =

x + λk

n =

x = ϕ

(x) (in Z

)

where we used the fact that

is an integer.

Example 7.9. We describe all homomorphisms ϕ : Z

→ Z

Since gcd( 12, 20) = 4, we see that Im ϕ ≤

⟨

⟩

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

. There are four choices:

(x) = 0, ϕ

(x) = 5x, ϕ

(x) = 10x, ϕ

(x) = 15x (mod 20)

Reversing the argument, we see that there are also four distinct homomorphisms ψ : Z

→ Z

(x) = 0, ψ

(x) = 3x, ψ

(x) = 6x, ψ

(x) = 9x (mod 12)

Exercises 7.1. Key concepts:

Image kernels are normal subgroups (G : ker ϕ) =

Im ϕ

| |

Im ϕ



gcd(

)

1. Check that you have a homomorphism (use Corollary 7.8) and compute its kernel and image.

(a) ϕ : Z

→ Z

deﬁned by ϕ(x) = 7x (mod 14).

(b) ϕ : Z

→ Z

deﬁned by ϕ(x) = 5x (mod 20).

2. Describe all homomorphisms between the groups:

(a) ϕ : Z

→ Z

(b) ϕ : Z → Z

→ D

(d) ϕ : Z

→ A

3. Find the kernel and image of each homomorphism.

(a) The trace of a matrix: tr : M

(R ) → R deﬁned by tr



a b

c d



= a + d = a + d

(b) T : R

→ R

: x 7→

1 1 −1

0 3 −1

1 4 −2

2 5 −3

(Hint: remember row operations. . . )

4. Explain why the map ϕ is a homomorphism and ﬁnd ker ϕ:

ϕ : S

→



{1, −1}, ·



: σ 7→

(

1 if σ even

−1 if σ odd

5. (a) Prove Part 4 of Lemma 7.3: if ϕ : G → L is a homomorphism, then Im ϕ ≤ L.

(b) If H ≤ G and ϕ : G → L a homomorphism, prove that ϕ(H) := {ϕ(h) : h ∈ H} ≤ Im ϕ.

6. Prove that the number of distinct isomorphisms ϕ : Z

→ Z

equals the cardinality of the group

of units in Z

(see Exercise 3.2.10))



{x ∈ Z

: gcd(x, n) = 1}

7. Prove that ϕ : Z

×Z

→ Z

×Z

is a well-deﬁned homomorphism if and only if there exist

integers a, b, c, d for which

ϕ(x, y) =



ax + by, cx + dy



, m | bn and n | cm

(Hint: let (a, c) = ϕ(1, 0), etc.)

8. Find all homomorphisms ϕ : Z

×Z

→ Z

×Z

. How do you know that there are no more?

9. Consider ϕ : D

→ D

: σ 7→ σ

. Show that ϕ is not a homomorphism.

7.2 The First Isomorphism Theorem

We’ve seen that all kernels of group homomorphisms are normal subgroups. In fact all normal sub-

groups are the kernel of some homomorphism.

Theorem 7.10 (Canonical Homomorphism). Let G be a group and H ◁ G. Then the function

γ : G →



deﬁned by γ(g) = gH

is a homomorphism with ker γ = H.

Proof. Since H is normal,



is a group. By the deﬁnition of multiplication in



γ(g

) γ(g

) = g

H · g

H = (g

)H = γ(g

)

whence γ is a group homomorphism. Moreover, the identity in the factor group is H, whence

ker γ = {g ∈ G : γ(g) = H} = {g ∈ G : gH = H} = H

This might feel a little sneaky and unsatisfying; we’d perhaps have preferred a homomorphism that

doesn’t have a factor group as its image! However, the following companion result says that, among

homomorphisms with the same kernel, γ is unavoidable.

Theorem 7.11 (1

Isomorphism Thm). Let ϕ : G → L be a homomorphism with kernel H. Then

µ :



→ Im ϕ deﬁned by µ(gH) = ϕ(g)

is an isomorphism. Otherwise said,



ker ϕ

∼

Im ϕ.

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

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

ical homomorphism with kernel ker ϕ. There are analogues in

several other parts of mathematics; in particular, the rank–nullity

theorem from linear algebra is of close kin.

Im ϕ



ker ϕ

;;

Proof. The factor group exists since ker ϕ ◁ G (Lemma 7.3). We check the isomorphism properties:

Well-deﬁnition and Bijectivity: These are immediate from Lemma 7.5 after writing H = ker ϕ:

H = g

H ⇐⇒ ϕ(g

) = ϕ(g

) ⇐⇒ µ(g

H) = µ(g

Homomorphism: For all g

H, g

H ∈



µ(g

H · g

H) = µ(g

H) = ϕ(g

) = ϕ(g

) ϕ(g

) (ϕ is a homomorphism)

= µ(g

H)µ(g

We conclude that µ is an isomorphism.

Examples 7.12. 1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 5x (mod 20) (Example 7.9). Its

kernel and image are

ker ϕ =



x ∈ Z

: 5x ≡ 0 (mod 20)



= {0, 4, 8} =

⟨

⟩

≤ Z

Im ϕ = {5x ∈ Z

: x ∈ Z

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

⟨

⟩

≤ Z

The relevant factor group is



ker ϕ

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



⟨

⟩

, 1 +

⟨

⟩

, 2 +

⟨

⟩

, 3 +

⟨

⟩



The canonical homomorphism γ and the isomorphism µ are

γ(x) = x +

⟨

⟩



⟨

⟩

Im ϕ



x +

⟨

⟩



= 5x x



x +

⟨

⟩



2. (Example 6.21.1) Let H =

⟨

2π

⟩

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

, ·) by ϕ(x) = e

. This is a

homomorphism with

ker ϕ = {x ∈ R : e

= 1} = H and Im ϕ = S

The canonical homomorphism is

γ : R →



: x 7→ x +

⟨

2π

⟩

while the isomorphism we saw previously

µ :



→ S

: x +

⟨

2π

⟩

7→ e

is precisely that arising from the 1

isomorphism theorem.

3. The map ϕ : Z ×Z → Z deﬁned by ϕ(x, y) = 3x −2y is a homomorphism. Moreover

ϕ(x, y) = (0, 0) ⇐⇒ 3x = 2y ⇐⇒ (x, y) = (2n, 3n) for some n ∈ Z

We conclude that ker ϕ =

⟨

(2, 3)

⟩

. The canonical homomorphism is

γ : Z ×Z →

Z × Z



⟨

(2, 3)

⟩

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

⟨

(2, 3)

⟩

Since ϕ is surjective, we see that

Z × Z



⟨

(2, 3)

⟩

∼

Z via µ



(x, y) +

⟨

(2, 3)

⟩



= 3x −2y

With a little creativity, the theorem can be applied to the identiﬁcation of factor groups: given H ◁ G,

cook up a homomorphism ϕ : G → L with ker ϕ = H, then



∼

Im ϕ. We revisit some examples

from the previous section in this context.

Examples (6.20, mk.II). Let G = Z

× Z

. For each subgroup H, we describe a homomorphism

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

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

choices are independent of our earlier discussion.

1. Given H =

⟨

(0, 1)

⟩

, we need a homomorphism where ϕ(0, 1) is the identity. A simple way to

do this is to ignore y and deﬁne

ϕ : Z

×Z

→ Z

: (x, y) 7→ x

This indeed has kernel ker ϕ = {(0, y) : y ∈ Z

} = H, whence



∼

Im ϕ = Z

via the isomorphism µ : (x, y) + H 7→ x.

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

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

2. Given H =

⟨

(0, 2)

⟩

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

modulo 2 and deﬁning

ϕ : Z

×Z

→ Z

×Z

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

This is a homomorphism with the correct kernel ker ϕ = H. Indeed ϕ is also surjective, whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y). Once again µ is the inverse of ψ(x, y) = (x, y) + H

in the original example.

3. If H =

⟨

(2, 4)

⟩

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

One approach is to observe that

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

We therefore choose the homomorphism

ϕ : Z

×Z

→ Z

×Z

: (x, y) 7→



x, y −2x



It is worth checking that this is well-deﬁned: the 2x in the second factor is crucial! Certainly ϕ

has the correct kernel. It is moreover surjective, e.g. (p, q) = ϕ(p, q + 2p), whence



∼

Im ϕ = Z

×Z

via the isomorphism µ



(x, y) + H



= (x, y −2x).

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

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

Exercises 7.2. Key concepts:

Canonical homomorphism γ : G →



isomorphism theorem µ :



∼

Im ϕ

1. Let ϕ : Z

→ Z

be the homomorphism ϕ(x) = 10x.

(a) Find the kernel of and image of ϕ.

(b) List the elements of the factor group



ker ϕ



ker ϕ

→ Im ϕ.

(d) To what basic group Z

is the factor group isomorphic?

2. Repeat the previous question for the homomorphism ϕ : Z → Z

: x 7→ 8x.

3. For each function ϕ : Z ×Z → Z, ﬁnd the kernel and identify the factor group

Z × Z



ker ϕ

(a) ϕ(x, y) = 3x + y (b) ϕ(x, y) = 2x −4y

4. (a) If a subgroup H of G = Z

×Z

has order 5, ﬁnd its elements.

(b) Show that ϕ(x, y) = (x, y) is a homomorphism ϕ : G → Z

×Z

with ker ϕ = H.

isomorphism theorem tell us about the factor group



5. Suppose G is a ﬁnite group with normal subgroup H and that ϕ : G → L is a homomorphism

with ker ϕ = H. Prove that (G : H) ≤

with equality if and only if ϕ is surjective.

6. Consider the map ϕ : Z ×Z

→ Z

×Z

deﬁned by

ϕ(x, y) =



2x + y, y



(a) Verify that ϕ is a well-deﬁned homomorphism.

(b) Compute ker ϕ and identify the factor group

Z × Z



ker ϕ

7. Let H =

⟨

(3, 1)

⟩

≤ G = Z

×Z

. Find an explicit homomorphism ϕ : G → Z

whose kernel is

H, and thus identify the factor group



(Hint: (x, y) ∈ H = {( 0, 0), (3, 1), (6, 2)} ⇐⇒ . . .)

8. Consider H =

⟨

(3, 3)

⟩

≤ G = Z

× Z

. Find a surjective homomorphism ϕ : G → Z

× Z

whose kernel is H and hence prove that



∼

×Z

9. Let ϕ : S

→ S

: z 7→ z

(a) Find the kernel of ϕ and describe the canonical homomorphism γ : S

→



ker ϕ

(b) What does the ﬁrst isomorphism theorem say about the factor group



ker ϕ



, where U

is the group of n

roots of unity.

7.3 Conjugation, Cycle Types, Centers and Automorphisms

In this section we consider an important type of homomorphism and some its consequences.

Deﬁnition 7.13. Let G be a group and x, y ∈ G. We say that y is conjugate to x if

∃g ∈ G such that y = gxg

−1

If g ∈ G is ﬁxed, then conjugation by g is the map c

: G → G : x 7→ gxg

−1

We’ve met this notion before: recall that a subgroup H is normal if and only if c

(h) ∈ H for all g ∈ G

(Corollary 6.7). It should also be familiar from linear algebra, in the form of similarity. Recall that

square matrices A, B are similar if B = MAM

−1

for some invertible M. Such matrices have the same

eigenvalues and, essentially, ‘do the same thing’ with respect to different bases. An explicit group

theory analogue of this is Theorem 7.17 below.

Lemma 7.14. Conjugation by g is a isomorphism c

: G

∼

Proof. Conjugation by g

−1

is the inverse function of c

−1



(x)



= g

−1

gxg

−1

)

−1

= x, etc.

We moreover have a homomorphism:

(xy) = g(xy)g

−1



gxg

−1



gyg

−1



= c

(x)c

( y)

Lemma 7.15. Conjugacy is an equivalence relation (x ∼ y ⇐⇒ ∃g ∈ G such that y = gxg

−1

The proof is an exercise. The equivalence classes under conjugacy are termed conjugacy classes.

Examples 7.16. 1. If G is abelian then every conjugacy class contains only one element:

x ∼ y ⇐⇒ ∃g ∈ G such that y = gxg

−1

= xgg

−1

= x

2. The smallest non-abelian group is S

has conjugacy classes

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

This can be computed directly, but it follows immediately from. . .

Theorem 7.17. The conjugacy classes of S

are the cycle types: elements are conjugate if and only if

they have the same cycle type.

If an element σ ∈ S

is written as a product of disjoint cycles, then its cycle type is clear. For instance:

• (1 2 3)(4 5) has the same cycle type as (1 5 6)(2 3): we might call these 3,2-cycles.

• (1 2)(3 4) has a different cycle type; 2,2.

Before seeing the proof it is beneﬁcial to try an example.

Example 7.18. If ρ = (2 4 3) and σ = (1 2)(3 4) in S

, then

ρσρ

−1

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

Not only does this have the same cycle type as σ, but if may be obtained simply by applying ρ to the

entries of σ!

ρσρ

−1

= (1 4)(2 3) =



ρ(1) ρ(2)



ρ(3) ρ(4)



This also tells us how to reverse the process: given 2,2-cycles σ = (1 2)(3 4)

and τ = (1 4)(2 3) simply place σ on top of τ in a table to deﬁne a suitable

ρ = (2 4 3) for which ρσρ

−1

= τ.

x 1 2 3 4

ρ(x) 1 4 2 3

The proof is nothing more than the example done abstractly!

Proof. (⇒) We consider conjugation by ρ ∈ S

. First let σ = (a

···a

) be a k-cycle and write

A = {a

, . . . , a

}, R = {ρ(a

), . . . , ρ(a

) }

Since ρ is a bijection,

= k are distinct and x ∈ R ⇐⇒ ρ

−1

(x) ∈ A. There are two cases:

If x ∈ R: Let x = ρ(a

), then

ρσρ

−1



ρ(a

)



= ρσ(a

) = ρ(a

j+1

)

where a

k+1

is understood to be a

If x ∈ R: Since ρ

−1

(x) ∈ A it is unmoved by σ, whence

ρσρ

−1

(x) = ρσ(ρ

−1

(x)) = ρρ

−1

(x) = x

We conclude that ρσρ

−1



ρ(a

) ···ρ(a

)



is also a k-cycle!

More generally, if σ = σ

···σ

is a product of disjoint cycles, then

ρσρ

−1

= (ρσ

−1

)(ρσ

−1

) ···(ρσ

−1

)

has the same cycle type as σ.

(⇐) Suppose σ = σ

···σ

and τ = τ

···τ

∈ S

have the same cycle type, written so that the

corresponding orbits have the same length. Moreover, assume we’ve included all necessary

1-cycles so that

= {1, . . . , n} =

. Deﬁne a permutation ρ by writing the orbits of σ and

τ on top each other

··· σ

ρ(x) τ

··· τ

If s

i,j

and t

i,j

are the j

elements of the orbits σ

and τ

, then

ρσρ

−1

( t

i,j

) = ρσ(s

i,j

) = ρ



i,j+1



= t

i,j+1

= τ



i,j



We conclude that ρσρ

−1

= τ, as required.

Examples 7.19. 1. The permutations σ = (1 4 5)(2 7 6) and τ = (1 6 5)(3 4 7) in S

are conjugate: the

table deﬁnes a suitable ρ.

x 1 4 5 2 7 6 3

ρ(x) 1 6 5 3 4 7 2

=⇒ ρ = (2 3)(4 6 7)

Indeed

ρσρ

−1

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

There are other possible choices of ρ; just write the orbits of σ, τ in different orders.

2. (Example 6.3.2) We’ve checked previously that V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} is a

normal subgroup of A

. It is moreover a normal subgroup of S

: since V contains the identity

and all 2,2-cycles it is closed under conjugacy and thus a normal subgroup of both A

and S

Automorphisms

We’ve already seen that conjugation c

: G → G by a ﬁxed element is an isomorphism. We now

consider all such maps.

Deﬁnition 7.20. An automorphisms of a group G is an isomorphism of G with itself. The set of such

is denoted Aut G. The inner automorphisms are the conjugations

Inn G = {c

: G → G where c

(x) = gxg

−1

}

Example 7.21. There are four homomorphisms ϕ

: Z

→ Z

(Corollary 7.8);

(x) = 0, ϕ

(x) = x, ϕ

(x) = 2x, ϕ

(x) = 3x

of which two are automorphisms: Aut Z

= {ϕ

, ϕ

}. Observe that ϕ

is the identity function and

that ϕ

◦ ϕ

= ϕ

. The automorphisms therefore comprise a group (necessarily isomorphic to Z

)

under composition of functions.

As for conjugations, observe that for any g ∈ Z

(x) = g + x + (−g) = x

since Z

is abelian. There is only one inner automorphism of Z

, the identity function ϕ

Hunting for automorphisms can be difﬁcult. Here is a helpful observation for narrowing things

down; the proof is an exercise.

Lemma 7.22. If ϕ ∈ Aut G and x ∈ G, then the orders of x and ϕ(x) are identical.

This helps to streamline the previous example: ϕ(1) must have the same order (four) as 1 and so our

only possibilities are ϕ(1) = 1 or ϕ(1) = 3. These possibilities generate the two observed automor-

phisms.

Example 7.23. We describe all automorphisms ϕ of S

. Consider σ = (1 2) and τ = (1 2 3) . Since the

order of an element is preserved by ϕ, we conclude that

ϕ( e) = e, ϕ(σ) ∈



(1 2), (1 3), (2 3)



, ϕ(τ) ∈



(1 2 3), (1 3 2)



We therefore have a maximum of six possible automorphism; it is tedious to check, but all really do

deﬁne automorphisms! Indeed all may be explicitly realized as conjugations whence Aut S

= Inn S

Here is the data; verify some of it for yourself:

element g c

( e) c

(1 2) c

(1 3) c

(2 3) c

(1 2 3) c

(1 3 2)

e e (1 2) (1 3) (2 3) (1 2 3) (1 3 2)

(1 2) e (1 2) (2 3) (1 3) (1 3 2) (1 2 3)

(1 3) e (2 3) (1 3) (1 2) (1 3 2) (1 2 3)

(2 3) e (1 3) (1 2) (2 3) (1 3 2) (1 2 3)

(1 2 3) e (2 3) ( 1 2) (1 3) (1 2 3) (1 3 2)

(1 3 2) e (1 3) ( 2 3) (1 2) (1 2 3) (1 3 2)

As the next result shows, the automorphisms again form a group under composition, in this case a

group of order 6 which is easily seen to be non-abelian: for instance

(1 2)

(1 3)

= c

(1 3 2)

= c

(1 2 3)

= c

(1 3)

(1 2)

By process of elimination, we conclude that Aut S

∼

Theorem 7.24. Aut G and Inn G are groups under composition. Moreover Inn G ◁ Aut G.

Proof. That Aut G is a group is simply the fact that composition and inverses of isomorphisms are

isomorphisms: you should already have made this argument when answering Exercise 2.3.13. By

Lemma 7.14, every conjugation is an isomorphism, and it is simple to check that c

◦ c

= c

and

−1

= c

−1

: we conclude that Inn G ⊆ Aut G.

For normality, we check that Inn G is closed under conjugation! Let τ ∈ Aut G and c

∈ Inn G. For

any x ∈ G, we have

( τc

−1

)(x) = τ





−1

(x)





(deﬁnition of c

)

= τ





−1

(x)



−1





τ(g)





−1

(x)





τ(g

−1

)



(since τ is a homomorphism)



τ(g)





τ(g)



−1

(again since τ is an homomorphism)

= c

τ(g)

(x)

We conclude that τc

−1

= c

τ(g)

∈ Inn G, from which Inn G ◁ Aut G.

The challenge in reading the proof is simply to keep track of where everything lives. To help, the inverse symbol is

colored: τ

−1

means the inverse function, whereas g

−1

means the inverse of an element in G.

Centers

We say that an element g in a group G commutes with another element x ∈ G if the order of multipli-

cation is irrelevant: i.e. if gx = xg. Otherwise said, if c

(x) = x. It natural to ask whether there are

any elements which commute with all others. There are two very simple cases:

• If G is abelian, then every element commutes with every other element!

• The identity e commutes with everything, regardless of G.

In general, the set of such elements will fall somewhere between these extremes. This subset will

turn out to be another normal subgroup of G.

Deﬁnition 7.25. The center of a group G is the subset of G which commutes with everything in G:

Z(G) := {g ∈ G : ∀h ∈ G, gh = hg}

We will prove that Z( G) ◁ G shortly. First we give a few examples; unless G is abelian, the center is

typically difﬁcult to compute, so we omit more of the details.

Examples 7.26. 1. Z(G) = G ⇐⇒ G is abelian.

2. Z(S

) = {e} if n ≥ 3. This is straightforward to check when n = 3 since there are only six

elements. In general, think about the proof of Theorem 7.17. . .

3. Z(D

2n+1

) = {e} and Z(D

) = {e, ρ

n/2

}, where ρ

n/2

is rotation by 180

◦

. For instance, it is easy

to see in D

2n+1

that any rotation and reﬂection fail to commute.

4. Z



(R )



= {λI

: λ ∈ R

}. If you’ve done enough linear algebra, an argument is reason-

ably straightforward (Exercise 12)

Theorem 7.27. For any group G:

1. Z(G) ◁ G



Z(G)

∼

Inn G

Proof. 1. The function ϕ : G → Inn G deﬁned by ϕ(g) = c

is a homomorphism:

(x) = (gh)x(gh)

−1

= g(hxh

−1

= c

( c

(x))

=⇒ ϕ(gh) = ϕ(g)ϕ(h)

Now observe that

g ∈ ker ϕ ⇐⇒ ∀x ∈ G, c

(x) = gxg

−1

= x ⇐⇒ g ∈ Z(G)

from which ker ϕ = Z(G) is a normal subgroup of G.

2. Since ϕ is surjective, the 1

isomorphism theorem tells us that



Z(G)

∼

Im ϕ = Inn G

Exercises 7.3. Key concepts:

Conjugation conjugacy classes cycle types are conjugacy classes in S

(inner) automorphism center of a group

1. Either ﬁnd some ρ ∈ G such that ρσρ

−1

= τ, or explain why no such element exists:

(a) σ = (1 2 3), τ = (1 3 2) where G = S

(b) σ = (1 4 5 6)(2 3)(5 6), τ = (1 2 3 4)(5 6)( 2 6) where G = S

2. Recall Example 7.19.1. Find another element ν = ρ for which νσν

−1

= τ.

3. Prove Lemma 7.15. Prove that the relation

x ∼ y ⇐⇒ y is conjugate to x

is an equivalence relation on any group G.

4. (a) Suppose y is conjugate to x in a group G. Prove that the orders of x and y are identical.

(b) Show that the converse to part (a) is false by exhibiting two non-conjugate elements of the

same order in some group.

5. Let H ≤ G, ﬁx a ∈ G and deﬁne the conjugate subgroup K = c

(H) = {aha

−1

: h ∈ H}.

(a) Prove that K is indeed a subgroup of G.

(b) Prove that the function ψ : H → K : h 7→ aha

−1

is an isomorphism of groups.

(H)?

(d) Let H = {e, (1 2)} ≤ S

and a = (1 2 3). Compute the conjugate subgroup K = c

(H).

6. We’ve already seen that V = {e, (1 2)(3 4), (1 3) (2 4), (1 4)(2 3)} is a normal subgroup of S

(a) Show that normal subgroup is not transitive by giving an example of a normal subgroup

K ◁ V which is not normal in S

(b) How many other subgroups does S

have which are isomorphic to V? Why are none of

them normal in S



is a group of order six. Prove that

(1 2)V(1 3)V = (1 3)V(1 2)V

Hence conclude that



∼

(d) Why is it obvious that the following six left cosets are distinct.

V, (1 2)V, (1 3)V, (2 3)V, (1 2 3)V, (1 3 2)V

(Hint: Think about how none of the representatives a of the above cosets move the number 4 and

consider aV = bV ⇐⇒ b

−1

a ∈ V . . .)

(e) Deﬁne an isomorphism µ :



→ S

and prove that it is an isomorphism.

7. Prove Lemma 7.22: if ϕ ∈ Aut G and x ∈ G, then ϕ(x) has the same order as x.

8. Describe all automorphisms of the Klein four-group V.

(Hint: use the previous question!)

9. Recall Exercise 7.1.6. Explain why Aut Z

∼

(Hint: consider ϕ

(x) = kx where gcd(k, n) = 1 and map ψ : k 7→ ϕ

)

10. Let G be a group. Prove directly that Z(G) ◁ G, without using Theorem 7.27. That is:

(a) Prove that Z(G) is closed under the group operation and inverses.

(b) Prove that gZ(G) = Z(G)g for all g ∈ G.

11. Suppose n ≥ 3 and that σ ∈ Z(S

(a) By considering σ(1 2)σ

−1

, prove that {σ(1), σ(2)} = {1, 2}.

(b) If σ(1) = 2, repeat the calculation with σ(1 3)σ

−1

to obtain a contradiction.

) = {e}.

12. We identify the center of the general linear group.

The n ×n matrix A =







0 1 0 ··· · · · 0

0 0 1 0

0 0 0 0

0 0 0 0 1

0 0 0 ··· 0







has a single one-dimensional eigenspace: Ae

= 0.

(a) Let B ∈ Z



(R )



. Use the fact that AB = BA to prove that Be

= λe

for some λ = 0.

(b) Let x ∈ R

be non-zero and X an invertible matrix for which Xe

= x (e.g. put x in the 1

column of X). Prove that Bx = λx.

, what can we conclude about B?

What is the group Z



(R )



13. (a) Prove that D

has center Z(D

) = {e, ρ

}, where ρ

is rotation by 180

◦

(b) State the cosets of Z(D

). What is the order of each? Determine whether



Z(D

)

isomorphic to Z

or to the Klein four-group V.

→ D

whose kernel is Z(D

(Hint: draw a picture and think about doubling angles of rotation and reﬂection!)

8 Group Actions

8.1 Group Actions, Fixed Sets and Isotropy Subgroups

In this ﬁnal chapter, we revisit a central idea: groups are interesting and useful often because of how

they transform sets. Recall how the symmetric group S

was deﬁned in terms of what its elements do

to the set {1, . . . , n}. This is an example of a general situation.

Deﬁnition 8.1. A group G acts

on a set X via a map · : G × X → X if,

(a) ∀x ∈ X, e ·x = x, and,

(b) ∀x ∈ X, g, h ∈ G, g ·(h ·x) = (gh) · x.

Part (b) says g 7→ g· is a homomorphism of binary structures (the functions X → X needn’t form a

group).

Examples 8.2. 1. The symmetric S

group acts on X = {1, 2, . . . , n}. As a sanity check:

(a) e(x) = x for all x ∈ {1, . . . , n}.

(b) σ



τ(x)



= (στ)(x) is composition of functions!

2. Any group G acts on itself by left multiplication. This is essentially Cayley’s Theorem (5.8). It

also acts on itself by conjugation (c

◦c

= c

is Theorem 7.24).

3. If X is the set of orientations of a regular n-gon such that one vertex is at (1, 0) and the center is

at ( 0, 0), then D

acts on X by rotations and reﬂections. Note that X has cardinality 2n.

4. Matrix groups act on vector spaces by matrix multiplication. For example the orthogonal group

(R ) can be seen to transform vectors via rotations and reﬂections.

(R ) ×R

→ R

: (A, v) 7→ Av

5. A group can act on many different sets. Here are three further actions of the orthogonal group:

i. O

(R ) acts on the set X = {1, −1} via A ·x := (det A)x.

ii. O

(R ) acts on the set X = R

via A · v := A(v

i + v

j) + v

iii. O

(R ) acts on the unit circle X = S

⊆ R

via matrix multiplication A · v := Av.

We often use an action to visualize a group; in this context, some actions are better than others.

Consider the three actions of O

(R ) in part 5 above:

i. The set X is very small. Many matrices act in exactly the same way so the action is an unhelpful

means of visualizing the group.

ii. The set X feels too large. The action leaves any vertical vector untouched.

iii. The circle X = S

is large enough so that the action of distinct matrices can be distinguished

without being inefﬁciently large.

This is really a left action. There is an analogous deﬁnition of a right action. In this course, all actions will be left.

A Goldilocks action, perhaps?

These notions can be formalized.

Deﬁnition 8.3. Let G × X → X be an action.

1. The ﬁxed set of g ∈ G is the set

Fix(g) := {x ∈ X : g · x = x} (also written X

, though we won’t do this)

2. The isotropy subgroup or stabilizer of x ∈ X is the set

Stab(x) := {g ∈ G : g · x = x} (also written G

)

3. The action is faithful if the only element of G which ﬁxes everything is the identity. This can be

stated in two equivalent ways:

(a) Fix(g) = X ⇐⇒ g = e (b)

x∈X

Stab(x) = {e}

4. The action is transitive if any element of X may be transformed to any other:

∀x, y ∈ X, ∃g ∈ G such that y = g · x

Examples (8.2 cont). 1. The action of S

on {1, 2, . . . , n} is both faithful and transitive:

Faithful: if σ(x) = x for all x ∈ {1, 2, . . . , n}, then σ = e.

Transitive: if x = y, then the 2-cycle (x y) maps x 7→ y.

2. The action of a group on itself by left multiplication is both faithful and transitive. Conjugation

is more complex: in most situations it is neither.

3. D

acts faithfully and transitively on the orientations of the n-gon.

4. The action of O

(R ) on R

is faithful but not transitive: for instance the zero vector cannot be

transformed into any other vector so Stab(0) = O

(R ).

5. We leave these as exercises.

Lemma 8.4. For each x ∈ X, the stabilizer Stab(x) is indeed a subgroup of G.

Proof. Stab(x) is a non-empty subset of G since e ∈ Stab(x). It sufﬁcient to show that it is closed

under multiplication and inverses. Let g, h ∈ Stab(x), then

(gh) · x = g ·(h ·x) = g ·x = x =⇒ gh ∈ Stab(x)

Moreover

x = g ·x =⇒ g

−1

· x = g

−1

·(g · x) = (g

−1

g) · x = e ·x = x

Example 8.5. The dihedral group D

= {e, ρ

, ρ

, µ

} acts on the set X of vertices of an equi-

lateral triangle.

The ﬁxed sets and stabilizers for this action are as follows:

Element g Fix(g)

e {1, 2, 3}

∅

{1}

{2}

{3}

Vertex x Stab(x)

1 {e, µ

}

2 {e, µ

}

3 {e, µ

}

also acts on the set of edges of the triangle Y =



{1, 2}, {1, 3}, {2, 3}



. You needn’t write all these

out since, by the symmetry of the triangle, stabilizing an edge is equivalent to stabilizing its opposite

vertex. Still, here is the data:

Element g Fix(g)



1, 2, 3



∅



{2, 3}





{1, 3}





{1, 2}



Edge {x, y} Stab({x, y})

{1, 2} {e, µ

}

{1, 3} {e, µ

}

{2, 3} {e, µ

}

Exercises 8.1. Key concepts:

(left) action Fix(g) Stab(x) ≤ G faithful/transitive actions

1. For part 5 of Example 8.2, determine whether each action is faithful and/or transitive.

2. Let G =

⟨

⟩

≤ S

where σ = (1 2 3 4 5 6). G acts on the set X = {1, 2, 3, 4, 5, 6} in a natural way.

(a) State the ﬁxed sets and stabilizers for this action.

(b) Is the action of G faithful? Transitive?

3. Repeat the previous question when σ = (1 3)(2 4 6).

4. Mimic Example 8.5 for the actions of D

on X = {vertices} and Y = {edges} of the square.

(Use whatever notation you like; ρ, µ , δ or cycle notation)

5. Suppose G acts on X.

(a) Let Y ⊆ X and deﬁne Stab Y = {g ∈ G : ∀y ∈ Y, g ·y = y}. Prove that Stab Y is a subgroup

of G.

(b) Let G act on itself by conjugation (X = G!). What is another name for the subgroup Stab G?

6. Suppose G has a left action on X. Prove that G acts faithfully on X if and only if no two distinct

elements of G have the same action on every element.

Recall that ρ

rotates 120° counter-clockwise, that ρ

= ρ

and that µ

reﬂects across the altitude through vertex i.

8.2 Orbits & Burnside’s Formula

We ﬁrst encountered orbits in the context of the symmetric groups S

. The same idea applies to any

action.

Deﬁnition 8.6. Let G × X → X be an action. The orbit of x ∈ X under G is the set of elements into

which x may be transformed:

Gx = {g · x : g ∈ G} ⊆ X

Examples 8.7. 1. If X = {1, 2, . . . n} and G =

⟨

⟩

≤ S

, then

Gx = {σ

(x) : k ∈ Z} = orb

( σ)

The deﬁnition of orbits therefore coincides with that seen earlier in the course.

2. A transitive action

has only one orbit.

3. If O

(R ) acts on R

by matrix multiplication, then the orbits are circles centered at the origin!

Lemma 8.8. The orbits of an action partition X.

Since this is almost identical to the corresponding result for orbits in S

(Theorem 5.11), we leave the

proof as an exercise.

Our next result is analogous to Lemma 7.5, where we counted the number of (left) cosets of ker ϕ.

Lemma 8.9. The cardinality of the orbit Gx is the index of the isotropy subgroup Stab(x):



G : Stab(x)



Proof. Observe that

g · x = h ·x ⇐⇒ h

−1

g · x = x ⇐⇒ h

−1

g ∈ Stab(x) ⇐⇒ g Stab(x) = h Stab(x)

The contrapositive says that distinct elements of the orbit Gx correspond to distinct left cosets.

Example 8.10. Let σ = (1 4)(2 7 3) ∈ S

. Consider X = {1, 2, 3, 4, 5, 6, 7} under the action of the

cyclic group G =

⟨

⟩

. The orbits are precisely the disjoint cycles: {1, 4}, {2, 3, 7}, {5}, {6}. Observe

that G has six elements:

e, σ = (1 4)(2 7 3), σ

= (2 3 7), σ

= (1 4), σ

= (2 7 3), σ

= (1 4)(2 3 7)

The Lemma is easily veriﬁable: for instance if x = 3,

Stab(x) = {τ ∈ G : τ(3) = 3} = {σ

: σ

(3) = 3} = {e, σ

}

=⇒ (G : Stab(x)) =

= 3 =

{2, 3, 7}

Unhelpfully, we now have two meanings of transitive; one for equivalence relations and one for actions.

It is often useful to count the number of orbits of an action. For ﬁnite actions, this turns out to be

possible in two different ways.

Theorem 8.11 (Burnside’s formula). Let G be a ﬁnite group acting on a ﬁnite set X. Then the number

of orbits in X under G satisﬁes

# orbits =

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

Proof. By Lemma 8.9, It follows that

∑

x∈X

Stab(x)

∑

x∈X

Stab(x)

∑

x∈X

(G : Stab(x))

∑

x∈X

. (∗)

Consider a ﬁxed orbit Gy. Since

for each x ∈ Gy, we see that

∑

x∈Gy

= 1

The sum (∗) therefore counts 1 for each distinct orbit in X and therefore returns the number of orbits.

For the second equality, observe that

S = {(g, x) ∈ G ×X : g · x = x}

has cardinality

∑

x∈X

Stab(x)

∑

g∈G

Fix(g)

Example (8.10 cont). When G =

⟨

⟩

⟨

(1 4)(2 7 3)

⟩

acts on X = {1, 2, 3, 4, 5, 6, 7}, the stabilizers

and ﬁxed sets are as follows:

x ∈ X Stab(x)

1 {e, σ

, σ

}

2 {e, σ

}

3 {e, σ

}

4 {e, σ

, σ

}

5 G = {e, σ, σ

, σ

}

6 G

7 {e, σ

}

g ∈ G Fix(g)

e X = {1, 2, 3, 4, 5, 6, 7}

σ {5, 6}

{1, 4, 5, 6}

{2, 3, 5, 6, 7}

{1, 4, 5, 6}

{5, 6}

Burnside’s formula just sums the number of elements in all of the subsets in the right column of each

table:

4 = # orbits =

∑

x∈X

Stab(x)

(3 + 2 + 2 + 3 + 6 + 6 + 2)

∑

g∈G

Fix(g)

(7 + 2 + 4 + 5 + 4 + 2)

One reason to count the number of orbits of an action is that we often want to consider objects as

equivalent if they differ by the action of some simple group.

Example 8.12. A child’s toy consists of a wooden equilateral triangle where the edges are to be

painted using any choice of colors from the rainbow. How many distinct toys could we create?

There are two problems: we need to describe the variety of possible toys, and we need to know what

distinct means!

We use group actions to address both problems:

• A toy may be considered as a subset of X = {painted triangles} = {ordered color triples}.

Since there are 7 choices for the color of each edge, we see that

= 7

= 343 is a large set!

• Two toys are equivalent if they differ by a rotation in

3-dimensions. This amount to the natural action of

on X: for instance

·(red,green,violet) = (violet,red,green)

The number of orbits is the number of distinct toys, which we may compute using Burnside. Since

it would be time consuming to compute the stabilizer of each element of X, we use the ﬁxed set

approach.

• Identity e: Plainly Fix(e) = X, since e leaves every coloring unchanged.

• Rotations ρ

, ρ

: If a color-scheme is ﬁxed by ρ

, then all pairs of adjacent edges must be the

same color. The only color-schemes ﬁxed by ρ

are those where all sides have the same color,

whence

Fix(ρ

)

= 7.

• Reﬂections µ

, µ

: Since µ

swaps two edges, anything in its ﬁxed set must have these edges

the same. We have 7 choices for the color of the switched edges, and an independent choice of

7 colors for the other edge, whence



Fix(µ

)



= 7

= 49.

The number of distinct toys is therefore

# orbits =

∑

σ∈D

Fix(σ)

+ 7 + 7 + 7

+ 7

)

(49 + 1 + 1 + 7 + 7 + 7) = 84

The question was a little tricky because we are allowed multiple sides to have the same color. A

simpler version would restrict to the situation where all sides had to be different colors. In this case

acts on a set of color schemes with cardinality

= 7 · 6 ·5 = 210. Moreover, only the identity

element has a non-empty ﬁxed set; in this situation the number of distinct toys would be

# orbits =

∑

σ∈D

Fix(g)

(210 + 0 + ··· + 0) =

210

= 35

Of course you could answer these questions by pure combinatorics without any resort to group

theory!

Dice-rolling for Geeks!

Games like Dungeons & Dragons make use of several differently

shaped dice: rather than simply using the standard 6-sided cubic die,

situations might require rolling, say, a 4-sided tetrahedral die or a 20-

sided icosahedral die.

Since dice are designed for rolling, we consider two dice to be the

same if one can be rotated into the other. Play with the two tetrahedral

dice on the right; you should be convinced that you cannot rotate one

to make the other so these dice are distinct.

It is not difﬁcult to see that, up to rotations, these are the only tetrahe-

dral dice just by counting!

• Place face 4 on the table.

• When looking from above, the remaining faces are numbered 1,

2, 3 either clockwise or counter-clockwise.

For larger dice, this approach is not practical! However, with a little

thinking about symmetry groups, Burnside’s formula will ride to the

rescue.

Suppose a regular polyhedron has f faces, each with n sides.

• The faces may be labelled 1 thorough f in f ! distinct ways: the set of distinct labellings is X.

• We may rotate the polyhedron so that any face is mapped to any other, in any orientation. It

follows that the rotation group G has f n elements.

• Each non-identity element of the rotation group moves at least one face, whence

Fix(g)

(

X if g = e

∅ if g = e

• The number of distinct dice for a regular polyhedron is therefore

# orbits =

Fix(e)

f !

f n

( f −1) !

We don’t need to know what the rotation group is, only its order. For completeness, here are all

the possibilities for the regular platonic solids.

Polyhedron f n Rotation Group # distinct dice

Tetrahedron 4 3 A

Cube 6 4 S

Octahedron 8 3 S

1,680

Dodecahedron 12 5 A

7,983,360

Icosahedron 20 3 A

40,548,366,802,944,000

Subgroups of Prime Order & the Class Equation

We ﬁnish with a taste of where group theory traditionally goes next.

Suppose G acts on a ﬁnite set X, that x

. . . , x

are representatives of the distinct orbits and that

, . . . , x

enumerate the 1-element orbits (Stab(x

) = G ⇐⇒ j ≤ s). Then, by counting elements,

= s +

∑

j=s+1



= s +

∑

j=s+1



G : Stab(x

)



When G acts on itself by conjugation, the 1-element orbits together comprise the center of G and we

obtain the class equation:

Z(G)

∑

j=s+1



G : Stab(x

)



Example 8.13. Since the conjugacy classes in S

are the cycle types, the class equation reads

24 =

{e}

2-cycles

3-cycles

4-cycles

2,2-cycles

= 1 + 6 + 8 + 6 + 3

Here is an example of how the class equation may be applied.

Lemma 8.14. Suppose G is a non-abelian group whose order is divisible by a prime p. Then G has a

proper subgroup whose order is divisible by p.

Proof. Since G is non-abelian, Z(G) is a proper subgroup. Let x be any element not in the center. Then

2 ≤

Stab(x)

=⇒ Stab(x) is a proper subgroup of G

If p divides

Stab(x)

, then we’re done. If not, then p divides



G : Stab(x)



. If this holds for

all non-trivial orbits, the class equation says that

Z(G)

is divisible by p.

Theorem 8.15 (Cauchy). If a prime p divides

, then G contains a subgroup/element of order p.

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

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

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

2. If G is non-abelian, apply the Lemma. If the resulting subgroup is abelian, part 1 ﬁnishes things

off. Otherwise repeat. If we never reach an abelian subgroup, then we have an inﬁnite sequence

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

Cauchy’s Theorem may be extended to prove that if p

divides G, then G has a subgroup of order p

This is the beginning of the Sylow theory of p-subgroups which has applications to group classiﬁca-

tion and the existence of sequences of normal subgroups.

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

⟨

⟩

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

∼

is cyclic.

Exercises 8.2. Key concepts:

Orbits of G partition X Cardinality of orbit

= (G : Stab(x) ) divides

Burnside’s formula for counting number of orbits

1. Determine the orbits of G =

⟨

⟩

on X = {1, 2, 3, 4, 5, 6} for each of Exercises 8.1.2 and 3. In both

cases verify Burnside’s formula.

2. Revisit Example 8.12. How may distinct toys may be created if:

(a) A maximum of two colors can be used?

(b) Exactly two colors must be used?

3. Prove Lemma 8.8: the orbits of a left action partition X.

4. A 10-sided die is shaped so that all faces are congruent kites: ﬁve faces are arranged around the

north pole and ﬁve around the south, so that each face is adjacent to four others.

(a) Argue that the group of rotational symmetries of such a die has ten elements.

(In fact it is non-abelian and is therefore isomorphic to D

(b) Use Burnside’s formula to determine how many distinct 10-sided dice may be produced.

5. A soccer ball is constructed from 20 regular hexagons and 12 regular

pentagons as in the picture.

Suppose the 20 hexagonal patches are all to have different colors, as are

the 12 pentagonal patches. How many distinct balls may be produced?

6. The faces of a cuboid measuring 1 × 1 ×2 in is to be painted using (at

most) two colors. Up to equivalence by rotations, how many ways can

this be done?

7. Repeat the previous question for a regular tetrahedron.

8. Suppose G is a ﬁnite group with order p

where p is a prime. If x ∈ G lies in a conjugacy

class with at least 2 elements, prove that the order of Stab(x) divides p

n−1

. Now use the class

equation to prove that p divides the order of the center Z(G).

9. We prove the abelian part of Cauchy’s Theorem by induction on the order of G.

(a) Explain why the base case

= 2 is true.

(b) Suppose p divides

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

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

|⟨

⟩|

(necessarily m ≥ 2).

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

m/q

and let H :=

⟨

⟩

Why are we done if q = p?



of order p.

(d) Prove that z

has order p in G.