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$.

  • $\begingroup$ The oddness of the $\lambda,\mu,\ldots,\nu$ doesn't matter, does it? $\endgroup$ – 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 :)

  • $\begingroup$ 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. $\endgroup$ – Jxt921 Jul 18 '16 at 20:02
  • 1
    $\begingroup$ ok, do you remember the theorem that says that cyclic representation is unique???? do you remember up to what it is unique ? $\endgroup$ – Jorge Jul 18 '16 at 20:42
  • $\begingroup$ yes, I know it is unique up to permutation of the cycles. $\endgroup$ – Jxt921 Jul 18 '16 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$ – 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}$


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.