# Show any permutation of a finite set may be expressed as a product of transpositions

• Jan 24th 2010, 04:11 AM
kevinlightman
Show any permutation of a finite set may be expressed as a product of transpositions
Prove any permutation of a finite set may be expressed as a product of transpositions by using induction on |Supp(p)|.
Here Supp(p) means the support of p, the elements which are moved by the map p.
• Jan 24th 2010, 12:24 PM
Opalg
Quote:

Originally Posted by kevinlightman
Prove any permutation of a finite set may be expressed as a product of transpositions by using induction on |Supp(p)|.
Here Supp(p) means the support of p, the elements which are moved by the map p.

Base case |Supp(p)|=2 is rather obvious. Suppose the result holds for $|\text{Supp}(p)|\leqslant n$, and let p be a permutation with $|\text{Supp}(p)|=n+1$. Suppose that p moves i to j: $p (i)=j\ne i$. Then the product of the transposition (i j) with p fixes i and therefore moves at most n elements. So apply the inductive hypothesis to it ... .