4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Personally, I am quite happy with this argument. Perhaps I am hopelessly liberal. ☺ $\endgroup$ – Harald Hanche-Olsen Jan 3 '14 at 11:02
  • 2
    $\begingroup$ 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... $\endgroup$ – Sabino Di Trani Jan 3 '14 at 11:04
  • $\begingroup$ Interesting point Joseph. $\endgroup$ – Shuzheng Jan 3 '14 at 11:05
  • $\begingroup$ 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. $\endgroup$ – Gina Jan 4 '14 at 0:22
1
$\begingroup$

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.

This is essentially the "reversing" arguement and Joseph's idea takes care of the general case.

$\endgroup$
0
$\begingroup$

The inverse of a cycle is the cycle written backwards.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.