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 Monday, October 8. Main idea: If a normal subgroup has a 3-cycle, it has all 3-cycles. Key words: Master Mind, Puzzle Peg, Triangular Puzzle Peg Goal: Show that the cycle structure is preserved under conjugation Previous Assignment: Suppose that H and K are subgroups of a group G. 1. Show that HK need not be a group. You can find a counter example in S3. H = {I,(12)} K = {I,(23)} HK = {I,(12)}{I,(23)} = {I,(12),(23),(123)} HK has four elements and cannot be a subgroup because four does not divide the order of the group. 2. Show that if H or K is normal, then HK is a subgroup. Assume that K is normal. Closure: hk h1k1 = h (h1 h1') k h1 k1 = (h h1)(h1' k h1) k1 in HK in H in K in K for any h,h1 in H and k k1 in K. Inverse: (hk)' = k'h' = (h' h) k' h' = h' (h k' h') in HK in H in K for any h in H and k in K. The proof is similar when H is normal. 3. Show that if H and K are normal, then HK is a normal subgroup. If both H and K are normal, we already know that HK is a subgroup. We have to show that HK is normal. For any g in G g(HK)g' = (gHg')(gKg') = HK. Therefore HK is normal. Page 230 Problem 7; Theorem: pi (a,b,c ..., d) pi' = ( pi(a),pi(b),pi(c) ... pi(d) ). This theorem shows that conjugates have the same cycle structure. It also shows that if a normal subgroup of Sn has any three cycle, then it has all three cycles. If a normal subgroup has any 4-cycle, then it has all 4-cycles. In fact, if it has any permutation then it has all permutations with that same cycle structure. Proof: We compare the product on the left with the product on the right. pi(a) ---> a ---> b ---> pi(b) pi(b) ---> b ---> c ---> pi(c) etc. Example: (12)(123)(12) = (213) (123)(15432)(132) = (25413) Notice that conjugation preserves the same cycle structure. Find pi such that pi (123) pi' = (345) ans: pi = (135)(24) or many many others. Find pi such that pi (123) pi' = (234) ans pi = (1234) or many others. Permutation Mastermind. This game has n different colors of pins. There is a secret permutation of them which is hidden from view. The game is the discover the secret permutation by guessing various permutations. With each guess you are told how many positions you have correct. The object is to guess the secret permutation with as few guesses as possible. n = 3. The rule is: Guess anything. If 3-correct, game over. If 2-correct, impossible. If 1 correct, do any 2-cycle If 0 correct, do (123). You win after at most 3 moves. Why. n=4 The rule is: Guess anything. If 4 correct, game over. If 3 correct, impossible. If 2 correct, do any 2-cycle. If 1 correct, do any 3-cycle (but use the same one subsequently) If 0 correct, do (1234) initially until you get at least one correct. Subsequently, check the Kleinfour group. You win after at most how-many moves. Why? n=5. I never figured the moves out. Algebraic Invariants for puzzle peg. In the Klein-four group, the square of any element is the identity, and the product of two non-identity elements is the remaining non-identity. The group is commutative. One notation for the group is {0,1,p,q} where x+x = 0 for all x in the Group, and x+y=z where x,y,z are distinct and none is 0. 1 p q 1 p q 1 p q 1 p q 1 p p q 1 p q 1 p q 1 p q 1 p q q 1 p q 1 p q 1 p q 1 p q 1 1 p q 1 p q 1 p q 1 p q 1 p p q 1 p q 1 p q 1 p q 1 p q q 1 p q 1 p q 1 p q 1 p q 1 1 p q 1 p q 1 p q 1 p q 1 p p q 1 p q 1 p q 1 p q 1 p q q 1 p q 1 p q 1 p q 1 p q 1 1 p q 1 p q 1 p q 1 p q 1 p Let us take an infinite board and label the integer grid with 1's,p's, and q's as shown. Notice that no 0 appears on the board. Now we are going to place some checkers on the board as well. The 1's,p's,q's are marked on the board and are fixed. The checkers sit atop the marks on the board. The value of a checker is the 1,p,or q which it currently sits upon. The value of the board is the sum of all the values of the checkers. Now moves are done by jumping. You can jump vertically or horizontally. A jump goes over an adjacent checker an into an open space. The checker jumped over is removed. Notice that every 3 consecutive positions either horizontally or vertically involves positions labeled with all three distinct elements. A jump takes two checkers off, and places one checker in the remaining position. The sum of the values of two original equals the value of the remaining checker. Thus on jumps, the value of the board remains fixed. So the value of the board is an algebraic invariant. If you put a pattern of checkers on the board and jump down to one remaining checker, the value of the board is still the same. Thus the last checker has to be on the diagonal with that value. We could have labeled the board with the identical elements going the other diagonal and one would have a second criterion for the position of the last element. In particular the grid arrangement for the last element will be as follows. 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 . . 0 Find a series of jumps to reduce the following to a single peg. . . . . . . . . . . . . . 0 0 0 0 0 0 0 . . . . 0 0 0 0 0 0 0 . . . . 0 0 0 0 0 0 0 . . . . 0 0 0 0 0 0 0 . . . . 0 0 0 0 0 0 0 . . . . 0 0 0 0 0 0 0 . . . . . . . . . . . . . Answer: The parity is zero. It is impossible. The best one can hope for is to get it down to two pegs. Remove one peg and jump the remaining down to one peg. o o o o o o o o o o o o o o o o You have to remove an edge peg which is not a corner to have any hope of winning. The standard game is puzzle peg. o o o o o o o o o o o o o o o o . o o o o o o o o o o o o o o o o Where must the remaining single peg be. Explain why this statement is true. "If you can jump the game down to one peg, then I can jump down to one peg in the center." Assignment: The corresponding numbering for triangular puzzle peg is p 1 q q p 1 p 1 q p 1 q p 1 q q p 1 q p 1 p 1 q p 1 q p 1 q p 1 q p 1 q (1) For this puzzle, remove one peg and jump down to one peg. Which peg do you remove and where is the last peg? o o o o o o o o o o (2) Is this puzzle possible or impossible to solve if you are allowed to jump outside the figure? Why? . . . . o . . o o . . o o o . . o o o o . . o o o o o . . . . . . . . . (3) Prove that the Kleinfour group is a normal subgroup of S4. Use the fact that that the Kleinfour group contains all 2-2 cycles of S4. (4) (a) Find an even permutation pi such that pi (12)(34) pi' = (14)(23) (b) Find an odd permutation pi such that pi (12)(34) pi' = (14)(23) (5) Show that the subset of S5 containing the identity and all 2-2 cycles is not closed. ----------------------------------------------------------------- |This is not part of the assignment. Can you solve it? | |The following is impossible if you must stay within the figure, | |but possible if you can jump outside the figure. | | | | o | | o o | | o o o | | o . . o | | o o o o o | | | |This shows that the confines of the board also contribute to | |the possibility or impossibility of the puzzle. If the puzzle | |is algebraically impossible. Then it is impossible. But if | |it is algebraically possible, then it still might not be | |possible. | -----------------------------------------------------------------