Given two permutations , I'm asked to answer is they are conjugate permutations .
The two permutations are : $ \alpha=(12)(345)(78)$, $\beta=(162)(35)(89)$.
Definition: Two permutations $ \sigma,\sigma'\in S_n$ are conjugate if exists $\tau \in S_n $ such that:
$\sigma'=\tau\sigma\tau^{-1} = (\tau(a_0),\tau(a_1)\ldots \tau(a_k)) $, where $ \alpha=(a_0a_1\ldots a_k)$ .
It took me a long time to find the correct $\tau$ that would compute the exact $\beta$ , which is:
$$\tau=(13)(25)(46)(789)$$
So if we want to produce are $\beta$ we can do the following :
$$(\tau(1),\tau(2))(\tau(3)\tau(4)\tau(5))(\tau(7)\tau(8))=(35)(162)(89)$$
and indeed , they ($α$ and $β$) are conjugate.
My question, after this "long" post, is rather simple: is there a simple way to compute the $\tau$ ?
Regards
Best Answer
Yes.
Note, however, that in general there are many $\tau$ that work. You found one; here's another: $$\tau= (1,8,5,2,9,4,6,7,3).$$ Indeed, $$\tau\alpha\tau^{-1} = (\tau(1)\tau(2))(\tau(7)\tau(8))(\tau(3)\tau(4)\tau(5)) = (8,9)(3,5)(1,6,2)=\beta.$$
Theorem. Two permutations $\alpha$ and $\beta$ are conjugate in $S_n$ if and only if they have the same cycle structure.
The proof provides an algorithm for finding a $\tau$ that works.
If $\alpha$ and $\beta$ are conjugate, then they have the same cycle structure. This, because the conjugate of an $n$-cycle is an $n$-cycle, and the conjugate of a product is a product of conjugates.
Conversely, suppose that $\alpha$ and $\beta$ have the same cycle structure. Say $$\alpha = \sigma_1\cdots\sigma_m,\quad \beta=\sigma'_1\cdots \sigma'_m$$ where $\sigma_i$ and $\sigma'_i$ are $n_i$-cycles. Write $\alpha$ and $\beta$ one above the other, so that cycles of the same length coincide; interpret this as a $2$-line description of a permutation, completing it to an element of $\sigma_n$ any way you want.
For example, with the two permutation you have above, $\alpha=(1,2)(7,8)(3,4,5)$, $\beta=(3,5)(8,9)(1,6,2)$, we have: $$\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 3 & 4 & 5 & & &\\ 3 & 5 & 8 & 9 & 1 & 6 & 2 & & & \end{array}\right)$$ Note that the top line is missing $6$ and $9$, and the bottom line is missing $4$ and $7$; we can add them any way we want; for example, $$\left(\begin{array}{cccccccc} 1 & 2 & 7 & 8 & 3 & 4 & 5 &6 & 9\\ 3 & 5 & 8 & 9 & 1 & 6 & 2 & 7 & 4 \end{array}\right)$$ Now viewing this as a 2-line decription of a permutation, we get $$\tau = (1,3)(2,5)(7,8,9,4,6)$$ as one possibility. If you order the cycles differently (so long as they match), or reorder the terms within the cycle, you may get a different $\tau$. For instance, writing instead $$\begin{align*} \alpha &= (12)(78)(453)\\ \beta &= (89)(53)(162) \end{align*}$$ we get $$\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 4 & 5 & 3 & &\\ 8 & 9 & 5 & 3 & 1 & 6 & 2 & & \end{array}\right)$$ with $6$ and $9$ in the top line going to $4$ and $7$ in some way; randomly choosing one, $$\left(\begin{array}{ccccccccc} 1 & 2 & 7 & 8 & 4 & 5 & 3 & 6 & 9 \\ 8 & 9 & 5 & 3 & 1 & 6 & 2 & 4 & 7 \end{array}\right)$$ we get $\tau = (1,8,3,2,9,7,5,6,4)$.
To find out if the permutations are conjugate in $A_n$, however, is a bit trickier: it is necessary that they have the same cycle structure, but in general it is not sufficient. For instance, in $S_3$ the permutations $(123)$ and $(132)$ are conjugate (for example, conjugate via $(23)$); but in $A_3$ they are not (since $A_3$ is abelian, different elements cannot be conjugate).