Spent a long time trying to prove that if two permutations have the same cycle structure, then they are conjugate.

Wondering if this proof is sound, I understand there are other proofs (simpler ones) but I don't really understand them. I've managed to come up with this proof though I'm not fully convinced would appreciate if someone could let me know.

I've managed to prove that any two $k$ cycles are conjugate, from now on I will just refer to this as lemma 1. We also know that every element in $S_n$ is a product of disjoint cycles and disjoint cycles commute in $S_n$.

Now consider two permutations $ \alpha, \tau \in S_n$ such that $\alpha = a_1 a_2\cdots a_k$ and $\tau = b_1 b_2\cdots b_k$ where $a_i,b_i$ are cycles of length $i$. Now from lemma 1 we know that any two k cycles are conjugate thus one can write $\rho_1a_1\rho_1^{-1} = b_1$ and $\rho_2a_2\rho_2^{-1} = b_2$ all the way up to $\rho_ka_k\rho_k^{-1} = b_k $.

If one considers the following product keeping in mind that all these elements commute as they belong to $S_n$: \begin{align}(\rho_1a_1\rho_1^{-1})(\rho_2a_2\rho_2^{-1}) \cdots (\rho_ka_k\rho_k^{-1}) &= (\rho_1\rho_2\cdots\rho_k)(a_1a_2\cdots a_3)(\rho_1\rho_2\cdots\rho_k)^{-1} \\ &= \alpha\sigma\alpha^{-1} \\ &= b_1b_2\cdots b_k \\ &= \tau \end{align}

Where $\alpha$ is the product of the $\rho$ elements.

Thus the permutations $\sigma$ and $\tau$ are conjugate


In your question you've mentioned that you are familiar with the fact that

$$\pi(i_1\cdots i_k)\pi^{-1} = (\pi(i_1)\cdots\pi(i_k))$$

You can derive the general case with a trick (also keep in mind that $\mathrm{id} = \pi\pi^{-1}=\pi^{-1}\pi$):

\begin{align} \delta & = \pi\sigma\pi^{-1}=\pi(i_1\cdots i_k)(j_1\cdots j_n) \cdots (f_1\cdots f_m)\pi^{-1} \\ & =\pi(i_1\cdots i_k)\pi^{-1}\pi(j_1\cdots j_n) \pi^{-1}\pi\cdots\pi(f_1\cdots f_m) \pi^{-1} \\ & = (\pi(i_1) \cdots \pi(i_k))(\pi(j_1)\cdots\pi(j_n))\cdots(\pi(f_1) \cdots \pi(f_m)) \end{align}

Hope that I've answered the question for you!

Sorry, but the proof you've added is not correct: you are assuming that $ρ_i$ and $a_i$ are disjoint so they commute, but that's not necessarily the case. Consider an example: $\pi\sigma\pi^{-1}=(12)(123)(12)$ (as $(12)=(12)^{-1}$). You can check yourself that the fact still holds.

  • $\begingroup$ Hi thanks for that I've changed the question somewhat but this is still relevant. I inserted my 'proof' though i think it is overly complicated and perhaps not correct. $\endgroup$ – Dead_Ling0 Nov 21 '19 at 16:33
  • $\begingroup$ @Dead_Ling0 I've updated my answer, sorry to say but your proof does have a flaw :( $\endgroup$ – GinGin3203 Nov 21 '19 at 16:50
  • $\begingroup$ are $\rho_i$ and $a_i$ not all members of $S_n$ ? $\endgroup$ – Dead_Ling0 Nov 21 '19 at 17:24
  • $\begingroup$ @Dead_Ling0 what do you mean by $S_n$? $S_n$ is the usual notation for the group of all permutations on the set $\{1,2,3...n\}$, and generally permutations do not commute (check it yourself, if you haven't already) and they commute if they are disjoint, so I think that maybe you are referring to something else $\endgroup$ – GinGin3203 Nov 21 '19 at 17:29
  • 1
    $\begingroup$ Ah, ok that makes sense damn it :( $\endgroup$ – Dead_Ling0 Nov 21 '19 at 17:55

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.