I want to write $(1,2,4,3)$ as a product of adjacent transpositions, i.e., transpositions of the form $(k \;\; k +1)$.
Well, I manage to change this cycle to $(1,3)(1,4)(1,2)$, and $(1,3)=(1,2)(2,3)(1,2)$, $(1,4)=(1,2)(2,3)(3,4)(2,3)(1,2)$.
Hence, $(1,2,4,3)=(1,2)(2,3)(1,2)(1,2)(2,3)(3,4)(2,3)(1,2)(1,2)$.
And, since transposition is self-inverse, we have $(1,2,4,3)=(1,2)(3,4)(2,3)$.
Is my work correct?
But still, I can change $(1,2,4,3)$ to $(1,2)(2,4)(4,3)$. And $(2,4)=(2,3)(3,4)(2,3)$, so I got $(1,2)(2,3)(3,4)(2,3)(3,4)$, which should equal $(1,2)(3,4)(2,3)$, but I don't know how to manipulate it properly. Can anyone tell me how to do it?
Best Answer
For completeness, an adjacent transposition is a transposition of the form $(k \; \; k+1)$. I want to explain how to express arbitrary permutations as products of adjacent transpositions. I think you're doing okay.
The general procedure goes as follows. Each cycle $(a_1 \; \cdots a_n)$ can be expressed as a product of transpositions using
$$(a_1 \; \cdots \; a_n) = (a_1\; a_2)\cdots (a_n \; a_{n-1}).$$ E.g., $$(4\; 5\; 6\;7) = (4\; 5)(5\;6)(6\;7).$$ After that, this answer points out the following. Let $m < n$. Then you can express the transposition $(n \; m)$ as a product of adjacent transpositions by using $$(n \; m) = (m + 1 \; \; m)\cdots (n-1 \; \; n-2)(n \; \; n-1)(n-1 \;\;n-2)\cdots(m+1 \;\;m),$$ (which you might or might not know, judging from your question). For example, $$(7 \; 2) = (3\;2)(4\;3)(5\;4)(6\;5)\cdot (7\; 6) \cdot (6\;5)(5\;4)(4\;3)(3\;2).$$
Edit: To then move on to try to use as few transpositions as possible, you might want to apply the following formulas. If the numbers $k, m, n, \ell$ are pairwise distinct, then we have that $(k\; m)(n \; \ell)$ commute, i.e., $$(k \; m)(n \; \ell) = (n \; \ell)(k \; m).$$ Moreover, for any $k$ we have that $(k-1 \;\; k)$ and $(k \;\; k+1)$ satisfy the so-called braid relation $$ (k−1\;\;k)(k\;\;k+1)(k−1\;\;k)=(k\;\;k+1)(k−1\;\;k)(k\;\;k+1). $$ A Theorem by Tits (explained, e.g., in these notes on Coxeter groups in Section 4.3) states that after writing a permutation as a product of adjacent permutations, this expression can be turned into an expression that is as short as possible by applying only commutativity (where it applies), the braid relation (where it applies) and the fact that transpositions are self-inverse.