Why are two permutations conjugate iff they have the same cycle structure?

Solution 1:

It's much like with linear transformations: conjugating a matrix amounts to a "change of basis", a translation from one basis to another, but similar matrices still represent the same linear transformation.

Conjugating by a permutation amounts to "translating" into new labels for the elements being permuted, so "similar permutations" (conjugate permutations) must represent the same underlying "shuffling" of the elements of the set, just under possibly different names.

Formally: Suppose that $\sigma$ and $\tau$ are permutations.

Claim. Let $\rho = \tau\sigma\tau^{-1}$ (multiplication corresponding to composition of functions). If $\sigma(i)=j$, then $\rho(\tau(i)) = \tau(j)$. In particular, the cycle structure of $\rho$ is the same as the cycle structure of $\sigma$, replacing each entry $a$ with $\tau(a)$.

Proof. $\rho(\tau(i)) = \tau\sigma\tau^{-1}\tau(i) = \tau\sigma(i) = \tau(j)$. QED.

Conversely, suppose that $\sigma$ and $\rho$ have the same cycle structure. List the cycles of $\sigma$ above the cycles of $\rho$, aligning cycles of the same length with one another. Now interpret this as the two-line presentation of a permutation, and call it $\tau$; then $\tau\sigma\tau^{-1}=\rho$ by the claim.

For example, if $\sigma=(1,3,2,4)(5,6)$ and $\rho=(5,2,3,1)(6,4)$, then write $$\begin{array}{cccccc} 1&3&2&4&5&6\\ 5&2&3&1&6&4 \end{array}$$ Then we let $\tau$ be the permutation $1\mapsto 5$, $3\mapsto 2$, $2\mapsto 3$, $4\mapsto 1$, $5\mapsto 6$, and $6\mapsto 4$. Then by the claim above, $\tau\sigma\tau^{-1}=\rho$. (Note. As Gerry Myerson notes, if we aren't working in all of $S_n$, we may not have $\tau$ in whatever subgroup we happen to be working in; so there is an implicit assumption for the "if" part that we are working in $S_n$).

Solution 2:

Warning: the permutations are conjugate $\bf in\ S_n$ if they have the same cycle structure. This may not be true in subgroups of $S_n$. For example, $A_4$ is the alternating group on 4 symbols, it consists of the even permutations in $S_4$. The elements $(1\ 2\ 3)$ and $(1\ 3\ 2)$ of $A_4$ have the same cycle structure, but they are not conjugate in $A_4$. That is, there are elements $g$ in $S_4$ such that $g^{-1}(1\ 2\ 3)g=(1\ 3\ 2)$, but there is no such element in $A_4$.