Abstract Algebra: Permutations Let $\sigma$ be a permutation of $k$ elements such that $\sigma^2 = \epsilon$. Where $\epsilon$ denotes the identity permutation. How would you show that $\sigma$ consists of cycles of length 1 or 2 only?
 A: You can use two facts:


*

*If $\gamma$ is a cycle of length (=order) $r$, $\;\gamma^k$ has order $\dfrac r{\gcd(r, k)}$, and it actually splits into $\gcd(r,k)$ disjoint subcycles of order $\dfrac r{\gcd(r, k)}$.

*The order of a product of disjoints cycles is the l.c.m. of the orders of the factors.


So, if $\sigma^2=\epsilon$, and $\sigma=\prod_{k=1 }^n \gamma_k$, $\;\gamma_k$ being a cycle of order $r_k$, we know that for each $k$,
$$\frac{r_k}{\gcd(r_k, 2)}=1\iff r_k=\gcd(r_k,2).$$
and therefore, if $r_k$ is odd, necessarily $r_k=1$, and if $r_k$ is even, $r_k=2$.
A: Hint: suppose that when you write $\sigma$ as a composition of disjoint cycles there is a cycle of length at least $3$. What happens to the elements of this cycle in $\sigma^2$? 
A: Say $\sigma \in S_n$.
Define the iteration graph of $\sigma$ to be the graph with vertices $\{1, \ldots, n\}$, where there is a directed edge from $i$ to $\sigma(i)$ for all $i \in \{1, \ldots, n\}$.
This graph breaks up into a disjoint union of directed cycles. (Some of them may be self loops.) 
This is the same idea as the cycle decomposition. (However, it makes no choices regarding the ordering of the cycles, or the cyclic ordering within each cycle - I.e. $(12)(34) = (21)(34) = (34)(21)$ ... there are many ways to write the same permutation in cycle form, but only one iteration graph.)
We can imagine walking along the iteration graph - at any time $t$ if we are at $x$, we move to the vertex that the directed edge out of $x$ connects to. This is the same as sending $x$ to $\sigma(x)$ after one time step, by definition of the iteration graph.
Observe that $\sigma^2 = e$ means that for any point $x \in \{1, \ldots, n \}$, after walking for two steps along the directed cycle containing $x$, you will return back to where you started.
Now, if I start a walker on a directed cycle of length $\geq 3$, it can't return to where it started after 2 steps. So all of the directed cycles in the iteration graph have length $1$ or $2$. 
You can write all of this as an algebraic proof, using the observation that disjoint cycles commute. However, I think the picture of the iteration graph is helpful for thinking about permutations.
