1
$\begingroup$

I am following John B. Fraleigh -- A first course in abstract algebra. On page 90 of the 7th edition he say that

-- Decomposition of a cycle into products of transposition is possible since it is just the same as seeing that rearrangement of $n$ objects can he achieved by successively interchainging of pairs.

Now, I understand that rearrangement of $n$ objects can he achieved by successively interchainging pairs, but I cannot for the life of me see that this rationalizes cycle decomposition into compositions of transpositions.

Here are my attempts:

(1) Consider the cycle $(2,3,1) = (2,1)(2,3) = (2,1)\circ(2,3)$.

If I start with (1,2,3) and first transpose (2,3), and then (2,1) I get this:

Starting with :
(1,2,3),     then by transposing (2,3) gives
(1,3,2),     then by transposing (2,1) gives
(2,3,1)

Which seemed to work in some sense. But the same algorithm fails for

(2) Consider the cycle $(1,3,5,4) = (1,4)\circ(1,5)\circ(1,3)$

Starting with :
(1,3,4,5),     then by transposing (1,3) gives
(3,1,4,5),     then by transposing (1,5) gives
(3,5,4,1),     then by transposing (1,4) gives
(3,5,1,4)

But $(3,5,1,4) \neq (1,3,5,4)$, so the algorithm failed.

Can you help me to understand that the rearrangement of object by successive interchanges of pairs is the same as decomposing cycles into products of transpositions? A somewhat 'pictorial' explanation why these concepts are the same, would be best.

$\endgroup$
1
$\begingroup$

Remember that the transpositions refer to indices, not the numerical value. Additionally, note that transpositions are applied right-to-left—you already know this. So, consider the following diagram.

cycle decomposition

The cycle $(1, 3, 5, 4)$ looks like this: $x_4 \mapsto x_1 \mapsto x_3 \mapsto x_5 \mapsto x_4$.

Now, $(5,4)$ maps $x_4 \mapsto x_5 \mapsto x_4$, $(3,5)$ maps $x_5 \mapsto x_3 \mapsto x_5$, and $(1,3)$ maps $x_3 \mapsto x_1 \mapsto x_3$.

Chaining these together, we see that $(1,3)(3,5)(5,4)$ acts on $x_4$ in the following way(see the black and red arrows). $x_4 \to x_5 \to x_3 \to x_1$, so the final image is $x_4 \mapsto x_1$. Besides that, the images of $x_1, x_3, x_5$ are unchanged, so the total result is

$$x_4 \color{red}\mapsto x_1 \mapsto x_3 \mapsto x_5 \mapsto x_4$$

which shows the two are the same.

$\endgroup$
2
$\begingroup$

Your problem is a very common misconception that I have found even in lecture notes written by professors. The explanation lies in the following line:

The transposition $(i,j)$ does not swap the numbers $i$ and $j$. It swaps whichever numbers are currently in positions $i$ and $j$ in the arrangement.

When you consider $(1,3,5,4)$, it means the map that takes whichever object is first into the third placeholder, then the third object that was just kicked off goes to the fifth, and so on. It corresponds to the map $\left(\matrix{1&2&3&4&5\\3& 2& 5& 1& 4}\right)$ written here as a table of values.

If you start from $(1,2,3,4,5)$ and transpose the first and third objects you get $(3,2,1,4,5)$. Transpose then the first and fifth to get $(5,2,1,4,3)$, and finally the first and fourth to get $(4,2,1,5,3)$. In the end $1$ went to the third placeholder, $3$ to the fifth, etc. as expected.

Note for completeness that in cycle notation $(1,3,5,4)$ is also equal to the product $(1,3)(3,5)(5,4)$, which I personally find more fun and easier to remember.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I am loving your personally preferred way of decomposing cycles to transpositions, it is easier to remember. But I am still a little confused. I was expecting to recover the cycle (1,3,5,4) in the end. Is (4,2,1,5,3) somehow equal (1,3,5,4)? $\endgroup$ – Mikkel Rev May 11 '18 at 21:30
  • 1
    $\begingroup$ Yes, the fourth has moved to the first, the first has moved to the third, the third has moved to the fifth, and the fifth has moved to the fourth. $\endgroup$ – Jeffery Opoku-Mensah May 11 '18 at 21:52
  • $\begingroup$ Yes, that is the meaning of the sentence "In the end 1 went to the third placeholder, 3 to the fifth, etc. as expected." $(4,2,1,5,3)$ indicates the final position of each number after applying the permutation to $(1,2,3,4,5)$. $\endgroup$ – Arnaud Mortier May 11 '18 at 21:54

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.