1
$\begingroup$

Does the reverse composition (or reverse multiplication) of permutations have the same cycle length? Let $p$ and $q$ be elements $S_5$: $q = (1 4 5 2)$, $p = (5 2) (1 3 4)$. Permutation multiplication (or composition) is not commutative, but $pq$ and $qp$ end up to be cycles. What's more is that they end up to have the same length. Can we generalize this? Is this a coincidence?

$pq = (2 3 4)$

$qp = (1 3 5)$

$\endgroup$
1
$\begingroup$

The permutations $pq$ and $qp$ are conjugate: There is an element $g$ in $S_5$ that gives us $pq=g(qp)g^{-1}$, for instance $g=p$.

$pq=p(qp)p^{-1}$ in particular they have cycles of equal length.

$\endgroup$
  • $\begingroup$ Thank you! So we have $gpq=qpg$ for some $g$ with cycle length $m$. If $pq$ has cycle length $k$, then $qp$ has cycle length $k$ too? Why exactly? $\endgroup$ – user198044 Oct 10 '18 at 3:15
  • 1
    $\begingroup$ @JackBauer Because the permutations of $pq$ and $qp$ are conjugate $\endgroup$ – Key Flex Oct 10 '18 at 3:36
  • $\begingroup$ My question precisely is why conjugation implies the same length. Never mind Key Flex. I found a question that answers: If y is a cycle of length r, show that σyσ−1 is also a cycle of length r. $\endgroup$ – user198044 Oct 10 '18 at 3:37
0
$\begingroup$

Any of the following facts, arranged in ascending order of strength can prove that for any permutations $p$ and $q$ such that the permutations $pq$ and $qp$ are cycles, $pq$ and $qp$ will be of the same length.

  1. Let $a$ and $b$ be cycles. If they are conjugate, then they have the same length.

  2. Let $a$ be a cycle and $b$ be a permutation. If they are conjugate, then $b$ is also a cycle and has the same length as $a$.

  3. Let $a$ and $b$ be permutations. If they are conjugate, then they have the same cycle type, where $a$ and $b$ are defined to have the same cycle type (Proofwiki: Cycle Type) if they have the same number of cycles of equal length.

Proof that 2 $\implies$ 1: Since $b$ is a cycle, $b$ is a permutation. By 2, $b$ has the same length as $a$.

Proof that 3 $\implies$ 2: Since $a$ is a cycle, $a$ is a permutation. By 3, $a$ and $b$ have the same cycle type. Then $b$ is a cycle and has the same length as $a$.

Proof of 3: See Proofwiki: Conjugate Permutations have Same Cycle Type

Alternatively, we can prove $2$ without $3$ as done here: If $y$ is a cycle of length $r$, show that $\sigma y \sigma^{-1}$ is also a cycle of length $r$.

$\endgroup$
0
$\begingroup$

As mentioned earlier by @Key Flex that they are conjugates, so it suffices to show that conjugates have the same length. Also, one of the other important information while talking about permutations is that any permutation can be written as the product of disjoint cycles.

So given a permutation q it can be written as $c_1c_2\dots c_k$ where the $c_i$'s are disjoint cycles.

$pqp^{-1}$ is just $(pc_1p^{-1})(pc_2p^{-1})\dots (pc_kp^{-1})$. Thus if we show that cycles under conjugation have the same length we are done.

Claim: $\sigma (a_1, a_2, \dots a_k)\sigma^{-1}$ = $(a_\sigma(1), a_\sigma(2), \dots a_\sigma(k))$

It is same as showing this

$\sigma (a_1, a_2, \dots a_k)$ = $(a_\sigma(1), a_\sigma(2), \dots a_\sigma(k))\sigma$

For some $a_i$, LHS gives $\sigma(a_{i+1})$ so does the RHS. For $x \neq a_i$, check that both sides give x. Thus the conjugation of a cycle returns another cycle of the same length and the rest follows.

$\endgroup$
0
$\begingroup$

A little advanced:

Conjugation preserves order: $x$ has the same order as $gxg^{-1}$. Then order of a cycle equals the length of the cycle.

A little more advanced:

Automorphisms preserve order. $\varphi: S_5 \to S_5, \varphi(x)=gxg^{-1}$, conjugation is an automorphism.

$\endgroup$

Your Answer

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