0
$\begingroup$

I know that any permutation can be written as a product of transpositions. Does that complete the proof? I don't think so, because suppose we need $2\rightarrow 3$, we can't write that in the form $(1n)$.

$\endgroup$
2
$\begingroup$

As you've correctly stated, any permutation can be expressed as a product of transpositions. Then, as long as we can generate any transposition, $(kl)$ from a product of the form, $(12)(13)...(1n)$, we can write any permutation as some product of $(12)(13)...(1n)$. Consider, $$(kl)=(1k)(1l)(1k),$$ which is indeed a product of transpositions of the form, $(1n)$.

$\endgroup$
  • $\begingroup$ Thanks! So basically, if we have a particular permutation, then as long as we can generate the transpositions needed to write it as a product of those transpositions, we're good? $\endgroup$ – W. Ryan Oct 30 '17 at 12:48
  • $\begingroup$ Yes. That is how it works. Consider some permutation which can be written as $(k_1l_1)(k_2l_2)(k_3l_3)...(k_nl_n)$. As long as we can generate all of these transpositions with products of the form $(1n)$, we can generate the original permutation. $\endgroup$ – quanticbolt Oct 30 '17 at 12:51

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.