Conjugate permutations in $S_n$ and / or $A_n$

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

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

Write the two permutations in full cycle notation, writing cycles from longest to shortest (cycles of the same length can be ordered arbitrarily, the starting number of cycle can be chosen arbitrarily from within the cycle).

In your example: $$\begin{align*} \alpha &= (3,4,5)(1,2)(7,8)(6)(9) \\ \beta &= (1,6,2)(3,5)(8,9)(4)(7) \end{align*} \text{ so } \tau = \begin{bmatrix} 3 & 4 & 5 & 1 & 2 & 7 & 8 & 6 & 9 \\ 1 & 6 & 2 & 3 & 5 & 8 & 9 & 4 & 7\end{bmatrix}$$

In other words, $\tau(3)=1, \tau(4)=6$, etc. You can convert $\tau$ to cycle notation in the obvious way by "tracing", $\tau=(3,1)(4,6)(5,2)(7,8,9) = (1,3)(2,5)(4,6)(7,8,9)$.

Another $\tau$ is found by:

$$\begin{align*} \alpha &= (3,4,5)(7,8)(2,1)(9)(6) \\ \beta &= (1,6,2)(5,3)(8,9)(4)(7) \end{align*} \text{ so } \tau = \begin{bmatrix} 3 & 4 & 5 & 7 & 8 & 2 & 1 & 9 & 6 \\ 1 & 6 & 2 & 5 & 3 & 8 & 9 & 4 & 7\end{bmatrix}$$

and $\tau= (3,1,9,4,6,7,5,2,8)$.

Since you can reorder the cycles of the same length, and since you can "cycle" a cycle as much as you want, you actually get many different $\tau$, in fact an entire coset of a centralizer. One way to calculate the centralizer of $\alpha$ is to apply this procedure when $\alpha = \beta$.

You want to make $\alpha=(12)(345)(78)$ ‘look like’ $\beta=(162)(35)(89)$. First write them with matching cycle structures; there are several ways to do this, and it doesn’t matter which you choose, so I’ll rewrite $\beta$ as $(35)(162)(89)$. Now you want $\tau$ to ‘translate’ between the two permutations. The way I’ve lined them up, $$\begin{align*}&(12)(345)(78)\\&(35)(162)(89)\;,\end{align*}\tag{1}$$ you can see that $\tau$ needs to translate $1$ to $3$ and $2$ to $5$, so that $\alpha$’s $(12)$ turns into $\beta$’s $(35)$, and so on. As Jack Schmidt suggested, this amounts to writing $$\tau=\pmatrix{1&2&3&4&5&7&8\\3&5&1&6&2&8&9}\tag{2}$$ in two-line notation. However, this is clearly incomplete: it’s missing $6$ and $9$ on the top line and $4$ and $7$ on the bottom line. Thus, $(1)$ needs to be completed to $$\begin{align*}&(12)(345)(78)(6)(9)\\&(35)(162)(89)(4)(7)\;,\end{align*}$$ thereby allowing $(2)$ to be completed to $$\tau=\pmatrix{1&2&3&4&5&7&8&6&9\\3&5&1&6&2&8&9&4&7}\;.$$

In cycle notation this is $\tau=(13)(25)(46)(789)$, the one that you actually found.

This works because $\tau^{-1}$ in effect just renames the integers $1$ through $9$, so that $3$ is temporarily called $1$, $5$ is temporarily called $2$, and so on. Thus, when you apply $\tau^{-1}$, you’re translating from $\beta$’s language to $\alpha$’s; then you perform $\alpha$ and apply $\tau$, thereby translating back from $\alpha$’s language to $\beta$’s. The net result is that you’ve performed $\beta$. Consider $6$, for instance: $\tau^{-1}$ translates it to $4$, which $\alpha$ then carries to $5$, which $\tau$ translates back to $2$, exactly where $\beta$ would have put it in the first place.