Permutation written as product of transpositions

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

We want to show that: $(a_1, a_2, ..., a_n) = \prod_{i=0}^{n-2} (a_1, a_{n-i})$

Where $\prod_{i=1}^{n} a_i = a_1 \cdot a_2 \cdot ...\cdot a_n$

Use an induction step here. if the above then:

$(a_1, a_2, ..., a_{n+1}) = \prod_{i=0}^{n-1} (a_1, a_{n+1-i})$

that is equivalent to

$(a_1, a_2, ..., a_{n+1}) = (a_1, a_{n+1}) \cdot \prod_{i=0}^{n-2} (a_1, a_{n-i})$

Permutation $(a_1, a_2, ..., a_{n+1})$ differs from $(a_1, a_2, ..., a_{n})$ only in a way such that $a_n \rightarrow a_{n+1}$ and $a_{n+1} \rightarrow a_1$

Plugging in $a_n$ into permutation $(a_1, a_2, ..., a_{n})$ returns $a_{n+1}$. Then in the "highest layer" it is transformed into $a_1$ by $(a_1, a_{n+1})$.

On the other hand plugging in $a_{n+1}$ will leave us with 1 as there's no occurrence of $a_{n+1}$ anywhere, but in the leftmost element of a product.

Thus induction step is indeed proven.

Base step is trivial. Just check.

$ (a_1, a_2, a_3) = (a_1, a_3) \cdot (a_1, a_2)$