Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

1 Answer 1

up vote 3 down vote accepted

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)$.

share|improve this answer
    
Complete answer like always. :) –  Babak S. May 30 '12 at 7:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.