Lemma 9.2.1.
If the identity is written as a product of \(r\) transpositions, \(\identity = \tau_1 \tau_2 \cdots \tau_r\text{,}\) then \(r\) is even.
Section 9.2 Transpositions and the Alternating Group
A cycle of length \(2\) is a transposition. Since
\begin{equation*}
(a_1, a_2, \ldots, a_n ) = (a_1, a_n ) (a_1, a_{n-1} ) \cdots ( a_1, a_3 ) (a_1, a_2 )\text{,}
\end{equation*}
every cycle, and hence every permutation, is a product of transpositions — though not uniquely so. What is invariant is the parity of the number of transpositions used.
Proof.
We induct on \(r\text{.}\) A single transposition is not the identity, so \(r \gt 1\text{,}\) and if \(r = 2\) we are done. Suppose \(r \gt 2\text{.}\) The last two transpositions \(\tau_{r-1}\tau_r\text{,}\) with \(a, b, c, d\) distinct, satisfy one of
\begin{align*}
(a, b)(a, b) & = \identity\\
(b, c)(a, b) & = (a, c)(b, c)\\
(c, d)(a, b) & = (a, b)(c, d)\\
(a, c)(a, b) & = (a, b)(b, c)\text{.}
\end{align*}
In the first case, deleting \(\tau_{r-1}\tau_r\) leaves the identity as a product of \(r-2\) transpositions, even by induction, so \(r\) is even. In each other case, substituting the right-hand side pushes the last occurrence of \(a\) one transposition earlier without changing the total count; repeating this process, either two adjacent transpositions eventually cancel — reducing to the first case — or \(a\) would be shuffled into the very first transposition alone, which is impossible since the identity fixes \(a\text{.}\) So the first case must eventually occur, and \(r\) is even.
Theorem 9.2.2.
If a permutation can be written as a product of an even number of transpositions, then every such product for it has an even number of transpositions; likewise for odd.
Proof.
Suppose \(\sigma = \sigma_1 \cdots \sigma_m = \tau_1 \cdots \tau_n\) with \(m\) even. Then
\begin{equation*}
\identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1\text{,}
\end{equation*}
a product of \(n + m\) transpositions, which is even by Lemma 9.2.1; since \(m\) is even, so is \(n\text{.}\) The odd case is identical.
By Theorem 9.2.2, it is well-defined to call a permutation even or odd according to the parity of any expression for it as a product of transpositions. The even permutations in \(S_n\) form the alternating group \(A_n\text{.}\)
Theorem 9.2.3.
\(A_n\) is a subgroup of \(S_n\text{,}\) and for \(n \geq 2\) it has order \(n!/2\text{.}\)
Proof.
A product of even permutations is even, so \(A_n\) is closed; the identity is even; and if \(\sigma = \sigma_1 \cdots \sigma_r\) with \(r\) even, then \(\sigma^{-1} = \sigma_r \cdots \sigma_1\) is also a product of \(r\) transpositions. So \(A_n \leq S_n\text{.}\)
For the order, fix a transposition \(\tau \in S_n\) (possible since \(n \geq 2\)) and let \(B_n\) be the set of odd permutations. The map \(A_n \rightarrow B_n\) given by \(\mu \mapsto \tau\mu\) is a bijection — it is injective by cancellation, and its inverse is the same map, since \(\tau(\tau \mu) = \mu\) — so \(|A_n| = |B_n| = |S_n|/2 = n!/2\text{.}\)
