Exercise 13.4.9

Proof.

Let $\sigma \in S_n$ have cycle type $(k_1,k_2,...,k_l)$. Then $\sigma$ can be expressed uniquely as the product of disjoint cycles $\sigma ={\alpha }_1{\alpha }_2\cdots {\alpha }_l$, where ${\alpha }_i$ is a $k_i$-cycle. Let $\tau \in S_n$ such that $\rho =\mathit{\tau \sigma }{\tau }^{-1}$. Then:

$$\begin{array}{llll}\hfill \mathit{\tau \sigma }{\tau }^{-1}& =\tau {\alpha }_1{\alpha }_2\cdots {\alpha }_l{\tau }^{-1}=\tau {\alpha }_1{\tau }^{-1}\tau {\alpha }_2{\tau }^{-1}\cdots \tau {\alpha }_l{\tau }^{-1}={\alpha }_{\tau (1)}{\alpha }_{\tau (2)}\cdots {\alpha }_{\tau (l)}& \hfill & \end{array}$$ Since ${\alpha }_i$ and ${\alpha }_j$ are disjoint for $i,j\in \{1,2,...,l\}$, then $\tau {\alpha }_i{\tau }^{-1}$ and $\tau {\alpha }_j{\tau }^{-1}$ are also disjoint. Indeed, being disjoint means no number is moved by both ${\alpha }_i$ and ${\alpha }_j$, i.e., there is no $k$ such that ${\alpha }_i(k)\ne k$ and ${\alpha }_j(k)\ne k$. If $\tau {\alpha }_i{\tau }^{-1}$ and $\tau {\alpha }_j{\tau }^{-1}$ are not disjoint, then they both move some number $l$. Then $\tau {\alpha }_i{\tau }^{-1}(l)\ne l$ and $\tau {\alpha }_j{\tau }^{-1}(l)\ne l$, hence ${\alpha }_i{\tau }^{-1}(l)\ne {\tau }^{-1}(l)$ and ${\alpha }_j{\tau }^{-1}(l)\ne {\tau }^{-1}(l)$, which means that ${\tau }^{-1}(l)$ is moved by both ${\alpha }_i$ and ${\alpha }_j$. This is a contradiction. Therefore $\mathit{\tau \sigma }{\tau }^{-1}$ is the product of $\tau$-conjugates of disjoint cycles for $\sigma$, and these $\tau$-conjugates are disjoint cycles with the same respective lengths, i.e., $\mathit{\tau \sigma }{\tau }^{-1}$ has the same cycle type as $\sigma$. For the converse direction, suppose ${\sigma }_1$ and ${\sigma }_2$ have the same cycle type $(k_1,k_2,...,k_l)$. Then $${\sigma }_1=(a_1{a}_2...a_{k_1})(a_{k_1+1}{a}_{k_1+2}...a_{k_1+k_2})\cdots$$ and $${\sigma }_2=(b_1{b}_2...b_{k_1})(b_{k_1+1}{b}_{k_1+2}...b_{k_1+k_2})\cdots$$ where the cycles are disjoint. Let define the permutation $\tau \in S_n$ by $\tau (a_i)=b_i$ for all $i$. Then $\tau {\sigma }_1{\tau }^{-1}={\sigma }_2$, i.e., ${\sigma }_1$ and ${\sigma }_2$ are $\tau$-conjugate. □