1. Not finding help here? Sign up for a free 30min 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!

Show that the symmetric group S_n has elements of all order

  1. Feb 25, 2017 #1
    1. The problem statement, all variables and given/known data
    Prove that if ##1 \leq d \leq n##, then ##S_n## contains elements of order d.

    2. Relevant equations


    3. The attempt at a solution
    Here is my idea. The order of the identity permutation is 1. Written in cycle notation, the order of (1,2) is 2, the order of (1,2,3) is 3, the order of (1,2,3,4) is 4, and in general the order of (1,2,3,4,...,n-1,n) is n. It would seem that this shows that if ##1 \leq d \leq n##, then ##S_n## contains elements of order d.

    However, I am not sure how rigorous this is. Do I need to make an induction argument that in general (1,2,3,4,...,n-1,n) has order n, or is it fine as it is?
     
  2. jcsd
  3. Feb 25, 2017 #2

    fresh_42

    Staff: Mentor

    This only depends on whom it is meant for. For me, it is o.k., but I already had the same thought as I've read the question. For someone in high school, some kind of reasoning might be helpful. You don't need an induction here, because you can show it directly for ##(1,2,\ldots,n)## and the knowledge that ##(1,2,\ldots,n-1)## is of order ##n-1## is of no help for ##(1,2,\ldots,n)^n=1\, : \,## You would have to write
    $$ \begin{align*}(1,2,\ldots,n)^n &= [(1,2,\ldots,n-1) \cdot (n,n-1)]^n \\ &= (1,2,\ldots,n-1) \cdot (n,n-1) \cdot \ldots \cdot (1,2,\ldots,n-1) \cdot (n,n-1) \end{align*}$$
    and deal with the fact, that the permutations are not commutative, which would make it unnecessarily complicated.

    Thus simply take any number ##i\in \{1,2,\ldots,n\}## and justify why it takes ##n## turns to reach ##i## again.
     
  4. Feb 25, 2017 #3
    Okay, that answers my question.

    On a related note, how would I prove that the order of a cycle is equal to its length? It seems very obvious, but I can't quite see how to formalize a proof
     
  5. Feb 26, 2017 #4

    fresh_42

    Staff: Mentor

    Just count the steps: ##i \mapsto i+1 \mapsto \ldots \mapsto n \mapsto 1 \mapsto \ldots \mapsto i-1 \mapsto i## where you have to be careful at the turning point ##n## with the counting (e.g. I tend to make a mistake by one at this point) and remark, that there is no way of getting back to ##1## earlier.

    Or assume ## {(1,2,\ldots,n)}^m = 1 = id## which is ## {i}+m \cdot 1 = 1({i}) = i \mod n ## for all ##1 \leq i \leq n## and show that this can only be true for ##m=n##.
     
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: Show that the symmetric group S_n has elements of all order
Loading...