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!

Proof about symmetric groups and generators

  1. Aug 8, 2016 #1
    1. The problem statement, all variables and given/known data
    Let n>=2 n is natural and set x=(1,2,3,...,n) and y=(1,2). Show that Sym(n)=<x,y>



    2. Relevant equations


    3. The attempt at a solution
    Approach: Induction

    Proof:

    Base case n=2

    x=(1,2)
    y=(1,2)

    Sym(2)={Id,(1,2)}
    (1,2)=x and Id=xy

    so base case holds

    Inductive step assume Sym(k)=<x,y> where x=(1,2,3,4,...,k) and y=(1,2)

    Show Sym(k+1)=<t,y> where t={1,2,...,k+1} and y=<1,2>

    To prove the inductive step, I was thinking we have to use the fact that every b in Sym(k+1) can be represented as the product of pairwise disjoint cycles. I think that we can express $\lambda$ in terms of x
     
  2. jcsd
  3. Aug 8, 2016 #2

    fresh_42

    Staff: Mentor

    Hint: ##(1\;2\; \dots \; k\; (k+1)) =(1\;2\; \dots \; k)\circ (k \; (k+1))## - from right to left. So ##(k \; (k+1)) = (1\;2\; \dots \; k)^{-1} \circ (1\;2\; \dots \; k\; (k+1)) \in \mathcal{Sym}(k+1)## by induction and the fact that all permutations that doesn't involve ##k+1## are in
    If you can show, that all other transpositions ##(i \; (k+1))## are in it, too, you're done. This is because you then can place ##k+1## in every position with an arbitrary fixed order of the other elements.
    Remember that all transpositions ##(i \; j)## with ##i\, , \, j \, \leq \, k## are already in the group.

    Edit: Plus the fact that ##\{ \pi \in \mathcal{Sym}(k+1) \; | \; \pi(k+1) = k+1 \} \cong \mathcal{Sym}(k) \subset \mathcal{Sym}(k+1)##
     
    Last edited: Aug 8, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about symmetric groups and generators
  1. Proof about a group (Replies: 3)

  2. Symmetric groups proof (Replies: 8)

Loading...