0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Jal Oct 4 '16 at 20:15
  • $\begingroup$ @sina why not post an answer? It's certainly a valid approach. $\endgroup$ – Matt Samuel Oct 4 '16 at 20:42
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – massimo Jan 9 '17 at 8:14
  • $\begingroup$ 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. $\endgroup$ – Nitin Jan 9 '17 at 17:48
  • $\begingroup$ 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. $\endgroup$ – massimo Jan 9 '17 at 18:16
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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