# Prove $\sigma \in S_n$ has the same cycle type as $\sigma^{-1} \in S_n$

Let $\sigma \in S_n$.

We can then write $\sigma = s_1 \cdot \ldots \cdot s_k$ as a product of disjoint cycles $s_j$ for $1 \le j \le k$

Denote the cycle type of $\sigma$ as $x_1, \ldots ,x_k$ where $x_i \le x_j$ for $i \le j$.

I want to prove that $\sigma^{-1} \in S_6$ has the same cycle type as $\sigma$. That is their disjoint cycle decomposition consists of the same number of cycles of the same length.

For each of the cycles $s_j$ we can write the cycle in reverse, which imply that the resulting cycle decomposition is still disjoint and that $\sigma$ and $\sigma^{-1}$ cancel each other. However this argument is not very rigorous, and I don't really know how to write it down mathematically.

• Personally, I am quite happy with this argument. Perhaps I am hopelessly liberal. ☺ – Harald Hanche-Olsen Jan 3 '14 at 11:02
• You can reduce to the case of a cycle $s$ (because the inverse of $s_1 \dots s_k$ is $s_k^{-1}\dots s_1^{-1}$). In this case i think you can use the decomposition in transposition... – Sabino Di Trani Jan 3 '14 at 11:04
• Interesting point Joseph. – Shuzheng Jan 3 '14 at 11:05
• I believe that the usual proof to show that a permutation can be writtten as product of disjoint cycle would also go on to show that: such product is UNIQUE up to permutation. Once you got that, then your argument go through. In fact, the very fact that you can even talk about "cycle type of $\sigma$" implied that such product is already unique, otherwise it would not even make sense. – Gina Jan 4 '14 at 0:22

I'm not quite sure what your notation for permutation theory is, so let $x^{\sigma}$ be the image of $x$ under $\sigma$ and $\sigma^i$ be a composition of $i$ many $\sigma$'s
Let $\sigma =(a_1 \dots a_n) \in S_m$ be a $n$-cycle, and $x \in \{a_1, \dots , a_n\}$. Note that $x^{\sigma^j} = x^{\sigma^k}$ iff $j \equiv k \mod n$.
So $x^{\sigma^n} = x$ and $\sigma^{-1}$ has the following mapping, $x \mapsto x^{\sigma^{n-1}}$, $x^{\sigma^{n-1}} \mapsto x^{\sigma^{n-2}}$, $\dots$, $x^\sigma \mapsto x$. Hence $\sigma^{-1} = ( x x^{\sigma^{n-1}} x^{\sigma^{n-2}} \dots x^{\sigma})$ which has $n$ distinct elements. Therefore $\sigma$ and $\sigma^{-1}$ have the same cycle type.