# Let $\sigma,\tau \in S_n$. Prove that $\sigma \tau$ and $\tau \sigma$ have the same cycle type.

Let $\sigma,\tau \in S_n$. Prove that $\sigma \tau$ and $\tau \sigma$ have the same cycle type.

I was thinking that you could rewrite $\sigma=g_1\cdots g_k$ with $g_i$ disjoint cycles and $\tau=h_1\cdots h_l$ with $h_i$ disjoint cycles. But I don't know what to do next, as $g_i$ and $h_j$ doesn't have to be disjoint.

Edit: Could I prove it like this ?

We can write $σ$ in disjoint cycles: $σ=σ_1...σ_r$ with lenghts $l_1,...l_r$. So you get: $σ_1=(a_1...a_{l_1}), σ_2=(b_1...b_{l_2}), σ_3=...$.

Which gives: \begin{align*} τστ^{-1}&=τσ_1...σ_rτ^{-1}\\ &=τσ_1(τ^{-1}τ)σ_2(τ^{-1}τ)...(τ^{-1}τ)σ_rτ^{-1}\\ &=τ(a_1...a_{l_1})τ^{-1}τ(b_1...b_{l_2})τ^{-1}τ...τσ_rτ^{-1}\\ &=(τ(a_1)...τ(a_{l_1}))(τ(b_1)...τ(b_{l_2}))...τσ_rτ^{-1}\\ \end{align*}

Therefore $σ$ and $τστ^{-1}$ have the same cycle type. So $τσ$ and $στ$ have the same cycle type.

-

Hint: they are conjugate elements of the group.

-
My book introduces conjugates in the next chapter. – 90intuition Mar 19 '13 at 15:59

First, it suffices to prove that $\tau\sigma\tau^{-1}$ and $\sigma$ have the same cycle type.

Suppse one of the cycles in $\sigma$ is $(a_1,a_2,\dots,a_n)$. Then, try to prove that there is a corresponding cycle in $\tau\sigma\tau^{-1}$ that is $\big(\tau(a_1),\tau(a_2),\dots,\tau(a_n) \big)$.

If $\sigma$ sends $a_1$ to $a_2$, what does $\tau\sigma\tau^{-1}$ send $\tau(a_1)$ to?

-
Specifically, it suffices to show $\alpha\beta\alpha^{-1}$ and $\beta$ have the same cycle type, because then one can set $\beta=\tau\sigma$ and $\alpha=\sigma^{-1}$ to conclude $\sigma\tau$ and $\tau\sigma$ have the same cycle type. Which is also the hint of Robert's answer. (Sorry for the anachronistic comment.) – whacka Aug 2 '15 at 21:06

First consider the case that $\tau$ is a single cycle, say $\tau = (i_1,i_2,\ldots,i_k)$. You should be able to compute $\sigma\tau$ and $\tau\sigma$ explicitly in this case. Then figure out how to generalize when $\tau$ is a product of disjoint cycles: for this try inserting copies of $\sigma^{-1}\sigma$ in various places of the product $\sigma\tau\sigma^{-1}$ when $\tau$ is written as a product of disjoint cycles.

-
This one did it ! Thanks – 90intuition Mar 19 '13 at 20:09
Let $σ=σ_1...σ_r$ with $σ_1=(a_1...a_{l_1}), σ_2=(b_1...b_{l_2}), σ_3=...$. Then you get: \begin{align*} τστ^{-1}&=τσ_1...σ_rτ^{-1}\\ &=τσ_1(τ^{-1}τ)σ_2(τ^{-1}τ)...(τ^{-1}τ)σ_rτ^{-1}\\ &=τ(a_1...a_{l_1})τ^{-1}τ(b_1...b_{l_2})τ^{-1}τ...τσ_rτ^{-1}\\ &=(τ(a_1)...τ(a_{l_1}))(τ(b_1)...τ(b_{l_2}))...τσ_rτ^{-1}\\ \end{align*} – 90intuition Mar 19 '13 at 20:38
I hope that this is what you meant. – 90intuition Mar 19 '13 at 20:38

In the light of @Robert's answer, if $x$ and $y$ are two permutations of a set $\Omega$, and $x=(\xi_1,\xi_2,...,\xi_k)$ then $$y^{-1}xy=(\xi_1^y,\xi_2^y,...,\xi_k^y)$$ In fact, in the product $xy$ we expect to have the result of first applying the mapping $x$ and then the mapping $y$. This is what @Robert's trying to tell you.

-
Nice! $\quad \ddot \smile \quad +1 \quad$ – amWhy Mar 20 '13 at 0:15

Suppose that $\sigma \tau=(a_1a_2\cdots a_k)(b_1b_2\cdots b_{\lambda})\cdots$.
Then $\tau\sigma(\tau(a_i))=\tau(\sigma\tau(a_i))=\tau(a_{i+1})\ldots$

Show that $\tau\sigma=\left(\tau(a_1)\tau(a_2)\cdots\tau(a_k)\right)\left(\tau(b_1)\tau(b_2)\cdots\tau(b_{\lambda})\right)\cdots$.

-