How to find the square root of a permutation Observe that 
$$\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
2 & 4 & 1 & 5 & 3
\end{pmatrix}
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
2 & 4 & 1 & 5 & 3
\end{pmatrix} = 
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
4 & 5 & 2 & 3 & 1
\end{pmatrix},$$
so $\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
4 & 5 & 2 & 3 & 1
\end{pmatrix}$ is the square of a permutation. More generally, how do I check if a permutation is square and how can I find its root?

Any permutation can be written as a product of disjoint cycles $\sigma = c_1\cdot\ldots\cdot c_n$. Because disjoint cycles commute, $\sigma^2 = c_1^2\cdot\ldots\cdot c_n^2$.
So a square permutation is one that consists of a product of disjoint square cycles. Now when is a cycle square?
If $c=(i_1 i_2\ldots i_k)$, then $c^2$ takes $i_1$ to $i_3$, $i_2$ to $i_4$, and so on. In other words:
If $k$ is odd, $c^2$ is another $k$-cycle, which means that every $k$-cycle is a square.
If $k$ is even, then $c^2=(i_1i_3\ldots i_{k-1})(i_2i_4\ldots i_{k})$.
Therefore: a permutation is a square if and only if the number of cycles of any even length in its disjoint cycle decomposition is even, and the algorithm you can use to find its root is as following:


*

*Find the roots of all odd cycles, $\sqrt{c} = (i_1 i_{(k+3)/2} i_2 i_{(k+5)/2} \ldots i_k i_{(k+1)/2})$.

*Take pairs $c=(i_1\ldots i_k),d=(j_1\ldots j_k)$ of the even cycles of the same length and construct $\sqrt{c,d} = (i_1j_1\ldots i_kj_k)$.


Your permutation is an example of an odd cycle with a root that matches what would follow this method.
