Definition 1.16.1. Transposition.
Let \(X\) be a finite set of cardinality at least 2. A \(2\)-cycle \(\sigma=(a\ b)\in S_X\) is called a transposition of \(S_X\text{.}\)
Section 1.16 Alternating subgroup
Theorem 1.16.2. Transpositions generate \(S_n\).
Let \(X\) be a finite set of cardinality at least 2.
-
Given \(k\)-cycle \(\sigma=(a_1\ a_2\ \dots a_k)\text{,}\) we have\begin{equation} \sigma=(a_1\ a_k)\cdots (a_1\ a_3)(a_1\ a_2)\text{.}\tag{1.16.1} \end{equation}
-
Let \(T\) be the set of transpositions of \(S_X\text{.}\) We have \(S_X=\angvec{T}\text{:}\) i.e., \(S_X\) is generated by its transpositions.
Proof.
-
This is a straightforward proof by induction, the base case \(k=2\) being trivial. For the induction step, assume any \(k\)-cycle can be written as in (1.16.1). Given any \((k+1)\)-cycle \(\sigma=(a_1\ a_2 \dots \ a_{k+1}\text{,}\) we have\begin{align*} \sigma\amp =(a_1\ a_{k+1})(a_1\ a_2\ \dots a_k)\\\\ \amp =(a_1\ a_{k+1})(a_1\ a_{k})\cdots (a_1 a_2) \amp (\text{induc. hypo.}) \text{,} \end{align*}as desired.
-
From (1) we see that \(H=\angvec{T}\) contains all cycles. Since any permutation can be written as a product of (disjoint) cycles, it follows that \(S_n=\angvec{T}\text{.}\)
The {\em alternating subgroup} of \(S_X\) is defined as the set of all {\em even permutations}, which are defined as the permutations that can be written as a product of an even number of transpositions. We hasten to acknowledge that this definition is highly suspect, since it is not in the least obvious that if a permutation can be written as an even number of transpositions, then it cannot be written as an odd number of transpositions! We will justify the definition at the end of the section after looking at some concrete examples.
Definition 1.16.3. Even and odd permutations.
Let \(X\) be a finite set of cardinality at least 2. A permutation \(\sigma\in S_X\) is called even if it can be written as a product of an even number of transpositions, and odd if it can be written as an odd product of transpositions. Two permutations have the same parity if they are both even or both odd.
We define the sign map \(\sgn \colon S_X\rightarrow \{\pm 1\}\) as
\begin{equation}
\sgn(\sigma) = \begin{cases}
1 \amp \text{if } \sigma \text{ is even}\\
-1 \amp \text{if } \sigma \text{ is odd}.
\end{cases}\tag{1.16.2}
\end{equation}
Equivalently, if \(\sigma\) can be written as a product of \(i\) transpositions, then \(\sgn(\sigma)=(-1)^i\text{.}\)
Example 1.16.4. Sign of permutations.
From (1.16.1), we see that any \(k\)-cycle can be written as a product of \(k-1\) transpositions. It follows that a \(k\)-cycle is even if and only if \(k\) is odd.
What about the identity permutation \(\id\in S_X\text{?}\) Since \(\id=(a\ b)(a\ b)\) for any \(2\)-cycle, we see that \(\id\) is even.
Proposition 1.16.5. Sign map.
Let \(X\) be a set of cardinality at least 2. The sign map \(\sgn \colon S_X\rightarrow \{\pm 1\}\) is a surjective homomorphism.
Proof.
The proof is straightforward, assuming of course that our definition of even/odd is well defined! Indeed, if \(\sigma\) can be written as a product of \(i\) traspositions, and \(\tau\) can be written as a product of \(j\) transpositions, then \(\sigma\tau\) can be written as a product of \(i+j\) transpositions, and thus
\begin{align*}
\sgn (\sigma\tau) \amp =(-1)^{i+j}\\
\amp =(-1)^i (-1)^j\\
\amp =\sgn(\sigma)\sgn(\tau)\text{.}
\end{align*}
Surjectivity is clear since \(\sgn(\id)=1\) and \(\sgn((a\ b))=-1\) for any transposition \((a\ b)\text{.}\)
Specimen 13. Alternating subgroup.
Let \(X\) be a finite set of cardinality at least 2. The alternating subgroup of \(S_X\text{,}\) denoted \(A_X\text{,}\) is defined as the kernel of \(\sgn\colon S_X\rightarrow \{\pm 1\}\text{:}\) i.e.,
\begin{align*}
A_X \amp =\{\sigma\in S_X\mid \sgn(\sigma)=1\}\\
\amp =\{\sigma\in S_X\mid \sigma \text{ is even}\}\text{.}
\end{align*}
Since \(\sgn\colon S_X\rightarrow \{\pm 1\}\) is a surjective homomorphism, it follows from the first isomorphism theorem that \(A_X\normalin S_X\) and
\begin{equation*}
[S_X\colon A_X]=\abs{S_X/A_X}=2\text{.}
\end{equation*}
Example 1.16.6. \(A_4\).
Compute the full lattice of subgroups of \(A_4\) and identify any normal subgroups.
Solution.
Let’s first describe all elements of \(A_4\text{.}\) Below we look at all cycle types of elements in \(S_4\text{,}\) determine their parity, and count the number of elements of that cycle type.
\begin{equation*}
\begin{array}{ccc}
\text{Cycle type} \amp \text{Parity} \amp \text{Number of elements}\\
\hline
(abcd) \amp \text{odd} \amp 6\\
(abc) \amp \text{even} \amp 8\\
(ab)(cd) \amp \text{even} \amp 3\\
(ab) \amp \text{odd} \amp 6\\
\id \amp \text{even} \amp 1
\end{array}\text{.}
\end{equation*}
If \(H\) is a subgroup of \(A_4\text{,}\) then since \(\abs{A_4}=12\text{,}\) we have
\begin{equation*}
\abs{H}\in \{1,2,3,4,6,12\}\text{.}
\end{equation*}
There are \(3\) cardinality-2 subgroups generated by the elements of the form \((ab)(cd)\text{.}\) There are exactly \(4\) cyclic subgroups of cardinality \(3\text{:}\) one for each pair \(\{(abc),(acb)\}\text{.}\) Furthermore, as we have seen before, we have
\begin{equation*}
\angvec{(12)(34),(13)(24)}=\{1, (12)(34),(13)(24),(14)(23)\}\text{,}
\end{equation*}
a cardinality-4 subgroup isomorphic to the Klein 4-group. Since conjugation preserves cycle type, and since this subgroup contains all elements of type \((ab)(cd)\text{,}\) it is easy to see that it is normal. This gives rise to the the lattice of subgroups in Figure 1.16.7. We claim that this is the complete lattice of subgroups. It suffices to argue that any subgroup of \(A_4\) containing an element of the form \((ab)(cd)\) and an element of the form \((efg)\) must be all of \(A_4\text{.}\) It is not difficult to show this just by computing some products of elements of order 2 and 3. Below you find a slightly slicker argument.
Suppose we had a subgroup \(H'\ne A_4\) containing $H=\angvec{(12)(34)}$ and \(K=\angvec{(123)}\text{.}\) It would follow that \(H'\geq HK\text{.}\) Since \(\abs{H}=2\) and \(\abs{K}=3\text{,}\) we have \(\abs{H\cap K}=1\) and thus \(\abs{HK}=\abs{H}\abs{K}=6\text{.}\) But then we must have \(\abs{H'}=6\text{,}\) in which case \(H'\) is normal in \(A_4\) since \([A_4\colon H']=2\text{.}\) Since all elements of type \((ab)(cd)\) are conjugate in \(A_4\) (as one can easily verify), we’d have \(\angvec{(12)(34),(13)(24)}\leq H'\text{.}\) This is a contradiction, since \(\abs{\angvec{(12)(34),(13)(24)}}=4\nmid 6\text{.}\) Thus there is no such \(H'\text{.}\)
We now set about proving that our definition of the parity of a permutation is well defined. There are many ways of doing this. The text uses an argument based on the discriminant polynomial
\begin{equation*}
f_\Delta(x_1,x_2,\dots, x_n)=\prod_{1\leq i< j\leq n}(x_i-x_j)
\end{equation*}
and the observation that given any \(\sigma\in S_n\text{,}\) we have
\begin{equation*}
\prod_{1\leq i< j\leq n}(x_{\sigma(i)}-x_{\sigma(j)})=\pm f_\Delta(x_1,x_2,\dots, x_n)\text{.}
\end{equation*}
We will pursue a completely different line of thought, thereby supplementing the book’s nice proof, with another one. Our approach has the added advantage of making uses of an interesting group homomorphism
\begin{equation*}
\phi\colon S_n\rightarrow \GL_n(\R)\text{.}
\end{equation*}
Moreover, our argument gives us the opportunity of introducing another important subgroug of the general linear group, called the orthogonal group.
Specimen 14. Orthogonal group.
Let \(n\) be a positive integer. The orthogonal subgroup of \(\GL_n(\R)\text{,}\)denoted \(O_n(\R)\text{,}\) is defined as the set of \(A\in \GL_n(\R)\) satisfying \(A^{-1}=A^T\text{:}\) i.e.,
\begin{equation}
O_n(\R)=\{A\in \GL_n(\R) \mid A^{-1}=A^T\}\text{.}\tag{1.16.3}
\end{equation}
We leave as an exercise the fact that \(O_n(\R)\) is a subgroup of \(\GL_n(\R)\text{,}\) and hence a group in its own right.
Theorem 1.16.8. Permutation group representation.
Let \(n\geq 2\) be an integer. For all \(1\leq j\leq n\text{,}\) let \(\bolde_j\in \R^n\) be the \(n\)-tuple whose \(j\)-th coordinate is \(1\text{,}\) and whose other coordinates are \(0\text{.}\) Given \(\sigma\in S_n\text{,}\) we define \(A_\sigma\) to be the unique matrix in \(M_n(\R)\) satisfying
\begin{equation*}
A_\sigma \bolde_j=\bolde_{\sigma(j)}
\end{equation*}
for all \(1\leq j\leq n\text{.}\)
-
The map \(\sigma\mapsto A_\sigma\) defines a group homomorphism\begin{align*} \phi\colon S_n \amp \rightarrow O_n(\R)\\ \sigma \amp \mapsto A_\sigma\text{.} \end{align*}
-
The composition \(\sgn=\det\circ \phi\) defines a surjective group homomorphism\begin{equation*} \sgn\colon S_n \rightarrow \{\pm 1\}\text{.} \end{equation*}
-
We have \(\sigma\in \ker\sgn\) if and only if \(\sigma\) can be written as a product of an even number of transpositions. As a result, Definition 1.16.3 is well defined.
Remark 1.16.9. Parity.
At last, thanks to Theorem 1.16.8, we see that our definition of parity is well defined. But wait, you might object, Theorem 1.16.8 applies only to \(S_n\text{,}\) not a general permutation group \(S_X\text{.}\) Of course, the easy way to get around this is to choose an isomorphism from \(S_X\) to \(S_n\) that sends transpositions to transpositions (the isomorphism in Example 1.6.7 does this), and compose this with \(\sgn\colon S_n\rightarrow \{\pm 1\}\text{.}\) The resulting homomorphism \(S_X\rightarrow \{\pm 1\}\) satisfies the same properties as \(\sgn\colon S_n\rightarrow \{\pm 1\}\) described in Theorem 1.16.8.
There is another way of seeing this, however. Namely, Theorem 1.16.8 tells us that \(S_n\) has a normal subgroup of index 2, and hence so does and \(S_X\text{,}\) where \(\abs{X}=n\geq 2\text{.}\) In fact, it is possible to show that \(S_X\) has exactly one such subgroup, and it is made up precisely of the elements of \(\sigma\) that can be written as a product of an even number of transpositions. We leave this fact as an exercise.
