Understand a part of the proof about permutations in a symmetric group on $n$ elements

Let $\sigma$ be an even permutation in $S_n$($\sigma \in A_n$). Assume $\sigma = \tau\sigma\tau^{-1}$ for some $\tau \in S_n$ and assume that the type of $\sigma$ consists of distinct odd integers.

Write $\sigma$ in cycle notation(including cycles of length $1$):

$\sigma = (a_1...a_{\lambda})(b_1...b_{\mu})...(c_1...c_{\nu})$

We know that

$\tau\sigma\tau^{-1} = (\tau^{-1}(a_1)...\tau^{-1}(a_{\lambda}))(\tau^{-1}(b_1)...\tau^{-1}(b_{\mu}))...(\tau^{-1}(c_1)...\tau^{-1}(c_{\nu}))$ (this is proved previously in my book as a lemma )

Since $\lambda, \mu, ..., \nu$ are odd and distinct, we have(since all cycle lengths are distinct):

$(\tau^{-1}(a_1)...\tau^{-1}(a_{\lambda})) = (a_1...a_{\lambda})$

$(\tau^{-1}(b_1)...\tau^{-1}(b_{\mu})) = (b_1...b_{\mu})$

$\ \ \ \ \ \ ... \ \ \ \ \ \ ... \ \ \ \ \ \ ... \ \ \ \ \ \ ... \ \ \ \ \ \$

$(\tau^{-1}(c_1)...\tau^{-1}(c_{\nu})) = (c_1...c_{\nu})$

This is were I'm a bit lost. An author of my book then says that it follows that

$\tau = (a_1...a_{\lambda})^r(b_1...b_{\mu})^s...(c_1...c_{\nu})^t$

but I cannot see why it follows. I tried playing around with the equality

$(\tau^{-1}(a_1)...\tau^{-1}(a_{\lambda})) = (a_1...a_{\lambda})$

seeing what I can extract from it, but to no avail. All I know that $\tau^{-1}(a_i) \in \{a_1, ..., a_{\lambda} \}$, and if $\tau^{-1}(a_i) = a_j$, then $\tau^{-1}(a_{i+1}) = a_{j+1}$ given $i, j \leq \lambda$.

• The oddness of the $\lambda,\mu,\ldots,\nu$ doesn't matter, does it? – darij grinberg Sep 11 '16 at 22:36

Suppose you have a cycle $C=(c_1,c_2\dots c_n)$ of $\sigma$. then after conjugating it you must get another cycle of the same size. Of course, since $\sigma$ is equal to its conjugate and all of its cycles have different lengths, we conclude $C$ is equal to its conjugate.

And therefore, by your lemma we have $\tau^{-1}(c_1),\tau^{-1}(c_2)\dots \tau^{-1}(c_n)$ is a cyclic permutation of $c_1,c_2\dots c_n$.

So $\tau$ restricted to $c_1,c_2\dots c_n$ is a cyclic permutation, applying this to every cycle yields the desired result.

PS: This was problem $7$ of the $2015$ OIMU, totally nailed it :)

• Sorry, but I don't see it. You claim $\tau^{-1}(c_1), \tau^{-1}(c_2), ..., \tau^{-1}(c_n)$ is a cyclic permutation of $c_1, c_2, ..., c_n$. I don't understand why? Not intuitively, I need a rigorous proof. Please, expand your answer. You might think those are subtleties, but to me they are not. – Jxt921 Jul 18 '16 at 20:02
• ok, do you remember the theorem that says that cyclic representation is unique???? do you remember up to what it is unique ? – Jorge Jul 18 '16 at 20:42
• yes, I know it is unique up to permutation of the cycles. – Jxt921 Jul 18 '16 at 22:16
• so then , since $(\tau^{-1}c_1\dots \tau^{-1}c_n)$ is the same cycle as $(c_1,c_2\dots c_n)$ we conclude that the terms in the first cycle are obtained by taking the elements in the second cycle and rotating them. – Jorge Jul 18 '16 at 23:48

I don't think it's that trivial. First, we need to prove for nontrivial cycles that if

$(a_1...a_t) = (a'_1...a'_t)$

in $S_n$, then

$\forall i \in \{1, ..., t \} \ \ a_i = a'_j$, where $j \in \{1, ..., t \}$ and $j \equiv i + r \mod t$ for some fixed $r$.

We use induction here: we know that

$a_1 = a'_s$ for some $s \in \{1, ..., t \}$. So, $s = 1 + j$, and we defined $r$ to be an elements of $\{0, ..., t \}$ such that $r =s-1$.

So, we induct on the number $i$ of $a_i$(the step $i = 1$ is follows from our definition of $r$):

$a_i = (a_1...a_t)(a_{i-1}) = (a'_1...a'_t)(a'_m) = a'_j$ $m \equiv i-1 + r \mod t$ and $j \equiv m + 1 \mod t$, so $j \equiv i + r \mod t$.

Now we apply the result to the equality

$(a_1...a_{\lambda}) = (\tau^{-1}(a_1)...\tau^{-1}(a_{\lambda}))$

If $a_1 = \tau^{-1}(a_{1+r}), 0 \leq r \leq \lambda$, then

$a_i = \tau^{-1}(a_l), l \equiv i + r \mod \lambda$

We claim that $\tau^{-1}$ acts the same way on $\{a_1, ..., a_{\lambda} \}$ as $(a_1...a_{\lambda})^r$. And it is indeed true!

The same follows from other equalities for nontrivial cycles.

Now, the decomposition of $\sigma$ may contain a trivial cycle $(f)$, where $(\tau^{-1}(f)) = (f)$ tells us nothing. Then again, $f$ is the unique fixed point of $\sigma$, then so is $\tau^{-1}(f)$, and they are equal.

So, $\tau^{-1} = (a_1...a_{\lambda})^r(b_1...b_{\mu})^s...(c_1...c_{\nu})^t$

$\tau$ would have the same form expect it will be

$(a_1...a_{\lambda})^{(\lambda-1)r}(b_1...b_{\mu})^{(\mu - 1)s}...(c_1...c_{\nu})^{(\nu-1)t}$.

It can easily be checked that

$(a_1...a_{\lambda})^r(b_1...b_{\mu})^s...(c_1...c_{\nu})^t(a_1...a_{\lambda})^{(\lambda-1)r}(b_1...b_{\mu})^{(\mu - 1)s}...(c_1...c_{\nu})^{(\nu-1)t} = e_{S_n}$