product of transpositions

• Aug 6th 2007, 10:33 PM
r7iris
product of transpositions
Show that everly element of S(n) (n>=2) is a product of transpositions of the form (k k+1).
[Hint:(k k+2) = (k k+1)(k+1 k+2)(k k+1).]
• Aug 7th 2007, 06:03 AM
ThePerfectHacker
Quote:

Originally Posted by r7iris
Show that everly element of S(n) (n>=2) is a product of transpositions of the form (k k+1).
[Hint:(k k+2) = (k k+1)(k+1 k+2)(k k+1).]

Theorem: For \$\displaystyle n\geq 2\$ every element of \$\displaystyle S_n\$ can be expressed as a product of transpositions.

Thus, given any premutation we can write it as a product of transpositions and we will show that each of these transpositions is a product of the form \$\displaystyle \prod (k,k+1)\$.

Say we are working in \$\displaystyle S_{10}\$ (products are taken from right to left).

Consider \$\displaystyle (1,3)\$. We can write it as \$\displaystyle (1,2)(2,3)(1,2)\$.

Consider \$\displaystyle (1,4)\$. We can write it as \$\displaystyle (1,2)(2,3)(3,4)(2,3)(1,2)\$.

Consider \$\displaystyle (2,6)\$. We can write it as \$\displaystyle (2,3)(3,4)(4,5)(5,6)(4,5)(3,4)(2,3)\$.

You get the general idea. So that means everything can be expressed in consecutive form by using the theorem.