Test 1 September 24, 2001 Math 301 Abstract Algebra Hentzel +---+---+---+---+ +---+---+---+---+ 1. | A | B | C | D | | A | B | D | G | +---+---+---+---+ +---+---+---+---+ | E | F | G | H | Pi | C | E | H | K | +---+---+---+---+ -------> +---+---+---+---+ | I | J | K | L | | F | I | L | N | +---+---+---+---+ +---+---+---+---+ | M | N | O | | | J | M | O | | +---+---+---+---+ +---+---+---+---+ (a) Write Pi in orbit notation for the 16 puzzle (b) Square Pi (c) Find the inverse of Pi. (d) Tell if Pi is even or odd. (e) Find the order of Pi. answer +---+---+---+---+ +---+---+---+---+ 1 | A | B | C | D | 1 | A | B | D | G | +---+---+---+---+ +---+---+---+---+ 5 | E | F | G | H | Pi 5 | C | E | H | K | +---+---+---+---+ -------> +---+---+---+---+ 9 | I | J | K | L | 9 | F | I | L | N | +---+---+---+---+ +---+---+---+---+ 13 | M | N | O | | 13 | J | M | O | | +---+---+---+---+ +---+---+---+---+ (a) Write Pi in orbit notation for the 16 puzzle ( 1)( 2)( 3 5 6 9 10 13 14 12 11 8 7 4)(15)(16) (b) Square Pi ( 1)( 2)( 3 6 10 14 11 7)(5 9 13 12 8 4)(15)(16) (c) Find the inverse of Pi. ( 1)( 2)(4 7 8 11 12 14 13 10 9 6 5 3)(15)(16) (d) Pi is ODD (e) Find the order of Pi. The order of Pi is 12. 2. Prove that if G is a finite group and H is a subgroup of G, then |H| divides |G|. This means that I want you to write down the proof of Lagrange's theorem. Suppose that H = {h1,h2,...,hr}. Pick some element g1 of G which is not in H. Compute Hg1 = {h1g1 h2g1 ... hrg1}. These elements are all distinct. To show that they are all distinct, suppose that for different hi and hj, we have hig1 = hjg1. If we multiply on the right by g1^(-1) we get that hi = hj which is a contradiction. Continue this set construction, each time picking a gn which is not contained in any of the previous sets Hgm. There will never be any elements in common between the two distinct sets Hgm and Hgn. To show this, assume that for m < n, Hgm and Hgn have some element in common. This means for some hi and hj in H, higm = hjgn. Multiplying on the left by hj^(-1) gives hj^(-1)higm = gn. Since hj^(-1)hi is an element in H, we have gn in Hgm. This contradicts the choice of gn. This contradiction shows that the subsets created by the successive choices of gi are all distinct. Eventually you will exhaust a finite group. The number of elements in the group will be |H|*(number of subsets). Therefore, |H| divides |G|. 3. Find integers x and y such that 29x + 79y = 1. 2 29 | 79 58 -- 1 21 | 29 21 -- 2 8 | 21 16 -- 1 5 | 8 5 --- 1 3 | 5 3 - 1 2 | 3 2 - 2 1 | 2 2 _ 0 2 1 2 1 1 1 2 1 2 3 8 11 19 30 79 0 1 1 3 4 7 11 29 ans: 30 29 - 11 79 4. How many different bracelets with 8 beads can you you make with 3 red, 3 blue and 2 green bead. 1 2 3 4 5 6 7 8 1 2 1 4 1 2 1 I ()()()()()()()() 8!/(3! 3! 2!) = 560 4 ( , , , , , , , ) 0 2 ( , , , )( , , , ) 0 1 ( , )( , )( , )( , ) 0 edge 4 ( , )( , )( , )( , ) 0 corner 4 ( )( )( , )( , )( , ) 4*12 = 48 ------ 608/16 = 38 5. If a group G acts on a set S (a) If s in S is given, let H = {g in G | gs = s} is a subgroup of G. (b) Prove that all the elements in gH map s to the same element in the orbit of s. (c) Prove that different cosets map s to different elements in the orbit of s. (d) Prove that Sum F(g) = Sum | Stabilizer(s) | g in G s in S. F(g) is the number of elements of S such that gs = s. | Stabilizer(s) | is the number of elements in g such that gs = s. (a) We have to show H is closed with inverses. If g1 and g2 are in H, then (g1 g2)s = g1*(g2*s) = g1*s (* since g2*s = s *). = s (* since (g1*s) = s. *) Therefore if g1 and g2 are in H, then g1g2 is also in H. Therefore H is closed. g1^(-1)*s = g1^(-1)*(g1*s) (* since g1*s = s *) = (g1^(-1) g1)*s = e*s = s. Therefore if g1 is in H, then g1^(-1) is also in H. Therefore H has inverses. (b) If gh is in gH, then (gh)*s = g*(h*s) = g*s (* since h*s = s) Therefore the element of gH all map s to the same object. (c). Suppose that g1H and g2H are different cosets yet g1*s = g2*s. Multiplying by g2^(-1) on the left gives g2^(-1)*(g1*s) = g2^(-1)*(g2*s) (g2^(-1)g1)*s = (g2^(-1)g2)*s (g2^(-1)g1)*s = e*s (g2^(-1)g1)*s = s This shows that g2^(-1)g1 is in H. The closets generated by H are distinct. Since g1 = g2( g2^(-1)g1 ) is in g2 H we get g1 is in g2 H. Since g1 H and g2 H have no elements in common g1H = g2H. This is a contradiction occurred because we assumed that the cosets were distinct. (d) We look at the set T = { (g,s) | g is in G, s is in S, and gs = s}. If we count the number of elements in T by summing on G we get | T | = SUM [ the number of elements of S such that gs = s] g in G = SUM F[g]. g in G If we count the number of elements in T by summing on S we get | T | = SUM [ the number of elements of G such that gs = s ] s in S = SUM | Stabilizer of s | g in G 6. Suppose you have a commutative group satisfying these relations. 18 a + 24 b + 6 c = 0 32 a + 8 b + 12 c = 0 Write G = Zr x Zs x Zt and give the elements a,b,c in Zr x Zs x Zt. 18 a + 24 b + 6 c = 0 32 a + 8 b + 12 c = 0 a b c 18 24 6 32 8 12 c a b 6 18 24 12 32 8 c a b 6 18 24 0 -4 -40 add -3 column 1 to column 2 add -4 column 1 to column 3 3a+4b+c a b 6 0 0 0 -4 -40 add -10 column 2 to column 3 3a+4b+c a+10b b 6 0 0 0 -4 0 3a+4b+c a+10b b 6 0 0 0 +4 0 Z6 (+) Z4 (+) Z a' = 3a+4b+c b' = a+10b c' = b |a'| |3 4 1||a| |b'| = |1 10 0||b| |c'| |0 1 0||c| |a | |0 1 -10 ||a'| |b | = |0 0 1 ||b'| |c | |1 -3 26 ||c'| 18 a + 24 b + 6 c = 0 32 a + 8 b + 12 c = 0 18 (0 1 -10) +24 (0 0 1) +6 (1 -3 26) ---------------- (6 0 0) = (0,0,0) 32 (0 1 -10) +8 (0 0 1) +12 (1 -3 26) -------------- (12 -4 0) = (0,0,0)