Section 8: Symmetric Groups

MAT-314 Section 8: Symmetric Groups

1. Abstract Algebra, Saracino Second Edition Section 8 Symmetric Groups and Alternating Groups

2. Definitions and Examples (1 of 2) Let be a nonempty set, then a one-to-one and onto mapping is called a permutation of . The set of all such mappings forms a group under composition of functions. The group is called the symmetric group , or permutation group on . If the set is finite and has, say elements, we can represent by the set , and we denote by . In this case, is called the symmetric group of degree , or the symmetric group on letters . Let , then simply rearranges the elements of .  

3. Definitions and Examples (2 of 2) We can write explicitly in the form: Let us consider the group . What are the possible permutations of the set ? The first three are obtained by cyclically permuting the elements of the set , while the second set are obtained by fixing one element and rearranging the other two. It follows that .                

4. Product of Permutations (1 of 5) How do we determine the product of two permutations? Recall that the group operation is function composition and in function composition the rightmost function is taken first: It follows that the product of the two permutations is the identity permutation        

5. Product of Permutations (2 of 5) Let us look at another product It follows that the product of the two permutations is the permutation: What if we reverse the order of the product?          

6. Product of Permutations (3 of 5) From the previous slide, we see that But So the operation is not commutative and is nonabelian. Theorem 1 . If is a positive integer such that , then the symmetric group is a nonabelian group. Proof . Let , and let be defined by:       , and for all   , and for all  

7. Product of Permutations (4 of 5) Proof (cont’d) . , and let be defined by: It follows that: Now, we have   , and for all   , and for all          

8. Product of Permutations (3 of 5) Proof (cont’d) . Similarly We note above that , but , so and for is a nonabelian group. We will introduce the following notation, suppose is given by: We will write as:          

9. Cycle Notation (1 of 2) If is given as then we mean the permutation: is an example of a 2-cycle and and example of a 3-cycle . A 2-cycle is also called a transposition . Consider the permutation : Then is a 4-cycle. We will represent it by        

10. Cycle Notation (2 of 2) Let us rewrite the elements of using cycle notation: Hence, consists of one 1-cycle, three 2-cycles and two 3-cycles. Non-cycles . Consider the permutation Then is not a cycle .                

11. Disjoint Cycles (1 of 1) Non-cycles (cont’d) . In general, the product of two cycles may not be a cycle. Consider the permutations where and Then is not a cycle . Two cycles in are called disjoint if no element of is moved by both cycles. In , the cycles and are disjoint cycles. But the cycles and are not disjoint.      

12. Product of Cycles (1 of 3) Let us look at the composition of the two disjoint cycles and Hence Theorem 2 . Let and be two disjoint cycles in , then . Conclusion: Disjoint cycles commute        

13. Product of Cycles (2 of 3) Consider the element Theorem 3 . Any nonidentity permutation can be written as a product of disjoint cycles, where each cycle is of length .          

14. Product of Cycles (3 of 3) N can be written in the form Hence Theorem 4 . Any cycle of length is either a transposition (a 2-cycle) or can be written as a product of transpositions (not necessarily disjoint). Theorem 5 . Any nonidentity permutation is either a transposition or can be written as a product of transpositions (not necessarily disjoint).        

15. Inverse of a Permutation (1 of 2) Let be given by: Then is obtained by simply reversing the orders of the pairs in . That is Let be given by: Then          

16. Inverse of a Permutation (2 of 2) Let be given by: For we obtain      

17. Odd and Even Permutations (1 of 1) A permutation is called even if it can be written as the product of an even number of transpositions. A permutation is called odd if it can be written as the product of an odd number of transpositions. Theorem 6 . Any permutation of is either an even permutation or an odd permutation, but never both. Consider the element        

18. Cycles to Transpositions (1 of 1) Consider the following 4-cycle from How do we decompose it into a product of 2-cycles (transpositions)? Similarly for the 5-cycle from from , we have Notice that cycles of odd length decompose into an even number of 2-cycles and that cycles of even length decompose into an odd number of 2-cycles        

19. Alternating Group (1 of 2) Consider the element Hence is an odd permutation. Theorem 8.5 (textbook) . Let and let denote the subset of consisting of all even permutations. Then is a subgroup of called the alternating group on letters . In addition, and . Theorem 5.3 (textbook). Let be a group and let be a finite nonempty subset of . Then is a subgroup of if it is closed under the group operation. Proof. Let . Since is closed under multiplication, then But is finite, so all powers of    

20. Alternating Groups (2 of 2) Theorem 5.3 (Proof). Let . Since is closed under multiplication, then But is finite, so all powers of cannot be distinct. Therefore has finite order , and the distinct elements are so every power of is an element of that set including . Proof of Theorem 8.5 . is a nonempty subset of a finite set ( and is therefore finite. Since the product of two even permutations is even. (why?) then is closed under the group operation. By theorem 5.3, is a subgroup of .  

21. Elements of (1 of 4)   Consider the elements of Let us denote Then                  

22. Elements of (3 of 4)   For we have So , and generates the cyclic subgroup Let us denote Then So , and          

23. Elements of (4 of 4)   Now and It follows that How about the element ? Well Similarly,            

24. Elements of (2 of 2)   We can use the identities and to do group multiplication without writing down the permutations. For example So both and have order 2. Now to find the order of . We have So .          

25. Order of Permutations (1 of 2) We may notice above that the order of the two 3-cycles in is three and the order of the 2-cycles is two. Theorem 7. Let and let be a cycle. Then is a k-cycle if and only if . Therefore, the order of a k-cycle is k. How do we find the order of a permutation that is not a cycle? Let be a permutation. By Theorem 3, can be decomposed into disjoint cycles. Theorem 8. Let and let be a permutation, with a product of disjoint cycles.  

26. Order of Permutations (2 of 2) Theorem 8. Let and let be a permutation, with a product of disjoint cycles. Example 1 . In the permutation group , consider the elements and . Determine the order of . Answer: Since is not a product of disjoint cycles, we cannot use Theorem 8.   )      

27. Examples (1 of 6) Example 1 (cont’d) . Since , then is a 5-cycle. Therefore, by Theorem 7, . Example 2 . List all even permutations of . We know that 2-cycles are odd permutations. A k-cycle with k odd is an even permutation. Say and . The remaining even permutation is the identity . So the alternating group Example 3 . Inverses in . Let . We know that , and have order 2, so they are their own inverses. Since , then and . Also by uniqueness of inverses    

28. Examples (2 of 6) Let us further examine inverses of elements in in cycle notation. Since the 2-cycles are their own inverses, then For the 3-cycles: Example 4 . The group . This group contains elements. Let us list these elements starting from the identity:                

29. Examples (3 of 6) Next, we list the six 4-cycles. Now for the eight 3-cycles                    

30. Examples (4 of 6) More 3-cycles Now for the six 2-cycles                    

31. Examples (5 of 6) Now for the three elements that are not cycles: For inverses:             )  

32. Examples (6 of 6) Proof of inverses: and vice versa . For the element ) , this is a product of disjoint 2-cycles, so by Theorem 8: It follows that ) is its own inverse.         )  

33. Examples (6 of 6) Alternate (shorter) proof of Theorem 1: for , and (2 3) are elements of . But sends to , while sends to . It follows that the group for is nonabelian. Example 5 . Determine the center of . Clearly, . sends to , but sends to Similarly, sends to , but sends to . So these elements do not commute. Finally, for the two 3-cycles, sends to , but sends to , Similarly, sends to . But sends to    

34. Examples (6 of 6) It follows that is trivial. Theorem 9 . For , has trivial center. Proof. Clearly Assume that has a nonidentity element . Then there exists numbers and , such that . Now, by assumption , so there exists another number . Consider the transposition        

35. Examples (6 of 6) Then we have , and . It follows that Since and is one-to-one and onto. Thus But this contradicts the assumption that . Therefore for is trivial.