301 Abstract Algebra 2:00 - 2:50 MWF Hentzel 432 Carver hentzel@iastate.edu Web Page http://www.math.iastate.edu/hentzel/class.301 Text: A First Course in Abstract Algebra, sixth Edition by John B. Fraleigh Course: Chapter 1,2,3,4,5 The material we are covering today is on Page 111-114 Section 2.2 beginning with "Even and Odd Permutations." Main Idea: There are two types of permutations. Key Words: Even, Odd, Transpositions, 2-cycles. Goal: Learn a proof that a permutation cannot be both even and odd. Apply this to the 16-puzzle. A transposition is a 2-cycle. That is, something whose orbit notation is (a,b). Examples are (1,2), (1,10), (8,14). Theorem: Every n cycle is a product of transpositions. Proof: (1,5) (1,4) (1,3) (1,2) = (1,2,3,4,5). (1,n) (1,n-1) (1,n-2) ... (1,3) (1,2) = (1,2,3,4,...,n) Theorem: Every permutation is a product of transpositions. Proof: Express the permutation as a product of cycles, and then express every cycle as a product of transpositions. Remark: A permutation can be expressed as a product of transpositions is any number of ways. In no way is it possible to "factor" the permutation uniquely. There is a small, but very important result on the uniqueness of the factorization. Some permutations can be factored into an even number of transpositions. Some can be factored into an odd number of transpositions. No permutation -------------- can be factored one time into an even number and another -------------------------------------------------------- time into an odd number of transpositions. ----------------------------------------- Definition: A permutation is called even if is can be factored into an even number of transpositions. A permutation is called odd if it can be factored into an odd number of transposition. Theorem: A permutation cannot be both odd and even. Proof: The book gives two proofs of this. When a book gives two proofs of the same thing, it means that the author is not happy with either one of them. The same is true for me. So I will give a third. Actually, my proof is pretty close to the determinant proof given in the book. I show you a way to visualize the effects of transpositions. Definition: An inversion in a string of numbers occurs whenever a larger number precedes a smaller. Example: 4 1 3 5 2 |-| |---| 4 precedes 1,3,2 so contributes 3 inversions |-------| |---| 3 precedes 2 so contributes 1 inversion |-| 5 precedes 2 so contributes 1 inversion. The total number of inversions is 5. Example: 1 2 3 4 5 has no inversions 1 3 2 5 4 has 2 inversions 5 4 3 2 1 has 10 inversions Lemma: If one interchanges two adjacent numbers in s string of distinct numbers, the number of inversions changes by one. Proof: ............. x y ........... If x and y are interchanged, any inversion before will be an inversion after the interchange except for the one involving x and y. If x < y the switch introduces one inversion. If x > y the switch removes one inversion. If we define the parity of a string of distinct numbers to be "even" if the number of inversions is even, and "odd" if the number of inversions is odd, then from the above lemma, switching any two adjacent numbers changes the parity of the string. Lemma: If one interchanges any two numbers in a string of distinct numbers, the parity of the string changes. Proof: . . . . . . . . . . x . . . . y . . . . . . . . . We interchange x and y by a sequence of adjacent interchanges. Suppose there are r elements between x and y. We can interchange x successively with each of these elements to move x next to y. . . . . . . . . . . . . . . x y . . . . . . . . . We can interchange x and y now. . . . . . . . . . . . . . . y x . . . . . . . . . We can now move y back across the r elements to produce . . . . . . . . . . y . . . . x . . . . . . . . . All together we made 2*r+1 adjacent interchanges so the parity changed an odd number of times. That means the parity of the string with x and y switched is opposite what it was originally. Theorem: A permutation cannot be both even an odd. Proof: If it were, we could factor it in two ways t1 t2 t3 ... tr and t'1 t'2 t'3 ... t' s with r even and s odd. Now apply the permutation to 1 2 3 4 5 .... n to get x1 x2 x3 ... xn. The parity of x1 x2 x3 ... xn is the same as 1 2 3 ... n since r is even. On the other hand it must be odd since s is odd. This contradiction tells us that whenever we have two factorizations, the number of factors must both be even or both be odd. H A Y [] 1 R A W [] M O W S ----Pi-->5 D E B T D I E T 9 H U M S G R U B 13 Y O G I Pi = ( 1, 9, 5,11, 6,14)( 2)( 3,13,15,10,16, 7)( 4)( 8,12) odd odd odd Pi is odd. Let us count the parity of Pi in another way. Each move is a transposition involving the blank. Notice that with every move the blank changes color. [#][ ][#][ ] [ ][#][ ][#] [#][ ][#][ ] [ ][#][ ][#] Since it started at [ ] and ended on [ ], an even number of moves must have occurred. That means that Pi is a product of an even number of transpositions. Thus Pi has to be even. This means that Pi cannot be constructed by a sequence of legal moves and Pi must be impossible. We have shown that for the 16 puzzle, if the parity of the arrangement computed from the permutation is different from the parity of the arrangement computed from the position of the blank then the arrangement is impossible. We have not shown it, but it is also true that if the two computations of the parity agree, then in fact the arrangement is possible. Hand-in-homework. Starting from: R A W [] D E B T H U M S Y O G I 1. Is this possible or impossible? H A Y [] M O W S D I E T G R U B 2. Is this possible or impossible? H I M [] D U T Y R O B E W A G S 3. Is this possible or impossible? M O W S H A Y [] D I E T G R U B 4. R A T E R A T E Y O U R Y O U R M I N D --------> M I N D P A L [] P L A [] ^ ^ Explain how this could occur. 5. What is the secret to the Rate Your Mind Pal puzzle?