This term I have taken my first course in formal group theory and as with many of my peers, I have problems with the Symmetric Group. It just doesnt make sense to me. My current thoughts are because I am not supposed to write out the elements as I do with the dihedral group. Note: This is some very scratchy notes for my own sake, don't take this as gospel. I will assume that you have done some group theory before, so probably read that before you read this.
Firstly let us define what we mean by conjugate,
Definition (Conjugate). Suppose \(G\) is a group and \(x, g \in G\), then the conjugate of \(g\) by \(x\) is \(xgx^{-1}\)
Now we further this by saying that if we have some \(g, h \in G\), and there is some \(x \in G\) such that \(xgx^{-1} = h\) we say that \(g\) and \(h\) are conjugate in \(G\). We now define a relation \(\sim\) in \(G\) by \(g \sim h\) if \(g\) and \(h\) are conjugate.
Lemma 1. Suppose \(G\) is a group and the relation \(\sim\) is as we defined above. Then, \(\sim\) is an equivalence relation.
Proof. We aim to prove that \(\sim\) is reflexive, symmetric and transitive.
Naturally from equivalence relation we reach equivalence classes, these are just a partition of \(G\). We call these the conjugacy classes of \(G\). Hence for some \(g \in G\) the conjugacy class is,
We aren't interested in talking about the conjugacy classes of abelian groups because for all \(a \in G\) where \(G\) is abelian, \([a] = \{a\}\). Hence we now only consider non-abelian groups, in general \(S_n\) is one of them. We can define \(S_n\) as the group of permutations of the set \(S = \{1, 2, \dots, n\}\) or the group of bijections \(\sigma : S \to S\). The interesting thing about \(S_n\) is how we can consider cycles of the elements; we call these \(k\)-cycles.
Lemma 2. Let \(\sigma, \tau \in S_n\), where \(\sigma\) is the \(k\)-cycle \(\begin{pmatrix} a_1 & a_2 & \dots & a_k \end{pmatrix}\). Then,
Proof. Consider some \(\tau(a_i)\), such that \(1 \le i \le k\). Then \(\tau^{-1}\tau(a_i) = a_i\) and \(\sigma(a_i) = a_{i+1 \mod k}\). We now can say that \(\tau\sigma\tau^{-1}(\tau(a_i)) = \tau(a_{i+1\mod k})\). Now take some \(j \in \{1, \dots, n\}\) such that \(j \ne a_i \) for any \(i\). We now can say that \(\alpha(j) = j\) since \(j \not\in \alpha\). Therefore, \(\tau\alpha\tau^{-1}(\tau(j)) = \tau(j)\). This shows us that \(\tau\alpha\tau^{-1}\) fixes anything not of the form \(\tau(a_i)\) and so we get the required result. \(\blacksquare\)
This proofs is slightly verbose, but it follows the following argument. We aim to show that under \(\tau\sigma\tau^{-1}\) each element of \(\sigma\) is shifted by one and have \(\tau\) applied to them. Then we aim to show that every other element of \(\sigma\), the fixed points that we don't write in cycle notation, are mapped to themselves and are also fixed. Hence we get the cycle in the Lemma.
The final piece of the puzzle before we can talk about the conjugacy classes is cycle types. We define them as follows,
Definition (Cycle Type). For any permutation \(\sigma \in S_n\) we can write \(\sigma\) as a product of disjoint cycles. Suppose we write \(\sigma\) in this way where we have cycles \(k_1, k_2 \dots, k_\ell\) where we have an increasing sequence, \(k_1 \ge k_2 \ge \dots \ge k_\ell\) (including the fixed points of length \(1\)). Then the cycle type is this sequence, \((k_1, k_2, \dots, k_n)\).
Now here is the theorem we have been working towards,
Theorem 3. The conjugacy classes of \(S_n\) is determined by the cycle types. That is, if \(\sigma\) and \(\tau\) have the same cycle type, then they are conjugate and if \(\sigma\) and \(\tau\) were conjugate they have the same cycle type.
Proof. We have two different statements to prove here, firstly if \(\sigma\) and \(\tau\) have the same cycle type, then they are conjugate and secondly, the other statement of if \(\sigma\) and \(\tau\) were conjugate they have the same cycle type. We shall prove the first statement. Let \(\sigma, \rho \in S_n\) both be of the cycle type, \((k_1, k_2,\dots, k_\ell)\) and we aim to show that they are conjugate in \(S_n\). We can write both as disjoint cycles,
where all the \(\alpha_i\)'s and \(\beta_i\)'s are \(k\)-cycles. Further we write,
and now we define a \(\tau\) such that we map between the two, that is \(\tau(a_{ij}) = b_{ij}\) for every \(1 \le i \le \ell\) and \(1 \le j \le k_i\). Then from Lemma 2, we have \(\tau\alpha_i\tau^{-1} = \beta_i\). So we can write,
Hence, they are conjugate and any two elements of the same cycle type are conjugate.
Now for the second part, we aim to prove that any conjugate of \(\sigma\) has the same cycle type as \(\sigma\). Suppose that \(\sigma\) has a cycle type of \((k_1, k_2,\dots, k_\ell)\), such that \(\sigma\) can be written as a product of disjoint cycles,
It now remains to prove that the \(\tau\alpha_i\tau^{-1}\)'s are disjoint cycles and they have the same cycle type as \(a_i\). This follows from the fact that Lemma 2 tells us that \(\tau\alpha_i\tau^{-1}\) is a \(k_i\)-cycle. Then for some \(i, j \in \{1, 2, \dots, \ell\}\) such that \(i \ne j\) we know that \(\alpha_i\) and \(\alpha_j\) are disjoint and as \(\tau\) is injective, we must have that \(\tau\alpha_i\tau^{-1}\) and \(\tau\alpha_j\tau^{-1}\) are disjoint. We have a product of disjoint cycles with cycle type \((k_1, k_2,\dots, k_\ell)\); hence any conjugate of \(\sigma\) has a cycle type of \((k_1, k_2,\dots, k_\ell)\). \(\blacksquare\)
and we are done. We have proved that any two elements in \(S_n\) are conjugate if and only if they have the same cycle type. To make this clear, here is an example consider \(S_3\), then I claim that \(\sigma = \begin{pmatrix} 1 & 2 & 3 \end{pmatrix}\) and \(\rho = \begin{pmatrix} 1 & 3 & 2 \end{pmatrix}\) are conjugate. This means,
and so using Lemma 2,
and so we see that we they are conjugate as we can construct a \(\tau\) such that \(\tau\sigma\tau^{-1} = \rho\) and more specifically we have \(\tau = \begin{pmatrix} 2 & 3 \end{pmatrix}\).