Symmetric Group is Generated by Transposition and n-Cycle
Jump to navigation
Jump to search
Theorem
Let $n \in \Z: n > 1$.
Let $S_n$ denote the symmetric group on $n$ letters.
Then the set of cyclic permutations:
- $\set {\begin {pmatrix} 1 & 2 \end{pmatrix}, \begin {pmatrix} 1 & 2 & \cdots & n \end{pmatrix} }$
is a generator for $S_n$.
Proof
Denote:
- $s = \begin {pmatrix} 1 & 2 \end{pmatrix}$
- $r = \begin {pmatrix} 1 & 2 & \cdots & n \end{pmatrix}$
By Cycle Decomposition of Conjugate,:
- $r s r^{-1} = r \begin {pmatrix} 1 & 2 \end{pmatrix} r^{-1} = \begin {pmatrix} \map r 1 & \map r 2 \end{pmatrix} = \begin {pmatrix} 2 & 3 \end{pmatrix}$.
By repeatedly using Cycle Decomposition of Conjugate:
- $r^2 s r^{-2} = \begin {pmatrix} 3 & 4 \end{pmatrix}$
- $r^3 s r^{-3} = \begin {pmatrix} 4 & 5 \end{pmatrix}$
- $\cdots$
- $r^{n - 2} s r^{-\paren {n - 2} } = \begin {pmatrix} n - 1 & n \end{pmatrix}$
The result then follows from Transpositions of Adjacent Elements generate Symmetric Group.
$\blacksquare$
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $2$: The Symmetric Groups: $\S 80 \delta$