Show that the symmetric group S_n has elements of all order

1. Feb 25, 2017

Mr Davis 97

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. Feb 25, 2017

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.

3. Feb 25, 2017

Mr Davis 97

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

4. Feb 26, 2017

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$.