Exercise 4.3.21 ($\sigma \in S_n$ does not commute with any odd permutation if and only if the cycle type of $\sigma$ consists of distinct odd integers)

Proof.

(a)

Assume first that $\sigma \in A_n$ does not commute with any odd permutation. Let $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_r$ be the cycle decomposition of $\sigma$. Since the cycles ${\sigma }_i$ are disjoints, ${\sigma }_i{\sigma }_j={\sigma }_j{\sigma }_i$ for all indices $i,j$ (even if $i=j$ !), therefore for every $l\in [[1,r]]$, $$\sigma {\sigma }_l={\sigma }_1{\sigma }_2\cdots {\sigma }_r{\sigma }_l={\sigma }_l{\sigma }_1{\sigma }_2\cdots {\sigma }_r={\sigma }_l\sigma .$$

So $\sigma$ commutes with each individual cycle in its cycle decomposition. Since $\sigma$ does not commute with any odd permutation, all the cycles in the cycle decomposition of $\sigma$ are even, thus all these cycles must be of odd length. The cycle type of $\sigma$ consists of odd integers (included the fixed points with value $1$ in the cycle type).

If two distinct non trivial cycles have the same odd length $k>1$, say ${\sigma }_i=(a_1{a}_2\dots a_k)$ and ${\sigma }_j=(b_1{b}_2\dots b_k)$, where $i\ne j$, then ${\sigma }_i$ and ${\sigma }_j$ are two disjoint cycles. Put

$${\tau }_1=(a_1{b}_1),{\tau }_2=(a_2{b}_2),\dots ,{\tau }_k=(a_k{b}_k),$$

and $\tau ={\tau }_1{\tau }_2\cdots {\tau }_k$. Since all the elements in the list $(a_1,a_2,\dots ,a_k,b_1,b_2,\dots ,b_k)$ are distinct, the permutations ${\tau }_i$ are transpositions (not identity), and

$$\tau (a_i)=({\tau }_1{\tau }_2\cdots {\tau }_k)(a_i)=b_i(1\le i\le r).$$

Therefore

$$\tau (a_1{a}_2\dots a_k){\tau }^{-1}=(b_1{b}_2\dots b_k).$$

Hence $\tau {\sigma }_i{\tau }^{-1}={\sigma }_j$, and since $\tau ={\tau }^{-1}$, $\tau {\sigma }_j{\tau }^{-1}={\sigma }_i$. Moreover $\tau {\sigma }_l{\tau }^{-1}={\sigma }_l$ if $l\notin \{i,j\}$. Therefore

$$\begin{array}{llll}\hfill \mathit{𝜏𝜎}{\tau }^{-1}& =(\tau {\sigma }_1{\tau }^{-1})\cdots (\tau {\sigma }_i{\tau }^{-1})\cdots (\tau {\sigma }_j{\tau }^{-1})\cdots (\tau {\sigma }_k{\tau }^{-1})& \hfill & \\ \hfill & =(\tau {\sigma }_1{\tau }^{-1})\cdots (\tau {\sigma }_j{\tau }^{-1})\cdots (\tau {\sigma }_i{\tau }^{-1})\cdots (\tau {\sigma }_k{\tau }^{-1})& \hfill & \\ \hfill & ={\sigma }_1\cdots {\sigma }_j\cdots {\sigma }_i\cdots {\sigma }_k& \hfill & \\ \hfill & =\sigma ,& \hfill & \end{array}$$

so $\tau$ commutes with $\sigma$. Since $\sigma$ does not commute with any odd permutation, this shows that $\tau$ is even, thus $k$ is even, and so ${\sigma }_i$ has an even length, which is impossible by the first part of the proof. This shows that the cycles of $\sigma$ have distinct odd length.

It remains to prove that $\sigma$ cannot have two distinct fixed points. If $\sigma (a)=a$ and $\sigma (b)=b$, where $a\ne b$, then the transposition $\tau =(ab)$ satisfies $\tau \circ \sigma =\sigma \circ \tau$. This is impossible by hypothesis. So the cycle type of $\sigma$ contains $1$ at most one time.

The cycle type of $\sigma$ consists of distinct odd integers.

Conversely, assume that the cycle type of $\sigma$ consists of distinct integers. We want to show that $\sigma$ commutes only with the elements of the group $H$ generated by the cycles ${\sigma }_i$ in its cycle decomposition $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_r$. If $l_i$ is the length of ${\sigma }_i$, we can order this list such that $l({\sigma }_1)<l({\sigma }_2)<\cdots <l({\sigma }_r)$ (note that $l_1=1$ is a possibility, thus $\sigma$ has $0$ or $1$ fixed point).

$$H=⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r⟩.$$

Then $H$ is an abelian group with generators ${\sigma }_1,\dots ,{\sigma }_r$, so $\sigma \in H$ commutes with every element of $H$, so

$$\begin{array}{lll}\hfill H\subseteq C_{S_n}(\sigma ).& & \hfill \text{(1)}\end{array}$$

To prove equality, we compute the order of these two subgroups.

Note that every element $h\in H$ has a unique writing of the form

$$h={\sigma }_1^{i_1}{\sigma }_2^{i_2}\cdots {\sigma }_r^{i_r},0\le i_1<l_1,0\le i_2<l_2,\dots ,0\le i_r<l_r,$$

hence

$$\begin{array}{lll}\hfill |H|=|⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r⟩|=l_1{l}_2\cdots l_r.& & \hfill \text{(2)}\end{array}$$

Now we compute the cardinality of the conjugacy class ${𝒪}_{S_n}(\sigma )$ of $\sigma$. All elements of this conjugacy class have the same cycle type than $\sigma$. To build such an element we start from any arrangement $(a_1,a_2,\dots ,a_n)$ of the integers $1,2,\dots ,n$, among $n!$ possible arrangements, then we define $\tau ={\tau }_1{\tau }_2\cdots {\tau }_r$, where

$${\tau }_1=(a_1{a}_2,\dots a_{l_1}),{\tau }_2=(a_{l_1+1}{a}_{l_1+1}\dots a_{l_1+l_2}),\dots ,{\tau }_r=(a_{l_1+l_1+\cdots +l_{r-1}+1},\cdots ,a_{l_1+l_1+\cdots +l_r}),$$

so that $\tau$ is conjugate to $\sigma$. Since ${\tau }_1=(a_1{a}_2,\dots a_{l_1})=(a_2{a}_3,\dots a_1)=\cdots =(a_{l_1}{a}_1\dots a_{l_1-1})$, and similar equalities for ${\tau }_2,\dots ,{\tau }_r$, exactly $l_1{l}_2\cdots l_r$ arrangements map to the same $\tau$, therefore

$$|{𝒪}_{S_n}(\sigma )|=\frac{n!}{l_1{l}_2\cdots l_r}.$$

(This is a particular case of the formula of Exercise 33, with $m_i=l_i$ and $k_i=1$.) The orbit-stabilizer formula gives

$$|{𝒪}_{S_n}(\sigma )|=|S_n:C_{S_n}(\sigma )|=\frac{n!}{|C_{S_n}(\sigma )|},$$

therefore

$$\begin{array}{lll}\hfill |C_{S_n}(\sigma )|=l_1{l}_2\cdots l_r.& & \hfill \text{(3)}\end{array}$$

The equalities (1), (2) and (3) prove that

$$\begin{array}{lll}\hfill H=⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r⟩=C_{S_n}(\sigma ).& & \hfill \text{(4)}\end{array}$$

In other words, $\sigma$ commutes only with the elements of the subgroup generated by the cycles in its cycle decomposition.

Finally, assume that the cycle type of $\sigma$ consists of odd distinct integers. Then every permutation ${\sigma }_i$ in the cycle decomposition of $\sigma$ is even, so $\sigma \in A_n$. If $\tau$ is an odd permutation, then $\tau \notin H=⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r⟩$, so $\sigma$ does not commute with $\tau$. This shows that $\sigma$ does not commute with any odd permutation.

In conclusion, $\sigma \in S_n$ does not commute with any odd permutation if and only if the cycle type of $\sigma$ consists of distinct odd integers.

(b)

Let $𝒦$ be a conjugacy class in $S_n$, and $\sigma \in 𝒦$, so that ${𝒪}_{S_n}(\sigma )=𝒦$.

Suppose that $𝒦$ consists of two conjugacy classes in $A_n$. By Exercise 20, $\sigma$ does not commute with any odd permutation, and by part (a), the cycle type of $\sigma$ consists of distinct odd integers.

Conversely, if the cycle type of $\sigma$ consists of distinct odd integers, then by part (a), $\sigma \in S_n$ does not commute with any odd permutation. Then Exercise 20 shows that there are some elements in $𝒦$ which are not conjugate in $A_n$. Therefore The number $k$ of orbits for the action of conjugation of $A_n$ on $𝒦$ is greater than $1$. By Exercise 19, with $G=S_n$ and $H=A_n⊴S_n$,

$$k=|S_n:A_n{C}_{S_n}(\sigma )|>1.$$

Since $A_n\le A_n{C}_{S_n}(\sigma )$, where $A_n$ is a maximal subgroup of $S_n$, we obtain $A_n{C}_{S_n}(\sigma )=A_n$, thus $k=|S_n:A_n{C}_{S_n}(\sigma )|=2$, so $𝒦$ consists of two conjugacy classes in $A_n$.

In conclusion, a conjugacy class $𝒦$ consists of two conjugacy classes in $A_n$ if and only if the cycle type of an element of $𝒦$ consists of distinct odd integers.