Take the 2-minute tour ×

Observe that $$\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr)* \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 3 & 1 \end{smallmatrix}\bigr),$$

so $\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 3 & 1 \end{smallmatrix}\bigr)$ is the square of a permutation. More generally, how do I check if a permutation is square and how can I find its root?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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+1)/2} i_2 i_{(k+3)/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.

share|improve this answer
What you need is that the number of cycles of same even length is even. For example, $(12)(3456)$ has an even number of even cycles but does not have a square root. –  spin Dec 28 '12 at 18:09
Of course, that's what I meant, thanks. Correcting. –  Alfonso Fernandez Dec 28 '12 at 18:13
Can't the square of a cycle of even length be two cycles of odd length? E.g. the square of a length-6 cycle is two length-3 cycles. This also shows that square roots are not unique (as indeed they can't be since some permutations have no roots); (1 3 5) (2 4 6) has the square roots (1 5 3) (2 6 4) and (1 2 3 4 5 6). –  Steven Stadnicki Dec 28 '12 at 19:44
@StevenStadnicki Yes, but the number of even disjoint cycles in the decomposition is then still even, since the parity of both disjoint cycles in the square is the same. In this case, there are simply zero even cycles contributed to the disjoint cycle decomposition of the overarching square. –  Optional Jul 11 at 5:20

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

share|improve this answer

Your Answer


