Abstract Algebra PDF

 5 Permutation Groups Wigner’s discovery about the electron permutation group was just the beginning. He and others found many similar applications and...

 5 Permutation Groups Wigner’s discovery about the electron permutation group was just the beginning. He and others found many similar applications and nowadays group theoretical methods—especially those involving characters and representations—pervade all branches of q­ uantum mechanics. George Mackey, Proceedings of the American Philosophical Society Symmetry has been the scientists’ pillar of fire, leading toward relativity and the standard model. Mario Livio, The Equation That Could Not Be Solved ­Definition and Notation In this chapter, we study certain groups of functions, called permutation groups, from a set A to itself. In the early and mid-19th century, groups of permutations were the only groups investigated by mathematicians. It was not until around 1850 that the notion of an abstract group was intro- duced by Cayley, and it took another quarter century before the idea firmly took hold. Definitions Permutation of A, Permutation Group of A A permutation of a set A is a function from A to A that is both one- to-one and onto. A permutation group of a set A is a set of permutations of A that forms a group under function composition. Although groups of permutations of any nonempty set A of objects exist, we will focus on the case where A is finite. Furthermore, it is customary, as well as convenient, to take A to be a set of the form {1, 2, 3,... , n} for some positive integer n. Unlike in calculus, where most functions are defined on infinite sets and are given by formulas, in algebra, permutations of finite sets are usually given by an explicit listing of each element of the domain and its corresponding functional value. For example, we define a permutation a of the set {1, 2, 3, 4} by specifying a(1) 5 2,    a(2) 5 3,    a(3) 5 1,    a(4) 5 4. 93 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 94 Groups A more convenient way to express this correspondence is to write a in array form as 1 2 3 4 a c d. 2 3 1 4 Here a( j) is placed directly below j for each j. Similarly, the permuta- tion b of the set {1, 2, 3, 4, 5, 6} given by b(1) 5 5,   b(2) 5 3,   b(3) 5 1,   b(4) 5 6,   b(5) 5 2,   b(6) 5 4 is expressed in array form as 1 2 3 4 5 6 b c d. 5 3 1 6 2 4 Composition of permutations expressed in array notation is carried out from right to left by going from top to bottom, then again from top to bottom. For example, let 1 2 3 4 5 s c d 2 4 3 5 1 and 1 2 3 4 5 g c d; 5 4 1 2 3 then 1 2 3 4 5 1 2 3 4 5 gs 5 £ 1 2 3 4 5 § £ § 5c d 4 2 1 3 5 5 4 1 2 3 2 4 3 5 1 On the right we have 4 under 1, since (gs)(1) 5 g(s(1)) 5 g(2) 5 4, so gs sends 1 to 4. The remainder of the bottom row gs is obtained in a similar fashion. We are now ready to give some examples of permutation groups. EXAMPLE 1 Symmetric Group S3 Let S3 denote the set of all one-to-one ­­ functions from {1, 2, 3} to itself. Then S3, under function composition, is a group with six elements. The six elements are 1 2 3 1 2 3 1 2 3 e c d ,    a  c d ,    a2  c d, 1 2 3 2 3 1 3 1 2 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 95 1 2 3 1 2 3 1 2 3 b c d ,    ab  c d ,    a2b  c d. 1 3 2 2 1 3 3 2 1 1 2 3 Note that ba 5 c d 5 a 2b 2 ab, so that S3 is non-Abelian. 3 2 1 The relation ba 5 a 2b can be used to compute other products in S3 without resorting to the arrays. For example, ba2 5 (ba)a 5 (a 2b)a 5 a 2(ba) 5 a 2(a 2b) 5 a 4b 5 ab. Example 1 can be generalized as follows. EXAMPLE 2 Symmetric Group Sn Let A 5 {1, 2,... , n}. The set of all permutations of A is called the symmetric group of degree n and is de- noted by Sn. Elements of Sn have the form 1 2 p n a c d. a(1) a(2) p a(n) It is easy to compute the order of Sn. There are n choices of a(1). Once a(1) has been determined, there are n 2 1 possibilities for a(2) [since a is one-to-one, we must have a(1) 2 a(2)]. After choosing a(2), there are exactly n 2 2 possibilities for a(3). Continuing along in this fashion, we see that Sn has n(n 2 1) ? ? ? 3 ? 2 ? 1 5 n! elements. We leave it to the reader to prove that Sn is non-Abelian when n $ 3 (Exercise 43).     The symmetric groups are rich in subgroups. The group S4 has 30 subgroups, and S5 has well over 100 subgroups. EXAMPLE 3 Symmetries of a Square As a third example, we ­associate each motion in D4 with the permutation of the locations of each of the four corners of a square. For example, if we label the four corner positions as in the figure below and keep these labels fixed for reference, we may describe a 90° ­counterclockwise rotation by the permutation 3 2 4 1 1 2 3 4 r c d, 2 3 4 1 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 96 Groups whereas a reflection across a horizontal axis yields 1 2 3 4 f c d. 2 1 4 3 These two elements generate the entire group (that is, every element is some combination of the r’s and f’s). When D4 is represented in this way, we see that it is a subgroup of S4.     Cycle Notation There is another notation commonly used to specify permutations. It is called cycle notation and was first introduced by the great French mathe­ matician Cauchy in 1815. Cycle notation has theoretical advantages in that certain important properties of the permutation can be readily deter- mined when cycle notation is used. As an illustration of cycle notation, let us consider the permu­tation 1 2 3 4 5 6 a c d. 2 1 4 6 5 3 This assignment of values could be presented schematically as follows. 1 3 5 α α α α 6 4 2 α α Although mathematically satisfactory, such diagrams are cumbersome. Instead, we leave out the arrows and simply write a 5 (1, 2) (3, 4, 6)(5). As a second example, consider 1 2 3 4 5 6 b c d. 5 3 1 6 2 4 In cycle notation, b can be written (2, 3, 1, 5)(6, 4) or (4, 6)(3, 1, 5, 2), since both of these unambiguously specify the function b. An expression of the form (a1, a2,... , am) is called a cycle of length m or an m-cycle. A multiplication of cycles can be introduced by thinking of a cycle as a permutation that fixes any symbol not appearing in the Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 97 cycle. Thus, the cycle (4, 6) can be thought of as representing the 1 2 3 4 5 6 permutation c d. In this way, we can multiply cycles 1 2 3 6 5 4 by thinking of them as permutations given in array form. Consider the following example from S8. Let a 5 (13)(27)(456)(8) and b 5 (1237)(648)(5). (When the domain consists of single-digit integers, it is common practice to omit the commas between the digits.) What is the cycle form of ab? Of course, one could say that ab 5 (13)(27)(456)(8)(1237)(648)(5), but it is usually more desirable to ex- press a permutation in a disjoint cycle form (that is, the various cycles have no number in common). Well, keeping in mind that function com- position is done from right to left and that each cycle that does not contain a symbol fixes the symbol, we observe that (5) fixes 1; (648) fixes 1; (1237) sends 1 to 2; (8) fixes 2; (456) fixes 2; (27) sends 2 to 7; and (13) fixes 7. So the net effect of ab is to send 1 to 7. Thus, we begin ab 5 (17 ? ? ?) ? ? ?. Now, repeating the entire process beginning with 7, we have, cycle by cycle, right to left, 7 → 7 → 7 → 1 → 1 → 1 → 1 → 3, so that ab 5 (173 ? ? ?) ? ? ?. Ultimately, we have ab 5 (1732)(48)(56). The important thing to bear in mind when multiplying cycles is to “keep moving” from one cycle to the next from right to left. (Warning: Some authors compose cycles from left to right. When reading another text, be sure to determine which convention is being used.) To be sure you understand how to switch from one notation to the other and how to multiply permutations, we will do one more example of each. If array notations for a and b, respectively, are 1 2 3 4 5 1 2 3 4 5 c d     and     c d, 2 1 3 5 4 5 4 1 2 3 then, in cycle notation, a 5 (12)(3)(45), b 5 (153)(24), and ab 5 (12)(3)(45)(153)(24). To put ab in disjoint cycle form, observe that (24) fixes 1; (153) sends 1 to 5; (45) sends 5 to 4; and (3) and (12) both fix 4. So, ab sends 1 to 4. Continuing in this way we obtain ab 5 (14)(253). One can convert ab back to array form without converting each cycle of ab into array form by simply observing that (14) means 1 goes to 4 and 4 goes to 1; (253) means 2 → 5, 5 → 3, 3 → 2. One final remark about cycle notation: Mathematicians prefer not to write cycles that have only one entry. In this case, it is understood that any Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 98 Groups missing element is mapped to itself. With this convention, the permutation a above can be written as (12)(45). Similarly, 1 2 3 4 5 a c d 3 2 4 1 5 can be written a 5 (134). Of course, the identity permutation consists only of cycles with one entry, so we cannot omit all of these! In this case, one usually writes just one cycle. For example, 1 2 3 4 5 e c d 1 2 3 4 5 can be written as e 5 (5) or e 5 (1). Just remember that missing e­ lements are mapped to themselves. Properties of Permutations We are now ready to state several theorems about permutations and ­cycles. The proof of the first theorem is implicit in our discussion of writing permutations in cycle form. Theorem 5.1 Products of Disjoint Cycles Every permutation of a finite set can be written as a cycle or as a product of disjoint cycles. PROOF Let a be a permutation on A 5 {1, 2,... , n}. To write a in ­disjoint cycle form, we start by choosing any member of A, say a1, and let a2 5 a(a1),    a3 5 a(a(a1)) 5 a 2(a1), and so on, until we arrive at a1 5 a m(a1) for some m. We know that such an m exists because the sequence a1, a(a1), a 2(a1), ? ? ? must be finite; so there must eventually be a repetition, say a i(a1) 5 a j(a1) for some i and j with i , j. Then a1 5 a m(a1), where m 5 j 2 i. We express this rela- tionship among a1, a2,... , am as a 5 (a1, a2,... , am) ? ? ?. The three dots at the end indicate the possibility that we may not have ex- hausted the set A in this process. In such a case, we merely choose any ele- ment b1 of A not appearing in the first cycle and proceed to create a new cycle as before. That is, we let b2 5 a(b1), b3 5 a2(b1), and so on, until we reach b1 5 a k(b1) for some k. This new cycle will have no elements in Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 99 common with the previously constructed cycle. For, if so, then a i(a1) 5 aj(b1) for some i and j. But then a i2j(a1) 5 b1, and therefore b1 5 at for some t. This contradicts the way b1 was chosen. Continuing this pro- cess until we run out of elements of A, our permutation will appear as a 5 (a1, a2,... , am)(b1, b2,... , bk) ? ? ? (c1, c2,... , cs). In this way, we see that every permutation can be written as a product of disjoint cycles.     Theorem 5.2 Disjoint Cycles Commute If the pair of cycles a 5 (a1, a2,... , am) and b 5 (b1,b2,... , bn ) have no entries in common, then ab 5 ba. PROOF For definiteness, let us say that a and b are permutations of the set S 5 {a1, a2,... , am, b1, b2,... , bn, c1, c2,... , ck}, where the c’s are the members of S left fixed by both a and b (there may not be any c’s). To prove that ab 5 ba, we must show that (ab)(x) 5 (ba)(x) for all x in S. If x is one of the a elements, say ai, then (ab)(ai) 5 a(b(ai)) 5 a(ai) 5 ai11, since b fixes all a elements. (We interpret ai11 as a1 if i 5 m.) For the same reason, (ba)(ai) 5 b(a(ai)) 5 b(ai11) 5 ai11. Hence, the functions of ab and ba agree on the a elements. A similar argument shows that ab and ba agree on the b elements as well. F ­ inally, suppose that x is a c element, say ci. Then, since both a and b fix c ele- ments, we have (ab)(ci) 5 a(b(ci)) 5 a(ci) 5 ci and (ba)(ci) 5 b(a(ci)) 5 b(ci) 5 ci. This completes the proof.     In demonstrating how to multiply cycles, we showed that the p­ roduct (13)(27)(456)(8)(1237)(648)(5) can be written in disjoint c­ ycle form as (1732)(48)(56). Is economy in expression the only advantage to writing a permutation in disjoint cycle form? No. The next theorem shows that the disjoint cycle form has the enormous advantage of ­allowing us to “eyeball” the order of the permutation. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 100 Groups Theorem 5.3 Order of a Permutation (Ruffini, 1799) The order of a permutation of a finite set written in disjoint cycle form is the least common multiple of the lengths of the cycles. PROOF First, observe that a cycle of length n has order n. (Verify this yourself.) Next, suppose that a and b are disjoint cycles of lengths m and n, and let k be the least common multiple of m and n. It follows from Theorem 4.1 that both ak and bk are the identity permutation e and, since a and b commute, (ab)k 5 a kb k is also the identity. Thus, we know by Corollary 2 to Theorem 4.1 (a k 5 e implies that |a| ­divides k) that the order of ab—let us call it t—must divide k. But then (ab)t 5 a tb t 5 e, so that a t 5 b 2t. However, it is clear that if a and b have no common symbol, the same is true for a t and b 2t, since raising a cycle to a power does not introduce new symbols. But, if a t and b 2t are equal and have no common symbol, they must both be the identity, because every symbol in a t is fixed by b 2t and vice versa (re- member that a symbol not a­ ppearing in a permutation is fixed by the permutation). It follows, then, that both m and n must divide t. This means that k, the least common multiple of m and n, divides t also. This shows that k 5 t. Thus far, we have proved that the theorem is true in the cases where the permutation is a single cycle or a product of two disjoint cycles. The general case involving more than two cycles can be handled in an analogous way. Theorem 5.3 is an powerful tool for calculating the orders of permu- tations and the number of permutations of a particular order. We demon- strate this in the next four examples. EXAMPLE 4 |(132)(45)| 5 6 |(1432)(56)| 5 4 |(123)(456)(78)| 5 6 |(123)(145)| 5 |14532| 5 5 Arranging all possible disjoint cycle structures of elements of Sn a­ ccording to the longest cycle lengths listed from left to right provides a systematic way of counting the number of elements in Sn of any particu- lar order. There are two cases: permutations where the lengths of the disjoint cycles (ignoring 1-cycles) are distinct and permutations where there are at least two disjoint cycles (ignoring 1-cycles) of the same length. The two cases are illustrated in Examples 5, 6, and 7. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 101 EXAMPLE 5 To determine the orders of the 7! 5 5040 elements of S7, we need only consider the possible disjoint cycle structures of the ­elements of S7. For convenience, we denote an n-cycle by (n). Then, arranging all possible disjoint cycle structures of elements of S7 ­according to longest cycle lengths left to right, we have (7) (6) (1) (5) (2) (5) (1) (1) (4) (3) (4) (2) (1) (4) (1) (1) (1) (3) (3) (1) (3) (2) (2) (3) (2) (1) (1) (3) (1) (1) (1) (1) (2) (2) (2) (1) (2) (2) (1) (1) (1) (2) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1). Now, from Theorem 5.3 we see that the orders of the elements of S7 are 7, 6, 10, 5, 12, 4, 3, 2, and 1. To do the same for the 10! 5 3628800 elements of S10 would be nearly as simple. EXAMPLE 6 We determine the number of elements in S7 of order 12. By Theorems 5.2 and 5.3, we need only count the number of permutations with disjoint cycle form (a1a2a3a4) (a5a6a7). First consider the cycle (a1a2a3a4). Although the number of ways to fill these slots is 7 ? 6 ? 5 ? 4, this product counts the cycle (a1a2a3a4) four times. For example, the 4-cycle (2741) can also be written as (7412), (4127), (1274) whereas the product 7 ? 6 ? 5 ? 4 counts them as distinct. Likewise, the 3 ? 2 ? 1 expressions for (a5a6a7) counts the cycles (a5a6a7), (a6a7a5) and (a7a5a6) as distinct even though they are equal in S7. Adjusting for these multiple countings, we have that there are (7 ? 6 ? 5 ? 4)(3 ? 2 ? 1)/(4 ? 3) 5 420 elements of order 12 in S7. EXAMPLE 7 We determine the number of elements in S7 of order 3. By Theorem 5.3, we need only count the number of permutations of the form (a1a2a3) and (a1a2a3)(a4a5a6). As in Example 6, there are (7 ? 6 ? 5)/3 5 70 elements of the form (a1a2a3). For elements of S7 of the form (a1a2a3) (a4a5a6) there are (7 ? 6 ? 5)/3 ways to create the first cycle and (4 ? 3 ? 2)/3 to create the second cycle but the product of (7 ? 6 ? 5)/3 and (4 ? Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 102 Groups 3 ? 2)/3) counts (a1a2a3) (a4a5a6) and (a4a5a6)(a3a2a1) as distinct when they are equal group elements. Thus, the number of elements in S7 of the form (a1a2a3) (a4a5a6) is (7 ? 6 ? 5)(4 ? 3 ? 2)/(3 ? 3 ? 2) 5 280. This gives us 350 elements of order 3 in S7. To count the number of elements in S7 of the form say (a1a2)(a3a4) (a5a6), we proceed as before to obtain (7 ? 6)(5 ? 4)(3 ? 2)/(2 ? 2 ? 2 ? 3!) 5 105. The 3! term in the denominator appears because there are 3! ways the product of three 2-cycles can be written and each represents the same group element. As we will soon see, it is often greatly advantageous to write a per- mutation as a product of cycles of length 2—that is, as permutations of the form (ab) where a 2 b. Many authors call these permutations trans- positions, since the effect of (ab) is to interchange or transpose a and b. Example 8 and Theorem 5.4 show how this can always be done. EXAMPLE 8 (12345) 5 (15)(14)(13)(12) (1632)(457) 5 (12)(13)(16)(47)(45) Theorem 5.4 Product of 2-Cycles Every permutation in Sn, n. 1, is a product of 2-cycles. PROOF First, note that the identity can be expressed as (12)(12), and so it is a product of 2-cycles. By Theorem 5.1, we know that every permuta- tion can be written in the form (a1a2 ? ? ? ak)(b1b2 ? ? ? bt) ? ? ? (c1c2 ? ? ? cs). A direct computation shows that this is the same as (a1ak)(a1ak21) ? ? ? (a1a2)(b1bt)(b1bt21) ? ? ? (b1b2) ? ? ? (c1cs)(c1cs21) ? ? ? (c1c2). This completes the proof.     The decomposition of a permutation into a product of 2-cycles given in Example 8 and in the proof of Theorem 5.4 is not the only way a per- mutation can be written as a product of 2-cycles. Although the next ­example shows that even the number of 2-cycles may vary from one de- composition to another, we will prove in Theorem 5.5 (first proved by Cauchy) that there is one aspect of a decomposition that never varies. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 103 EXAMPLE 9 (12345) 5 (54)(53)(52)(51) (12345) 5 (54)(52)(21)(25)(23)(13) We isolate a special case of Theorem 5.5 as a lemma. Lemma   If e 5 b1b2 ? ? ? br , where the b’s are 2-cycles, then r is even. PROOF Clearly, r 2 1, since a 2-cycle is not the identity. If r 5 2, we are done. So, we suppose that r. 2, and we proceed by induction. Suppose that the rightmost 2-cycle is (ab). Then, since (ij) 5 ( ji), the product br21br can be expressed in one of the following forms shown on the right: e 5 (ab)(ab), (ab)(bc) 5 (ac)(ab), (ac)(cb ) 5 (bc)(ab), (ab)(cd) 5 (cd)(ab). If the first case occurs, we may delete br21br from the original product to obtain e 5 b1b2 ? ? ? br22, and therefore, by the Second Principle of Mathematical Induction, r 2 2 is even. In the other three cases, we ­replace the form of br21br on the right by its counterpart on the left to obtain a new product of r 2-cycles that is still the identity, but where the rightmost occur- rence of the integer a is in the second-from-the-rightmost 2-cycle of the product instead of the rightmost 2-cycle. We now repeat the procedure just described with br22br21, and, as be­fore, we obtain a product of (r 2 2) 2-cycles equal to the identity or a new p­ roduct of r 2-cycles, where the rightmost occurrence of a is in the third 2-cycle from the right. Continuing this process, we must ob­tain a product of (r 2 2) 2-cycles equal to the iden- tity, because otherwise we have a product equal to the identity in which the only occurrence of the integer a is in the leftmost 2-cycle, and such a prod- uct does not fix a, whereas the identity does. Hence, by the Second Principle of Mathematical Induction, r 2 2 is even, and r is even as well.     Theorem 5.5 Always Even or Always Odd If a permutation a can be expressed as a product of an even (odd) number of 2-cycles, then every decomposition of a into a product of 2-cycles must have an even (odd) number of 2-cycles. In symbols, if a 5 b1b2 ? ? ? br    and    a 5 g1g2 ? ? ? gs , where the b’s and the g’s are 2-cycles, then r and s are both even or both odd. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 104 Groups PROOF Observe that b1b2 ? ? ? br 5 g1g2 ? ? ? gs implies e 5 g1g2 ? ? ? gsbr 21 ? ? ? b221b121     5 g1g2 ? ? ? gsbr ? ? ? b2b1, since a 2-cycle is its own inverse. Thus, the lemma on page 103 guarantees that s 1 r is even. It follows that r and s are both even or both odd. Definition Even and Odd Permutations A permutation that can be expressed as a product of an even number of 2-cycles is called an even permutation. A permutation that can be ­expressed as a product of an odd number of 2-cycles is called an odd permutation. Theorems 5.4 and 5.5 together show that every permutation can be unambiguously classified as either even or odd. The significance of this observation is given in Theorem 5.6. Theorem 5.6 Even Permutations Form a Group The set of even permutations in Sn forms a subgroup of Sn. PROOF This proof is left to the reader (Exercise 17).     The subgroup of even permutations in Sn arises so often that we give it a special name and notation. Definition Alternating Group of Degree n The group of even permutations of n symbols is denoted by An and is called the alternating group of degree n. The next result shows that exactly half of the elements of Sn (n. 1) are even permutations. Theorem 5.7 For n. 1, An has order n!/2. PROOF For each odd permutation a, the permutation (12)a is even and, by the cancellation property in groups, (12)a 2 (12)b when a 2 b. Thus, there are at least as many even permutations as there are odd ones. On the other hand, for each even permutation a, the permutation (12)a is odd and (12)a 2 (12)b when a 2 b. Thus, there are at least as many odd permutations as there are even ones. It follows that there are Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  5 | Permutation Groups 105 equal numbers of even and odd permutations. Since |Sn| 5 n!, we have |An| 5 n!/2. The names for the symmetric group and the alternating group of ­degree n come from the study of polynomials over n variables. A symmetric poly- nomial in the variables x1, x2,... , xn is one that is u­ nchanged under any transposition of two of the variables. An alternating polynomial is one that changes signs under any transposition of two of the variables. For exam- ple, the polynomial x1 x2 x3 is unchanged by any transposition of two of the three variables, whereas the polynomial (x12x2)(x12x3)(x22x3) changes signs when any two of the variables are transposed. Since every member of the symmetric group is the product of transpositions, the symmetric polynomials are those that are unchanged by members of the symmetric group. Likewise, since any member of the alternating group is the product of an even number of transpositions, the alternating polynomials are those that are unchanged by members of the alternating group. The alternating groups are among the most important examples of groups. The groups A4 and A5 will arise on several occasions in later chapters. In particular, A5 has great historical significance. A geometric interpretation of A4 is given in Example 10, and a multi- plication table for A4 is given as Table 5.1. EXAMPLE 10 Rotations of a Tetrahedron The 12 rotations of a regular tetrahedron can be conveniently described with the e­ lements of A4. The top row of Figure 5.1 illustrates the identity and three 180° “edge” rotations about axes joining midpoints of two Table 5.1 The Alternating Group A4 of Even Permutations of {1, 2, 3, 4} (In this table, the permutations of A4 are designated as a1, a2,... , a12 and an entry k inside the table represents ak. For example, a3 a8 5 a6.) a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 (1) 5 a1 1 2 3 4 5 6 7 8 9 10 11 12 (12)(34) 5 a2 2 1 4 3 6 5 8 7 10 9 12 11 (13)(24) 5 a3 3 4 1 2 7 8 5 6 11 12 9 10 (14)(23) 5 a4 4 3 2 1 8 7 6 5 12 11 10 9 (123) 5 a5 5 8 6 7 9 12 10 11 1 4 2 3 (243) 5 a6 6 7 5 8 10 11 9 12 2 3 1 4 (142) 5 a7 7 6 8 5 11 10 12 9 3 2 4 1 (134) 5 a8 8 5 7 6 12 9 11 10 4 1 3 2 (132) 5 a9 9 11 12 10 1 3 4 2 5 7 8 6 (143) 5 a10 10 12 11 9 2 4 3 1 6 8 7 5 (234) 5 a11 11 9 10 12 3 1 2 4 7 5 6 8 (124) 5 a12 12 10 9 11 4 2 1 3 8 6 5 7 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 Isomorphisms Mathematics is the art of giving the same name to different things. Henri Poincaré (1854–1912) The basis for poetry and scientific discovery is the ability to ­comprehend the unlike in the like and the like in the unlike. Jacob Bronowski Motivation Suppose an American and a German are asked to count a handful of ob- jects. The American says, “One, two, three, four, five,... ,” whereas the German says, “Eins, zwei, drei, vier, fünf,....” Are the two doing different things? No. They are both counting the objects, but they are using different terminology to do so. Similarly, when one person says, “Two plus three is five” and another says, “Zwei und drei ist fünf,” the two are in agreement on the concept they are describing, but they are using different terminology to describe the concept. An analogous situation often occurs with groups; the same group is described with different terminology. We have seen two examples of this so far. In Chapter 1, we described the symmetries of a square in geometric terms (e.g., R90), whereas in Chapter 5 we described the same group by way of permutations of the corners. In both cases, the underlying group was the symmetries of a square. In Chapter 4, we ob- served that when we have a cyclic group of order n generated by a, the op- eration turns out to be essentially that of addition modulo n, since aras 5 ak, where k 5 (r 1 s) mod n. For example, each of U(43) and U(49) is cyclic of order 42. So, each has the form kal, where aras 5 a (r 1 s)mod 42. Definition and Examples In this chapter, we give a formal method for determining whether two groups defined in different terms are really the same. When this is the case, we say that there is an isomorphism between the two groups. This notion was first introduced by Galois about 180 years ago. The term isomorphism is derived from the Greek words isos, meaning “same” or “equal,” and 120 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 121 morphe, meaning “form.” R. Allenby has colorfully ­defined an algebraist as “a person who can’t tell the difference between isomorphic systems.” Definition Group Isomorphism An isomorphism f from a group G to a group G is a one-to-one mapping (or function) from G onto G that preserves the group operation. That is, f(ab) 5 f(a)f(b)    for all a, b in G. If there is an isomorphism from G onto G, we say that G and G are ­isomorphic and write G < G. The definition of isomorphism ensures that if f is an isomorphism from G to G then the operation table for G can be obtained from the opera- tion table for G be replacing each entry in the table for G by f(x). See Figure 6.1. Thus the groups differ in notation only. G 2 2 2 b 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 a 2 2 2 ab 2 2 2 2 2 2 2 2 2 G 2 2 2 f(b) 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 f(a) 2 2 2 f(ab) 2 2 2 2 2 2 2 2 2 Figure 6.1 It is implicit in the definition of isomorphism that isomorphic groups have the same order. It is also implicit in the definition of isomorphism that the operation on the left side of the equal sign is that of G, whereas the operation on the right side is that of G. The four cases involving ? and 1 are shown in Table 6.1. Table 6.1 G Operation G Operation Operation Preservation ? ? f(a ? b) 5 f(a) ? f(b) ? 1 f(a ? b) 5 f(a) 1 f(b) 1 ? f(a 1 b) 5 f(a) ? f(b) 1 1 f(a 1 b) 5 f(a) 1 f(b) There are four separate steps involved in proving that a group G is isomorphic to a group G. Step 1 “Mapping.” Define a candidate for the isomorphism; that is, ­define a function f from G to G. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 122 Groups Step 2 “1–1.” Prove that f is one-to-one; that is, assume that f(a) 5 f(b) and prove that a 5 b. Step 3 “Onto.” Prove that f is onto; that is, for any element g in G, find an element g in G such that f(g) 5 g. Step 4 “O.P.” Prove that f is operation-preserving; that is, show that f(ab) 5 f(a)f(b) for all a and b in G. None of these steps is unfamiliar to you. The only one that may appear novel is the fourth one. It requires that one be able to obtain the same result by combining two elements and then mapping, or by mapping two ele- ments and then combining them. Roughly speaking, this says that the two processes—operating and mapping—can be done in either order without affecting the result. This same concept arises in calculus when we say lim 1f 1x2. g1x2 2  xSa lim f 1x2 xSa lim g1x2 xSa or b b b  1f  g2 dx   f dx   g dx. a a a In linear algebra an invertible linear transformation from a vector space V to a vector space W is a group isomorphism from V to W. (Every vector space is an Abelian group under vector addition). Before going any further, let’s consider some examples. EXAMPLE 1 Let G be the real numbers under addition and let G be the positive real numbers under multiplication. Then G and G are isomor- phic under the mapping f(x) 5 2x. Certainly, f is a function from G to G. To prove that it is one-to-one, suppose that 2x 5 2y. Then log2 2x 5 log2 2y, and therefore x 5 y. For “onto,” we must find for any positive real number y some real number x such that f(x) 5 y; that is, 2x 5 y. Well, solving for x gives log2 y. Finally, f(x 1 y) 5 2x1y 5 2x ? 2y 5 f(x)f(y) for all x and y in G, so that f is operation-preserving as well. EXAMPLE 2 Any infinite cyclic group is isomorphic to Z. Indeed, if a is a generator of the cyclic group, the mapping ak → k is an isomorphism. Any ­finite cyclic group kal of order n is isomorphic to Zn under the mapping ak → k mod n. That these correspondences are functions and are one-to-one is the ­essence of Theorem 4.1. Obviously, the mappings are onto. That the map- pings are operation-preserving ­follows from Exercise 9 in Chapter 0 in the finite case and from the ­definitions in the infinite case. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 123 EXAMPLE 3 The mapping from R under addition to itself given by f(x) 5 x3 is not an isomorphism. Although f is one-to-one and onto, it is not operation-preserving, since it is not true that (x 1 y)3 5 x3 1 y3 for all x and y. EXAMPLE 4 U(10) < Z4 and U(5) < Z4. To verify this, one need only observe that both U(10) and U(5) are cyclic of order 4. Then appeal to Example 2. EXAMPLE 5 There is no isomorphism from Q, the group of rational numbers under addition, to Q*, the group of nonzero rational numbers under multiplication. If f were such a mapping, there would be a ra- tional number a such that f(a) 5 21. But then 21 5 f(a) 5 f( 12a 1 12a) 5 f( 12a)f( 12a) 5 [f( 12a)]2. However, no rational number squared is 21. EXAMPLE 6 Let G 5 SL(2, R), the group of 2 3 2 real matrices with determinant 1. Let M be any 2 3 2 real matrix with determinant 1. Then we can define a mapping from G to G itself by fM(A) 5 MAM21 for all A in G. To verify that fM is an isomorphism, we carry out the four steps. Step 1 fM is a function from G to G. Here, we must show that fM(A) is indeed an element of G whenever A is. This follows from properties of determinants: det (MAM21) 5 (det M)(det A)(det M)21 5 1 ? 1 ? 121 5 1. Thus, MAM21 is in G. Step 2 fM is one-to-one. Suppose that fM(A) 5 fM(B). Then MAM21 5 MBM21 and, by left and right cancellation, A 5 B. Step 3 fM is onto. Let B belong to G. We must find a matrix A in G such that fM(A) 5 B. How shall we do this? If such a matrix A is to ­exist, it must have the property that MAM21 5 B. But this tells us ex- actly what A must be! For we can solve for A to obtain A 5 M21BM and ­verify that fM(A) 5 MAM21 5 M(M21BM)M21 5 B. Step 4 fM is operation-preserving. Let A and B belong to G. Then, fM(AB) 5 M(AB)M21 5 MA(M21M)BM21 5 (MAM21)(MBM21) 5 fM(A)fM(B). The mapping fM is called conjugation by M. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 124 Groups Cayley’s Theorem Our first theorem is a classic result of Cayley. An important generaliza- tion of it will be given in Chapter 25. Theorem 6.1 Cayley’s Theorem (1854) Every group is isomorphic to a group of permutations. PROOF To prove this, let G be any group. We must find a group G of per- mutations that we believe is isomorphic to G. Since G is all we have to work with, we will have to use it to construct G. For any g in G, ­define a function Tg from G to G by Tg(x) 5 gx    for all x in G. (In words, Tg is just multiplication by g on the left.) We leave it as an exercise (Exercise 35) to prove that Tg is a permutation on the set of ­elements of G. Now, let G 5 {Tg | g [ G}. Then, G is a group under the operation of function composition. To verify this, we first observe that for any g and h in G we have TgTh(x) 5 Tg(Th(x)) 5 Tg(hx) 5 g(hx) 5 (gh)x 5 Tgh(x), so that TgTh 5 Tgh. From this it follows that Te is the iden- tity and (Tg)21 5 Tg21 (see Exercise 9). Since function composition is associative, we have verified all the conditions for G to be a group. The isomorphism f between G and G is now ready-made. For every g in G, define f(g) 5 Tg. If Tg 5 Th, then Tg(e) 5 Th(e) or ge 5 he. Thus, g 5 h and f is one-to-one. By the way G was constructed, we see that f is onto. The only condition that remains to be checked is that f is ­operation-preserving. To this end, let a and b belong to G. Then f(ab) 5 Tab 5 TaTb 5 f(a)f(b). The group G constructed previously is called the left regular repre- sentation of G. EXAMPLE 7 For concreteness, let us calculate the left regular repre- sentation U1122 for U(12) 5 {1, 5, 7, 11}. Writing the permutations of U(12) in array form, we have (remember, Tx is just multiplication by x) 1 5 7 11 1 5 7 11 T1  c d ,    T5  c d, 1 5 7 11 5 1 11 7 1 5 7 11 1 5 7 11 T7  c d ,    T11  c d. 7 11 1 5 11 7 5 1 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 125 It is instructive to compare the Cayley tables for U(12) and its left regu- lar representation U1122. U(12) 1 5 7 11 U1122 T1 T5 T7 T11 1 1 5 7 11 T1 T1 T5 T7 T11 5 5 1 11 7 T5 T5 T1 T11 T7 7 7 11 1 5 T7 T7 T11 T1 T5 11 11 7 5 1 T11 T11 T7 T5 T1 It should be abundantly clear from these tables that U(12) and U1122 are only notationally different. EXAMPLE 8 Writing the left regular representations for the permuta- tions TR and TH from D4 in disjoint cycle form we have (see the 270 Cayley table in Chapter 1) TR270  1R0R270 2 1R90R0 2 1HD2 1VD2 TH  1R0H2 1R90D2 1R180V2 1R270D2 Cayley’s Theorem is important for two contrasting reasons. One is that it allows us to represent an abstract group in a concrete way. A sec- ond is that it shows that the present-day set of axioms we have adopted for a group is the correct abstraction of its much earlier predecessor—a group of permutations. Indeed, Cayley’s Theorem tells us that abstract groups are not different from permutation groups. Rather, it is the view- point that is different. It is this difference of viewpoint that has stimu- lated the tremendous progress in group theory and many other branches of mathematics in the past 100 years. It is sometimes very difficult to prove or disprove, whichever the case may be, that two particular groups are isomorphic. For example, it re- quires somewhat sophisticated techniques to prove the surprising fact that the group of real numbers under addition is isomorphic to the group of complex numbers under addition. Likewise, it is not easy to prove the fact that the group of nonzero complex numbers under multiplication is isomorphic to the group of complex numbers with absolute value of 1 under multiplication. In geometric terms, this says that, as groups, the punctured plane and the unit circle are isomorphic.  Properties of Isomorphisms Our next two theorems give a catalog of properties of isomorphisms and isomorphic groups. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 126 Groups Theorem 6.2 Properties of Isomorphisms Acting on Elements Suppose that f is an isomorphism from a group G onto a group G. Then 1. f carries the identity of G to the identity of G. 2. For every integer n and for every group element a in G, f(an) 5 [f(a)]n. 3. For any elements a and b in G, a and b commute if and only if f(a) and f(b) commute. 4. G 5 kal if and only if G 5 kf(a)l. 5. |a| 5 |f(a)| for all a in G (isomorphisms preserve orders). 6. For a fixed integer k and a fixed group element b in G, the ­equation xk 5 b has the same number of solutions in G as does the equation xk 5 f(b) in G. 7. If G is finite, then G and G have exactly the same number of ­elements of every order. PROOF We will restrict ourselves to proving only properties 1, 2, and 4, but observe that property 5 follows from properties 1 and 2, property 6 fol- lows from property 2, and property 7 follows from property 5. For conve- nience, let us denote the identity in G by e and the identity in G by e. Then, since e 5 ee, we have f(e) 5 f(ee) 5 f(e)f(e). Also, because f(e) [ G, we have f(e) 5 ef (e), as well. Thus, by can- cellation, e 5 f(e). This proves property 1. For positive integers, property 2 follows from the definition of an isomorphism and mathematical induction. If n is negative, then 2n is positive, and we have from property 1 and the observation about the positive integer case that e 5 f(e) 5 f(g ng 2n) 5 f(g n)f(g 2n) 5 f(gn)(f(g))2n. Thus, multiplying both sides on the right by (f(g))n, we have (f(g))n 5 f(gn). Property 1 takes care of the case n 5 0. To prove property 4, let G 5 kal and note that, by closure, kf(a)l # G. Because f is onto, for any element b in G, there is an element ak in G such that f(a k) 5 b. Thus, b 5 (f(a)) k and so b [ kf(a)l. This proves that G 5 kf(a)l. Now suppose that G 5 kf(a)l. Clearly, kal # G. For any element b in G, we have f(b) [ kf(a)l. So, for some integer k we have f(b) 5 (f(a))k 5 f(ak). Because f is one-to-one, b 5 ak. This proves that kal 5 G. When the group operation is addition, property 2 of Theorem 6.2 is f(na) 5 nf(a); property 4 says that an isomorphism between two cyclic groups takes a generator to a generator. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 127 Theorem 6.3 Properties of Isomorphisms Acting on Groups Suppose that f is an isomorphism from a group G onto a group G. Then 1. f21 is an isomorphism from G onto G. 2. G is Abelian if and only if G is Abelian. 3. G is cyclic if and only if G is cyclic. 4. If K is a subgroup of G, then f(K) 5 {f(k) | k [ K} is a ­subgroup of G. 5. If K is a subgroup of G, then f21 (K) 5 {g [ G | f(g) [ K} is a subgroup of G. 6. f(Z(G)) 5 Z(G). PROOF Properties 1 and 4 are left as exercises (Exercises 33 and 34). Properties 2 and 6 are a direct consequence of property 3 of Theorem 6.2. Property 3 follows from property 4 of Theorem 6.2 and property 1 of Theorem 6.3. Property 5 follows from properties 1 and 4. Theorems 6.2 and 6.3 provide several convenient ways to prove that groups G and G are not isomorphic. 1. Observe that 0 G 0 ? 0 G 0. 2. Observe that G or G is cyclic and the other is not. 3. Observe that G or G is Abelian and the other is not. 4. Show that largest order of any element in G is not the same as the largest order of any element in G. 5. Show that the number of elements of some specific order in G (the smallest order greater than 1 is often the good choice) is not the same as the number of elements of that order in G. EXAMPLE 9 Consider these three groups of order 12: Z12, D6 and A4. A quick check shows that the largest order of any element in the three are 12, 6 and 3, respectively. So no two are isomorphic. Alternatively, the number of elements of order 2 in each is 1, 7, and 3.  EXAMPLE 10 The group Q of rational numbers under addition is not isomorphic to the group Q* of nonzero rational numbers under multipli- cation because every non-identity element of Q has infinite order (be- cause nx 5 0 if and only if n 5 0) or x 5 0 whereas in Q*, 0 1 0 5 2. Theorems 6.2 and 6.3 show that isomorphic groups have many prop- erties in common. Actually, the definition is precisely formulated so that isomorphic groups have all group theoretic properties in common. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 128 Groups By this we mean that if two groups are isomorphic, then any property that can be expressed in the language of group theory is true for one if and only if it is true for the other. This is why algebraists speak of iso- morphic groups as “equal” or “the same.” Admittedly, calling such groups equivalent, rather than the same, might be more appropriate, but we bow to long-standing tradition. Automorphisms Certain kinds of isomorphisms are referred to so often that they have been given special names. Definition Automorphism An isomorphism from a group G onto itself is called an automorphism of G. The isomorphism in Example 6 is an automorphism of SL(2, R). Two more examples follow. EXAMPLE 11 The function f from C to C given by f(a 1 bi) 5 a 2 bi is an automorphism of the group of complex numbers under ­addition. The restriction of f to C* is also an automorphism of the group of nonzero complex numbers under multiplication. (See­ Exercise 37.) EXAMPLE 12 Let R2 5 {(a, b) | a, b [ R}. Then f(a, b) 5 (b, a) is an automorphism of the group R2 under componentwise addition. Geo- metrically, f reflects each point in the plane across the line y 5 x. More generally, any reflection across a line passing through the ­origin or any rotation of the plane about the origin is an automorphism of R2. The isomorphism in Example 6 is a particular instance of an auto- morphism that arises often enough to warrant a name and notation of its own. Definition Inner Automorphism Induced by a Let G be a group, and let a [ G. The function fa defined by fa(x) 5 axa21 for all x in G is called the inner automorphism of G induced by a. We leave it for the reader to show that fa is actually an automor- phism of G. (Use Example 6 as a model.) EXAMPLE 13 The action of the inner automorphism of D4 induced by R90 is given in the following table. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 129 fR90 x → R 90 x R 90–1 R0 → R90R0R 90–1 5 R0 R90 → R90R90R 9021 5 R90 R180 → R90R180R 9021 5 R180 R270 → R90R270R 9021 5 R270 H → R90HR 9021 5 V V → R90VR 9021 5 H D → R90DR 9021 5 D9 D9 → R90D9R 9021 5 D When G is a group, we use Aut(G) to denote the set of all auto- morphisms of G and Inn(G) to denote the set of all inner automorphisms of G. The reason these sets are noteworthy is demonstrated by the next theorem. Theorem 6.4 Aut(G) and Inn(G) Are Groups† The set of automorphisms of a group and the set of inner automorphisms of a group are both groups under the operation of function composition. PROOF The proof of Theorem 6.4 is left as an exercise (Exercise 17).      The determination of Inn(G) is routine. If G 5 {e, a, b, c....}, then Inn(G) 5 {fe, fa, fb, fc,...}. This latter list may have duplications, however, since fa may be equal to fb even though a 2 b (see Exercise 45). Thus, the only work involved in determining Inn(G) is deciding which distinct elements give the distinct automorphisms. On the other hand, the determination of Aut(G) is, in general, quite involved. EXAMPLE 14 Inn(D4) To determine Inn(D4), we first observe that the complete list of inner auto- morphisms is fR0, fR90, fR180, fR270, fH, fV, fD, and fD9. Our job is to de- termine the repetitions in this list. Since R180 [ Z(D4), we have fR180(x) 5 R180 xR18021 5 x, so that fR180 5 fR0. Also, fR270(x) 5 R270 xR27021 5 R90R180 xR18021R9021 5 R90 xR9021 5 fR90(x). Similarly, since H 5 R180V and D9 5 R180D, we have fH 5 fV and fD 5 fD9. This proves that the †Thegroup Aut(G) was first studied by O. Hölder in 1893 and, independently, by E. H. Moore in 1894. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 130 Groups previous list can be pared down to fR0, fR90, fH, and fD. We leave it to the reader to show that these are distinct ­(Exercise 15). EXAMPLE 15 Aut(Z10) To compute Aut(Z10), we try to discover enough information about an element a of Aut(Z10) to determine how a must be defined. Because Z10 is so simple, this is not difficult to do. To begin with, observe that once we know a(1), we know a(k) for any k, because a(k) 5 a(1 1 1 1 ? ? ? 1 1) k terms 5 a(1) 1 a(1) 1 ? ? ? 1 a(1) 5 ka(1). k terms So, we need only determine the choices for a(1) that make a an ­automorphism of Z10. Since property 5 of Theorem 6.2 tells us that |a(1)| 5 10, there are four candidates for a(1): a(1) 5 1,    a(1) 5 3,    a(1) 5 7,    a(1) 5 9. To distinguish among the four possibilities, we refine our notation by denoting the mapping that sends 1 to 1 by a 1, 1 to 3 by a 3, 1 to 7 by a 7, and 1 to 9 by a 9. So the only possibilities for Aut(Z10) are a 1, a 3, a 7, and a 9. But are all these automorphisms? Clearly, a1 is the identity. Let us check a3. Since x mod 10 5 y mod 10 implies 3x mod 10 5 3y mod 10, a3 is well defined. Moreover, because a3 112  3 is a generator of Z10, it follows that a 3 is onto (and, by Exercise 12 in Chapter 5, it is also one-to-one). Finally, since a 3(a 1 b) 5 3(a 1 b) 5 3a 1 3b 5 a 3(a) 1 a 3(b), we see that a 3 is operation-preserving as well. Thus, a 3 [ Aut(Z 10 ). The same argument shows that a 7 and a 9 are also ­automorphisms. This gives us the elements of Aut(Z 10) but not the structure. For ­instance, what is a3a3? Well, (a3a3)(1) 5 a3(3) 5 3 ? 3 5 9 5 a9(1), so a3a3 5 a 9. Similar calculations show that a33 5 a 7 and a34 5 a1, so that |a3| 5 4. Thus, Aut(Z10 ) is cyclic. Actually, the following Cayley tables reveal that Aut(Z10 ) is isomorphic to U(10). U(10) 1 3 7 9 Aut(Z10) a1 a3 a7 a9 1 1 3 7 9 a1 a1 a3 a7 a9 3 3 9 1 7 a3 a3 a9 a1 a7 7 7 1 9 3 a7 a7 a1 a9 a3 9 9 7 3 1 a9 a9 a7 a3 a1 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  6 | Isomorphisms 131 With Example 15 as a guide, we are now ready to tackle the group Aut(Zn). The result is particularly nice, since it relates the two kinds of groups we have most frequently encountered thus far—the cyclic groups Zn and the U-groups U(n). Theorem 6.5 Aut(Zn) < U(n) For every positive integer n, Aut(Zn) is isomorphic to U(n). PROOF As in Example 15, any automorphism a is determined by the value of a(1), and a(1) [ U(n). Now consider the correspondence from Aut(Zn) to U(n) given by T: a → a(1). The fact that a(k) 5 ka(1) (see Example 13) implies that T is a one-to-one mapping. For if a and b be- long to Aut(Zn) and a(1) 5 b(1), then a(k) 5 ka(1) 5 kb(1) 5 b(k) for all k in Zn, and therefore a 5 b. To prove that T is onto, let r [ U(n) and consider the mapping a from Zn to Zn defined by a(s) 5 sr (mod n) for all s in Zn. We leave it as an exercise to verify that a is an automorphism of Zn (see Exercise 29). Then, since T(a) 5 a(1) 5 r, T is onto U(n). Finally, we establish the fact that T is operation-preserving. Let a, b [ Aut(Zn). We then have T(ab) 5 (ab)(1) 5 a(b(1)) 5 a(1 1 1 1 ? ? ? 1 1) b(1) 5 a(1) 1 a(1) 1 ? ? ? 1 a(1) 5 a(1)b(1) b(1) 5 T(a)T(b). This completes the proof. The next example shows how inner automorphisms of a group provide a convenient way to create multiple isomorphic subgroups of the group. EXAMPLE 16 Given the subgroup of S4 H  5 112, 112342, 1132 1242, 114322, 1122 1342, 1242, 1142 1232, 11326 we have the subgroups 1122H1212  5 112, 113422, 1142 1232, 112342, 1122 1342, 1142, 1132 1242, 12326 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 132 Groups and 11232H13212  5 112, 114232, 1122 1342, 113242, 1142 1232, 1342, 1132 1242, 11226 of S4 that are isomorphic to H. Exercises Being a mathematician is a bit like being a manic depressive: you spend your life alternating between giddy elation and black despair. Steven G. Krantz, A Primer of Mathematical Writing  1. Find an isomorphism from the group of integers under addition to the group of even integers under addition.  2. Find Aut(Z).  3. Let R1 be the group of positive real numbers under multiplication. Show that the mapping f(x) 5 2x is an automorphism of R1.  4. Show that U(8) is not isomorphic to U(10).  5. Show that U(8) is isomorphic to U(12).  6. Prove that isomorphism is an equivalence relation. That is, for any groups G, H, and K G < G; G < H implies H < G G < H and H < K implies G < K.  7. Prove that S4 is not isomorphic to D12.  8. Show that the mapping a → log10 a is an isomorphism from R+ ­under multiplication to R under addition.  9. In the notation of Theorem 6.1, prove that Te is the identity and that (Tg)21 5 Tg. 21 10. Given that f is a isomorphism from a group G under addition to a group G under addition, convert property 2 of Theorem 6.2 to addi- tive notation. 11. Let G be a group under multiplication, G be a group under addition and f be an isomorphism from G to G. If f1a2  a and f1b2  b, find an expression for f1a3b 2 2 in terms of a and b. 12. Let G be a group. Prove that the mapping a(g) 5 g21 for all g in G is an automorphism if and only if G is Abelian. 13. If g and h are elements from a group, prove that fgfh 5 fgh. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  7 Cosets and Lagrange’s Theorem It might be difficult, at this point, for students to see the extreme importance of this result [Lagrange’s Theorem]. As we penetrate the subject more deeply they will become more and more aware of its basic character. I. N. Herstein, Topics in Algebra Lagrange’s theorem is extremely important and justly famous in group theory. Norman J. Block, Abstract Algebra with Applications Properties of Cosets In this chapter, we will prove the single most important theorem in finite group theory—Lagrange’s Theorem. In his book on abstract algebra, I. N. Herstein likened it to the ABC’s for finite groups. But first we in- troduce a new and powerful tool for analyzing a group—the notion of a coset. This notion was invented by Galois in 1830, although the term was coined by G. A. Miller in 1910. Definition Coset of H in G Let G be a group and let H be a nonempty subset of G. For any a [ G, the set {ah | h [ H} is denoted by aH. Analogously, Ha 5 {ha | h [ H} and aHa21 5 {aha21 | h [ H}. When H is a subgroup of G, the set aH is called the left coset of H in G containing a, whereas Ha is called the right coset of H in G containing a. In this case, the element a is called the coset ­representative of aH (or Ha). We use |aH| to denote the number of ele- ments in the set aH, and |Ha| to denote the number of elements in Ha. EXAMPLE 1 Let G 5 S3 and H 5 {(1), (13)}. Then the left cosets of H in G are (1)H 5 H, (12)H 5 {(12), (12)(13)} 5 {(12), (132)} 5 (132)H, (13)H 5 {(13), (1)} 5 H, 138 (23)H 5 {(23), (23)(13)} 5 {(23), (123)} 5 (123)H. Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.  7 | Cosets and Lagrange’s Theorem 139 EXAMPLE 2 Let _ 5 {R0, R180} in D4, the dihedral group of order 8. Then, R0_ 5 _, R90_ 5 {R90, R270} 5 R270_, R180_ 5 {R180, R0} 5 _,