Transpositions of Adjacent Elements generate Symmetric Group
Theorem
Let $n \in \Z: n > 1$.
Let $S_n$ denote the symmetric group on $n$ letters.
Then the transpositions $a_k = \begin{pmatrix} k & k + 1 \end{pmatrix}$ for $1 \le k < n$ are a set of generators for $S_n$.
They satisfy the relations:
\(\ds a_k^2\) | \(=\) | \(\ds e\) | (for $1 \le k < n$) | |||||||||||
\(\ds \paren {a_k a_{k + 1} }^3\) | \(=\) | \(\ds e\) | (for $1 \le k < n - 1$) | |||||||||||
\(\ds \paren {a_i a_j}^2\) | \(=\) | \(\ds e\) | (for $1 \le i, j < n, \size {i - j} > 1$) |
Proof
First, we show that each $\begin{pmatrix} i & j \end{pmatrix}$ where $i < j$ is in the subgroup $\gen {a_1, a_2, \ldots, a_{n - 1} }$.
From Cycle Decomposition of Conjugate, we can conjugate $a_i$ by $a_{i + 1}$ to give:
- $\begin{pmatrix} i & i + 2 \end{pmatrix}$
Conjugating $a_i$ by the product $a_{j - 1} a_{j - 2} \ldots a_{i + 1}$ will give:
- $\begin{pmatrix} i & j \end{pmatrix}$
Next, we note that:
- from K-Cycle can be Factored into Transpositions, every cycle is a product of transpositions.
and:
- from Existence and Uniqueness of Cycle Decomposition, every permutation is a product of cycles.
Thus, every permutation can be obtained from some product of the given transpositions.
Thus $\gen {a_1, a_2, \ldots, a_{n - 1} }$ is a generator of $S_n$.
From Transposition is Self-Inverse, we have:
- $a_k^2 = e$
From K-Cycle can be Factored into Transpositions, $a_i a_{i + 1}$ is the $3$-cycle $\begin{pmatrix} i & i + 1 & i + 2 \end{pmatrix}$.
Thus:
- $\paren {a_k a_{k + 1} }^3 = e$
If $\size {i - j} > 1$, then from Disjoint Permutations Commute, $a_i$ and $a_j$ are disjoint.
Thus:
- $\paren {a_i a_j}^2 = a_i^2 a_j^2 = e$
$\blacksquare$
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $2$: The Symmetric Groups: $\S 80 \gamma$
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $9$: Permutations: Proposition $9.21$