2
$\begingroup$

I've been searching extensively for the simplest way of finding a root of a permutation, but I can't understand half of the things that I've found.

Let's say we have 2 permutations:

$\alpha^2 = (1\:4\:7)(2\: 5\: 8)(3\: 6\: 9) $

$\beta^2 = (1\:5)(2\:3)(4\:6\:7)$

What is the best way of finding $\alpha $ and $\beta$ ? I'm really looking for an ELI5(explain to me like I'm five) answer, I'm having trouble understanding these permutations.. Is there really no fool-proof way to solve this?

$\endgroup$
  • $\begingroup$ It sounds like you need to pick up any abstract algebra book and read the first chapter. $\endgroup$ – Alex R. Jan 26 '15 at 1:15
  • $\begingroup$ I've solved a lot of problems regarding permutations and this is one last thing I don't understand.. I've searched and read about it, but it seems so complicated. $\endgroup$ – peroxy Jan 26 '15 at 1:18
2
$\begingroup$

What happens when you square a permutation? It suffices to say what happens to each of the cycles. If the cycle is of even length it splits into two cycles which can be obtained by copying the permutation twice and one of them only has the even ones and the other one only the odd ones:

$(1234)=(13)(24)$

If the cycle is odd it remains being a cycle of the same size , it can be written by first writing the even elements and then the odd ones, respecting the order:

$(12345)=(13524)$.

In your example we have $(147)(258)(369)$ There are many permutations which yield this when squared. The easiest one is $(174)(285)(396)$.

For $(15)(23)(467)$ it is unique because a permutation which gives that one when squared has a cycle of length four. The permutation is $(1253)(476)$


Here is a simple algorithm for finding a square root of a permutation:

Identify the cycles of odd length. For each cycle of odd length $(a_1,a_2\dots a_{2k+1})$ write the cycle $(a_1 a_{k+2} a_2 a_{k+3}a_3a_{k+4}\dots a_{k} a_{2k+1} a_{k+1})$

Identify the cycles of even length and pair each cycle of even length with a cycle of the same length (If this is not possible there are no roots). Now that the cycles are paired, for each pair $(a_1a_2\dots a_n) (b_1b_2\dots b_n)$ take the cycle $(a_1b_1a_2b_2\dots a_nb_n)$

$\endgroup$
  • $\begingroup$ Thanks so much, this helps so much! I'm still not sure how you got the $(15)(23)(467)$ result; the $(15)$ and $(23)$ cycles are even, shouldn't they simply change to $(1),(5),(2),(3)$? How do I know if the cycle is unique? $\endgroup$ – peroxy Jan 26 '15 at 1:35
  • $\begingroup$ if you square a sycle of length 4 you get two cycles of length two which is what you want. If you square four cycles of length $1$ you get four cycles of length $(1)$ which is not what you want. $\endgroup$ – Jorge Fernández Hidalgo Jan 26 '15 at 1:38
  • $\begingroup$ So how do I find all the solutions in the example $(147)(258)(369)$? You said there are many more permutations, how do I find all of them? $\endgroup$ – peroxy Jan 26 '15 at 2:15
  • $\begingroup$ well, it possible that $(147)$ and $(258)$ where the same cycle. This would yield $(124578)(396)$ there are another $2$ possibilities depending on which pair of cycles are to be joined into a bigger cycle. $\endgroup$ – Jorge Fernández Hidalgo Jan 26 '15 at 2:17
  • 1
    $\begingroup$ oh yeaaah, my bad :) thanks so much for helping me, you've been super awesome!! $\endgroup$ – peroxy Jan 26 '15 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.