Identity ElementDate: 02/09/2002 at 15:22:28 From: bill Flynn Subject: modern algebra Let f be an element of S_n. Show that there exists a positive integer k such that f^k = i, the identity function. Thank you very much, Bill Date: 02/09/2002 at 15:42:32 From: Doctor Paul Subject: Re: Modern algebra Hi Bill, As a consequence of Lagrange's Theorem, a random element of *any* group (not just S_n) raised to the order of the group is the identity element. So choose k = |S_n| = n! and you're done. See if you can prove that if a is a random element of a group G, then a^|G| = i. (Use Lagrange's theorem.) If you need help, try searching our archives; write back if you can't find it. I hope this helps. Please write back if you'd like to talk about this more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 02/11/2002 at 16:08:55 From: Bill Flynn Subject: Modern algebra Dr. Paul, thank you for your help. But we have not covered groups yet. We are still in the first chapter of our textbook, dealing with functions, sets, and mappings. Is there a simpler explanation for this problem? Date: 02/11/2002 at 17:28:50 From: Doctor Paul Subject: Re: Modern algebra Hi Bill, I'm not sure what notation you use to represent elements of S_n. An element of S_n will be a permutation of the set {1, 2, 3, ..., n}. So one way to write this is in matrix form: [1 2 3 4] [3 2 4 1] This says that the permutation takes 1 to 3, fixes 2, takes 3 to 4, and takes 4 to 1. An alternate notation is to write: (1 3 4) This is read as 1 goes to 3, 3 goes to 4, 4 goes to 1 and sometimes written as 1 -> 3, 3 -> 4, 4 -> 1. Since 2 is missing, we know that this permutation fixes 2. We can also write: (1 3 4)(2) How would you compose two permuations? Suppose you had (1 4 3)(3 2 1 4) Start with the permutation on the right, and consider the first element: 1 goes to 4. But then move to the permutation on the left and see what happens to 4: it goes back to 3. So the end result is that 1 gets moved to 3. Now look at 3. 3 goes to 2, which gets fixed in the left permutation, so in the end 3 goes to 2. Now look at 2. 2 goes to 1, but 1 goes to 4, so in the end, 2 goes to 4. Now look at 4. 4 goes to 3, which goes to 1, so 4 goes to 1. Thus (1 4 3)(3 2 1 4) = (1 3 2 4) The length of a cycle is the number of digits it contains. So (1 4 3) is a three cycle, (2) is a one cycle, and (3 2 1 4) is a four cycle. Consider the element s = (1 5 4 2) in S_6. See if you can convince yourself that s^4 = i, that is, (1 5 4 2)(1 5 4 2)(1 5 4 2)(1 5 4 2) = (1)(2)(3)(4)(5)(6) It might help you to write (1 5 4 2) as (1 5 4 2)(3)(6) and then verify that (1 5 4 2)(3)(6)(1 5 4 2)(3)(6)(1 5 4 2)(3)(6)(1 5 4 2)(3)(6) is the identity element in S_6 (i.e., the permutation that fixes all elements of S_6). Why did raising this to the 4th power work? Because the cycle length is four. An n-cycle composed with itself n times will always give the identity permutation. This is nice, but it's not going to completely solve the problem. Why not? Because some elements can't be written as n-cycles. Consider the following element of S_5: [1 2 3 4 5] [3 4 1 5 2] In shorter notation, this permuation is: s = (1 3)(2 4 5) Here we have a perfectly legitimate element of S_5 written as a product of a two cycle and a three cycle. Let's consider powers of this element to see when we get the identity. We can start with s^2: s^2 = (1 3)(2 4 5)(1 3)(2 4 5) If we find that s^2 takes some number k to a number that isn't k, then we know that s^2 isn't the identity permutation and we'll stop short of computing all of s^2 and move on to s^3. Let's see: 1 -> 3 -> 1 (we're okay so far) 2 -> 4 -> 5 So s^2 takes 2 -> 5, which means that s^2 isn't the identity. What about s^3? s^3 = (1 3)(2 4 5)(1 3)(2 4 5)(13)(2 4 5) Let's see: 1 -> 3 -> 1 -> 3 Already we see that s^3 takes 1 -> 3 and hence can't be the identity. Do you see that s^k will never be the identity if k is odd? This is because s^k will always send 1 -> 3 if k is odd. Thus the only powers of k that we have to consider from here on out are even powers of k. What about s^4? s^4 = (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) Let's see: 1 -> 3 -> 1 -> 3 -> 1 2 -> 4 -> 5 -> 2 -> 4 No good. So s^4 doesn't work either. Let's consider s^6: s^6 = (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) (1 3)(2 4 5) Check it yourself and see that s^6 is the identity. So why does s^6 work? Notice that (1 3)^2 = identity and that (2 4 5)^3 = identity So in order to make both of these the identity, we need to make sure that we are simultaneously squaring and cubing. This requires taking the sixth power. In other words, we choose 6 because 6 is the product of the cycle lengths. But what if we had (1 3)(2 6 4 5) as an element of S_6? Do we need to raise this to the 2*4 = 8th power to get the identity? It turns out that we don't. The 8th power will work, but is a bit of an overkill because the 4th power is enough. Notice that raising to the 4th power fixes each of the elements of (2 6 4 5) since it is a 4-cycle and raising to the 4th power fixes all of the elements of (1 3) since its elements will be fixed by any even power. (Verify this with an example if it's not clear why this is the case.) So why did we need 2*3 in the first example, while 2*4 was too big in the 2nd example? It turns out that the LCM of the cycle lengths will be the smallest power that will give the identity. Recall that LCM(a,b,c) = LCM(LCM(a,b),c) and you can apply this formula inductively if you need to compute the LCM of 4 or more numbers. So if you have s = (1 4 5)(6 2 8 7)(9 3 10 11 12) which is an element of S_12, the smallest power that will produce the identity is LCM(3,4,5) = 3*4*5 = 60 In this case, since the numbers are all relatively prime, the LCM is just the product. But if s = (1 4 5)(6 2 8 7)(9 3 10 11) then the smallest power that will produce the identity is LCM(3,4,4) = LCM(3,4) = 12. Does this explain what's going on? I hope so. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/