I just want to show that a permutation can be written as a composition of transpositions. I cannot use cycles.
Any permutation in symmetric group n can be rewritten as a composition of transpositions
-
0Okay; I’ll write up an answer to get you started, at least. – 2012-05-30
1 Answers
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
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)$.
-
0Complete answer like always. :) – 2012-05-30