# Permutation written as product of transpositions

Prove every non-trivial permutation of $\omega = {\{1,2,....,n}\}$ can be written as a composite of less than $n$ transpositions.

I have no idea where to start with this, I know every permutation can be written as a product of disjoint cycles, and I know a transposition is a cycle of length $2", but I honestly don't know where to start. • I believe you can prove this by induction. Consider a permutation$\sigma \in Sym(n+1)$. Cow consider two cases. Two cases being whether the permutation$\sigma$changes the position of the last element or not. – Jal Oct 4 '16 at 20:15 • @sina why not post an answer? It's certainly a valid approach. – Matt Samuel Oct 4 '16 at 20:42 ## 3 Answers Hint. Note that a cycle of length$k\geq 2$can be written as a product of$k-1$transpositions as follows: $$(a_1 ... a_{k-1} a_{k})=(a_1 a_{k})(a_1 a_{k-1})...(a_1 a_2).$$ By induction - suppose any permutation of$[n]$takes less than$n$transpositions. Consider any permutation$w$of$[n+1].$Use one transposition to swap$n+1$into the correct location, if$w_{n+1} \neq n+1$. Now, you have less than$n$transpositions for the rest, by inductive hypothesis. So the total required is less than$n+1$. • But what about the inductive base? I think you should first prove the statement for some value of$n$. Moreover, in the inductive step you suggest to use one transposition to swap$n+1$into the correct location But in this way arent'you mixing up all the others? – massimo Jan 9 '17 at 8:14 • Valid concerns. I left out the base case because for$S_2$it is clear. The second question - you're mixing up the others, but it doesn't matter. The important point is that you used one transposition, and now you have$n$elements permuted. – Nitin Jan 9 '17 at 17:48 • I agree with @Nitin. Indeed, I missed the second point: you can exploit the inductive hypothesis to correctly remix the old elements. A minor remark on this inductive proof: it is not constructive, that is, it does not show how to actually obtain the composition. Which is not a lack, since it fully answers the question, and in a very concise way, but I think the Hint that was first given is a useful complementary answer. – massimo Jan 9 '17 at 18:16 As you observed, any permutation can be expressed as a product of cycles. But any cycle can be expressed via suitable transpositions. In fact, consider a cycle of length$n$:$(a_1,a_2,a_3,...a_n)$. Think of$a_{i+1}$as the destination of box$i$and let's start sending the content of boxes using transpositions. For box 1 this can be done via$(a_1,a_2)$. Now the content of box 1 is in its final destination but the content of box 2 is not. Since the content of box 2 must go in$a_3$we add the transposition$(a_1,a_3)$. Going on this way we are done with$(a_1,a_{n})$which sends to its final destination both$a_{n-1}$and$a_n$(in the remaining slot). Thus, the cycle will be rewritten as $$\prod_{i=2}^n(a_1,a_i)$$ i.e. using$n-1<n\$ transpositions.

• Though why n - 1 is not clear – Shailesh Jan 8 '17 at 0:39
• index in the product goes from 2 to n. – massimo Jan 8 '17 at 0:41