\part{Symmetric Groups}

\chapter{Symmetric Group}

\begin{definition}
A \emph{permutation function on $X$} is a bijective function $\sigma : X \to X$. It represents the idea of permuting (swapping around) elements of $X$.
\end{definition}




\begin{definition}
A \emph{symmetric group} is a group $( \mathrm{Sym}(X), \circ )$.
\begin{itemize}
	\item $\mathrm{Sym}(X)$ is the set of all permutation functions on $X$
	\item $\circ$ is the function composition operator
\end{itemize}
\end{definition}


\begin{definition}
$\mathrm{Sym}(n)$ represents the symmetry group with permutations on $\mathbb{N}\cap[1,n]$.
\end{definition}

\begin{proposition}
Symmetric groups on sets of the same cardinality are isomorphic.
\[ |X|=|Y| \implies \mathrm{Sym}(X) \cong \mathrm{Sym}(Y)\]
\end{proposition}

This means that finite symmetric groups can always (up to an isomorphism) be represented as some $\mathrm{Sym}(n)$.


\begin{proposition}
\[ | \mathrm{Sym}(n)| = n! \]
\end{proposition}


There are 3 standard notations to represent the mappings of a permutation 
\begin{itemize}
	\item Standard function notation
	\item Matrix notation
	\item Cycle notation
\end{itemize}

As with any general function, a permutation is expressible as an equality of the function on its argument to its mappings, for instance, there is an element $\sigma \in \mathrm{Sym}(3)$ denoted as such.
\[ \sigma(n) = \begin{cases} 3 & n=1 \\ 1 & n=2 \\ 2 & n=3 \end{cases} \]. 

Since permutations are bijective functions, this is perhaps the most mathematically faithful, and it can theoretically represent any permutation (even when considering infinite symmetric groups!). However, this notation grows exponentially inefficient for representing permutations of larger symmetry groups.

The 'two line' notation uses a matrix where the first row indicates the indexes, and the second row indicates mappings
\[ \sigma = \begin{bmatrix} 1 2 3 \\ 3 1 2 \end{bmatrix} \]
This can be more concise than the function notation, however can only really be used for permutations of finite (maybe countable with some adjustments) symmetric groups.

- matrix notation
- permutation group

There exists a notation of 'cycles' which is even more efficient; it describes where to send an element, and then where to send that displaced element to, and then the next displaced element, until the original element's index is filled. Not every permutation is reducible to a single cycle, however compositions of cycles can represent any permutation in a symmetric group; this result will be proved shortly.

\[ \sigma = (1 & 3 & 2) \]

Assume indexed in order, the cycle then says to send 'index 3' to 'index 1, 'index 2' to 'index 3', and finally 'index 1' to 'index 2'.








\chapter{Cycles}
 \section{Cycles}
\begin{definition}
A \emph{$k$-cycle} is a permutation $\sigma$ defined as $(x & \sigma(x) & \sigma^2(x) & \hdots & \sigma^{k}(x) \)$.
A $2$-cycle is calso called a \emph{transposition}.
A \emph{simple transposition} is a transposition that permutes adjacent elements, so is of the form $(i,i+1)$.
\end{definition}


\begin{definition}
\emph{disjoint pairs of cycles} are a pairs of cycles that permute no element in common; they contain no element in common.
\end{definition}

\section{Properties of Cycles}

- commutativity of disjoint cycles
- all bijections have unique disjoint cycle product representation
- cycle type
- conjugate cycle lemma
- cycle type-conjugation theorem

\section{Inversions}

It's often useful to see how 'out of order' a permutation is from the identity permutation (in other words, how many simple transpositions are required to form the permutation). The idea of inversions captures this.

\begin{definition}
The \emph{inversion set of a permutation} is the set of all pairs of elements that are 'out of order' in the sense that  permutation permutes some number to a larger number. Let $n(\sigma)=|I_\sigma|$ be the \emph{inversion number function}.
\[I_{\sigma} = \{ (i,j) : 1 \leq i < j \leq N \land \sigma(i) > \sigma(j) \}  \]
\end{definition}

\begin{proposition}
$\sigma$ is identity permutation iff $n(\sigma)=0$
\end{proposition}

When two 'adjacent' elements are permuted by a simple transposition, the number of inversions changes by 1. This is characterized in the following lemma.

\begin{lemma}
For a simple transposition $s_i$ and permutation $\sigma$, we have the following.
	\[ n(\sigma s_i ) = \begin{cases}  n(\sigma)+1 & \sigma(i) < \sigma(i+1)\\ n(\sigma)-1  & \sigma(i) > \sigma(i+1) \end{cases} \]
\end{lemma}

\begin{proposition}
$\sigma$ is a product of $n(\sigma)$ simple transpositions.
\end{proposition}

\chapter{Alternating group}

\section{Permutation signatures}

So far we have been counting the amount of simple transpositions required to form a permutation; we can class permutations by the parity of this count.

\begin{definition}
The \emph{permutation signature} is a function $\mathrm{sgn} : \mathrm{Sym}(n) \to \{\pm 1\}$ defined on symmetry groups that keeps parity of the amount of inversions.
\[ \mathrm{sgn}(\sigma) = (-1)^{n(\sigma)} \]
\end{definition}

The signature function has a codomain of two elements; however an important homomorphism can be established.
\begin{proposition}
The signature function is a homomorphism from $\mathrm{Sym}(n)$ to $\mathbb{Z} / 2\mathbb{Z}$.
\end{proposition}


Calculating the signature for a cycle is simply a matter of counting the amount of elements it cycles between.

\begin{proposition}
\[ \mathrm{sgn}((x_1  & x_2  & ... & x_k)) =(-1)^{k-1} \]
\end{proposition}


\section{Alternating group}

Permutation signatures serve as a function that encapsulates a notion of 'parity' of permutations; does it require an even or odd amount of simple transpositions to form?

What happens when one considers the subgroup of only 'even' signatures? This is the kernel of the signature homomorphism, hence it is a normal subgroup. It is specifically called the \emph{alternating group}.

\begin{definition}
$\mathrm{Alt}(n)$ represents the subgroup of $\mathrm{Sym}(n)$ of permutations with signature $1$. 
Alternatively, it is $\mathrm{ker}(\mathrm{sgn})$, where $\mathrm{sgn} : \mathrm{Sym}(n) \to \mathbb{Z} / 2\mathbb{Z}$ is the permutation signature function.
\[ \mathrm{Alt}(n) < \mathrm{Sym}(n) \]
\[ \mathrm{Alt}(n) =\{ \sigma \in  \mathrm{Sym}(n) : \mathrm{sgn}(\sigma)=1 \} \]
\end{definition}

\begin{proposition}
\[ |\mathrm{Alt}(n)| = \frac{n!}{2}\]
\end{proposition}


Since the signature function is a homomorphism to $\mathbb{Z} / 2\mathbb{Z}$ we can create the following isomorphism by the first isomorphism theorem.

\begin{proposition}
\[ \mathrm{Sym}(n) / \mathrm{Alt}(n) \cong \mathbb{Z} / 2\mathbb{Z} \]
\end{proposition}


\begin{proposition}
Let $\sigma \in \mathrm{Alt}(n)$, then $\sigma$ is a product of 3-cycles. 
\end{proposition}


\section{Simple group}

\begin{definition}
A \emph{simple group} is a group whose only normal subgroups are the trivial group and itself.
\end{definition}

Every permutation of $\mathrm{Alt}(n)$ where $n \geq 3$ is a product of $3$-cycles.
\begin{proposition}
For $n \geq 5$, $\mathrm{Alt}(n)$ is simple.
\end{proposition}

\section{Cayley's theorem}



\begin{theorem}
Every group is isomorphic to a permutation group.
\[ (G,\cdot) \]
\[\exists H \leq \mathrm{Sym}(G) [  G \cong H ] \]
\end{theorem}

