\chapter{Symmetric Group}


In combinatorics an elementary question that students encounter is how to count permutations; how many ways can $n$ distinct objects be ordered? We can represent a certain permutation of elements on a set as a bijective function.

\begin{definition}[Permutation function]
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}


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 : \{1,2,3\} \to \{1,2,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.

Generalizing this to any $\mathbb{Z} / n\mathbb{Z}$
\[\sigma( m ) = \sigma_{m2}  \]







This book is about group theory afterall, and indeed, permutatiuon functions form a group! Not only this, but they form extremely powerful and fundamental groups.


\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 operation
\end{itemize}
	A subgroup of a symmetric group is called a permutation group
	Note that composition of this group is literally the composition of functions.
\end{definition}

Since we usually don't care about the actual elements of $X$ but rather how many elements there are in $X$ (since these will all be isomorphic to eachother anyways), we usually just consider the elements to be the first $n$ natural numbers.



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


As alluded to, finite symmetric groups can always (up to an isomorphism) be represented as some $\mathrm{Sym}(n)$.


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

As we know from combinatorics, there are $n!$ permutations of $n$ distinct objects.

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



- permutation group is a subgroup of a symmetry group

\section{Cayley's theorem}

Aside from combinatorial applications, symmetric groups are useful in the classification of groups; representing groups in terms of more basic groups. A simple example of this being Cayley's theorem.

Consider the following class of functions.
\[\sigma_{g}(h)=gh\]
These functions can be seen to be permutations of $\mathrm{Sym}(G)$, and furthermore, $g \to \sigma_{g}$ is an injective homomorphism. The image of this injective homomorphism represents a subgroup of $\mathrm{Sym}(G)$, hence every group is isomorphic to some permutation group.


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


It has been noted that as interesting as this result may be, it doesn't seem to have profound implications regarding the methods used by group theorists.


 \section{Cycles}


There exists a special class of permutation functions called 'cycles'; 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 function is a cycle, however as it turns out, 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'.


\begin{definition}[$k$-cycle]
A \emph{$k$-cycle} is a permutation $\sigma : X \to X$ such that there is a $x\in X$ such that for any $y \in X$ we either have an $n \leq k$ where $\sigma^n (x) = y$ or $\sigma(y)=y$. Call $x$ the generator of this cycle.



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}




Let $\sigma$ be a $k$-cycle, then $\sigma^k (x)=x$.


Let $\sigma$ be a $k$-cycle, then there are $k$ generators of that cycle, precisely the elements of the form $\sigma^n (x)$, where $x$ is a known generator.


We can represent a special notation for cycles; tuples that represent those elements that such an $x$ generates under repeated composition.

We represent a \emph{$k$-cycle} as $(x, \sigma(x), \sigma^2(x), \hdots , \sigma^{k-1}(x) )$.

One may note that any element in this tuple can 


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

\subsection{Properties of Cycles}

- commutativity of disjoint cycles

\begin{proposition}
Let $\sigma,\tau$ be disjoint cycles. then $\sigma \tau = \tau \sigma$.
\end{proposition}

\begin{proposition}
All permutation functions are the unique representation as the product of disjoint cycles.
\end{proposition}


\begin{definition}[Cycle type]
\end{definition}

\begin{lemma}[Conjugate cycle lemma]
Let $\sigma$ be a permutation function and $ \tau = ( t_1 , \hdots , t_n )$ be a cycle, then the following holds.
\[\sigma \tau \sigma^{-1} = ( \sigma(t_1) , \hdots , \sigma(t_n) ) \]
\end{lemma}

\begin{theorem}[Cycle type-conjugation theorem]
Given a $k$-cycle $\tau$, any other $k$-cycle can be represented by some $\sigma \tau \sigma^{-1}$ for some permutation function $\sigma$.
\end{theorem}

I've just come up with the following theorem, it's not very important.

\begin{theorem}
Let $\sigma$ be a permutation of $n$ disjoint cycles with lengths $l_1,l_2,...,l_n$. Then $\sigma^{\mathrm{lcm}(l_1,l_2,...,l_n)}=\sigma$
Hence we have  $\sigma^{\mathrm{lcm}(l_1,l_2,...,l_n)-1}=\sigma^{-1}$
\end{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}[Inversion set of a permutation]
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}

\section{Alternating group}

\subsection{Permutation signature}
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}[Permutation signature]
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  , \hdots , x_k)) =(-1)^{k-1} \]
\end{proposition}


\subsection{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}