Permutation is Product of Transpositions
Jump to navigation
Jump to search
Theorem
Let $S_n$ denote the symmetric group on $n$ letters.
Every element of $S_n$ can be expressed as a product of transpositions.
Proof
Let $\pi \in S_n$.
From Existence and Uniqueness of Cycle Decomposition, $\pi$ can be uniquely expressed as a cycle decomposition, up to the order of factors.
From K-Cycle can be Factored into Transpositions, each one of the cyclic permutations that compose this cycle decomposition can be expressed as a product of transpositions.
The result follows.
$\blacksquare$
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $2$: The Symmetric Groups: $\S 80$: Corollary