# Writing permutations as products of adjacent transposition.

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?

• $(2,3)(3,4)(2,3)(3,4)=(2,4)(3,4)=(3,2,4)=(3,4)(2,3)$ – J. W. Tanner Nov 3 '19 at 19:44
• Well, I know how to prove that (2,4)(3,4)=(3,4)(2,3). But is there a formula or something like that to do it, or you just find it by pluging numbers? – Chang Henry Nov 3 '19 at 19:55
• Do you want to write $(1,2,4,3)$ as a product of adjacent transpositions? Because this is not clear to me from reading the question. – rawbacon Nov 3 '19 at 20:03
• I just did it by plugging numbers, but also $(2,3)(3,4)(2,3)=(2,4)$ is a conjugation – J. W. Tanner Nov 3 '19 at 20:04

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 adjacent transpositions using
$$(a_1 \; \cdots \; a_n) = (a_1\; a_2)\cdots (a_n \; a_{n-1}).$$ E.g., $$(4\; 5\; 6\;7) = (7\; 6)(6\;5)(5\;4).$$ 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.
• Also, you might want to use that $(k-1 \;\; k)(k \;\; k +1)(k-1 \;\; k) =(k \;\; k +1)(k-1 \;\; k)(k \;\; k +1)$ (let's call this the braid relation). A theorem by Tits (his so-called solution to the word problem in Coxeter groups, whatever that means) then says that you can obtain any of the shortest adjacent cycle decomposition by applying commutativity and the braid relation. – rawbacon Nov 4 '19 at 9:20