# Two permutations of $S_n$ are conjugate if and only if they have the same cycle structure: Looking for a proof based on actions.

The cycle structure of a permutation $$\sigma \in S_n$$ pops up naturally if we consider the action of $$\langle \sigma \rangle$$ as a group of permutations on the set $$I_n:=\{1,\dots,n\}$$ ("natural action"). By the Orbit-Stabilizer Theroem (O.S.T.), we get:

$$|O_\sigma(j)||\operatorname{Stab}_\sigma(j)|=o(\sigma), \forall j\in I_n \tag 1$$

where:

$$\operatorname{Stab}_\sigma(j):=\{\sigma^k\mid \sigma^k(j)=j\} \le \langle\sigma\rangle, \forall j\in I_n \tag 2$$

Now, given $$\alpha \in S_n$$, it is $$(\alpha\sigma\alpha^{-1})^k=\alpha\sigma^k\alpha^{-1}$$ (induction on $$k$$), so we get:

\begin{alignat}{1} \operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)&=\{\alpha\sigma^k\alpha^{-1}\mid (\alpha\sigma^k\alpha^{-1})(j)=j\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \alpha(\sigma^k(\alpha^{-1}(j)))=j\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \sigma^k(\alpha^{-1}(j))=\alpha^{-1}(j)\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \sigma^k \in \operatorname{Stab}_\sigma(\alpha^{-1}(j))\} \\ &=\alpha \operatorname{Stab}_\sigma(\alpha^{-1}(j)) \alpha^{-1}, \forall \alpha \in S_n,\forall j\in I_n\\ \tag 3 \end{alignat}

whence:

$$|\operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)|=|\operatorname{Stab}_\sigma(\alpha^{-1}(j))|, \forall \alpha \in S_n,\forall j\in I_n \tag 4$$

But since $$\forall \alpha \in S_n, o(\alpha\sigma\alpha^{-1})=o(\sigma)$$, $$(4)$$ implies (again by the O.S.T.):

$$|O_\sigma(\alpha^{-1}(j))|=|O_{\alpha\sigma\alpha^{-1}}(j)|, \forall \alpha \in S_n, \forall j\in I_n \tag 5$$

Therefore, for every $$\alpha \in S_n$$, the orbits induced by $$\langle \alpha\sigma\alpha^{-1}\rangle$$ and $$\langle \sigma\rangle$$ are pairwise of equal size. Moreover, if we denote by $$\mathcal{O}$$ the set of orbits, we have:

\begin{alignat}{1} |\mathcal{O}_{\alpha\sigma\alpha^{-1}}| &= \frac{1}{o(\alpha\sigma\alpha^{-1})}\sum_{j=1}^{n}|\operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)| \\ &=\frac{1}{o(\sigma)}\sum_{j=1}^{n}|\operatorname{Stab}_\sigma(\alpha^{-1}(j))| \\ &=\frac{1}{o(\sigma)}\sum_{i=1}^{n}|\operatorname{Stab}_\sigma(i)| \\ &=|\mathcal{O}_\sigma| \\ \tag 6 \end{alignat}

So, for every $$\alpha \in S_n$$, the natural actions of $$\langle\sigma\rangle$$ and $$\langle\alpha\sigma\alpha^{-1}\rangle$$ induce the same number of orbits of the same size in pairs, namely $$\sigma$$ and $$\alpha\sigma\alpha^{-1}$$ have the same cycle structure.

I would like to prove within this framework the converse implication (if two permutations have the same cycle structure, then they are conjugate), but I'm finding it harder. Could you give me some hint, please?

• The $\alpha$ in the conjugation $\alpha\sigma\alpha^{-1}$ can be thought of as a relabelling of the set. So, $\{i_1,\ldots,i_r\}$ is an orbit for $\sigma$ if and only if $\{\alpha(i_1),\ldots,\alpha(i_r)\}$ is an orbit for $\alpha\sigma\alpha^{-1}$. – Andrew Hubery Nov 26 '19 at 10:31
• Cf. Michael Artin, Algebra, Chapter 7. He gave a pretty easily understandable way to prove and explain this: relabeling indices. – xbh Nov 26 '19 at 11:27

2) Use the formula: $$\enspace\sigma\, (a_{i_1}\,\dots\,a_{i_k})\,\sigma^{-1}=(a_{\sigma (i_1)}\,\dots\,a_{\sigma (i_k)})$$.