2.4. HOMOMORPHISMS AND ISOMORPHISMS
i
“bookmt” — 2006/8/8 — 12:58 — page 109 — #121
i
i
2.4. HOMOMORPHISMS AND ISOMORPHISMS
109
2.3.5.
(a) Show that if n is odd, then the axis of each of the “flips” passes through a vertex of the n-gon and the midpoint of the opposite edge. See Figure 2.3.2 on page 107 for the case n D 5.
(b) If n is even and k is even, show that jk=n D rk j is a rotation about an axis passing through a pair of opposite vertices of the n-gon.
(c) Show that if n is even and k is odd, then jk=n D rk j is a rotation about an axis passing through the midpoints of a pair of opposite edges of the n-gon. See Figure 2.3.2 on page 107 for the case n D 6.
2.3.6. Find a subgroup of D6 that is isomorphic to D3.
2.3.7. Find a subgroup of D6 that is isomorphic to the symmetry group of the rectangle.
2.3.8. Consider a regular 10-gon in which alternate vertices are painted red and blue. Show that the symmetry group of the painted 10-gon is isomorphic to D5.
2.3.9. Consider a regular 15-gon in which every third vertex is painted red.
Show that the symmetry group of the painted 15-gon is isomorphic to D5.
However, if the vertices are painted with the pattern red, green, blue, red, green, blue, ..., red, green, blue, then the symmetry group is reduced to Z5.
2.3.10. Consider a card in the shape of an n-gon, whose two faces (top and bottom) are painted red and green. Show that the symmetry group of the card (including reflections) is isomorphic to Dn.
2.3.11. Consider a card in the shape of an n-gon, whose two faces (top and bottom) are indistinguishable. Determine the group of symmetries of the card (including both rotations and reflections).
2.4. Homomorphisms and Isomorphisms
We have already introduced the concept of an isomorphism between two groups: An isomorphism ' W G ! H is a bijection that preserves group multiplication (i.e., '.g1g2/ D '.g1/'.g2/ for all g1; g2 2 G).
For example, the set of eight 3-by-3 matrices fE; R; R2; R3; A; RA; R2A; R3Ag; where E is the 3-by-3 identity matrix, and
21
0
03
20
1 03
A D 0
1
0
1
0 0
4
5
R D 4
5 ;
0
0
1
0
0 1
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 110 — #122
i
i
110
2. BASIC THEORY OF GROUPS given in Section 1.4, is a subgroup of GL.3; R/. The map ' W rkal 7!
RkAl (0 k 3, 0 l 1) is an isomorphism from the group of symmetries of the square to this group of matrices.
Similarly, the set of eight 2-by-2 matrices fE; R; R2; R3; J; RJ; R2J; R3J g; where now E is the 2-by-2 identity matrix and
1
0
0
1
J D
R D
0
1
1
0
is a subgroup of GL.2; R/, and the map W rkal 7! RkJ l (0 k 3, 0 l 1) is an isomorphism from the group of symmetries of the square to this group of matrices.
There is a more general concept that is very useful:
Definition 2.4.1. A map between groups ' W G ! H is called a homomorphism if it preserves group multiplication, '.g1g2/ D '.g1/'.g1/ for all g1; g2 2 G. An endomorphism of G is a homomorphism ' W G ! G.
There is no requirement here that ' be either injective or surjective.
Example 2.4.2. We consider some homomorphisms of the symmetry group of the square into permutation groups. Place the square card in the .x y/– plane so that the axes of symmetry for the rotations a, b, and r coincide with the x–, y–, and z–axes, respectively. Each symmetry of the card induces a bijective map of the space S D f.x; y; 0/ W jxj 1; jyj 1g occupied by the card. For example, the symmetry a induces the map
2x3
2
x3
y
y
4
5 7! 4
5 :
0
0
The map associated to each symmetry sends the set V of four vertices of S onto itself. So for each symmetry of the square, we get an element . / of Sym.V /. Composition of symmetries corresponds to composition of maps of S and of V , so the assignment 7! ./ is a homomorphism from the symmetry group of the square to Sym.V /. This homomorphism is injective, since a symmetry of the square is entirely determined by what it does to the vertices, but it cannot be surjective, since the square has only eight symmetries while jSym.V /j D 24.
Example 2.4.3. To make these observations more concrete and computationally useful, we number the vertices of S . It should be emphasized that we are not numbering the corners of the card, which move along with
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 111 — #123
i
i
2.4. HOMOMORPHISMS AND ISOMORPHISMS
111
the card, but rather the locations of these corners, which stay put. See Figure 2.4.1.
4
1
3
2
Figure 2.4.1. Labeling the vertices of the square.
Numbering the vertices gives us a homomorphism ' from the group of symmetries of the square into S4. Observe, for example, that '.r/ D .1432/, '.a/ D .14/.23/, and '.c/ D .24/. Now you can compute that '.a/'.r/ D .14/.23/.1432/ D .24/ D '.c/ D '.ar/: You are asked in Exercise 2.4.1 to complete the tabulation of the map ' from the symmetry group of the square into S4 and to verify the homomorphism property.
Note that all of this is a formalization of the computation by pictures that was done in Section 1.3.
2
1
1
2
Figure 2.4.2. Labeling the diagonals of the square.
Example 2.4.4. There are other sets of geometric objects associated with the square that are permuted by symmetries of the square: the set of edges, the set of diagonals, the set of pairs of opposite edges. Let’s consider the diagonals (Figure 2.4.2). Numbering the diagonals gives a homomorphism from the group of symmetries of the square into S2.
You can compute, for example, that .r / D .a/ D .12/, while .c/ D e. You are asked in Exercise 2.4.2 to complete the tabulation of the map and to verify its homomorphism property.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 112 — #124
i
i
112
2. BASIC THEORY OF GROUPS Example 2.4.5. It is well known that the determinant of an invertible matrix is nonzero, and that the determinant satisfies the identity det.AB/ D det.A/ det.B/. Therefore, det W GL.n; R/ ! R is a homomorphism from the group of invertible matrices to the group of nonzero real numbers under multiplication.
Example 2.4.6. Recall that a linear transformation T W Rn ! Rn has the property that T .a Cb/ D T .a/CT .b/. Thus T is a group homomorphism from the additive group Rn to itself. More concretely, for any n-by-n matrix M , we have M.a C b/ D M a C M b. Thus multiplication by M is a group homomorphism from the additive group Rn to itself.
Example 2.4.7. Let G be any group and a and element of G. The the map from Z to G given by k 7! ak is a group homomorphism. This is equivalent to the statement that akC` D aka` for all integers k and `. The image of this homomorphism is the cyclic subgroup of G generated by g.
Example 2.4.8. There is a homomorphism from Z to Zn defined by k 7!
Œk. This follows directly from the definition of the addition in Zn: Œa C Œb D Œa C b. (But recall that we had to check that this definition makes sense; see the discussion following Lemma 1.7.5.)
This example is also a special case of the previous example, with G D Zn and the chosen element a D Œ1 2 G. The map is given by k 7! kŒ1 D Œk.
Example 2.4.9. Let G be an abelian group and n a fixed integer. Then the map from G to G given by g 7! gn is a group homomorphism. This is equivalent to the statement that .ab/n D anbn when a; b are elements in an abelian group.
Let us now turn from the examples to some general observations. Our first observation is that the composition of homomorphisms is a homomorphism.
Proposition 2.4.10. Let ' W G ! H and W H ! K be homo morphisms of groups. Then the composition ı ' W G ! K is also a homomorphism.
Proof. Exercise 2.4.3.
n
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 113 — #125
i
i
2.4. HOMOMORPHISMS AND ISOMORPHISMS
113
Next we check that homomorphisms preserve the group identity and inverses.
Proposition 2.4.11. Let ' W G ! H be a homomorphism of groups.
(a) '.eG/ D eH .
(b) For each g 2 G, '.g 1/ D .'.g// 1.
Proof. For any g 2 G, '.eG/'.g/ D '.eGg/ D '.g/: It follows from Proposition 2.1.1(a) that '.eG/ D eH . Similarly, for any g 2 G, '.g 1/'.g/ D '.g 1g/ D '.eG/ D eH ; so Proposition 2.1.1(b) implies that '.g 1/ D .'.g// 1.
n
Before stating the next proposition, we recall some conventional math ematical notation. For any function f W X ! Y , and any subset B Y , the preimage of B in X is fx 2 X W f .x/ 2 Bg. The conventional notation for the preimage of B is f 1.B/. The preimage of B makes sense regardless of whether f has an inverse function, and the notation f 1.B/ is not supposed to suggest that f has an inverse function. In case that f does have an inverse function, then f 1.B/ D ff 1.y/ W y 2 Bg. For example, if ' W Z ! Z6 is the map n 7! Œn, then ' 1.fŒ0; Œ3g/ is the set of integers congruent to 0 or to 3 mod 6.
Proposition 2.4.12. Let ' W G ! H be a homomorphism of groups.
(a) For each subgroup A G, '.A/ is a subgroup of H .
(b) For each subgroup B H , ' 1.B/ D fg 2 G W '.g/ 2 Bg is a subgroup of G.
Proof. We have to show that '.A/ is closed under multiplication and inverses. Let h1 and h2 be elements of '.A/. There exist elements a1; a2 2 A such that hi D '.ai / for i D 1; 2. Then h1h2 D '.a1/'.a2/ D '.a1a2/ 2 '.A/; since a1a2 2 A. Likewise, for h 2 '.A/, there is an a 2 A such that '.a/ D h. Then, using Proposition 2.4.11(b) and closure of A under inverses, we compute h 1 D .'.a// 1 D '.a 1/ 2 '.A/:
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 114 — #126
i
i
114
2. BASIC THEORY OF GROUPS
The proof of part (b) is left as an exercise.
n
The Kernel of a Homomorphism
You might think at first that it is not very worthwhile to look at non injective homomorphisms ' W G ! H since such a homomorphism loses information about G. But in fact, such a homomorphism also reveals certain information about the structure of G that otherwise might be missed.
For example, consider the homomorphism from the symmetry group G of the square into the symmetric group S2 induced by the action of G on the two diagonals of the square, as discussed in Example 2.4.4. Let N denote the set of symmetries of the square such that . / D e. You can compute that N D fe; c; d; r2g. (Do it now!) From the general theory, which I am about to explain, we see that N is a special sort of subgroup G, called a normal subgroup. Understanding such subgroups helps to understand the structure of G. For now, verify for yourself that N is, in fact, a subgroup.
Definition 2.4.13. A subgroup N of a group G is said to be normal if for all g 2 G, gNg 1 D N . Here gNg 1 means fgng 1 W n 2 N g.
Definition 2.4.14. Let ' W G ! H be a homomorphism of groups. The kernel of the homomorphism ', denoted ker.'/, is ' 1.eH / D fg 2 G W '.g/ D eH g.
According to Proposition 2.4.12 (b), ker.'/ is a subgroup of G (since feH g is a subgroup of H ). We now observe that it is a normal subgroup.
Proposition 2.4.15. Let ' W G ! H be a homomorphism of groups.
Then ker.'/ is a normal subgroup of G.
Proof. It suffices to show that g ker.'/g 1 D ker.'/ for all g 2 G. If x 2 ker.'/, then '.gxg 1/ D '.g/'.x/.'.g// 1 D '.g/e.'.g// 1 D e. Thus gxg 1 2 ker.'/. We have now shown that for all g 2 G, g ker.'/g 1 ker.'/. We still need to show the opposite containment.
But if we replace g by g 1, we obtain that for all g 2 G, g 1 ker.'/g
ker.'/; this is equivalent to ker.'/ g ker.'/g 1. Since we have both g ker.'/g 1 ker.'/ and ker.'/ g ker.'/g 1, we have equality of the two sets.
n
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 115 — #127
i
i
2.4. HOMOMORPHISMS AND ISOMORPHISMS
115
If a homomorphism ' W G ! H is injective, then its kernel ' 1.eH / contains only eG. The converse of this statement is also valid:
Proposition 2.4.16. A homomorphism ' W G ! H is injective if, and only if, ker.'/ D feGg.
Proof. If ' is injective, then eG is the unique preimage of eH under '.
Conversely, suppose that ker .'/ D feGg. Let h 2 H and suppose that g1; g2 2 G satisfy '.g1/ D '.g2/ D h. Then '.g 1g
1
2/ D '.g1/ 1'.g2/ D h 1h D eH , so g 1g
g
1
2 2 ker.'/. Therefore, g 1
1
2 D eG , which gives g1 D g2.
n
Example 2.4.17. The kernel of the determinant det W GL.n; R/ ! R is the subgroup of matrices with determinant equal to 1. This subgroup is called the special linear group and denoted SL.n; R/.
Example 2.4.18. Let G be any group and a 2 G. If the order of a is n, then the kernel of the homomorphism k 7! ak from Z to G is the set of all multiples of n, fk n W k 2 Zg. If a is of infinite order, then the kernel of the homomorphism is f0g.
Example 2.4.19. In particular, the kernel of the homomorphism from Z to Zn defined by k 7! Œk is Œ0 D fk n W k 2 Zg.
Example 2.4.20. If G is an abelian group and n is a fixed integer, then the kernel of the homomorphism g 7! gn from G to G is the set of elements whose order divides n.
Parity of Permutations
Additional examples of homomorphisms are explored in the Exercises.
In particular, it is shown in the Exercises that there is a homomorphisms W Sn ! f˙1g with the property that ./ D 1 for any 2–cycle . This is an example of a homomorphism that is very far from being injective and that picks out an essential structural feature of the symmetric group.
Definition 2.4.21. The homomorphism is called the sign (or parity) homomorphism. A permutation is said to be even if ./ D 1, that is, if is in the kernel of the sign homomorphism. Otherwise, is said to be odd.
The subgroup of even permutations (that is, the kernel of ) is generally denoted An. This subgroup is also referred to as the alternating group.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 116 — #128
i
i
116
2. BASIC THEORY OF GROUPS
The following statement about even and odd permutations is implicit in the Exercises: Proposition 2.4.22. A permutation is even if, and only if, can be written as a product of an even number of 2–cycles.
Even and odd permutations have the following property: The product of two even permutations is even; the product of an even and an odd permutation is odd, and the product of two odd permutations is even. Hence
Corollary 2.4.23. The set of odd permutations in Sn is .12/An, where An denotes the subgroup of even permutations.
Proof. .12/An is contained in the set of odd permutations. But if is any odd permutation, then .12/ is even, so D .12/..12// 2 .12/An.
n
Corollary 2.4.24. A k–cycle is even if k is odd and odd if k is even.
Proof. According to Exercise 1.5.5, a k cycle can be written as a product of .k 1/ 2–cycles.
n
Exercises 2.4 2.4.1. Let ' be the map from symmetries of the square into S4 induced by the numbering of the vertices of the square in Figure 2.4.1 on page Complete the tabulation of '. / for in the symmetry group of the square, and verify the homomorphism property of ' by computation.
2.4.2. Let be the map from the symmetry group of the square into S2 induced by the labeling of the diagonals of the square as in Figure on page 111. Complete the tabulation of and verify the homomorphism property by computation. Identify the kernel of .
2.4.3. Prove Proposition 2.4.10.
2.4.4. Prove part (b) of Proposition 2.4.12. Note: Do not assume that ' has an inverse function ' 1 W H ! G.
2.4.5. For any subgroup A of a group G, and g 2 G, show that gAg 1 is a subgroup of G.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 117 — #129
i
i
2.4. HOMOMORPHISMS AND ISOMORPHISMS
117
2.4.6. Show that every subgroup of an abelian group is normal.
2.4.7. Let ' W G ! H be a homomorphism of groups with kernel N .
For a; x 2 G, show that '.a/ D '.x/ , a 1x 2 N , aN D xN: Here aN denotes fan W n 2 N g.
2.4.8. Let ' W G ! H be a homomorphism of G onto H . If A is a normal subgroup of G, show that '.A/ is a normal subgroup of H .
2.4.9. Define a map from Dn to C2 D f˙1g by ./ D 1 if does not interchange top and bottom of the n-gon, and . / D 1 if does interchange top and bottom of the n-gon. Show that is a homomorphism.
The following exercises examine an important homomorphism from Sn to C2 D f˙1g (for any n).
2.4.10. Let fx1; x2; : : : ; xng be variables. For any polynomial p in n variables and for 2 Sn, define .p/.x1; : : : ; xn/ D p.x.1/; : : : ; x.n//: Check that . .p// D ./.p/ for all and 2 Sn 2.4.11. Now fix n 2 N, and define
Y
D
.xi
xj /: 1i
./= is a homomorphism from Sn to f1; 1g.
2.4.12. Show that for any 2–cycle .a; b/, ..a; b// D 1; hence if a per mutation is a product of k 2–cycles , then ./ D . 1/k. Now any permutation can be written as a product of 2–cycles (Exercise 1.5.5). If a permutation can be written as a product of k 2–cycles and also as a product of l 2–cycles, then ./ D . 1/k D . 1/l , so the parity of k and of l is the same. The parity is even if, and only if, ./ D 1.
2.4.13. For each permutation 2 Sn, define an n-by-n matrix T ./ as follows. Let Oe1; Oe2; : : : ; Oen be the standard basis of Rn; Oek has a 1 in the kth coordinate and zeros elsewhere. Define T ./ D ŒOe.1/; Oe.2/; : : : ; Oe.n/I that is, the kth column of T ./ is the basis vector Oe.k/. Show that the map 7! T ./ is a homomorphism from Sn into GL.n; R/. What is the range of T ?
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 118 — #130
i
i
118
2. BASIC THEORY OF GROUPS Definition 2.4.25. Two elements a and b in a group G are said to be conjugate if there is an element g 2 G such that a D gbg 1.
2.4.14. This exercise determines when two elements of Sn are conjugate.
(a) Show that for any k cycle .a1; a2; : : : ; ak/ 2 Sn, and for any permutation 2 Sn, we have .a1; a2; : : : ; ak/ 1 D ..a1/; .a2/; : : : ; .ak//: Hint: As always, first look at some examples for small n and k. Both sides are permutations (i.e., bijective maps defined on f1; 2; : : : ; ng). Show that they are the same maps by showing that they do the same thing.
(b) Show that for any two k cycles, .a1; a2; : : : ; ak/
and
.b1; b2; : : : ; bk/ in Sn there is a permutation 2 Sn such that .a1; a2; : : : ; ak/ 1 D .b1; b2; : : : ; bk/:
(c) Suppose that ˛ and ˇ are elements of Sn and that ˇ D g˛g 1 for some g 2 Sn. Show that when ˛ and ˇ are written as a product of disjoint cycles, they both have exactly the same number of cycles of each length. (For example, if ˛ 2 S10 is a product of two 3–cycles, one 2–cycle, and four 1–cycles, then so is ˇ.) We say that ˛ and ˇ have the same cycle structure.
(d) Conversely, suppose ˛ and ˇ are elements of Sn and they have the same cycle structure. Show that there is an element g 2 Sn such that ˇ D g˛g 1.
The result of this exercise is as follows: Two elements of Sn are conjugate if, and only if, they have the same cycle structure.
2.4.15. Show that is the unique homomorphism from Sn onto f1; 1g.
Hint: Let ' W Sn ! f˙1g be a homomorphism. If '..12// D 1, show, using the results of Exercise 2.4.14, that ' D . If '..12// D C1, show that ' is the trivial homomorphism, './ D 1 for all .
2.4.16. For m