» ∈ On . Then „ Ž » ∈ An and f („ Ž ») = „ Ž („ Ž ») = » because „ Ž „ = µ. Thus

f is surjective, as required.

Proposition 3.37. Every even permutation can be written as a product of 3-cycles

(not necessarily disjoint).

Proof. By Theorem 3.33, an even permutation can be written as a product of

an even number of transpositions. We show that any product of two transpositions

is a product of 3-cycles. If these two transpositions are identical, their product

is the identity. If the two transpositions have one element in common, say (ab)

and (bc), their product (ab) Ž (bc) = (abc), a 3-cycle. If the two transpositions

have no elements in common, say (ab) and (cd ), we can write their product as

(ab) Ž (cd) = (ab) Ž (bc) Ž (bc) Ž (cd) = (abc) Ž (bcd),

a product of two 3-cycles.

EXERCISES 71

Theorem 3.33 and Proposition 3.37 show, respectively, that Sn is generated

by the 2-cycles and An is generated by the 3-cycles.

CAYLEY™S REPRESENTATION THEOREM

At the beginning of the nineteenth century, groups appeared only in a very

concrete form, such as symmetry groups or permutation groups. Arthur Cayley

(1821“1895) was the ¬rst mathematician to deal with groups abstractly in terms

of axioms, but he showed that any abstract group can be considered as a subgroup

of a symmetric group. Hence, in some sense, if you know all about symmetry

groups and permutation groups, you know all about group theory. This result is

analogous to Stone™s representation theorem for boolean algebras, which proves

that any abstract boolean algebra can be considered as an algebra of subsets of

a set.

Theorem 3.38. Cayley™s Theorem. Every group (G, ·) is isomorphic to a sub-

group of its symmetric group (S(G), Ž ).

Proof. For each element g ∈ G, de¬ne πg : G ’ G by πg (x) = g · x. We show

that πg is a bijection. It is surjective because, for any y ∈ G, πg (g ’1 · y) = g ·

(g ’1 · y) = y. It is injective because πg (x) = πg (y) implies that g · x = g · y,

and so, by Proposition 3.7, x = y. Hence πg ∈ S(G).

Let H = {πg ∈ S(G)|g ∈ G}. We show that (H, Ž ) is a subgroup of (S(G), Ž )

isomorphic to (G, ·). In fact, we show that the function ψ: G ’ H by ψ(g) = πg

is a group isomorphism. This is clearly surjective. It is also injective because

ψ(g) = ψ(h) implies that πg = πh , and πg (e) = πh (e) implies that g = h.

It remains to show that ψ preserves the group operation. If g, h ∈

G, πg·h (x) = (g · h)(x) = g · (h · x) = πg (h · x) = (πg Ž πh )(x) and πg·h = πg Ž

πh . Also, πh’1 Ž πh = πh’1 ·h = πe ; thus (πh )’1 = πh’1 ∈ H . Hence H is a

subgroup of S(G), and ψ(g · h) = ψ(g) Ž ψ(h).

Corollary 3.39. If G is a ¬nite group of order n, then G is isomorphic to a

subgroup of Sn .

Proof. This follows because S(G) is isomorphic to Sn .

This is not of very much practical value, however, because Sn has order n!,

which is much larger than the order of G, in general.

EXERCISES

Construct tables for the groups designated in Exercises 3.1 to 3.4.

3.1. C5 . 3.2 D4 .

3.3. (P (X), ), where X = {a, b, c}. 3.4 A4 .

72 3 GROUPS

For Exercises 3.5 to 3.16, state which are groups and which are abelian groups.

Give reasons for your answers.

3.5. (Mn (R), +). 3.6. ({1, 2, 3, 4, 6, 12}, gcd).

√

3.7. ({a + b 2|a, b ∈ Q}, +). 3.8. ({a/b ∈ Q|a, b ∈ Z, b odd}, +).

3.9. ({z ∈ C||z| = 1}, +). 3.10. ({z ∈ C||z| = 1}, ·).

’1 0 ’1

10 1 0 0

,· .

3.11. , , ,

0 ’1 0 ’1

01 01

3.12. (Mn (R) ’ {0}, ·), where 0 is the n — n zero matrix.

3.13. ({1, ζ, ζ 2 , ζ 3 , . . . , ζ n’1 }, ·), where ζ is a complex nth root of 1.

3.14. ({e, a}, ), where e e = e and e a = a e = a a = a.

3.15. (R— , ∼), where R— = R ’ {0} and x ∼ y is xy if x > 0, and x/y if x < 0.

3.16. (Z, ), where m n is m + n if m is even, and m ’ n if m is odd.

’1

3.17. Prove that in any group (G, ·), (a1 · · · an )’1 = an · · · a1 .

’1

3.18. If k is an integer (positive or negative), prove that (a ’1 ba)k = a ’1 bk a in

any group (G, ·).

3.19. If G is a group in which a 2 = e, the identity for all a ∈ G, show that G

is abelian.

3.20. Prove that G is abelian if and only if (ab)2 = a 2 b2 for all a, b ∈ G.

3.21. If a is not the identity in a group and a 4 b = ba 5 , prove that ab = ba.

3.22. Prove that the order of the element g ’1 is the same as the order of g.

3.23. Prove that the order of the element ab is the same as the order of ba.

3.24. Prove that every image of a cyclic group is cyclic.

3.25. The gaussian integers comprise the set of complex numbers Z[i] =

{a + ib|a, b ∈ Z}. Is the group (Z[i], +) a cyclic group?

For Exercises 3.26 to 3.33, describe the symmetry groups of the ¬gures.

3.26. 3.27. 3.28. 3.29.

3.30. 3.31. 3.32. 3.33.

For Exercises 3.34 and 3.35, describe the symmetry groups of the frieze patterns.

These patterns are repeated inde¬nitely in both directions.

3.34. 3.35.

3.36. Prove that the relation of being a subgroup is a partial order on the set of

subgroups of a group G.

3.37. Draw the poset diagram of the subgroups of C6 .

3.38. Draw the poset diagram of the subgroups of S3 .

EXERCISES 73

3.39. If H and K are subgroups of a group G, prove that H © K is also a

subgroup of G. Is H ∪ K necessarily a subgroup of G?

3.40. If f : G ’ H and g: H ’ K are group morphisms, show that g Ž f : G ’

K is also a group morphism.

3.41. Find all the group morphisms from (Z, +) to (Q, +).

3.42. Show that the set {f1 , f2 , f3 , f4 , f5 , f6 } of functions R ’ {0, 1} ’ R ’

{0, 1} under composition is isomorphic to S3 , where

1 1

f1 (x) = x, f2 (x) = 1 ’ x, f3 (x) = , f4 (x) = 1 ’ ,

x x

1 x

f5 (x) = f6 (x) =

, .

1’x x’1

Is (Z, +) isomorphic to (Q— , ·), where Q— = Q ’ {0}? Give reasons.

3.43.

Is (R, +) isomorphic to (R+ , ·), where R+ = {x ∈ R|x > 0}? Give reasons.

3.44.

3.45. Find the orders of all the elements in A4 .

Is A4 ∼ D6 ? Give reasons.

=

3.46.

3.47. Draw the table and ¬nd the order of all the elements in the group

({±1, ±i, ±j, ±k}, ·), where i 2 = j 2 = k 2 = ’1, ij = k = ’j i, j k = i =

’kj , and ki = j = ’ik. This is called the quaternion group Q of order 8.

01 01

3.48. Let G be the group generated by the matrices and

’1 0 10

under matrix multiplication. Show that G is a non-abelian group of order

8. Is it isomorphic to D4 or the quaternion group Q?

01

3.49. Show that Dk is isomorphic to the group generated by

10

0

ζ

under matrix multiplication, where ζ = exp(2πi/k), a

and

0 ζ ’1

complex kth root of unity.

3.50. Construct the table for the group generated by g and h, where g and h

satisfy the relations g 3 = h2 = e and gh = hg 2 .

3.51. Prove that a group of even order always has at least one element of order 2.

3.52. Find a subgroup of S7 of order 10.

3.53. Find a subgroup of S5 of order 3.

3.54. Find a subgroup of A4 isomorphic to the Klein 4-group.

Multiply out the permutations in Exercises 3.55 to 3.58.

12 34 12 34

3.55. .

Ž

24 31 43 21

3

1 23456

3.56. .

4 52631

1 2 3 4 5 Ž 2 3 4.

3.57.

3 6 2 Ž 1 5 Ž 4 2.

3.58.

74 3 GROUPS

For Exercises 3.59 to 3.62, write the permutations as a product of disjoint cycles.

Find the order of each permutation and state whether the permutation is even

or odd.

1 2 3 4 5 6 12 3456 7

3.59. . 3.60. .

6 1 2 3 4 5 24 6157 3

1 2 3 4 5 6

3.61. .

5 6 4 3 2 1

1 2 3 4 5 6789

3.62. .

8 9 4 2 7 3516

Find the permutations for Exercises 3.63 to 3.66.

’1 ’1

12 345 12 345 6

3.63. . 3.64. .

51 234 21 653 4

’1 ’2

123 124 657

3.65. . 3.66. .

For each polynomial in Exercises 3.67 to 3.69, ¬nd the permutations of the

subscripts that leave the value of the polynomial unchanged. These will form

subgroups of S4 , called the symmetry groups of the polynomials.

3.67. (x1 + x2 )(x3 + x4 ). 3.68. (x1 ’ x2 )(x3 ’ x4 ).

3.69. (x1 ’ x2 )2 + (x2 ’ x3 )2 + (x3 ’ x4 )2 + (x4 ’ x1 )2 .

3.70. Describe the group of proper rotations of the tetrahedron with vertices

(0, 0, 0), (1, 0, 0), (0, 1, 0), and (0, 0, 1) in R3 .

3.71. Write G = {1, ’1}, a multiplicative subgroup of R+ , and de¬ne

1 if σ is even

f : Sn ’ G by f (σ ) = . Prove that f is an onto

’1 if σ is odd

group morphism.

3.72. If g and h are elements in a group G, show that g and h’1 gh have the

same order.

3.73. What is the number of generators of the cyclic group Cn ?

3.74. Express (123) Ž (456) as the power of a single cycle in S6 . Can you gener-

alize this result?

3.75. A perfect interlacing shuf¬‚e of a deck of 2n cards is the permutation

1 2 3 ··· n n + 1 n + 2 ··· 2n

. What is the least

2 4 6 · · · 2n · · · 2n ’ 1

1 3

number of perfect shuf¬‚es that have to be performed on a deck of 52

cards before the cards are back in their original position? If there were 50

cards, what would be the least number?

3.76. The center of a group G is the set Z(G) = {x ∈ G|xg = gx for all g ∈

G}. Show that Z(G) is an abelian subgroup of G.

3.77. Find the center of D3 .

3.78. Find the center of D4 .

3.79. Prove that Sn is generated by the elements (12), (23), (34), . . . , (n ’ 1 n).

EXERCISES 75

3.80. Prove that Sn is generated by the elements (123 · · · n) and (12).

3.81. Prove that An is generated by the set {(12r)|r = 3, 4, . . . , n}.

3.82. The well-known 15-puzzle consists of a shallow box ¬lled with 16 small

squares in a 4 — 4 array. The bottom right corner square is removed, and the

other squares are labeled as in Figure 3.10. By sliding the squares around

(without lifting them up), show that the set of possible permutations that

can be obtained with the bottom right square blank is precisely A15 . (There

is no known easy proof that all elements in A15 must occur.)

1 2 34 4 3 21 10 9 87 8 14 11 3

5 6 78 5 6 78 11 2 16 12 2 15 9

9 10 11 12 12 11 10 9 12 3 45 6 4 13 1

13 14 15 13 14 15 13 14 15 7 10 5

Initial position (1) (2) (3)

Figure 3.10. The 15-puzzle.

3.83. Which of the positions of the 15-puzzle shown in Figure 3.10 can

be achieved?

3.84. An automorphism of a group G is an isomorphism from G to itself. Prove

that the set of all automorphisms of G forms a group under composition.

3.85. Find the automorphism group of the Klein 4-group.

3.86. Find the automorphism group of C3 .

3.87. Find the automorphism group of C4 .

3.88. Find the automorphism group of S3 .

3.89. A word on {x, y} is a ¬nite string of the symbols x, x ’1 , y, y ’1 , where x

and x ’1 cannot be adjacent and y and y ’1 cannot be adjacent; for example,

xxy ’1 x and x ’1 x ’1 yxy are words. Let F be the set of such words together

with the empty word, which is denoted by 1. The operation of concatenation

places one word after another. Show that F is a group under concatenation,

where any strings of the form xx ’1 , x ’1 x, yy ’1 , y ’1 y are deleted in a

concatenated word. F is called the free group on two generators. Is F

abelian? What is the inverse of x ’1 x ’1 yxy?

4

QUOTIENT GROUPS

Certain techniques are fundamental to the study of algebra. One such technique

is the construction of the quotient set of an algebraic object by means of an

equivalence relation on the underlying set. For example, if the object is the

group of integers (Z, +), the congruence relation modulo n on Z will de¬ne the

quotient group of integers modulo n.

This quotient construction can be applied to numerous algebraic structures,

including groups, boolean algebras, and vector spaces.

In this chapter we introduce the concept of an equivalence relation and go on

to apply this to groups. We obtain Lagrange™s theorem, which states that the order

of a subgroup divides the order of the group, and we also obtain the morphism

theorem for groups. We study the implications of these two theorems and classify

the groups of low order.

EQUIVALENCE RELATIONS

Relations are one of the basic building blocks of mathematics (as well as of the

rest of the world). A relation R from a set S to a set T is a subset of S — T .

We say that a is related to b under R if the pair (a, b) belongs to the subset,

and we write this as aRb. If (a, b) does not belong to the subset, we say that a

is not related to b, and write aRb. This de¬nition even covers many relations in

everyday life, such as “is the father of,” “is richer than,” and “goes to the same

school as” as well as mathematical relations such as “is equal to,” “is a member

of,” and “is similar to.” A relation R from S to T has the property that for any

elements a in S, and b in T , either aRb or aRb.

Any function f : S ’ T gives rise to a relation R from S to T by taking aRb

to mean f (a) = b. The subset R of S — T is the graph of the function. However,

relations are much more general than functions. One element can be related to

many elements or to no elements at all.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

76

EQUIVALENCE RELATIONS 77

A relation from a set S to itself is called a relation on S. Any partial order

on a set, such as “ ” on the real numbers, or “is a subset of” on a power set

P (X), is a relation on that set. “Equals” is a relation on any set S and is de¬ned

by the subset {(a, a)|a ∈ S} of S — S. An equivalence relation is a relation that

has the most important properties of the “equals” relation.

A relation E on a set S is called an equivalence relation if the following

conditions hold.

(i) aEa for all a ∈ S. (re¬‚exive condition)

(ii) If aEb, then bEa. (symmetric condition)

(iii) If aEb and bEc, then aEc. (transitive condition)

If E is an equivalence relation on S and a ∈ S, then [a] = {x ∈ S|xEa} is

called the equivalence class containing a. The set of all equivalence classes is

called the quotient set of S by E and is denoted by S/E. Hence

S/E = {[a]|a ∈ S}.

Proposition 4.1. If E is an equivalence relation on a set S, then

(i) If aEb, then [a] = [b].

(ii) If aEb, then [a] © [b] = ˜.

(iii) S is the disjoint union of all the distinct equivalence classes.

Proof. (i) If aEb, let x be any element of [a]. Then xEa and so xEb by

transitivity. Hence x ∈ [b] and [a] ⊆ [b]. The symmetry of E implies that bEa,

and an argument similar to the above shows that [b] ⊆ [a]. This proves that

[a] = [b].

(ii) Suppose that aEb. If there was an element x ∈ [a] © [b], then xEa, xEb,

so aEb by symmetry and transitivity. Hence [a] © [b] = ˜.

(iii) Parts (i) and (ii) show that two equivalence classes are either the same or

disjoint. The re¬‚exivity of E implies that each element a ∈ S is in the equivalence

class [a]. Hence S is the disjoint union of all the equivalence classes.

A collection of nonempty subsets is said to partition a set S if the union of

the subsets is S and any two subsets are disjoint. The previous proposition shows

that any equivalence relation partitions the set into its equivalence classes. Each

element of the set belongs to one and only one equivalence class.

It can also be shown that every partition of a set gives rise to an equivalence

relation whose classes are precisely the subsets in the partition.

Example 4.2. Let n be a ¬xed positive integer and a and b any two integers.

We say that a is congruent to b modulo n if n divides a ’ b. We denote

this by

a ≡ b mod n.

78 4 QUOTIENT GROUPS

Show that this congruence relation modulo n is an equivalence relation on Z. The

set of equivalence classes is called the set of integers modulo n and is denoted

by Zn .

Solution. Write “n|m” for “n divides m,” which means that there is some

integer k such that m = nk. Hence a ≡ b mod n if and only if n|(a ’ b).

(i) For all a ∈ Z, n|(a ’ a), so a ≡ a mod n and the relation is re¬‚exive.

(ii) If a ≡ b mod n, then n|(a ’ b), so n| ’ (a ’ b). Hence n|(b ’ a) and

b ≡ a mod n.

(iii) If a ≡ b mod n and b ≡ c mod n, then n|(a ’ b) and n|(b ’ c), so

n|(a ’ b) + (b ’ c). Therefore, n|(a ’ c) and a ≡ c mod n.

Hence congruence modulo n is an equivalence relation on Z.

In the congruence relation modulo 3, we have the following equivalence classes:

[0] = {. . . , ’3, 0, 3, 6, 9, . . .}

[1] = {. . . , ’2, 1, 4, 7, 10, . . .}

[2] = {. . . , ’1, 2, 5, 8, 11, . . .}

[3] = {. . . , 0, 3, 6, 9, 12, . . .} = [0]

Any equivalence class must be one of [0], [1], or [2], so Z3 = {[0], [1], [2]}.

In general, Zn = {[0], [1], [2], . . . , [n ’ 1]}, since any integer is congruent

modulo n to its remainder when divided by n.

One set of equivalence classes that is introduced in elementary school is the

set of rational numbers. Students soon become used to the fact that 1 and 3 2 6

represent the same rational number. We need to use the concept of equivalence

class to de¬ne a rational number precisely. De¬ne the relation E on Z — Z—

(where Z— = Z ’ {0}) by (a, b) E (c, d) if and only if ad = bc. This is an

equivalence relation on Z — Z— , and the equivalence classes are called rational

numbers. We denote the equivalence class [(a, b)] by a . Therefore, since (1, 2)

b

E(3, 6), it follows that 1 = 3 .

2 6

Two series-parallel circuits involving the switches A1 , A2 , . . . , An are said to

be equivalent if they both are open or both are closed for any position of the n

n

switches. This is an equivalence relation, and the equivalence classes are the 22

distinct types of circuits controlled by n switches.

Any permutation π on a set S induces an equivalence relation, ∼, on S where

a ∼ b if and only if b = π r (a), for some r ∈ Z. The equivalence classes are the

orbits of π. In the decomposition of the permutation π into disjoint cycles, the

elements in each cycle constitute one orbit.

COSETS AND LAGRANGE™S THEOREM

The congruence relation modulo n on Z can be de¬ned by a ≡ b mod n if and

only if a ’ b ∈ nZ, where nZ is the subgroup of Z consisting of all multiples

COSETS AND LAGRANGE™S THEOREM 79

of n. We now generalize this notion and de¬ne congruence in any group modulo

one of its subgroups. We are interested in the equivalence classes, which we call

cosets.

Let (G, ·) be a group with subgroup H . For a, b ∈ G, we say that a is

congruent to b modulo H , and write a ≡ b mod H if and only if ab’1 ∈ H .

Proposition 4.3. The relation a ≡ b mod H is an equivalence relation on G. The

equivalence class containing a can be written in the form H a = {ha|h ∈ H }, and

it is called a right coset of H in G. The element a is called a representative of

the coset Ha.

Proof. (i) For all a ∈ G, aa ’1 = e ∈ H ; thus the relation is re¬‚exive.

(ii) If a ≡ b mod H , then ab’1 ∈ H ; thus ba ’1 = (ab’1 )’1 ∈ H . Hence b ≡

a mod H , and the relation is symmetric.

(iii) If a ≡ b and b ≡ c mod H , then ab’1 and bc’1 ∈ H . Hence ac1 =

(ab’1 )(bc’1 ) ∈ H and a ≡ c mod H . The relation is transitive. Hence ≡ is an

equivalence relation. The equivalence class containing a is

{x ∈ G|x ≡ a mod H } = {x ∈ G|xa ’1 = h ∈ H }

= {x ∈ G|x = ha, where h ∈ H }

= {ha|h ∈ H },

which we denote by Ha.

Example 4.4. Find the right cosets of A3 in S3 .

Solution. One coset is the subgroup itself A3 = {(1), (123), (132)}. Take any

element not in the subgroup, say (12). Then another coset is

A3 (12) = {(12), (123) Ž (12), (132) Ž (12)} = {(12), (13), (23)}.

Since the right cosets form a partition of S3 and the two cosets above contain all

the elements of S3 , it follows that these are the only two cosets.

In fact, A3 = A3 (123) = A3 (132) and A3 (12) = A3 (13) = A3 (23).

Example 4.5. Find the right cosets of H = {e, g 4 , g 8 } in C12 = {e, g, g 2 , . . . , g 11 }.

Solution. H itself is one coset. Another is Hg = {g, g 5 , g 9 }. These two cosets

have not exhausted all the elements of C12 , so pick an element, say g 2 , which

is not in H or Hg. A third coset is Hg 2 = {g 2 , g 6 , g 10 } and a fourth is Hg 3 =

{g 3 , g 7 , g 11 }.

Since C12 = H ∪ Hg ∪ Hg 2 ∪ Hg 3 , these are all the cosets.

As the examples above suggest, every coset contains the same number of

elements. We use this result to prove the famous theorem of Joseph Lagrange

(1736“1813).

80 4 QUOTIENT GROUPS

Lemma 4.6. There is a bijection between any two right cosets of H in G.

Proof. Let Ha be a right coset of H in G. We produce a bijection between

Ha and H , from which it follows that there is a bijection between any two

right cosets.

De¬ne ψ: H ’ H a by ψ(h) = ha. Then ψ is clearly surjective. Now suppose

that ψ(h1 ) = ψ(h2 ), so that h1 a = h2 a. Multiplying each side by a ’1 on the

right, we obtain h1 = h2 . Hence ψ is a bijection.

Theorem 4.7. Lagrange™s Theorem. If G is a ¬nite group and H is a subgroup

of G, then |H | divides |G|.

Proof. The right cosets of H in G form a partition of G, so G can be written

as a disjoint union

G = H a1 ∪ H a2 ∪ · · · ∪ H ak for a ¬nite set of elements a1 , a2 , . . . , ak ∈ G.

By Lemma 4.6, the number of elements in each coset is |H |. Hence, counting

all the elements in the disjoint union above, we see that |G| = k|H |. Therefore,

|H | divides |G|.

If H is a subgroup of G, the number of distinct right cosets of H in G is

called the index of H in G and is written |G : H |. The following is a direct

consequence of the proof of Lagrange™s theorem.

Corollary 4.8. If G is a ¬nite group with subgroup H , then

|G : H | = |G|/|H |.

Corollary 4.9. If a is an element of a ¬nite group G, then the order of a divides

the order of G.

Proof. Let H = {a r |r ∈ Z} be the cyclic subgroup generated by a. By Propo-

sition 3.13, the order of the subgroup H is the same as the order of the element

a. Hence, by Lagrange™s theorem, the order of a divides the order of G.

Corollary 4.10. If a is an element of the ¬nite group G, then a |G| = e.

Proof. If m is the order of a, then |G| = mk for some integer k. Hence a |G| =

a mk = (a m )k = ek = e.

Corollary 4.11. If G is a group of prime order, then G is cyclic.

Proof. Let |G| = p, a prime number. By Corollary 4.9, every element has

order 1 or p. But the only element of order 1 is the identity. Therefore, all the

COSETS AND LAGRANGE™S THEOREM 81

other elements have order p, and there is at least one because |G| 2. Hence

by Theorem 3.14, G is a cyclic group.

The converse of Lagrange™s theorem is false, as the following example shows.

That is, if k is a divisor of the order of G, it does not necessarily follow that G

has a subgroup of order k.

Example 4.12. A4 is a group of order 12 having no subgroup of order 6.

Solution. A4 contains one identity element, eight 3-cycles of the form (abc),

and three pairs of transpositions of the form (ab) Ž (cd), where a, b, c, and

d are distinct elements of {1, 2, 3, 4}. If a subgroup contains a 3-cycle (abc),

it must also contain its inverse (acb). If a subgroup of order 6 exists, it must

contain the identity and a product of two transpositions, because the odd number

of nonidentity elements cannot be made up of 3-cycles and their inverses. A

subgroup of order 6 must also contain at least two 3-cycles because A4 only

contains four elements that are not 3-cycles.

Without loss of generality, suppose that a subgroup of order 6 contains the

elements (abc) and (ab) Ž (cd). Then it must also contain the elements (abc)’1 =

(acb), (abc) Ž (ab) Ž (cd) = (acd), (ab) Ž (cd) Ž (abc) = (bdc), and (acd)’1 =

(adc), which, together with the identity, gives more than six elements. Hence A4

contains no subgroup of order 6.

The next proposition strengthens Lagrange™s theorem in the case of ¬nite

cyclic groups. The following lemma, of interest in its own right, will be needed.

Lemma 4.13. Let g be an element of order n in a group, and let m 1.

(i) If gcd(n, m) = d, then g m has order n/d.

(ii) In particular, if m divides n, then g m has order n/m.

Proof. (i). We have (g m )n/d = (g n )m/d = em/d = e. If (g m )k = e, we must

n

show that divides k. We have g mk = e, so n divides mk by Proposition 3.11.

d

n m n m

Hence divides k. But and are relatively prime by Theorem 11,

d d d d

n

Appendix 2, so divides k (by the same theorem).

d

(ii). If m divides n, then gcd(n, m) = m, so (i) implies (ii).

Proposition 4.14. If G is a cyclic group of order n, and if k divides n, then

G has exactly one subgroup H of order k. In fact, if g generates G, then H is

generated by g n/k .

Proof. Let H denote the subgroup generated by g n/k . Then |H | = k because

n

g n/k has order k by Lemma 4.13 with m = . Now let K be any subgroup of

k

82 4 QUOTIENT GROUPS

G of order k. By Proposition 3.12, K is generated by g m for some m ∈ Z. Then

g m has order |K| = k by Proposition 3.13. But if d = gcd(m, n), then g m also

has order n/d by Lemma 4.13. Thus k = n/d, so d = n/k. Write d = xm +

yn, x, y ∈ Z (by Theorem 8, Appendix 2). Then g n/k = g d = (g m )x (g n )y =

(g m )x ∈ K. Since g n/k generates H , it follows that H ⊆ K, so H = K because

|H | = |K|.

NORMAL SUBGROUPS AND QUOTIENT GROUPS

Let G be a group with subgroup H . The right cosets of H in G are equivalence

classes under the relation a ≡ b mod H , de¬ned by ab’1 ∈ H . We can also

de¬ne the relation L on G so that aLb if and only if b’1 a ∈ H . This relation,

L, is an equivalence relation, and the equivalence class containing a is the left

coset aH = {ah|h ∈ H }. As the following example shows, the left coset of an

element does not necessarily equal the right coset.

Example 4.15. Find the left and right cosets of H = A3 and K = {(1), (12)}

in S3 .

Solution. We calculated the right cosets of H = A3 in Example 4.4.

Right Cosets Left Cosets

= {(1), (123), (132)} = {(1), (123), (132)}

H H

H (12) = {(12), (13), (23)} (12)H = {(12), (23), (13)}

In this case, the left and right cosets of H are the same.

However, the left and right cosets of K are not all the same.

Right Cosets Left Cosets

= {(1), (12)} = {(1), (12)}

K K

K(13) = {(13), (132)} (13)K = {(13), (123)}

K(23) = {(23), (123)} (23)K = {(23), (132)}

Since a ≡ b mod H is an equivalence relation for any subgroup H of a group

G and the quotient set is the set of right cosets {H a|a ∈ G}, it is natural to ask

whether this quotient set is also a group with a multiplication induced by the

multiplication in G. We show that this is the case if and only if the right cosets

of H equal the left cosets.

A subgroup H of a group G is called a normal subgroup of G if g ’1 hg ∈ H

for all g ∈ G and h ∈ H .

Proposition 4.16. Hg = gH , for all g ∈ G, if and only if H is a normal sub-

group of G.

NORMAL SUBGROUPS AND QUOTIENT GROUPS 83

Proof. Suppose that Hg = gH . Then, for any element h ∈ H, hg ∈ Hg =

gH . Hence hg = gh1 for some h1 ∈ H and g ’1 hg = g ’1 gh1 = h1 ∈ H . There-

fore, H is a normal subgroup.

Conversely, if H is normal, let hg ∈ Hg and g ’1 hg = h1 ∈ H . Then hg =

gh1 ∈ gH and Hg ⊆ gH . Also, ghg ’1 = (g ’1 )’1 hg ’1 = h2 ∈ H , since H is

normal, so gh = h2 g ∈ Hg. Hence, gH ⊆ Hg, and so Hg = gH .

Therefore, A3 is a normal subgroup of S3 by Example 4.13, whereas {(1), (12)}

is not.

Proposition 4.17. Any subgroup of an abelian group is normal.

Proof. If H is a subgroup of an abelian group, G, then g ’1 hg = hg ’1 g =

h ∈ H for all g ∈ G, h ∈ H . Hence H is normal.

If N is a normal subgroup of a group G, the left cosets of N in G are the

same as the right cosets of N in G, so there will be no ambiguity in just talking

about the cosets of N in G.

Theorem 4.18. If N is a normal subgroup of (G, ·), the set of cosets G/N =

{Ng|g ∈ G} forms a group (G/N , ·), where the operation is de¬ned by

(Ng1 ) · (Ng2 ) = N (g1 · g2 ). This group is called the quotient group or factor

group of G by N .

Proof. The operation of multiplying two cosets, Ng1 and Ng2 , is de¬ned in

terms of particular elements, g1 and g2 , of the cosets. For this operation to make

sense, we have to verify that, if we choose different elements, h1 and h2 , in

the same cosets, the product coset N (h1 · h2 ) is the same as N (g1 · g2 ). In other

words, we have to show that multiplication of cosets is well de¬ned.

Since h1 is in the same coset as g1 , we have h1 ≡ g1 mod N . Similarly,

’1

h2 ≡ g2 mod N . We show that N h1 h2 = Ng1 g2 . We have h1 g1 = n1 ∈

’1 ’1 ’1 ’1 ’1

N and h2 g2 = n2 ∈ N , so h1 h2 (g1 g2 )’1 = h1 h2 g2 g1 = n1 g1 n2 g2 g2 g1 =

’1 ’1 ’1

n1 g1 n2 g1 . Now N is a normal subgroup, so g1 n2 g1 ∈ N and n1 g1 n2 g1 ∈ N .

Hence h1 h2 ≡ g1 g2 mod N and N h1 h2 = Ng1 g2 . Therefore, the operation is

well de¬ned.

The operation is associative because (Ng1 · Ng2 ) · Ng3 = N (g1 g2 ) · Ng3 =

N (g1 g2 )g3 and also Ng1 · (Ng2 · Ng3 ) = Ng1 · N (g2 g3 ) = Ng1 (g2 g3 ) =

N (g1 g2 )g3 .

Since Ng · N e = Nge = Ng and N e · Ng = Ng, the identity is N e = N . The

inverse of Ng is Ng ’1 because Ng · Ng ’1 = N (g · g ’1 ) = N e = N and also

Ng ’1 · Ng = N .

Hence (G/N, ·) is a group.

The order of G/N is the number of cosets of N in G. Hence

|G/N | = |G : N| = |G|/|N |.

84 4 QUOTIENT GROUPS

TABLE 4.1. Quotient

Group S3 /A3

H (12)

H

Ž

H (12)

H H

H (12) H (12) H

We have seen in Example 4.15 that A3 is a normal subgroup of S3 ; therefore,

S3 /A3 is a quotient group. If H = A3 , the elements of this group are the cosets

H and H (12), and its multiplication table is given in Table 4.1.

Example 4.19. (Zn , +) is the quotient group of (Z, +) by the subgroup nZ =

{nz|z ∈ Z}.

Solution. Since (Z, +) is abelian, every subgroup is normal. The set nZ can

be veri¬ed to be a subgroup, and the relationship a ≡ b mod nZ is equivalent

to a ’ b ∈ nZ and to n|a ’ b. Hence a ≡ b mod nZ is the same relation as

a ≡ b mod n. Therefore, Zn is the quotient group Z/nZ, where the operation on

congruence classes is de¬ned by [a] + [b] = [a + b].

(Zn , +) is a cyclic group with 1 as a generator, and therefore, by Theorem 3.25,

is isomorphic to Cn . The group (Z5 , +) is shown in Table 4.2.

When there is no confusion, we write the elements of Zn as 0, 1, 2, 3, . . . ,

n ’ 1 instead of [0], [1], [2], [3], . . . , [n ’ 1].

Proposition 4.20. If H is a subgroup of index 2 in G, so that |G : H | = 2, then

H is a normal subgroup of G, and G/H is cyclic group of order 2.

Proof. Since |G : H | = 2, there are only two right cosets of H in G. One

must be H and the other can be written as Hg, where g is any element of G that

is not in H . To show that H is a normal subgroup of G, we need to show that

g ’1 hg ∈ H for all g ∈ G and h ∈ H . If g is an element of H , it is clear that

g ’1 hg ∈ H for all h ∈ H . If g is not an element of H , suppose that g ’1 hg ∈ H .

/

’1

In this case, g hg must be an element of the other right coset Hg, and we

can write g ’1 hg = h1 g, for some h1 ∈ H . It follows that g = hh’1 ∈ H , which

1

contradicts the fact that g ∈ H . Hence g ’1 hg ∈ H for all g ∈ G and h ∈ H ; in

/

other words, H is normal in G.

TABLE 4.2. Group (Z5 , +)

+ [0] [1] [2] [3] [4]

[0] [0] [1] [2] [3] [4]

[1] [1] [2] [3] [4] [0]

[2] [2] [3] [4] [0] [1]

[3] [3] [4] [0] [1] [2]

[4] [4] [0] [1] [2] [3]

NORMAL SUBGROUPS AND QUOTIENT GROUPS 85

Theorem 4.21. If G is a ¬nite abelian group and the prime p divides the order

of G, then G contains an element of order p and hence a subgroup of order p.

Proof. We prove this result by induction on the order of G. For a particular

prime p, suppose that all abelian groups of order less than k, whose order is

divisible by p, contain an element of order p. The result is vacuously true for

groups of order 1. Now suppose that G is a group of order k. If p divides k,

choose any nonidentity element g ∈ G. Let t be the order of the element g.

Case 1. If p divides t, say t = pr, then g r is an element of order p. This follows

because g r is not the identity, but (g r )p = g t = e, and p is a prime.

Case 2. On the other hand, if p does not divide t, let K be the subgroup generated

by g. Since G is abelian, K is normal, and the quotient group G/K has order

|G|/t, which is divisible by p. Therefore, by the induction hypothesis, G/K has

an element of order p, say Kh. If u is the order of h in G, then hu = e and

(Kh)u = Khu = K. Since Kh has order p in G/K, u is a multiple of p, and we

are back to case 1.

The result now follows from the principle of mathematical induction.

This result is a partial converse to Lagrange™s theorem. It is a special case of

some important results, in more advanced group theory, known as the Sylow the-

orems. These theorems give information on the subgroups of prime power order,

and they can be found in books such as Herstein [9], Hall [30], or Nicholson [11].

Example 4.22. Show that A5 has no proper normal subgroups.

Solution. It follows from Corollary 3.34 that A5 contains three types of non-

identity elements: 3-cycles, 5-cycles, and pairs of disjoint transpositions. Suppose

that N is a normal subgroup of A5 that contains more than one element.

Case 1. Suppose that N contains the 3-cycle (abc). From the de¬nition of nor-

mal subgroup, g ’1 Ž (abc) Ž g ∈ N for all g ∈ A5 . If we take g = (ab) Ž (cd),

we obtain

(ab) Ž (cd) Ž (abc) Ž (ab) Ž (cd) = (adb) ∈ N

and also (adb)’1 = (abd) ∈ N . In a similar way, we can show that N contains

every 3-cycle. Therefore, by Proposition 3.37, N must be the entire alternat-

ing group.

Case 2. Suppose that N contains the 5-cycle (abcde). Then

and (abc)’1 Ž (abcde) Ž (abc) = (acb) Ž (abcde) Ž (abc) = (abdec) ∈ N

(abcde) Ž (abdec)’1 = (abcde) Ž (acedb) = (adc) ∈ N.

We are now back to case 1, and hence N = A5 .

86 4 QUOTIENT GROUPS

Case 3. Suppose that N contains the pair of disjoint transpositions (ab) Ž (cd).

Then, if e is the element of {1, 2, 3, 4, 5} not appearing in these transpositions,

we have

(abe)’1 Ž (ab) Ž (cd) Ž (abe) = (aeb) Ž (ab) Ž (cd) Ž (abe) = (ae) Ž (cd) ∈ N.

Also, (ab) Ž (cd) Ž (ae) Ž (cd) = (aeb) ∈ N , and again we are back to case 1.

We have shown that any normal subgroup of A5 containing more than one

element must be A5 itself.

A group without any proper normal subgroups is called a simple group. The

term simple must be understood in the technical sense that it cannot be broken

down, because it cannot have any nontrivial quotient groups. This is analogous to

a prime number, which has no nontrivial quotients. Apart from the cyclic groups

of prime order, which have no proper subgroups of any kind, simple groups are

comparatively rare.

The group A5 is of great interest to mathematicians because it is used in Galois

theory to show that there is an equation of the ¬fth degree that cannot be solved

by any algebraic formula.

It can be shown that every alternating group An , n 5, is simple. The cyclic

groups Cp , p a prime, are another in¬nite series of simple groups (the abelian

ones), and other series have been known for decades. But it was not until 1981

that the ¬nite simple groups were completely classi¬ed. This was the culmina-

tion of more than 30 years of effort by hundreds of mathematicians, yielding

thousands of pages of published work, and was one of the great achievements of

twentieth-century mathematics. One spectacular landmark came in 1963, when

J. G. Thompson and W. Feit veri¬ed a long-standing conjecture of W. Burnside

(1852“1927) that every ¬nite, non-abelian, simple group has even order (the

proof is more than 250 pages long!). The main dif¬culty in the classi¬cation was

the existence of sporadic ¬nite simple groups, not belonging to any of the known

families. The largest of these, known as the monster, has order approximately

2 — 1053 . The complete classi¬cation encompasses several in¬nite families and

exactly 26 sporadic groups.

MORPHISM THEOREM

The morphism theorem is a basic result of group theory that describes the rela-

tionship between morphisms, normal subgroups, and quotient groups. There is an

analogous result for most algebraic systems, including rings and vector spaces.

If f : G ’ H is a group morphism, the kernel of f , denoted by Kerf , is

de¬ned to be the set of elements of G that are mapped by f to the identity of

H . That is, Kerf = {g ∈ G|f (g) = eH }.

Proposition 4.23. Let f : G ’ H be a group morphism. Then:

(i) Kerf is a normal subgroup of G.

(ii) f is injective if and only if Kerf = {eG }.

MORPHISM THEOREM 87

Proof. (i) We ¬rst show that Kerf is a subgroup of G. Let a, b ∈ Kerf so

that f (a) = f (b) = eH . Then

f (ab) = f (a)f (b) = eH eH = eH , ab ∈ Kerf

so

and

’1

f (a ’1 ) = f (a)’1 = eH = eH , a ’1 ∈ Kerf.

so

Therefore, Kerf is a subgroup of G.

If a ∈ Kerf and g ∈ G, then

f (g ’1 ag) = f (g ’1 )f (a)f (g) = f (g)’1 eH f (g) = f (g)’1 f (g) = eH .

Hence g ’1 ag ∈ Kerf , and Kerf is a normal subgroup of G.

(ii) If f is injective, only one element maps to the identity of H. Hence

Kerf = {eG }. Conversely, if Kerf = {eG }, suppose that f (g1 ) = f (g2 ). Then

’1 ’1

f (g1 g2 ) = f (g1 )f (g2 )’1 = eH so g1 g2 ∈ Kerf = {eG }. Hence g1 = g2 , and

f is injective.

Proposition 4.24. For any group morphism f : G ’ H , the image of f , Imf =

{f (g)|g ∈ G}, is a subgroup of H (although not necessarily normal).

Proof. Let f (g1 ), f (g2 ) ∈ Imf . Then eH = f (eG ) ∈ Imf, f (g1 )f (g2 ) =

’1

f (g1 g2 ) ∈ Imf , and f (g1 )’1 = f (g1 ) ∈ Imf . Hence Imf is a subgroup of H .

Theorem 4.25. Morphism Theorem for Groups. Let K be the kernel of the

group morphism f : G ’ H . Then G/K is isomorphic to the image of f , and

the isomorphism ψ: G/K ’ Imf is de¬ned by ψ(Kg) = f (g).

This result is also known as the ¬rst isomorphism theorem; the second and

third isomorphism theorems are given in Exercises 4.43 and 4.44.

Proof. The function ψ is de¬ned on a coset by using one particular element

in the coset, so we have to check that ψ is well de¬ned; that is, it does not matter

which element we use. If Kg = Kg , then g ≡ g mod K so g g ’1 = k ∈ K =

Kerf . Hence g = kg and so

f (g ) = f (kg) = f (k)f (g) = eH f (g) = f (g).

Thus ψ is well de¬ned on cosets.

The function ψ is a morphism because

ψ(Kg1 Kg2 ) = ψ(Kg1 g2 ) = f (g1 g2 ) = f (g1 )f (g2 ) = ψ(Kg1 )ψ(Kg2 ).

If ψ(Kg) = eH , then f (g) = eH and g ∈ K. Hence the only element in the

kernel of ψ is the identity coset K, and ψ is injective. Finally, Im ψ = Imf ,

88 4 QUOTIENT GROUPS

by the de¬nition of ψ. Therefore, ψ is the required isomorphism between G/K

and Imf .

Conversely, note that if K is any normal subgroup of G, the map g ’ Kg is

a morphism from G to G/K, whose kernel is precisely K.

By taking f to be the identity morphism from G to itself, the morphism

theorem implies that G/{e} ∼ G. =

The function f : Z ’ Zn , de¬ned by f (x) = [x], has nZ as its kernel, and

therefore the morphism theorem yields the fact that Z/nZ ∼ Zn . =

If a and b are generators of the cyclic groups C12 = a and C6 = b , respec-

tively, consider the function f : C12 ’ C6 given by f (a r ) = b2r . This is well

de¬ned. In fact, if a r = a r1 , then 12 divides r ’ r1 by Proposition 3.11, so cer-

tainly b2r = b2r1 . It is easily veri¬ed that f is morphism, and the kernel is

K = {e, a 3 , a 6 , a 9 } because if a r is in K, then b2r = 0, so 6 divides 2r, whence

3 divides r. Thus C12 /K ∼ C6 , and this isomorphism is obtained by mapping

=

2r

r

the coset Ka to b .

The alternating group An is of index 2 in the symmetric group Sn (by The-

orem 3.36) and so is a normal subgroup by Proposition 4.20. It is instructive

to obtain this same conclusion from the morphism theorem. If σ is a per-

mutation in Sn , recall that σ is called even or odd according as σ D = D or

σ D = ’D, where D is the discriminant in n variables (see the discussion lead-

ing to Theorem 3.33). Consider the multiplicative group {1, ’1}, and de¬ne a

1 if σ D = D

function f : Sn ’ {1, ’1} by f (σ ) = . Then f is a surjec-

’1 if σ D = ’D

tive morphism (verify) and the kernel is the group An of even permutations. Since

|Sn | = n!, the morphism theorem and Corollary 4.8 give the following result (and

reprove Theorem 3.36).

Proposition 4.26. An is a normal subgroup of Sn , Sn /An ∼ C2 , and |An | = 1 n!.

= 2

Example 4.27. Show that the quotient group R/Z, of real numbers modulo 1 is

isomorphic to the circle group W = {eiθ ∈ C|θ ∈ R}.

Solution. The set W consists of points on the circle of complex numbers

of unit modulus, and forms a group under multiplication. De¬ne the function

f : R ’ W by f (x) = e2πix . This is a morphism from (R, +) to (W, ·) because

f (x + y) = e2πi(x+y) = e2πix · e2πiy = f (x) · f (y).

This function can be visualized in Figure 4.1 as wrapping the real line around

and around the circle.

The morphism f is clearly surjective, and its kernel is {x ∈ R|e2πix = 1} = Z.

Therefore, the morphism theorem implies that R/Z ∼ W . The quotient space R/Z

=

is the set of equivalence classes of R under the relation de¬ned by x ≡ y mod Z

if and only if the real numbers x and y differ by an integer. This quotient space

is called the group of real numbers modulo 1.

MORPHISM THEOREM 89

i

’1 W

’2 ’1 f

0 1 2 3

1

’i

Morphism f : R ’ W .

Figure 4.1.

Proposition 4.28. If G and H are ¬nite groups whose orders are relatively prime,

there is only one morphism from G to H , the trivial one.

Proof. Let K be the kernel of a morphism f from G to H . Then G/K ∼ Imf ,

=

a subgroup of H . Now |G/K| = |G|/|K|, which is a divisor of |G|. But by

Lagrange™s theorem, |Imf | is a divisor of |H |. Since |G| and |H | are relatively

prime, we must have |G/K| = |Imf | = 1. Therefore K = G, so f : G ’ H is

the trivial morphism de¬ned by f (g) = eH for all g ∈ G.

Example 4.29. Find all the subgroups and quotient groups of D4 , the symmetry

group of a square, and draw the poset diagram of its subgroups.

Solution. Any symmetry of the square induces a permutation of its vertices.

Thus, as in Example 3.30, this de¬nes a group morphism f : D4 ’ S4 . How-

ever, unlike the case of the symmetries of an equilateral triangle, this is not an

isomorphism because |D4 | = 8, whereas |S4 | = 24. The kernel of f consists of

symmetries ¬xing the vertices and so consists of the identity only. Therefore, by

the morphism theorem, D4 is isomorphic to the image of f in S4 . We equate

an element of D4 with its image in S4 . All the elements of D4 are shown in

Figure 4.2. The corner by the vertex 1 is blocked in, and the reverse side of the

square is shaded to illustrate the effect of the symmetries. The order of each

symmetry is given in Table 4.3.

1 2 1 2 1 2 1 2

4 3 4 3 4 3 4 3

(1) = e (1234) = g (13)°(24) = g (1432) = g

2 3

1 2 1 2 1 2 1 2

4 3 4 3 4 3 4 3

(24) = h (12) ° (34) = gh (13) = g h (14) ° (23) = g h

2 3

Figure 4.2. Symmetries of the square.

90 4 QUOTIENT GROUPS

TABLE 4.3. Orders of the Symmetries of a Square

g2 g3 g2 h g3 h

Elements of D4 gh

e g h

Order of Element 1 4 2 4 2 2 2 2

D4

e, g 2, gh, g 3h = K 2

K1 = e, g 2,h, g 2h C4

=L

e, g 2 e, g 3h

e, g 2h e, gh

e, h

e

Figure 4.3. Poset diagram of subgroups of D4 .

The cyclic subgroups generated by the elements are {e}, C4 = {e, g, g 2 , g 3 },

{e, g 2 }, {e, h}, {e, gh}, {e, g 2 h}, and {e, g 3 h}.

By Lagrange™s theorem, any proper subgroup must have order 2 or 4. Since

any group of order 2 is cyclic, the only proper subgroups that are not cyclic are

of order 4 and contain elements of order 1 and 2. There are two such subgroups,

K1 = {e, g 2 , h, g 2 h} and K2 = {e, g 2 , gh, g 3 h}. All the subgroups are illustrated

in Figure 4.3.

To ¬nd all the quotient groups, we must determine which subgroups are

normal.

The trivial group {e} and the whole group D4 are normal subgroups. Since

C4 , K1 , and K2 have index 2 in D4 , they are normal by Proposition 4.20, and

their quotient groups are cyclic of order 2.

Subgroup H Left Coset gH Right Coset Hg

{e, h} {g, gh} {g, hg} = {g, g 3 h}

{e, g 2 h} {g, g 3 h} {g, g 2 hg} = {g, gh}

{e, gh} {g, g 2 h} {g, ghg} = {g, h}

{e, g 3 h} {g, h} {g, g 3 hg} = {g, g 2 h}

For each of the subgroups above, the left and right cosets containing g are

different; therefore, none of the subgroups are normal.

Left Cosets of L Right Cosets of L

L = {e, g 2 } L = {e, g 2 }

gL = {g, g 3 } Lg = {g, g 3 }

hL = {h, hg 2 } = {h, g 2 h} Lh = {h, g 2 h}

ghL = {gh, ghg 2 } = {gh, g 3 h} Lgh = {gh, g 3 h}

The table above shows that L = {e, g 2 } is a normal subgroup. The multipli-

cation table for D4 /L given in Table 4.4 shows that it is isomorphic to the Klein

4-group.

DIRECT PRODUCTS 91

TABLE 4.4. Group D4 /L

· Lh Lg Lgh

L

Lh Lg Lgh

L L

Lh Lh Lgh Lg

L

Lg Lg Lgh Lh

L

Lgh Lgh Lg Lh L

DIRECT PRODUCTS

Given two sets, S and T , we can form their Cartesian product, S — T = {(s, t)|s ∈

S, t ∈ T }, whose elements are ordered pairs. For example, the product of the real

line, R, with itself is the plane, R — R = R2 . We now show how to de¬ne the

product of any two groups; the underlying set of the product is the Cartesian

product of the underlying sets of the original groups.

Proposition 4.30. If (G, Ž ) and (H , ) are two groups, then (G — H, ·) is a

group under the operation · de¬ned by

(g1 , h1 ) · (g2 , h2 ) = (g1 Ž g2 , h1 h2 ).

The group (G — H, ·) is called the direct product of the groups (G, Ž ) and (H , ).

Proof. All the group axioms follow from the axioms for (G, Ž ) and (H , ).

The identity of G — H is (eG , eH ), and the inverse of (g, h) is (g ’1 , h’1 ).

This construction can be iterated any ¬nite number of times to obtain the

direct product of n groups.

Sometimes the direct product of two groups G and H is called the direct

sum and is denoted by G • H . (The direct sum of a ¬nite number of groups is

the same as the direct product. It is possible to de¬ne a direct sum and direct

product of an in¬nite number of groups; these are different. An element of the

direct product is obtained by taking one element from each group, while an

element of the direct sum is obtained by taking one element from each group,

but with only a ¬nite number different from the identity.)

Example 4.31. Write down the table for the direct product of C2 with itself.

Solution. Let C2 = {e, g}, so that C2 — C2 = {(e, e), (e, g), (g, e), (g, g)}. Its

table is given in Table 4.5. We see that this group C2 — C2 is isomorphic to the

Klein 4-group of symmetries of a rectangle.

Theorem 4.32. If gcd(m, n) = 1, then Cmn ∼ Cm — Cn .

=

92 4 QUOTIENT GROUPS

TABLE 4.5. Group C2 — C2

· (e, e) (e, g) (g, e) (g, g)

(e, e) (e, e) (e, g) (g, e) (g, g)

(e, g) (e, g) (e, e) (g, g) (g, e)

(g, e) (g, e) (g, g) (e, e) (e, g)

(g, g) (g, g) (g, e) (e, g) (e, e)

Proof. Let g, h, and k be the generators of Cmn , Cm , and Cn , respectively.

De¬ne

f : Cmn ’ Cm — Cn

by f (g r ) = (hr , k r ) for r ∈ Z. This is well de¬ned for all integers r because if

g r = g r , then r ’ r is a multiple of mn, so r ’ r is a multiple of m and of n.

Hence hr = hr and k r = k r . Now f is a group morphism because

f (g r · g s ) = f (g r+s ) = (hr+s , k r+s ) = (hr · hs , k r · k s ) = (hr , k r ) · (hs , k s )

= f (g r ) · f (g s ).

If g r ∈ Kerf , then hr = e and k r = e. Therefore, r is divisible by m and n, and

since gcd(m, n) = 1, r is divisible by mn. Hence Kerf = {e}, and the image of f

is isomorphic to Cmn . However, |Cmn | = mn and |Cm — Cn | = |Cm | · |Cn | = mn;

hence Imf = Cm — Cn , and f is an isomorphism.

The following is an easy consequence of this result.

Corollary 4.33. Let n = p1 1 p2 2 . . . pr r where p1 , p2 , . . . , pr are distinct primes.

±± ±

Then Cn ∼ Cp±1 — Cp±2 — · · · — Cpr±r .

=1 2

If m and n are not coprime, then Cmn is never isomorphic to Cm — Cn . For

example, C2 — C2 is not isomorphic to C4 because the direct product contains

no element of order 4. In general, the order of the element (h, k) in H — K is

the least common multiple of the orders of h and k, because (h, k)r = (hr , k r ) =

(e, e) if and only if hr = e and k r = e. Hence, if gcd(m, n) > 1, the order of

(h, k) in Cm — Cn is always less than mn.

Direct products can be used to classify all ¬nite abelian groups. It can be

shown that any ¬nite abelian group is isomorphic to a direct product of cyclic

groups. For example, see Nicholson [11] or Baumslag and Chandler [25]. The

results above can be used to sort out those products of cyclic groups that are

isomorphic to each other. For example, there are three nonisomorphic abelian

groups with 24 elements, namely,

C8 — C3 ∼ C24

=

C2 — C4 — C3 ∼ C6 — C4 ∼ C2 — C12

= =

C2 — C2 — C2 — C3 ∼ C2 — C2 — C6 .

=

DIRECT PRODUCTS 93

Theorem 4.34. If (G, ·) is a ¬nite group for which every element g ∈ G satis¬es

g 2 = e, then |G| = 2n for some n 0, and G is isomorphic to the n-fold direct

product C2 = C2 — C2 — · · · — C2 .

n

Proof. Every element in G has order 1 or 2, and the identity is the only

element of order 1. Therefore, every element of G is its own inverse. The group

G is abelian because for any g, h ∈ G, gh = (gh)’1 = h’1 g ’1 = hg.

Choose the elements a1 , a2 , . . . , an ∈ G so that ai = e and ai cannot be written

as a product of powers of a1 , . . . , ai’1 . Furthermore, choose n maximal, so that

every element can be written in terms of the elements ai . If C2 is generated by

g, we show that the function

f : C2 ’ G, de¬ned by f (g r1 , g r2 , . . . , g rn ) = a11 a22 . . . ann

rr

n r

is an isomorphism. It is well de¬ned for all integers ri , because if g ri = g qi , then

q

airi = ai i . Now

f ((g r1 , . . . , g rn ) · (g s1 , . . . , g sn )) = f (g r1 +s1 , . . . , g rn +sn ) = a11 +s1 . . . ann +sn

r r

r s

= a11 . . . ann .a11 . . . ann

r s

because G is abelian

= f (g r1 , . . . , g rn ) · f (g s1 , . . . , g sn ).

Hence f is a group morphism.

Let (g r1 , . . . , g rn ) ∈ Kerf . Suppose that ri is the last odd exponent, so that

ri’1

r

ri+1 , ri+2 , . . . , rn are all even. Then a11... ai’1 ai = e and

ai = ai’1 = a11... ai’1 ,

r

r i’1

which is a contradiction. Therefore, all the exponents are even, and f is injective.

The choice of the elements ai guarantees that f is surjective. Hence f is the

required isomorphism.

Example 4.35. Describe all the group morphisms from C10 to C2 — C5 . Which

of these are isomorphisms?

Solution. Since C10 is a cyclic group, generated by g, for example, a morphism

from C10 is determined by the image of g. Let h and k be generators of C2 and C5 ,

respectively, and consider the function fr,s : C10 ’ C2 — C5 which maps g to the

element (hr , k s ) ∈ C2 — C5 . Then, if fr,s is a morphism, fr,s (g n ) = (hrn , k sn ) for

0 n 9. However, this would also be true for all integers n, because if g n = g m ,

then 10|n ’ m. Hence 2|n ’ m and 5|n ’ m and hrn = hrm and k sn = k sm .

We now verify that fr,s is a morphism for any r and s. We have

fr,s (g a g b ) = fr,s (g a+b ) = (h(a+b)r , k (a+b)s ) = (har , k as )(hbr , k bs )

= fr,s (g a )fr,s (g b ).

94 4 QUOTIENT GROUPS

Therefore, there are ten morphisms, fr,s , from C10 to C2 — C5 corresponding to

the ten elements (hr , k s ) of C2 — C5 .

Now

Kerfr,s = {g n |(hrn , k sn ) = (e, e)} = {g n |rn ≡ 0 mod 2 and sn ≡ 0 mod 5}.

Hence Kerfr,s = {e} if (r, s) = (1, 1), (1, 2), (1, 3), or (1, 4), while Kerf0,0 =

C10 , Kerf1,0 = {e, g 2 , g 4 , g 6 , g 8 }, and Kerf0,s = {e, g 5 }, if s = 1, 2, 3, or 4. If

Kerfr,s contains more than one element, fr,s is not an injection and cannot be an

isomorphism. By the morphism theorem,

|C10 |/|Kerfr,s | = |Imfr,s |,

and if Kerfr,s = {e}, then | Im fr,s | = 10, so fr,s is surjective also. Therefore, the

isomorphisms are f1,1 , f1,2 , f1,3 , and f1,4 .

GROUPS OF LOW ORDER

We ¬nd all possible isomorphism classes of groups with eight or fewer elements.

Lemma 4.36. Suppose that a and b are elements of coprime orders r and s,

respectively, in an abelian group. Then ab has order rs.

Proof. Let A and B denote the subgroups generated by a and b, respectively.

Since ab = ba, we have (ab)rs = a rs brs = (a r )s (bs )r = es er = e. Suppose that

(ab)k = e; we must show that rs divides k. Observe that a k = b’k ∈ A © B.

Since A © B is a subgroup of both A and B, its order divides |A| = r and

|B| = s by Lagrange™s theorem. Since r and s are coprime, this implies that

|A © B| = 1. It follows that a k = e and b’k = e, so r divides k and s divides

k. Hence rs divides k by Theorem 11, Appendix 2 (again because r and s are

coprime), as required.

With this we can describe the groups of order eight or less.

Order 1. Every trivial group is isomorphic to {e}.

Order 2. By Corollary 4.11, every group of order 2 is cyclic.

Order 3. By Corollary 4.11, every group of order 3 is cyclic.

Order 4. Each element has order 1, 2, or 4.

Case (i). If there is an element of order 4, the group is cyclic.

Case (ii). If not, every element has order 1 or 2 and, by Theorem 4.34, the

group is isomorphic to C2 — C2 .

Order 5. By Corollary 4.11, every group of order 5 is cyclic.

Order 6. Each element has order 1, 2, 3, or 6.

Case (i). If there is an element of order 6, the group is cyclic.

GROUPS OF LOW ORDER 95

Case (ii). If not, the elements have orders 1, 2, or 3. By Theorem 4.34, all

the elements in a group of order 6 cannot have orders 1 and 2. Hence

there is an element, say a, of order 3. The subgroup H = {e, a, a 2 } has

index 2, and if b ∈ H , the underlying set of the group is then H ∪ H b =

/

{e, a, a , b, ab, a b}. By Proposition 4.20, H is normal, and the quotient

2 2

group of H is cyclic of order 2. Hence

if r is even

H

br ∈ H br = (H b)r = .

if r is odd

Hb

Therefore, b has even order. It cannot be 6, so it must be 2. As H

is normal, bab’1 ∈ H . We cannot have bab’1 = e, because a = e. If

bab’1 = a, then ba = ab, and we can prove that the entire group is

abelian. This cannot happen because by Lemma 4.36, ab would have

order 6. Therefore, bab’1 = a 2 , and the group is generated by a and b

with relations a 3 = b2 = e and ba = a 2 b. This group is isomorphic to

D3 and S3 .

Order 7. Every group of order 7 is cyclic.

Order 8. Each element has order 1, 2, 4, or 8.

Case (i). If there is an element of order 8, the group is cyclic.

Case (ii). If all elements have order 1 or 2, the group is isomorphic to

C2 — C2 — C2 by Theorem 4.34.

Case (iii). Otherwise, there is an element of order 4, say a. The subgroup

H = {e, a, a 2 , a 3 } is of index 2 and therefore normal. If b ∈ H , the

/

underlying set of the group is H ∪ H b = {e, a, a , a , b, ab, a 2 b, a 3 b}.

2 3

Now b2 ∈ H , but b2 cannot have order 4; otherwise, b would have

order 8. Therefore, b2 = e or a 2 . As H is normal, bab’1 ∈ H and has

the same order as a because (bab’1 )k = ba k b’1 .

Case (iiia). If bab’1 = a, then ba = ab, and the whole group can be proved

to be abelian. If b2 = e, each element can be written uniquely in the form

a r bs , where 0 r 3 and 0 s 1. Hence the group is isomorphic

to C4 — C2 by mapping a r bs to (a r , bs ). If b2 = a 2 , let c = ab, so that

c2 = a 2 b2 = a 4 = e. Each element of the group can now be written

uniquely in the form a r cs , where 0 r 3, 0 s 1, and the group

is still isomorphic to C4 — C2 .

Case (iiib). If bab’1 = a 3 and b2 = e, the group is generated by a and

b with the relations a 4 = b2 = e, ba = a 3 b. This is isomorphic to the

dihedral group D4 .

Case (iiic). If bab’1 = a 3 and b2 = a 2 , then the group is isomorphic to the

quaternion group Q, described in Exercise 3.47. The isomorphism maps

a r bs to i r j s .

Any group with eight or fewer elements is isomorphic to exactly one group

in Table 4.6.

96 4 QUOTIENT GROUPS

TABLE 4.6. Groups of Low Order

Order 1 2 3 4 5 6 7 8

{e}

Abelian groups C2 C3 C4 C5 C6 C7 C8

C2 — C2 C4 — C2

C2 — C2 — C 2

Non-abelian groups S3 D4

Q

ACTION OF A GROUP ON A SET

The concept of a group acting on a set X is a slight generalization of the group

of symmetries of X. It is equivalent to considering a subgroup of S(X). This

concept is useful for determining the order of the symmetry groups of solids

in three dimensions, and it is indispensable in Chapter 6, when we look at the

P´ lya“Burnside method of enumerating sets with symmetries.

o

The group (G, ·) acts on the set X if there is a function

ψ: G — X ’ X

such that when we write g(x) for ψ(g, x), we have:

(i) (g1 g2 )(x) = g1 (g2 (x)) for all g1 , g2 ∈ G, x ∈ X.

(ii) e(x) = x if e is the identity of G and x ∈ X.

Proposition 4.37. If g is an element of a group G acting on the set X, then

the function g: X ’ X, which maps x to g(x), is a bijection. This de¬nes

a morphism

χ: G ’ S(X)

from G to the group of symmetries of X.

Proof. The function g: X ’ X is injective because if g(x) = g(y), then

g g(x) = g ’1 g(y), and e(x) = e(y) or x = y. It is surjective because if z ∈ X,

’1

g(g ’1 (z)) = gg ’1 (z) = e(z) = z.

Hence g is bijective, and g can be considered as an element of S(X), the group

of symmetries of X.

The function χ: G ’ S(X), which takes the element g ∈ G to the bijection

g: X ’ X, is a group morphism because χ(g1 g2 ) is the function from X

to X de¬ned by χ(g1 g2 )(x) = (g1 g2 )(x) = (g1 (g2 (x)) = χ(g1 ) Ž χ(g2 )(x); thus

χ(g1 g2 ) = χ(g1 ) Ž χ(g2 ).

If Kerχ = {e}, then χ is injective, and the group G is said to act faithfully

on the set X. G acts faithfully on X if the only element of G, which ¬xes every

ACTION OF A GROUP ON A SET 97

g

2 1

3 4

2 1

6 5

h

3 6

7 8

4 5

Figure 4.4. C2 acting on a hexagon. Figure 4.5. C3 acting on a cube.

element of X, is the identity e ∈ G. In this case, we identify G with Imχ and

regard G as a subgroup of S(X).

For example, consider the cyclic group of order 2, C2 = {e, h}, acting on

the regular hexagon in Figure 4.4, where h re¬‚ects the hexagon about the line

joining vertex 3 to vertex 6. Then C2 acts faithfully and can be identi¬ed with

the subgroup {(1), (15) Ž (24)} of D6 .

The cyclic group C3 = {e, g, g 2 } acts faithfully on the cube in Figure 4.5,

where g rotates the cube through one-third of a revolution about a line join-

ing two opposite vertices. This group action can be considered as the subgroup

{(1), (163) Ž (457), (136) Ž (475)} of the symmetry group of the cube.

Proposition 4.38. If G acts on a set X and x ∈ X, then

Stab x = {g ∈ G|g(x) = x}

is a subgroup of G, called the stabilizer of x. It is the set of elements of G that

¬x x.

Proof. Stab x is a subgroup because

(i) If g1 , g2 ∈ Stab x, then (g1 g2 )(x) = g1 (g2 (x)) = g1 (x) = x, so g1 g2 ∈

Stab x.

(ii) If g ∈ Stab x, then g ’1 (x) = x, so g ’1 ∈ Stab x.

The set of all images of an element x ∈ X under the action of a group G is

called the orbit of x under G and is denoted by

Orb x = {g(x)|g ∈ G}.

The orbit of x is the equivalence class of x under the equivalence relation on X

in which x is equivalent to y if and only if y = g(x) for some g ∈ G. If π is

a permutation in Sn , the subgroup generated by π acts on the set {1, 2, . . . , n},

and this de¬nition of orbit agrees with our previous one.

A graphic illustration of orbits can be obtained by looking at the group

of matrices

cos θ ’ sin θ

SO(2) = θ ∈R

sin θ cos θ

98 4 QUOTIENT GROUPS