1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove the symmetric group is generated by

  1. Jun 26, 2011 #1
    1. The problem statement, all variables and given/known data
    Use induction of n to prove that the transpositions [itex]s_i = (i, i+1)[/itex], [itex]1 \leq i \leq n - 1[/itex] generate [itex]S_n[/itex].

    2. Relevant equations
    Notation: [itex]e[/itex] = Identity permutation.

    Any permutation can be written as a disjoint product of transpositions.

    3. The attempt at a solution

    Proof. We proceed by induction on n. As our base case for [itex]n=2[/itex], we cite that the transposition [itex]s_1 = (12)[/itex] is sufficient to generate [itex]S_n[/itex] since [itex]s_1^2 = e[/itex]. Suppose now that the transpositions [itex]s_i = (i, i+1)[/itex], [itex]1 \leq i \leq n-1[/itex] generate [itex]S_n[/itex].

    I'm not really sure where to go next. I know that [itex]S_n[/itex] has [itex]n![/itex] elements and want to use that fact along with the transposition [itex](i+1,i+2)[/itex] to somehow show that [itex]S_{n+1}[/itex] will have [itex](n+1)![/itex] elements but I am not sure if that is sufficient to prove that the [itex]s_i[/itex]'s generate [itex]S_n[/itex].
  2. jcsd
  3. Jun 26, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    Try to show you can write an element s of S_n+1 as an element of S_n times some transpositions. Label which elements of the permutation s map to and from n+1.
  4. Jun 26, 2011 #3

    Thanks for your response. It makes sense that I should be able to generate the elements of [itex]S_{n+1}[/itex] using the permutations that are contained in [itex]S_n[/itex] plus the additional transposition [itex]s_{n+1} = (n, n+1)[/itex]. But how would I do this?

    For example, say I was constructing elements in [itex]S_4[/itex] from the old transpositions [itex]s_1 = (12)[/itex], [itex]s_2 = (23)[/itex], and the newly acquired transposition [itex]s_3 = (34)[/itex]. Then the products [itex]s_1 s_2 s_3[/itex], [itex]s_1 s_3 s_2[/itex], and [itex]s_2 s_2 s_3[/itex] are all different. Here's what confusing me: How can I work around the problem of generalizing a product when the newly acquired transposition is wedged in between two old permutations. Does this make sense? Would it suffice to say that if [itex]\sigma \in S_{n+1}[/itex] and [itex]\sigma ' \in S_n[/itex], then we can write [itex]\sigma[/itex] in the form of either [itex]\sigma' s_{n+1}[/itex], or [itex]s_{n+1} \sigma'[/itex], or [itex]\sigma_1' s_{n+1} \sigma_2'[/itex]?

    Also, I don't understand what you mean by label which elements of the permutation s map to and from n+1. Can you explain further, please?
  5. Jun 26, 2011 #4


    User Avatar
    Science Advisor
    Homework Helper

    If s is in S_n+1 there is some l in {1...n+1} such that s(l)=n+1 and some k in {1...n+1} such that s(n+1)=k. For the rest of the i in {1...n} s(i) is in {1...n}. So yes, what you say makes perfect sense. You do some transpositions, apply an element in S_n then do some more transpositions so the result is s in S_n+1. You just have to spell out what those initial and final transpositions are.
  6. Jun 26, 2011 #5
    Great. It makes perfect sense to me now. Thanks again!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook