Is it possible to write any permutation as the product of transpositions $(1 \text{ } 2),(2 \text{ } 3),...(n-1 \text{ } n)$ I understand any permutation $(a_1 \text{ } a_2 ... a_k)$ in $S_n$ where $k \leq n$ can be written as a product of $(a_1 \text{ } a_k)(a_1a_{k-1})...(a_2 \text{ } a_1)$. Similarly, $(a_1a_2...a_k)$ can be written as $(1 \text{ } a_1)(1 \text{ } a_k)...(1 \text{ } a_2)(1 \text{ } a_1)$ (if the permutation has $1$ in it, it can be rearranged so $1$ is the first integer appearing on the left and then the first and last transpositions can be removed) which shows any permutation can be written as the products of $(1 \text{ } 2), (1 \text{ } 3),...,(1 \text{ } n)$.
Is it possible to write a permutation as a product of $(1 \text{ } 2),(2 \text{ } 3),...,(n-1 \text{ } n)$? If the permutation consists of consecutive numbers in increasing order then $(a_1 \text{ } a_2)...(a_{k-1} \text{ } a_k)$ works fine. But I cannot generalize it for any sequence of integers. Is this actually possible?
Edit
It turns out it is possible. I am hoping to generalize this claim so for any permutation, so I can write it as a product of $(1 2), (2 3), ...,(n-1 \text{ } n)$, the way I have shown it works for $(1 2), (1 3),...,(1 n)$. For instance if $\sigma =(352)$ then $\sigma=(1 3)(1 2)(1 5)(13)$. How can the same cycle be written as a product of $(1 2),(2 3),...(n-1 \text{ } n)?$

Solution 1:

It is obvious that we can write any permutation as a product of transpositions.
So, we need only to show that any transposition is a product of special transpositions $(1 \text{ } 2),(2 \text{ } 3),...(n-1 \text{ } n)$.
Let $1\leq i<j\leq n$.
$(i\text{ }j)=(i\text{ }i+1)\cdots(j-2\text{ }j-1)(j-1\text{ }j)\cdots(i+1\text{ }i+2)(i\text{ }i+1)$.
For example, $(3\text{ }7)=(3\text{ }4)(4\text{ }5)(5\text{ }6)(6\text{ }7)(5\text{ }6)(4\text{ }5)(3\text{ }4)$.

Solution 2:

Let $\sigma$ be any permutation in $S_n$.
Let $a:=\sigma(1)$.
If $a=1$, let $\tau_1:=\sigma$.
If $a\neq 1$, then, $\tau_1:=(2\text{ }1)\cdots(a-1\text{ }a-2)(a\text{ }a-1)\sigma$.
Then $\tau_1(1)=1$.
Let $b:=\tau_1(2)\in\{2,\dots,n\}$.
If $b=2$, let $\tau_2:=\tau_1$.
If $b\neq 2$, let $\tau_2:=(3\text{ }2)\cdots(b-1\text{ }b-2)(b\text{ }b-1)\tau_1$.
Then $\tau_2(1)=1, \tau_2(2)=2$.
Let $c:=\tau_2(3)\in\{3,\dots,n\}$.
If $c=3$, let $\tau_3:=\tau_2$.
If $c\neq 3$, let $\tau_3:=(4\text{ }3)\cdots(c-1\text{ }c-2)(c\text{ }c-1)\tau_2$.
Then $\tau_3(1)=1, \tau_3(2)=2,\tau_3(3)=3$.
$\vdots$
Let $y:=\tau_{n-2}(n-1)\in\{n-1,n\}$.
If $y=n-1$, let $\tau_{n-1}:=\tau_{n-2}$.
If $y\neq n-1$, let $\tau_{n-1}:=(n\text{ }n-1)\tau_{n-2}$.
Then $\tau_{n-1}(1)=1,\tau_{n-1}(2)=2,\dots,\tau_{n-1}(n-2)=n-2,\tau_{n-1}(n-1)=n-1$.
Let $z:=\tau_{n-1}(n)\in\{n\}$.
Then, $z=n$.
So, $\tau_{n-1}$ is the identity.
Therefore, the inverse of $\sigma$ is a product of special transpositions $(1 \text{ } 2),(2 \text{ } 3),...(n-1 \text{ } n)$.
Since the inverse of the inverse of $\sigma$ is also a product of special transpositions $(1 \text{ } 2),(2 \text{ } 3),...(n-1 \text{ } n)$ and $\sigma$ is equal to the inverse of the inverse of $\sigma$, $\sigma$ is a product of special transpositions $(1 \text{ } 2),(2 \text{ } 3),...(n-1 \text{ } n)$.

