<<

. 4
( 13)



>>

„ Ž σ = „ Ž σ1 , so σ = σ1 by cancellation in Sn . To see that f is surjective, let
» ∈ 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

<<

. 4
( 13)



>>