Why is the conjugacy class of an element in a symmetric group the same as the set of all elements with the same cycle type?

My question extends my question from a previous post. I now understand orbits and stabilizers a little better, but I still don't get why the conjugacy class of an element in a symmetric group is the same as the set of all elements with the same cycle type.

Based on this proofs website, I get that $a \tau a^{-1} = a (i_1i_2i_3 \cdots i_k) a^{-1} = (a i_1a^{-1})(ai_2a^{-1})(ai_3a^{-1}) \cdots (ai_ka^{-1})$. I don't understand how this is equivalent to $i_{a(1)}i_{a(2)}i_{a(3)} \cdots i_{a(k)}$ as the website suggests. I see that the implication $\tau(i) = j \implies a\tau a^{-1}(a(i)) = a(j)$ is necessary to understanding how $(a i_1a^{-1})(ai_2a^{-1})(ai_3a^{-1}) \cdots (ai_ka^{-1}) = i_{a(1)}i_{a(2)}i_{a(3)} \cdots i_{a(k)}$, but I don't understand how exactly it is necessary.

More specifically, I understand that $\tau(i) = j \implies a\tau a^{-1}(a(i)) = a(j)$ (because $a\tau a^{-1}(a(i)) = a\tau (a^{-1}a)(i) = a\tau(i) = a(j)$) and that $a\tau a^{-1}$ maps $a(i)$ to $a(\tau(i)) = a(j)$, and even that $a(i)$ lies to the left of $a(\tau(i))$ and $i$ lies to the left of $\tau(i)$. I don't see how showing all this demonstrates that "the cycle decomposition of the permutation $a \tau a^{-1}$ can be obtained from $\tau$ by replacing each $i$ in the cycle decomposition of $\tau$ with a(i)."

May someone explain why the proof demonstrates the above statement?

Thanks in advance.

Solution 1:

Given a function $\,f: X \to Z\,$ and bijections $\,\alpha: X \to Y\,$ and $\,\beta: Z \to W.\,$ Suppose $\,f(x) = z,\,$ while $\,\alpha(x) = a\,$ and $\,\beta(z) = b.\,$ Then $\,g: Y \to W\,$ defined by $\, g := \beta\,\circ f\,\circ\,\alpha^{-1}\,$ satisfies $\, g(a) = b.\,$

\begin{array} &X\xrightarrow{f} Z \\ \downarrow{\alpha}\quad\downarrow{\beta}\\ Y \xrightarrow{g} W \end{array}

Now suppose we have a sequence of functions $\,f_i: X_i \to X_{i+1}\,$ and bijections $\,\alpha_i: X_i \to Y_i.\,$

\begin{array} &X_1\xrightarrow{f_1} &X_2\xrightarrow{f_2} &\dots\; \to X_{n-1} \xrightarrow{f_{n-1}} X_n \\ \downarrow{\alpha_1} & \downarrow{\alpha_2} &\vdots \quad \quad \quad \downarrow{\alpha_{n-1}} \quad\downarrow{\alpha_n}\\ Y_1 \xrightarrow{g_1} & Y_2\xrightarrow{g_2} &\dots\; \to Y_{n-1} \xrightarrow{g_{n-1}}\, Y_n \\ \end{array}

Apply the previous reasoning to $$f_1(x_1) = x_2,\; f_2(x_2) = x_3,\;\dots,\;f_{n-1}(x_{n-1}) = x_n. $$ Thus, suppose $\,\alpha(x_i) = a_i\,$ for all $i$. Define the composite functions $\,g_i : Y_i \to Y_{i+1}\,$ by $\,g_i := \alpha_{i+1} \circ f_i \circ \alpha_i^{-1}.\,$ Thus, $\,g_i(a_i) = a_{i+1}\,$ for all $\,i.$

Apply this result in the case of permutations $\,\sigma: X \to X\,$ and $\, \tau := \beta\,\circ \sigma\,\circ\,\alpha^{-1}\,$ where $$f_i = \sigma,\quad g_i = \tau,\quad \alpha_i = \alpha,\quad X_i = Y_i = X $$ for all $\,i.\,$ Now, suppose that $\,x_1 = x_n.\,$ By the definition of orbit and cycle, (consult Wikipedia article Cyclic permutation), the orbit cycle for $\,\sigma\,$ and element $\,x_1\,$ is $\,(x_1 x_2 \dots x_{n-1})\,$ while the corresponding orbit cycle for $\,\tau\,$ and element $\,a_1\,$ is $\,(a_1 a_2 \dots a_{n-1}).\,$ This proves that any permutation which is a cycle is conjugated by any bijection to a cycle of the same length, hence, the same cycle type. Same result applies for a product of disjoint cycles and thus, the conjugate of any permutation by any bijection must have the same cycle type.

Conversely, given two permutations on a set $\,X\,$ with the same cycle type. For example, let $$\sigma = (x_1 x_2 \dots x_i)\,(x_{i+1} x_{i+2} \dots x_j)\, \dots\, (x_k x_{k+1} \dots x_n), $$ where $\, X = \{x_1,x_2,\dots,x_n\}\,$ and we include $1$-cycles. Let $$\tau = (a_1 a_2 \dots a_i)\,(a_{i+1} a_{i+2} \dots a_j)\, \dots\, (a_k a_{k+1} \dots a_n), $$ where $\, X = \{a_1,a_2,\dots,a_n\}\,$ and we include $1$-cycles. Define $\,\alpha: X \to X\,$ by $\,\alpha(x_i) = a_i\,$ for $\,i = 1,2,\dots,n.\,$ This is well defined since all of the $\,x_i\,$ are distinct. It is one-to-one since all of the $\,a_i\,$ are distinct and it is onto since $\, X = \{a_1,a_2,\dots,a_n\}.\,$ Thus, $\,\alpha\,$ is a permutation and $\,\tau := \alpha \circ \sigma \circ \alpha^{-1}.\,$

This proves that the conjugacy class of a given permutation is exactly the set of permutations of the same cycle type as the given permutation.

Note carefully that this characterization of conjugacy classes is not necessarily true in every subgroup of the full permutation group since the conjugating permutation may not be in the subgroup itself. For example, it is not true for the alternating subgroup. An extreme example is the subgroup consisting of the identity and a single transposition. Here the conjugacy class of the transposition is the singleton of the transposition itself and not all of the transpositions even though they all have the same cycle type. A better example is the suhgroup which is generated by two disjoint transpositions. Here again, all of the conjugacy classes are singletons since the group is abelian which implies that the conjugacy class of a single transposition is a singleton even though the other transposition has the same cycle type.