Conjugacy Classes of the Symmetric Group I
Recall that an integer partition is simply a list of non-increasing integers. For example, 
is a partition.
For any partition 
, let 
denote the number of parts of of length 
. In our example. 
, 
, 
, 
, 
. etc…
Let us define:
To any permutation 
we may associate an integer partition by reading off the lengths of the disjoint cycles. For example, the permutation 
has cycle type 
.
One may convince oneself that 
counts the number of permutations in 
of cycle type . For example
Indeed there are three permutations with cycle type 
, namely:
Note that there are 
ways we could have arbitrary placed the numbers one through 4 inside the brackets to get the right “shape”. However, the vast majority of these do not conform to our convention for writing down the cycle type of a permutation. For example:
are all wrong, because the smallest element of each cycle doesn’t come first.
While:
are wrong because the cycles are not properly ordered by the size of their first elements. The remaining posibilities:
suffer from both types of fault. For every “correct” way of writing down the cycle type of a permutation, there are precisely 
“malformed” variations:
The purpose of this post is to show that two permutations and 
are conjugate in the symmetric group, if and only if they have the same cycle type.
To this end we introduce the notion of a “standard” permutation of given shape. For example if 
then the “standard” permutation of shape is:
Any permutation of shape can be conjugated to the standard permutation 
. To see this, let 
where the 
are the individual cycles, and let 
denote the smallest element in the 
th cycle.
Now, each 
can be written in the form 
for some 
and some 
.
Similarly, each can be written in the form 
where the cyclic permutation is applied 
times.
Let 
be the permutation which sends to (-times). We have:
Thus having the same cycle type is a sufficient condition for two permutations to be conjugate. To see that it is also a necessary condition, lets look at the eigenvalues the standard permutation of shape . For example, if 
then 
(using hexadecimal).
The important point, is that the standard permutation is block diagonal. Thus to diagonalize the matrix, we diagonalize the individual blocks separately.
But the individual blocks are cyclic permutations, which we know how to diagonalize.
For our example permutation the eigenvalues, with multiplicity, are given by:
Here
is a primitive fourth root of unity, and 
is a primitive cube root of unity.
In fact, one can read the cycle type of a permutation directly from its eigenvalues. The algorithm is as follows. Find the largest 
such that an th root of unity appears in the list of eigenvalues with nonzero multiplicity. Suppose it appears with multiplicity . Your permutation has cycles of length . Now let be a primitive -th root of unity and remove copies of each of 
from the list of eigenvalues. Repeat.
Since two permutations cannot be conjugate in 
, let alone in in unless they have the same eigenvalues, we see that having the same cycle type is also a necessary condition for two permutations to be conjugate.