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