2

I've got a permutation $S$ and I need to find out all the permutations $R$ with: $R \circ R = S$. How can I solve it using its product of disjoint cycles? I know how to solve such an equation,but using letters and trying every case. But this permutation $S$ has $12$ elements,so it's impossible to solve it this way.

Thanks in advance!

N. F. Taussig
  • 76,571
flaviumanica
  • 33

2 Answers2

0

To solve this problem it is sufficient to consider the case where the permutation is a cycle because disjoint cycles commute with each other. Assume therefore that $x$ is a $k$-cycle. Then $x^{k+1}=x$ because $x^k=1$, so if $k$ is odd then if we take $y=x^{(k+1)/2}$ then $y^2=x$.

If $k$ is even then $y$ must have order $2k$. We claim that $y$ does not exist. It will suffice to prove that the square of an even cycle of length larger than 2 is a product of two disjoint cycles, because an element of order $2k$ must have an even cycle in its decomposition. Suppose $z$ has length $2m$, with $a_1\mapsto a_2\mapsto\cdots \mapsto a_{2m}\mapsto a_1$. Then the square of $z$ maps $a_1\mapsto a_3\mapsto a_5\mapsto\cdots\mapsto a_{2m-1}\mapsto a_1$ and also maps $a_2\mapsto a_4\mapsto\cdots\mapsto a_{2m}\mapsto a_2$, and these are two disjoint cycles. Thus the claim is proved and there is no solution.

For a general permutation, we do this for each of the disjoint cycles and multiply the results together.

Edit: as proved here, squaring an even length cycle gives you two disjoint cycles of the same length. This allows squaring to get even cycles provided they come in pairs of the same length (as mentioned in the other answer). This actually provides a completely general algorithm for solving the problem: take the square roots of the odd cycles, and check if the even cycles come in pairs of the same length, and combine those pairs if so.

Matt Samuel
  • 58,164
  • I understood the odd k stuff. But I didn't understand even k is even. For example,I've got the cycle x=(1,3,4,2). If I take z=(1,2,3,4) => z^2=(1,3)(2,4) => z^3=(1,4,3,2) => z^4=e. Since there's not any p such that z^p=x,does that mean that y^2=x has no solution? – flaviumanica Feb 03 '15 at 10:34
  • Sorry for the error, I'm still thinking about this. – Matt Samuel Feb 03 '15 at 14:11
  • @flaviumanica fixed it, sorry about that. There is no solution. – Matt Samuel Feb 03 '15 at 14:58
0

Partial answer:

An odd length cycle (say length $2k+1$) squares to a cycle of the same length; while an even length cycle (say length $2k$) squares to two disjoint $k$ cycles. As Matt Samuel points out, one can find the square root of an odd length cycle, as an odd length cycle with the same length and using the same cycle elements. Thus in order for permutation $S$ to have a square root, when written in disjoint cycle notation, $S$ must have pairs of even length cycles that are the same length, and any number of odd length cycles.

For example, if we wanted a square root of $S=(1,2,3,4,5)(6,7,8,9)(10,11,12,13)$ we could take $R=(1,4,2,5,3)(6,10,7,11,8,12,9,13)$, and we'd have $R^2=R\circ R=S$.

paw88789
  • 40,402