# Any permutation in symmetric group n can be rewritten as a composition of transpositions

I just want to show that a permutation can be written as a composition of transpositions. I cannot use cycles.

-
If you know how do it with cycles, you can do it with transpositions. HINT: $(12)(13)(14)(15)=(12345)$. – Brian M. Scott May 30 '12 at 5:50
I don't know how to do it with cycles :( – frickskit May 30 '12 at 5:53
Okay; I’ll write up an answer to get you started, at least. – Brian M. Scott May 30 '12 at 6:04

Let $\pi$ be a permutation of $[n]=\{1,2,\dots,n\}$. One way is to start by writing $\pi$ as a composition of cycles. Consider the sequence $\pi^0(1),\pi^1(1),\pi^2(1),\pi^3(1),\dots\;$, where $\pi^0(1)=1$, and $$\pi^k(1)=\underbrace{\pi(\pi(\dots\pi}_{k\text{ times}}(1)\dots))$$ for $k\ge 1$. There are only finitely many possible values for the numbers $\pi^k(1)$, so eventually two of them have to be the same. Say that an ordered pair $\langle k,m\rangle$ is a repetition if $k<m$ and $\pi^k(1)=\pi^m(1)$.
Let $\langle k,m\rangle$ be a repetition with the smallest possible value of $k$, and suppose that $k>0$. Let $i=\pi^{k-1}(1)$ and $j=\pi^{m-1}(1)$; then $$\pi(i)=\pi^k(1)=\pi^m(1)=\pi(j)\;,$$ and $\pi$ is a bijection, so $i=j$. But then $\langle i,j\rangle$ is a repetition with a smaller first component than $k$, contradicting the choice of $\langle k,m\rangle$. This contradiction shows that $k=0$. Now choose $m$ minimal such that $\langle 0,m\rangle$ is a repetition, and show that $$\big(1,\pi(1),\dots,\pi^{m-1}(1)\big)\tag{1}$$ is a cycle of $\pi$; call it $\sigma$. Let $C$ be the set of elements occurring in $\sigma$.
Let $\psi$ be the restriction of $\pi$ to $[n]\setminus C$; clearly $\psi$ is a permutation of $[n]\setminus C$, and $[n]\setminus C$ has fewer than $n$ elements. If you’d begun by assuming as an induction hypothesis that permutations of fewer than $n$ things can always be written as compositions of transpositions, you could now appeal to that induction hypothesis to write $$\pi=\sigma\psi=\sigma\tau_1\dots\tau_r$$ for some transpositions $\tau_1,\dots,\tau_r$. The result is certainly trivial for $n=2$, so I recommend doing just that: prove it by induction on $n$.
The only remaining problem would be to write $\sigma$ as a composition of transpositions, and I gave a hint for that in the comments, which I’ll modify slightly here: $(13)(15)(12)(14)=(13524)$.