Generators for the Group S_n
Date: 10/08/2001 at 17:38:10 From: Julius Hodge Subject: Abstract Algebra - generators for the group S_n Show that S_n, the symmetric group on n elements, is generated by the elements: (1 2) and (1 2 3 ... n) for all n>=2. I tried it for n = 3 and (by brute force) I see that it works in that case. I wrote down all 24 of the permutations for n = 4 but couldn't figure out how to write a random element in S_4 as a product of (1 2)'s and (1 2 3 ... n)'s. For example I picked the element (3 4). I see I have to come up with a permutation that fixes 1 and 2 while sending 3 to 4 and 4 to 3. But how to do this with the given elements isn't clear to me. Perhaps if you could help me see how it works a given element I could generalize the procedure to work for any element in S_n for any n > 2. Any help would be appreciated. Thanks. Julius Hodge
Date: 10/09/2001 at 02:29:21 From: Doctor Schwa Subject: Re: Abstract Algebra - generators for the group S_n Hi Julius, the (1 2 3 ... n) cycles the whole list. So to swap 3 and 4, you 1) cycle the set till 3 and 4 are in the first two positions (that is, apply (1 2 3 4) twice) 2) swap the first two positions (that is, apply (1 2) once) and then 3) cycle the set to put everybody back where they came from (that is, apply (1 2 3 4) twice more). This general pattern - move stuff, do something, put it back where you found it - is so common it has a special name: conjugation. That is, x A x^-1 is called a "conjugate" of A. Anyway, using this conjugation idea you can take the (1 2) and make it flip any two adjacent elements; then you can put those together to flip any two elements at all, which in turn generates the whole set. Thanks for the fun question! - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/
Date: 10/09/2001 at 15:35:02 From: Julius Hodge Subject: Re: Abstract Algebra - generators for the group S_n Thanks for the help. After reading your reply, it wasn't immediately clear to me how things worked out, but your hint about conjugation really helped a lot. I let a = (1 2 ... n) and b = (1 2) and decided to see what would happen when I computed a^1 * b * a^(-1) = a^1 * b * a^(n-1) a^2 * b * a^(n-2) a^3 * b * a^(n-3) . . . a^i * b * a^(n-i) I noticed that a^i * b * a^(n-i) is always equal to the two-cycle (i+1 i+2) for i = 0 .. n-2 (and your explanation above explained why this was occurring). So then I was able to show that <a,b> = < (1 2), (2 3), ... , (n-1 n) > The previous exercise in the text we are using (Dummit and Foote) was to show that this generated S_n. So I knew I was on the right track. I was then able to show that every two-cycle of the form (i i+2) could be made from these n-1 2-cycles by the following procedure: (i i+1)(i+1 i+2)(i i+1) = (i i+2) Then I showed that every 2-cycle of the form (i i+3) could be made from the original n-1 2-cycles and from the n-2 2-cycles of the form (i i+2) that I just created: (i i+1)(i+1 i+3)(i i+1) = (i i+3) Similarly, *every* 2-cycle can be obtained from the original n-1 2-cycles by a sort of inductive argument. And that completed the proof. Since I had shown that S_n = < (1 2), (2 3), ... , (n-1 n) > and since I knew that <a,b> = < (1 2), (2 3), ... , (n-1 n) > I was able to conclude that S_n = <a,b>, which was to be shown. Thanks for the nice hint - I don't know if I would have seen how to do this problem without it. Now that I see how to do it, I agree that this is a fun question - as you said. But if you had asked me last night (before your hint), I'm not so sure I would have agreed with you! Regards, Julius
Date: 10/10/2001 at 18:14:36 From: Doctor Schwa Subject: Re: Abstract Algebra - generators for the group S_n Julius, Thanks very much for the note. I think your more detailed explanation of this problem is better than mine! I'm glad my hint helped get you started and you did a super job working things through on your own. Also thanks for sharing your work with me: it was fun to read, and helped me understand how you're thinking about this type of problem. Plus I now have a new convert to appreciate the power of conjugation! - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.