any substitution, which saves parity, can be decomposed to product of (1 2 3) (1 2 4) ... (1 2 n)

Question

How to show that any substitution, which saves parity, can be written as a product of $3$-cycles of the form:

(1 2 3) (1 2 4) ... (1 2 n)

Answer 1

Firstly, any permutation can be written as the product of a number of cycles of the form $(i,i+1)$ (eg: bucket sort). If the permutation is even, then the number of such cycles will be even.

So you can write pairs of them in terms of 3-cycles. There are two cases: the pairs are disjoint; the pairs have a common element.

We have: $(34)(56)=gfg$, where $g=(124)(126)=((14)(26))$ and $f=(123)(125)=((13)(25))$. Intuition: Once we see what $g$ does, we move 4 to 1, then apply $f$ to swap with 3, and bring it back. Ditto for swapping 5 and 6.

The other case is $(34)(35)$ which is equal to $(354)$. You can write this as $f(124)f$. [Intuitively, $f$ swaps 1,3 and 2,5, so after this applying (124) is like applying $(354)$, then you swap back again with $f$.]