\documentclass[12pt]{article}
%\usepackage[dvips]{graphicx}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{tikz} % diagram package

%\pagestyle{empty}

\topmargin -1.1in
\oddsidemargin -0.25in
\evensidemargin -0.25in
\textheight 9.825in
\textwidth 7in 

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}

\def\myfrac#1#2{
    \hspace{3pt}\!\!\!$^{#1}\!\!\hspace{1pt}/\hspace{2pt}\!\!_{#2}$\!\!\!\hspace{3pt}
} 

\setlength{\unitlength}{0.1in}


\newcommand{\force}{{$\mbox{\;}$}}

\begin{document}

\noindent \hfill
\fbox{\fbox{\parbox{6.8in}{{\scshape{Alternating Groups: $A_n$  \hfill An Even (or is it an Odd?) Handout}} }}} \hfill \\

\vspace{-0.2in}

\noindent {\large\sc Even vs. Odd}:

We say a permutation is {\bf even} if it can be written as a product of an even number of (usually non-disjoint) transpositions (i.e., 2-cycles).
Likewise a permutation is {\bf odd} if it can be written as a product of an odd number of transpositions. The first question is, ``Can any permutation 
be written as a product of transpositions?'' The answer is ``Yes.'' ...well if we're working in $S_n$ for $n>1$ (of course, $S_1$ doesn't
have any transpositions...it just has the identity). For the remainder of this handout, {\bf fix some $n>1$}. Recall the trick:

\vspace{-0.2in}

\[ (a_1a_2\dots a_\ell) = (a_1a_\ell)(a_1a_{\ell-1})\cdots(a_1 a_3)(a_1 a_2) \]

\vspace{-0.05in}

Also, $(1)=(12)(12)$. Therefore, any cycle of any length can be written as a product of transpositions. Now since 
every permutation can be written as a product of (disjoint) cycles, we can use this trick on each cycle and get: {\it Every permutation can 
be written as a product of transpositions.} For example, $(123)(4567)=(13)(12)(47)(46)(45)$.

Next, consider: $(123) = (13)(12) = (34)(14)(34)(12) = (34)(12)(12)(14)(34)(12) = \cdots$
Notice that $(123)$ can be written as a product of transpositions in (infinitely) many different ways. However, the three ways shown above 
have 2, 4, and 6 transpositions respectively -- thus $(123)$ is even. Our next question is, ``It is possible that $(123)$ or any other permutation
is both even {\it and} odd?'' The answer is ``No'' but this requires some proof.

\vspace{0.1in}

\noindent {\bf Lemma:} The identity is even --- and not odd.

\vspace{0.05in}

\noindent
{\bf proof:} First, we know that $(1)=(12)(12)$, so the identity is even, but is it possible it's also odd? 

Suppose that $(1) = (a_1a_2)\cdots(a_{\ell-1}a_\ell)$.
We want to show that there {\bf must} be an even number of these transpositions. First, let's see how to push transpositions past
each other. There are 4 cases of interest: Let $a,b,c,d$ be \underline{\it distinct} elements of the set $\{1,2,\dots, n\}$. 

\vspace{-0.15in}

\begin{itemize} \setlength{\itemsep}{0pt}
   \item $(cd)(ab)=(ab)(cd)$ --- disjoint cycles commute.
   \item $(bc)(ab)=(acb) = (cba) = (ca)(cb)$ --- multiply out, cyclicly permute, transposition trick.
   \item $(ac)(ab)=(abc) = (bca) = (ba)(bc)$ --- same as before.
   \item $(ab)(ab)=(1)$
\end{itemize}

\vspace{-0.15in}

\noindent
In the all cases, we made sure $a$ isn't in the second transposition. In the last case, we canceled $a$ out completely!

Now suppose $a$ is the largest number appearing among all the transpositions in $(a_1a_2)\cdots(a_{\ell-1}a_{\ell})$.
We can take the right-most occurrence of $a$ and move it to the left. As we move all of the $a$'s to the left, at some point, the $a$'s 
must cancel out (we have to end up with the ``$(ab)(ab)$'' case).  If not, we would have $(1) = (ab)\tau$ with no $a$'s appearing in $\tau$. 
But this is impossible since $\tau$ maps $a$ to $a$ (no occurrences of $a$ in $\tau$) so $(ab)\tau$ sends $a$ to $b$. It's not 
the identity! Therefore, we can get rid of all of the occurrences of $a$ by canceling out transpositions in {\bf pairs}. Continuing in this
fashion (after $a$ is gone pick the next smallest remaining number), we will eventually cancel out all of the transpositions. Since cancelations
always occur in pairs, it must be that $(1)$ was written as an even number of transpositions. Therefore, $(1)$ cannot be odd. $\Box$

\vspace{0.1in}

\noindent {\bf Theorem:} Every permutation in $S_n$ ($n>1$) is either even or odd, but not both.

\vspace{0.05in}

\noindent
{\bf proof:} Let $\sigma \in S_n$.  We know by the transposition trick above that $\sigma$ can be written as a product of transpositions.
Suppose $\sigma = (a_1a_2)\cdots(a_{2\ell-1}a_{2\ell})=(b_1b_2)\cdots(b_{2k-1}b_{2k})$. Then 

\vspace{-0.3in}

$$\begin{array}{rccc}
 (1)= & \sigma\sigma^{-1} & = & (a_1a_2)\cdots(a_{2\ell-1}a_{2\ell})[(b_1b_2)\cdots(b_{2k-1}b_{2k})]^{-1} \\
 = & (a_1a_2)\cdots(a_{2\ell-1}a_{2\ell})(b_{2k-1}b_{2k})^{-1}\cdots(b_1b_2)^{-1} & = & (a_1a_2)\cdots(a_{2\ell-1}a_{2\ell})(b_{2k-1}b_{2k})\cdots(b_1b_2)
\end{array}$$

\vspace{-0.1in}

\noindent
So we have written $(1)$ as the product of $\ell+k$ transpositions. Our lemma says that $\ell+k$ must be even. Therefore,
either both $k$ and $\ell$ are even or both are odd. $\Box$

\vspace{0.1in}

\noindent {\large \sc Quick Computations:}

We can quickly determine whether a permutation is even or odd by looking at its cycle structure. First, notice that we can
write an $\ell$-cycle as a product of $\ell-1$ transpositions. Therefore, even length cycles are odd permutations and odd length
cycles are even permutations (confusing but true). Thus the 3-cycle $(123)$ is an even permutation. More confusion: $|(123)|=3$ so $(123)$ has odd order!?!

Next, notice that if $\sigma$ can be written as a product of $\ell$ transpositions and $\tau$ can be written as a product of $k$ 
transpositions, then $\sigma\tau$ can be written as a product of $\ell+k$ transpositions. Then we just recall that ``even plus even is even''
``odd plus odd is even'' and ``even plus odd is odd''. So two even or two odd permutations multiplied (i.e. composed) together give
us an even permutation and an odd and an even permutation multiplied together give us an odd permutation. 

\vspace{0.05in}

\noindent
{\bf Example:} $(123)(45)(6789)$ is even since $(123)$ = even, $(45)$ = odd, and $(6789)$ = odd, so even + odd + odd = even.
Alternatively, $(123)(45)(6789) = (13)(12)(45)(69)(68)(67)$ --- 6 transpositions, therefore, even.  

\vspace{0.05in}

The inverse of a permutation can be computed merely by writing it down backwards:\\ $((123)(45))^{-1}=(54)(321)=(132)(45)$ (having good manners we ``simplified'' it). Thus it is obvious why the inverse of an even permutation is even and the inverse of an odd permutation is odd.


\vspace{0.1in}

\noindent {\large \sc The Sign Homomorphism:}

Since we have well-defined notions of even and odd-ness, we can now define the map: 

\vspace{-0.1in}

\[ \mbox{sgn}(\sigma) = (-1)^{\sigma} = \left\{ \begin{array}{cl} +1 & \sigma \mbox{ is even} \\ -1 & \sigma \mbox{ is odd} \end{array} \right\} \]

\vspace{-0.05in}

This map is called the ``sign homomorphism''. It can be used to define the determinant of a matrix. Let $A = (a_{ij})$ be an $n \times n$
matrix with entries $a_{ij}$. Then

\vspace{-0.1in}

\[ \mbox{det}(A) = \sum_{\sigma \in S_n} (-1)^{\sigma} a_{1\sigma(1)}a_{2\sigma(2)} \cdots a_{n\sigma(n)} \]

\vspace{-0.05in}

In particular, consider a $2 \times 2$ matrix. $S_2 = \{ (1), (12) \}$. Let $\sigma=(1)$. $\sigma$ is even so $(-1)^{\sigma} = +1$. Also, let
$\tau = (12)$. $\tau$ is odd so $(-1)^{\tau} = -1$. 
Thus $\mbox{det}(A) = (-1)^{\sigma} a_{1\sigma(1)}a_{2\sigma(2)} + (-1)^{\tau} a_{1\tau(1)}a_{2\tau(2)} = a_{11}a_{22}-a_{12}a_{21}$
(the regular $2 \times 2$ determinant formula).

\vspace{0.15in}

\noindent {\large \sc The Alternating Group:}

From the last discussion we see that: even composed with even is even, the identity is always even, and the inverse
of an even permutation is even. Putting this together we arrive at the following:

\vspace{0.05in}

\noindent {\bf Proposition:} For any $n>1$, $A_n = \{ \sigma \in S_n \,|\, \sigma \mbox{ is even } \}$ is a subgroup of $S_n$.

\vspace{0.05in}

Actually we can say even more. Notice that \vspace{-0.05in} $$\mathrm{kernel}(\mathrm{sgn}) = \{ \sigma \in S_n \;|\; \mathrm{sgn}(\sigma)=1 \} = \{ \sigma \in S_n \;|\; \sigma \mbox{ is even}\}=A_n.$$ \vspace{-0.05in}
Therefore, since $A_n$ is the kernel of the sign homomorphism, $A_n$ is a {\it normal} subgroup of $S_n$. $A_n$ is called the {\bf alternating group} on $n$ characters. These groups are very important. In fact, $A_n$ is a non-abelian {\bf simple} group when $n \geq 5$ (as we'll see later).

\vspace{0.1in}

\noindent
{\bf Examples:} $A_2 = \{ (1) \}$ \quad and \quad $A_3 = \{ (1), (123), (132) \}$.\quad For example, $(123)(45)(6789) \in A_9$.

\vspace{0.1in} 

Notice that multiplying by $(12)$ sends even permutations to odd permutations and vice-versa. The map $L(\sigma) = (12)\sigma$
is a bijection from $A_n$ to the set of odd permutations. Thus exactly half of the permutations in $S_n$ are even and half are odd.
This implies that the order of $A_n$ is $n!/2$. For example: $|A_3| = 3!/2 = 3$ and $|A_4|= 4!/2 = 12$.

It is also interesting to note that \fbox{every subgroup of $S_n$ is either all even or half even \& half odd.} Why? Consider a subgroup $H$ which contains an odd element $\sigma$. Then left 
multiplication by $\sigma$ gives bijection between the even and odd elements of $H$.
\newpage

\noindent {\large\sc $A_4$'s Subgroups and Quotients}:

First, recall that $A_1$ really isn't even defined, $A_2$ is the trivial group, and $A_3 = \langle (123) \rangle$ is cyclic. These are kind of anomalies. $A_4$ is a bit different from other$A_n$ as well. Let's study it in detail. We'll begin with the Cayley table for $A_4$.
$$A_4 = \{(1), (123), (132), (124), (142), (134), (143), (234), (243),(12)(34), (13)(24), (14)(23)\}$$

\vspace{0.1in}

\noindent \tiny
\begin{tabular}{c||c|c|c|c||c|c|c|c||c|c|c|c||}
        &    (1) &(12)(34)&(13)(24)&(14)(23)&  (123) &  (243) &  (142) &  (134) &  (132) &  (143) &  (234) &  (124) \\
\hline
\hline
    (1) &    (1) &(12)(34)&(13)(24)&(14)(23)&  (123) &  (243) &  (142) &  (134) &  (132) &  (143) &  (234) &  (124) \\
\hline
(12)(34)&(12)(34)&    (1) &(14)(23)&(13)(24)&  (243) &  (123) &  (134) &  (142) &  (143) &  (132) &  (124) &  (234) \\
\hline
(13)(24)&(13)(24)&(14)(23)&    (1) &(12)(34)&  (142) &  (134) &  (123) &  (243) &  (234) &  (124) &  (132) &  (143) \\
\hline
(14)(23)&(14)(23)&(13)(24)&(12)(34)&    (1) &  (134) &  (142) &  (243) &  (123) &  (124) &  (234) &  (143) &  (132) \\
\hline
\hline
  (123) &  (123) &  (134) &  (243) &  (142) &  (132) &  (124) &  (143) &  (234) &    (1) &(14)(23)&(12)(34)&(13)(24)\\
\hline
  (243) &  (243) &  (142) &  (123) &  (134) &  (143) &  (234) &  (132) &  (124) &(12)(34)&(13)(24)&    (1) &(14)(23)\\
\hline
  (142) &  (142) &  (243) &  (134) &  (123) &  (234) &  (143) &  (124) &  (132) &(13)(24)&(12)(34)&(14)(23)&    (1) \\
\hline
  (134) &  (134) &  (123) &  (142) &  (243) &  (124) &  (132) &  (234) &  (143) &(14)(23)&    (1) &(13)(24)&(12)(34)\\
\hline
\hline
  (132) &  (132) &  (234) &  (124) &  (143) &    (1) &(13)(24)&(14)(23)&(12)(34)&  (123) &  (142) &  (134) &  (243) \\
\hline
  (143) &  (143) &  (124) &  (234) &  (132) &(12)(34)&(14)(23)&(13)(24)&    (1) &  (243) &  (134) &  (142) &  (123) \\
\hline
  (234) &  (234) &  (132) &  (143) &  (124) &(13)(24)&    (1) &(12)(34)&(14)(23)&  (142) &  (123) &  (243) &  (134) \\
\hline
  (124) &  (124) &  (143) &  (132) &  (234) &(14)(23)&(12)(34)&    (1) &(13)(24)&  (134) &  (243) &  (123) &  (142) \\
\hline
\hline
\end{tabular}

\vspace{0.2in}
\normalsize

Let's find all of the subgroups of $A_4$. First, we have all of the cyclic subgroups.

\vspace{0.1in}

\noindent
\begin{minipage}[c]{3.5in}
\begin{itemize}
\item $\langle (1) \rangle = \{ (1) \}$ 
\item $\langle (12)(34) \rangle = \{ (1), (12)(34) \}$ 
\item $\langle (13)(24) \rangle = \{ (1), (13)(24) \}$ 
\item $\langle (14)(23) \rangle = \{ (1), (14)(23) \}$ 
\end{itemize}
\end{minipage}
\begin{minipage}[c]{3.5in}
\begin{itemize}
\item $\langle (123) \rangle = \langle (132) \rangle = \{ (1), (123), (132) \}$ 
\item $\langle (124) \rangle = \langle (142) \rangle = \{ (1), (124), (142) \}$ 
\item $\langle (134) \rangle = \langle (143) \rangle = \{ (1), (134), (143) \}$ 
\item $\langle (234) \rangle = \langle (243) \rangle = \{ (1), (234), (243) \}$ 
\end{itemize}
\end{minipage}

\vspace{0.1in}

By looking at the Cayley table we can see if we tried to form a subgroup
with a couple of 3-cycles (which aren't inverses of each other), we end up
generating all of $A_4$. For example: $(123)(134) = (234)$ so if
a subgroup contains $(123)$ and $(134)$, it must also contain $(234)$ and
inverses and the identity --- we're already up to $2+2+2+1=7$ elements
and since the order of a subgroup divides $|A_4|=12$, we must conclude
that any subgroup containing both $(123)$ and $(134)$ is all of $A_4$.

Next, what if we try to have a 3-cycle and an element like $(12)(34)$?
Say $(123)$ and $(12)(34)$. Well, $(123)(12)(34) = (134)$ so we have
two different 3-cycles again and thus we must generate the whole group $A_4$.
Summing up (so far), any subgroup with at least one 3-cycle must either
be one of the 4 cyclic subgroups of order 3 or all of $A_4$.

What about the non 3-cycle elements? $(12)(34)\;(13)(24) = (14)(23)$
So to we can't have a subgroup with just two of these elements. We
must include all 3 of them. Let's look at
$H = \{(1),(12)(34),(13)(24),(14)(23)\}$. Looking at the table,
we can see $H$ is closed -- so $H$ is a subgroup (by the finite subgroup
test).

Therefore, adding\dots

\vspace{0.1in}

\noindent 
\begin{minipage}[c]{3.5in}
\begin{itemize}
\item $H = \{(1),(12)(34),(13)(24),(14)(23)\}$
\end{itemize}
\end{minipage}
\begin{minipage}[c]{3.5in}
\begin{itemize}
\item $A_4$
\end{itemize}
\end{minipage}

\vspace{0.1in}

\noindent to the list (of cyclic subgroups) completes our list of all of the subgroups of $A_4$.
Our next question is, ``Which subgroups are normal?''

The following calculations show that $gKg^{-1}\not=K$ for each cyclic subgroup
$K$ (other than the trivial subgroup $\langle (1) \rangle$). Therefore, they are 
{\bf not} normal. (Does that mean they're {\it weird}?)

\vspace{0.1in}

\noindent \force\hspace*{-0.3in}
\begin{minipage}[c]{4in}
\begin{itemize}
\item $(123)\langle (12)(34) \rangle(123)^{-1} = \langle (14)(23) \rangle 
       \not= \langle (12)(34) \rangle$ 
\item $(123)\langle (13)(24) \rangle(123)^{-1} = \langle (12)(34) \rangle 
       \not= \langle (13)(24) \rangle$ 
\item $(123)\langle (14)(23) \rangle(123)^{-1} = \langle (13)(24) \rangle 
       \not= \langle (14)(23) \rangle$ 
\end{itemize}
\end{minipage}
\begin{minipage}[c]{3.5in}
\begin{itemize}
\item $(124)\langle (123) \rangle(124)^{-1} = \langle (243) \rangle 
       \not= \langle (123) \rangle$
\item $(123)\langle (124) \rangle(123)^{-1} = \langle (234) \rangle 
       \not= \langle (124) \rangle$
\item $(123)\langle (134) \rangle(123)^{-1} = \langle (142) \rangle 
       \not= \langle (134) \rangle$
\item $(123)\langle (234) \rangle(123)^{-1} = \langle (143) \rangle 
       \not= \langle (234) \rangle$
\end{itemize}
\end{minipage}

\vspace{0.05in}

\noindent
Of course the trivial subgroup $\langle (1) \rangle$ and $A_4$ itself are normal in $A_4$.
(For any group $G$, \{1\} and $G$ are normal subgroups of $G$.) 

Now the only subgroup left to consider is $H = \{(1),(12)(34),(13)(24),(14)(23)\}$. 

\vspace{-0.1in}

\begin{itemize}
\item $H = \{(1),(12)(34),(13)(24),(14)(23)\}$\force\\
      {\Large\strut}{\small $H = (1)H = (12)(34)H = (13)(24)H = (14)(23)H = H(1) = H(12)(34) = H(13)(24) = H(14)(23)$}
\item $(123)H = \{(123),(134),(243),(142)\}$\force\\
       {\Large\strut}{\small $(123)H = (134)H = (243)H = (142)H = H(123) = H(134) = H(243) = H(142)$} 
\item $(132)H = \{(132),(234),(124),(143)\}$\force\\
       {\Large\strut}{\small $(132)H = (234)H = (124)H = (143)H = H(132) = H(234) = H(124) = H(143)$}      
\end{itemize}

\vspace{-0.1in}

\noindent So $H \lhd A_4$.

Let's look at all of the quotients of $A_4$. First, the trivial cases.
\begin{itemize}
\item $\displaystyle{{A_4 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} 
       \hspace*{0.1in} {\; \atop A_4} \cong \{ 1 \}}$ \quad \quad
      $[A_4:A_4]=1$ so the quotient group has order 1 and thus is the trivial group.
\item $\displaystyle{{A_4 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} 
       \hspace*{0.1in} {\; \atop \{(1)\}} \cong A_4}$ \quad \quad  
      Quotienting by the trivial subgroup ``does nothing''.
\end{itemize}

\noindent
The quotient by $H = \{(1),(12)(34),(13)(24),(14)(23)\}$ is more interesting.
\[ \left|{A_4 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} 
   {\; \atop H}\right| = {|A_4| \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} 
   \hspace*{0.1in} {\; \atop |H|} = [A_4\;:\;H] = \frac{12}{4} = 3 \]
Since there is only 1 group order 3 (up to isomorphism),
$\displaystyle{{A_4 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} 
       \hspace*{0.1in} {\; \atop H} \cong \mathbb{Z}_3}$

\vspace{0.05in}

\noindent
{\bf Example:} Multiplying cosets.
\[ (243)H \; (124)H = (243)(124)H = (14)(23)H = H \]
Therefore, $\displaystyle{\left((243)H\right)^{-1} = (124)H}$. 

\vspace{0.05in}

\noindent
Working out all of the other cases, we get the following Cayley table for $\displaystyle{{A_4 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop H}}$:

\vspace{0.1in}

\begin{center}
\begin{tabular}{ccc}
\begin{tabular}{c||c|c|c|c|}
        &      H & (123)H & (132)H \\
\hline
\hline
      H &      H & (123)H & (132)H \\
\hline
 (123)H & (123)H & (132)H &      H \\
\hline
 (132)H & (132)H &      H & (123)H \\
\hline
\end{tabular} 
 & $\qquad \qquad \cong \qquad \qquad$ & 
\begin{tabular}{c||c|c|c|c|}
   & 0 & 1 & 2 \\
\hline
\hline
 0 & 0 & 1 & 2 \\ 
\hline
 1 & 1 & 2 & 0 \\ 
\hline
 2 & 2 & 0 & 1 \\
\hline
\end{tabular}
\end{tabular}
\end{center}

\vspace{0.2in}

\noindent
Notice that since we ordered the elements in the original Cayley table according to
cosets of $H$,\\ we have $4 \times 4$ ``blocks'' of the original table corresponding
to the entries of the quotient group's table.

Next, because $H$ itself is Abelian, so any subgroup of $H$ is automatically normal (in $H$). Thus $\langle (12)(34) \rangle \lhd H$. Then noting that $\displaystyle{{H \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} 
       \hspace*{0.1in} {\; \atop \langle (12)(34) \rangle } \cong \mathbb{Z}_2}$, we have the following composition series for $A_4$:

\begin{center}
\begin{tikzpicture}[node distance=0.5cm]
 \node(grp){$A_4$};
 \node(grp2)[right of = grp,xshift=1cm]{};
 \node(H)[right of = grp2,xshift=1cm]{$H$};
 \node(H2)[right of = H,xshift=1cm]{};
 \node(cyc)[right of = H2,xshift=1cm]{$\langle (12)(34) \rangle$};
 \node(cyc2)[right of = cyc,xshift=1cm]{};
 \node(1)[right of = cyc2,xshift=1cm]{$\{ 1 \}$};

 \node(grpMH)[above of = grp2]{$\mathbb{Z}_3$};
 \node(HMcyc)[above of = H2]{$\mathbb{Z}_2$};
 \node(cycM1)[above of = cyc2]{$\mathbb{Z}_2$};

  \draw(grp)--(H);
  \draw(H)--(cyc);
  \draw(cyc)--(1);
\end{tikzpicture}
\end{center}

\newpage 

The subgroup lattice for $A_4$...

\vspace{-0.2in}

\begin{tikzpicture}[node distance=2cm]
\node(grp){$A_4$};

\node(spot)[below of = grp]{};

\node(H)[right of = spot,xshift=1cm]{$H$};
\node(1324)[below of = H]{$\langle (13)(24) \rangle$};
\node(1234)[left of = 1324]{$\langle (12)(34) \rangle$};
\node(1423)[right of = 1324]{$\langle (14)(23) \rangle$};

\node(234)[below left of = spot]{$\langle (234) \rangle$};
\node(134)[left of = 234]{$\langle (134) \rangle$};
\node(124)[left of = 134]{$\langle (124) \rangle$};
\node(123)[left of = 124]{$\langle (123) \rangle$};

\node(1)[below of = 1234]{$\{ (1) \}$};

\draw(grp)--(123);
\draw(grp)--(124);
\draw(grp)--(134);
\draw(grp)--(234);
\draw(grp)--(H);

\draw(H)--(1234);
\draw(H)--(1324);
\draw(H)--(1423);

\draw(123)--(1);
\draw(124)--(1);
\draw(134)--(1);
\draw(234)--(1);
\draw(1234)--(1);
\draw(1324)--(1);
\draw(1423)--(1);
\end{tikzpicture}

\vspace{0.05in}

\noindent {\large\sc $A_n$ is Simple (for $n \geq 5$)}:

\vspace{0.05in}

\noindent {\bf Definition:} $G$ is {\bf simple} if $|G|>1$ and $G$ has no non-trivial proper normal subgroups.

\vspace{0.2in}

\noindent {\bf Theorem:} If $G$ is an abelian simple group, then $G \cong \mathbb{Z}_p$ for some prime $p$.

\vspace{0.05in}

\noindent {\it proof:} Let $G$ be an abelian simple group.

Remember that every subgroup of an abelian group is automatically normal (left cosets = 
right cosets because everything commutes). 

Let $x \in G$ with $x \not= 1$ (1 is the identity of $G$). Then $\langle x \rangle$ is a
non-trivial normal subgroup of $G$. So since $G$ is simple, we must have that $G = \langle x \rangle$
(If $G$ is abelian and simple, $G$ must be cyclic).

First, suppose $G$ is infinite. The only infinite cyclic group (up to isomorphism) is $\mathbb{Z}$. But 
this is not a simple group since $2\mathbb{Z}$ is a non-trivial proper (normal) subgroup. Therefore,
$G$ must be finite.

Suppose $|G|=n$. If $n$ is composite, say with proper divisors $k \not= 1$ and $\ell \not= 1$ such that $n=k\ell$,
then $x^{n/k}$ is an element of order $\ell$. So $\langle x^{n/k} \rangle$ is a non-trivial proper (normal) subgroup
of $G$ (of order $\ell$). Thus $n$ must be prime ($n$ can't be 1 since simple groups are non-trivial).

Now suppose $|G|=p$ ($p$ prime). Let $N$ be a non-trivial (normal) subgroup of $G$. Since $|N|$ must 
divide $|G|=p$ and $|N| \not= 1$ (it's non-trivial). We must have $|N|=p$ and so $N=G$. Thus $G$ has
no non-trivial (normal) subgroups. Thus it's simple. $\Box$

\vspace{0.2in}

\noindent {\bf Lemma:} Let $N$ be a normal subgroup of $A_n$. If $N$ contains a 3-cycle, then $N=A_n$.

\vspace{0.05in}

\noindent {\it proof:} Suppose $N$ contains a 3-cycle. We can relabel 1, 2, \dots, $n$ so this 3-cycle is labeled $(123)$.
So without loss of generality assume $(123) \in N$ and so $(123)^2 = (132) \in N$ since $N$ is a subgroup.

If $n=3$, then $A_3 = \{ (1), (123), (123)^2 \} \subseteq N$ so $N=A_3$. So assume $n \geq 4$ and pick some $k \geq 4$.
$(12)(3k)(132)[(12)(3k)]^{-1} = (12)(3k)(132)(12)(3k) = (12k) \in N$.  So $(12k) \in N$ for all $k \geq 3$. 

Let $a,b,c$ be distinct numbers between 3 and $n$. $(1a2) = (12a)(12a) \in N$. $(1ab) = (12b)(12a)(12a) \in N$.
$(2ab) = (12b)(12b)(12a) \in N$. $(abc) = (12a)(12a)(12c)(12b)(12b)(12a) \in N$. Thus $N$ contains all 3-cycles.

Finally notice that if $a,b,c,d$ are all distinct, then $(ab)(cd) = (adb)(adc)$ and $(ab)(ac) = (acb)$ and $(ab)(ab)=(1)$
so any permutation written as a product of an even number of transpositions can be written as a product of 3-cycles.
Thus $A_n$ is generated by 3-cycles. So if $N$ contains all the 3-cycles, then $N=A_n$. $\Box$

\vspace{0.1in}

\noindent {\bf Theorem:} $A_n$ is simple when $n \geq 5$ and $n=3$.

\vspace{0.05in}

\noindent {\it proof:} Note that $A_n$ only makes sense for $n \geq 2$. $A_2$ is trivial and $A_4$ has a proper normal
subgroup $H = \{ (1), (12)(34), (13)(24), (14)(23) \}$, so $A_2$ and $A_4$ are not simple. $A_3 = \langle (123) \rangle \cong \mathbb{Z}_3$ 
so it's simple (\& abelian). Now let $n \geq 5$ and let $N$ be a non-trivial normal subgroup of $A_n$.

\vspace{0.05in}

\noindent {\bf Case 1:} $N$ has an element with a cycle of length $\geq 4$. Without loss of generality we can relabel $1, 2, \dots, n$ so that
this cycle is $(123\cdots r)$ for some $r \geq 4$. So there exists some $\sigma = (12\cdots r)\tau \in N$ where $(12\cdots r)$ and $\tau$
are disjoint. Consider $(123) \in A_n$ so that $(123)\sigma(123)^{-1} \in N$ since $N$ is normal. Thus $\sigma^{-1}(123)\sigma(123)^{-1} \in N$ since $N$ is a subgroup and thus closed under inverses and the product. 
$\sigma^{-1}(123)\sigma(123)^{-1} = \tau^{-1}(r \cdots 321)(123)(123 \cdots r)\tau(123)^{-1}=$ $\tau^{-1}\tau (r \cdots 321)(2314 \cdots r)=$
$(13r) \in N$ ($\tau$ commutes because it's disjoint from $\{1,\dots,r\}$). Thus $N$ contains a 3-cycle so $N=A_n$.

\vspace{0.05in}

\noindent {\bf Case 2:} $N$ has an element with a 3-cycle and no cycles of length $>3$ (which is covered by case 1). 
Call this element $\sigma$.

First, suppose $\sigma$ has at least 2 disjoint 3-cycles. Without loss of generality suppose they are $(123)$ and $(456)$ so
$\sigma = (123)(456)\tau$ where $\tau$ is disjoint from $(123)$ and $(456)$.  Consider $(124) \in A_n$. Then $(124)\sigma(124)^{-1} \in N$
and so $\sigma^{-1}(124)\sigma(124)^{-1} \in N$. Thus $\sigma^{-1}(124)\sigma(124)^{-1}  = \tau^{-1}(456)^{-1}(123)^{-1}(124)(123)(456)\tau(124)^{-1}=$ $(654)(321)(124)(123)(456)(421)=$ $(14263) \in N$. So $N$ contains a cycle of length $>3$. Thus $N=A_n$ by case 1.

Next, suppose $\sigma$ has 1 cycle of length 3 and then just disjoint transpositions.  Without loss of generality suppose this 3-cycle
is $(123)$. So $\sigma = (123)\tau \in N$ where $\tau$ is the product of disjoint transpositions so that $\tau=\tau^{-1}$. Then
$\sigma^2 \in N$ since $N$ is a subgroup. $\sigma^2 = (123)\tau(123)\tau = (123)^2 \tau^2 = (123)^2 = (132)$. Thus $N$ contains
a 3-cycle so $N=A_n$.

The only possibility left is that $\sigma$ is just a 3-cycle. But then $N$ contains a 3-cycle so $N=A_n$.

\vspace{0.05in}

\noindent {\bf Case 3:} $N$ contains an element which is the product of disjoint transpositions. Call it $\sigma$. 
Now since $N$ is a subset of $A_n$, $\sigma$ is even. So $\sigma$ must contain at least 2 disjoint transpositions. Without loss
of generality assume these transpositions are $(12)$ and $(34)$. So $\sigma = (12)(34)\tau$ where $\tau$ is disjoint from $(12)$ and
$(34)$ and $\tau = \tau^{-1}$ since it's the product of disjoint transpositions itself. $(123)\sigma(123)^{-1} \in N$ since $N$ is normal
and thus $\sigma^{-1}(123)\sigma(123)^{-1} \in N$ since $N$ is closed under inverses and products. 
$\sigma^{-1}(123)\sigma(123)^{-1}=$ $\tau^{-1}(34)(12)(123)(12)(34)\tau(132) =$  $(34)(12)(123)(12)(34)(132) =$ $(13)(24) \in N$.
So $(135)(13)(24)(135)^{-1} \in N$ and also $(13)(24)(135)(13)(24)(135)^{-1} \in N$. But 
$(13)(24)(135)(13)(24)(135)^{-1} = (135)$. Thus $N$ contains a 3-cycle so $N=A_n$ [Note: We didn't use the fact that $n \geq 5$ until
the very end!] $\Box$

\vspace{0.05in}

\noindent {\bf Corollary:} Let $n \geq 5$. The only normal subgroups of $S_n$ are $\{ (1) \}$, $A_n$, and $S_n$.

\vspace{0.05in}

{\it proof:} First note that these are in fact normal subgroups of $S_n$ since the trivial subgroup and the whole group are
always normal. $A_n$ is the kernel of the sign homomorphism so it's normal [or we could use the fact that $A_n$ is a subgroup
of index 2 and index 2 subgroups are always normal].

Let $N$ be a normal subgroup of $S_n$. Then $N \cap A_n$ is normal in $A_n$. Thus $N \cap A_n = A_n$ or $N \cap A_n = \{ (1) \}$.
If $N \cap A_n = A_n$. Then either $N = A_n$ or $|N| > n!/2$ so $|N|=n!$ (there are no divisors of $\ell$ between $\ell/2$ and $\ell$) so
$N=S_n$. 

Now let's consider the case where $N \cap A_n = \{ (1) \}$. Thus $N - \{(1)\}$ is a collection of odd permutations. Let $\sigma, \tau \in N - \{ (1) \}$. Then 
$\sigma \tau \in N$ but $\sigma \tau$ is even since the product of two odd permutations is an even permutation. Thus $\sigma \tau = (1)$.
This applies to all non-identity elements of $N$. So $\sigma \sigma = (1)$ if $\sigma \not= (1)$ in $N$ as well. Thus
$\sigma\sigma=(1)=\sigma\tau$ so $\sigma=\tau$. Thus if $N \not= \{ (1) \}$, then $N = \{ (1), \tau \}$ where $\tau^2=(1)$.
So $\tau$ is a product of disjoint transpositions (since its order is 2). Also, $\tau$ must be odd so it's the
product of an {\it odd} number of disjoint transpositions. 

Suppose $\tau$ is a single transposition. Without loss of generality assume $\tau = (12)$, then $(13)(12)(13) = (23) \in N$ since $N$ 
is normal in $S_n$. But $(12) \not= (13)$ so $N$ has more than 2 elements (contradiction). 

Finally consdier the case where $\tau$ is the product of more than a single transposition. Without loss of generality assume two the
disjoint transpositions are $(12)$ and $(34)$. So $\tau = (12)(34)\sigma$ where $\sigma$ is disjoint from $(12)$ and $(34)$, then
$(13)\tau(13) = (13)(12)(34)\sigma(13) = (14)(23)\sigma \in N$. But $\tau = (12)(34)\sigma \not= (14)(23)\sigma$ so $N$ has more than 2 elements (contradiction).  

Therefore, $N$ cannot contain a single odd permuation. Thus $N=\{ (1) \}$. $\Box$


\end{document}

