«A cycle is a product of transpositions» $\iff$ «Rearrangement of $n$ objects is the same as successively interchanging pairs»

Question

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.

Answer 1

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.

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.

Answer 2

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.