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?

Solution 1:

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:

1. 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})$.
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.

Solution 2:

A permutation $\sigma \in S_n$ has a unique representation as the product of disjoint cycles. We show that $\sigma$ has a square root in $S_n$ if and only if the number of cycles of same even length in the representation is even (or zero). This condition is necessary because the square of an cycle of even length $2k$ splits in to two disjoint cycles of length $k$ and squares of cycles of odd length have odd length.

Your example permutation is an odd cycle, and hence has no cycles of even length. Thus it satisfies the condition. Another example would be $(12)(34)(567)$ which has two cycles of length $2$ and no even length cycles of other lengths.

For an algorithm to find the root when $\sigma \in S_n$ satisfies the condition, let $\sigma = \alpha_1 \alpha_1^* \alpha_2 \alpha_2^* \ldots \alpha_t \alpha_t^* \beta_1 \beta_2 \ldots \beta_s$ be a product of disjoint cycles where for all $i$, the $\alpha_i, \alpha_i^*$ are cycles of same even length and $\beta_i$ are cycles of odd length.

It suffices to find for all $i$ a square root $\sigma_i$ for $\alpha_i \alpha_i^*$ that moves the same elements $\alpha_i \alpha_i^*$ does and similarly a root $\tau_i$ for $\beta_i$ such that $\tau_i$ moves the same elements $\beta_i$ does. Then $\sigma = \tau^2$, where $\tau = \sigma_1 \sigma_2 \ldots \sigma_t \tau_1 \tau_2 \ldots \tau_s$.

If $\alpha_i = (a_1 a_2 \ldots a_{2k})$ and $\alpha_i^* = (a_1^* a_2^* \ldots a_{2k}^*)$, let $\sigma_i = (a_1 a_1^* a_2 a_2^* \ldots a_{2k} a_{2k}^*)$.

If $\beta_i = (a_1 a_2 \ldots a_{2k+1})$, then let $\tau_i = (a_1 a_{k+1} a_2 a_{k+2} a_3 a_{k+3} \ldots a_{k + (k+1)} a_{k+1})$.

For example, if $\sigma = (12)(34)(567)$, then $(12)(34) = (1324)^2$ and $(567) = (576)^2$, so $\sigma$ has a square root $\tau = (1324)(576)$.