= Solution
With rightmost-first composition, a <permutation cycle> satisfies
$$
(a_1\ a_2\ \cdots\ a_m)
=(a_1\ a_m)(a_1\ a_{m-1})\cdots(a_1\ a_2).
$$
Tracing each $a_j$ verifies the equality, and every other letter is fixed. Thus every cycle is a product of <transpositions>; decomposing a <permutation> into <disjoint permutation cycles> proves that every element of $S_n$ is such a product. The identity is the empty product.
To establish that parity is well defined, use the <permutation matrix> $P_\sigma$ defined by $P_\sigma e_i=e_{\sigma(i)}$. Its <determinant> is $\pm1$, and $P_{\sigma\tau}=P_\sigma P_\tau$. A <transposition> swaps two columns of the <identity matrix> and has <determinant> $-1$. Therefore if $\sigma$ is expressed as a product of $r$ <transpositions>,
$$
\det P_\sigma=(-1)^r.
$$
The left side depends only on $\sigma$, so any two decompositions have the same parity. Define
$$
\boxed{\operatorname{sgn}(\sigma)=\det P_\sigma=(-1)^r.}
$$
Multiplicativity of the <determinant> makes this the <sign homomorphism>. Its <kernel of a group homomorphism> is the <alternating group>
$$
\boxed{A_n=\{\sigma\in S_n:\operatorname{sgn}(\sigma)=1\}.}
$$
It is a <normal subgroup> consisting of the <even permutations>. For $n\geq2$ the sign map is surjective because a <transposition> has sign $-1$, so $[S_n:A_n]=2$. For $n=1$ both <groups> are trivial.
Back to article page
