0

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

1 Answers1

1

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

quanticbolt
  • 1,746
  • 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? –  Oct 30 '17 at 12:48
  • 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. – quanticbolt Oct 30 '17 at 12:51