grouptheory.tex

\documentclass[10pt]{book}

\newif\ifispdf
\ifx\pdfoutput\undefined
\ispdffalse % we are not running PDFLaTeX
\else
\pdfoutput=1 % we are running PDFLaTeX
\ispdftrue
\fi

\ifispdf
\usepackage[pdftex]{graphicx}
\else
\usepackage{graphicx}
\fi


\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{theorem}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{ifthen}
\usepackage{makeidx}
\usepackage{hyperref}

\newcommand{\version}{0.1}

%theorems and similar
\theoremstyle{break}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theorembodyfont{\slshape}
\newtheorem{definition}{Definition}[section]

\theorembodyfont{\rmfamily}
%\newtheorem{example}{Example}[section]

\newcounter{example}[section]

\renewcommand{\theexample}{\thesection.\arabic{example}}

\newenvironment{example}[1][]%
{\par\vspace{\theorempreskipamount}\refstepcounter{example}\noindent\textbf{Example
\theexample\ifthenelse{\equal{#1}{}}{}{
(#1)}}\\\hspace*{\parindent}}%
{\hfill$\Diamond$\par\vspace{\theorempostskipamount}}

\newenvironment{proof}[1][]%
{\par\noindent\textit{Proof\ifthenelse{\equal{#1}{}}{}{
(#1)}:}\\\hspace*{\parindent}}%
{\hfill\rule{2ex}{2ex}\par\vspace{\theorempostskipamount}}

\newcounter{exercise}[section]
\renewcommand{\theexercise}{\thesection.\arabic{exercise}}

\newenvironment{exercises}%
{\begin{list}{\theexercise.}{\usecounter{exercise}}}%
{\end{list}}

\newcounter{theoremenum}
\renewcommand{\thetheoremenum}{\roman{theoremenum}}

\newenvironment{theoremenum}%
{\begin{list}{(\thetheoremenum)}{\usecounter{theoremenum}}}%
{\end{list}}

\newcommand{\defn}[2]{\textsl{\textbf{#1\index{#2|emph}}}}

\newcommand{\sidebar}[2]{\mbox{}\marginpar{\footnotesize\raggedright\hspace{0pt}\textbf{#1:}
\textsl{#2}}}

\newcommand{\opsidebar}[2]{\reversemarginpar\sidebar{#1}{#2}\normalmarginpar}

\newcommand{\naturals}{\ensuremath{\mathbb{N}}}
\newcommand{\integers}{\ensuremath{\mathbb{Z}}}
\newcommand{\rationals}{\ensuremath{\mathbb{Q}}}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\newcommand{\complex}{\ensuremath{\mathbb{C}}}
\newcommand{\torus}{\ensuremath{\mathbb{T}}}
\newcommand{\field}{\ensuremath{\mathbb{F}}}
\newcommand{\ring}{\ensuremath{\mathbb{K}}}

\newcommand{\powerset}{\mathcal{P}}
\newcommand{\divides}{\mid}
\newcommand{\intersect}{\cap}
\newcommand{\bigintersect}{\bigcap}
\newcommand{\union}{\cup}
\newcommand{\bigunion}{\bigcup}
\newcommand{\symdiff}{\bigtriangleup}
\newcommand{\cross}{\times}
\newcommand{\isom}{\cong}

\newcommand{\id}{\text{id}}
\newcommand{\tr}{\text{tr}}
\newcommand{\diag}{\text{diag}}
\newcommand{\diam}{\text{diam}}

\newcommand{\seq}[1]{(#1_{n})_{n=1}^{\infty}}
\newcommand{\net}[3]{(#1_{#2})_{#2 \in #3}}

\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}

\newcommand{\Sym}{\operatorname{Sym}}

\newcommand{\sign}{\operatorname{sign}}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\cod}{\operatorname{cod}}
\newcommand{\parity}{\operatorname{parity}}

\renewcommand{\emptyset}{\mbox{\O}}

\makeatletter
\newcommand{\ps@draft}{%
\renewcommand{\@evenhead}{\textrm{\thepage}\hfil\textsl{\leftmark}}%
\renewcommand{\@oddhead}{\textsl{\rightmark}\hfil\textrm{\thepage}}%
\renewcommand{\@evenfoot}{\small \today\hfil Version\ \version}%
\renewcommand{\@oddfoot}{\@evenfoot}}
\makeatother

\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection. #1}}

\makeindex
\title{Group Theory}
\author{Corran Webster}

\begin{document}

\maketitle
\pagenumbering{roman}

This work is licensed under a
\href{http://creativecommons.org/licenses/by-nc-sa/3.0/}{Creative Commons
Attribution-NonCommercial-ShareAlike 3.0 Unported License}.

\tableofcontents

\setcounter{chapter}{-1}

\chapter{Preliminaries}

\pagenumbering{arabic}

\pagestyle{draft}

Abstract algebra does not require a great deal of mathematical background to
get started: we really only need the concepts of sets and functions to
present the theory.  You should have come across the formal definitions of
these concepts in previous courses, such as a typical discrete mathematics
course.

\section{Sets}

A \defn{set}{set} is a collection of mathematical objects.  We do not care about
the order that the objects are presented, nor any potential duplication of
elements.  The mathematical objects contained in a set $S$ are called
the \defn{elements}{element} or \defn{members}{member} of a set, and write $x \in S$ to say
that $x$ is an element of $S$.  We say that two sets are equal if they have
exactly the same elements.

The simplest way to present a set is as a list of all the elements of the
set enclosed in parentheses, such as the set $\{1, 2, 3\}$.  For sets with
large numbers of elements, or infinite sets, this presentation is tedious
(or impossible!), so there are two alternatives.  If there is a clear
pattern to the elements, one can use ellipses to elide the majority of the
set, leaving just enough to make the pattern of elements clear:
\[
  \{2, 4, 6, \ldots, 100\} \qquad \text{and} \qquad \{2, 3, 5, 7, 11, 13,
\ldots\}
\]
are clearly meant to represent the set of all even numbers from 2 to 100,
and the set of all prime numbers respectively.  However some sets are too
complicated for this sort of presentation, and for these we use ``set
builder'' notation.  In set builder notation we simply specify the set by
some property $P$ which defines the set:
\[
  \{x | x \text{ satisfies } P\} \qquad \text{or} \qquad \{x : x \text{ satisfies }
P\}.
\]
For example, one could write the set of all prime numbers as
\[
  \{ x | x \text{ is prime}\},
\]
or the set of all numbers greater than $2$ and less than or equal to $10$ as
\[
  \{ x : 2 < x \le 10 \}.
\]
This last example illustrates an ambiguity: which collection of numbers do
we mean? Integers? Rational numbers? Real numbers?  To resolve this
ambiguity, we usually specify the set $S$ from which we take our elements,
and use the notation
\[
  \{x \in S | x \text{ satisfies } P\} \qquad \text{or} \qquad \{x \in S : x
\text{ satisfies } P\}.
\]
Therefore the interval of all real numbers greater than 2 and less than or
equal to 10 would most clearly be represented by
\[
  \{ x \in \reals : 2 < x \le 10\}.
\]

There are several special sets that come up with sufficient frequency to
deserve their own notation.  The most important is the \defn{empty set}{set!empty}
$\emptyset = \{\}$, the set which contains no elements.  The next most
important are the various sets of numbers:

\begin{alignat*}{4}
  \naturals &= \{1, 2, 3, 4, \ldots \} & \qquad & \text{\defn{natural
numbers}{natural numbers}}\\
  \integers &= \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \} &&
\text{\defn{integers}{integers}}\\
  \rationals &= \{p/q : p \in \integers, q \in \naturals, \text{$p$ and $q$
    coprime}\} && \text{\defn{rational numbers}{rational numbers}}\\
  \reals &= \{ x : \text{$x$ is an infinite decimal\footnote{This is far
from the whole story: take a real analysis course for more information.}}\}
&& \text{\defn{real numbers}{real numbers}}\\
  \complex &= \{ x+iy : x, y \in \reals \} && \text{\defn{complex numbers}{complex numbers}}
\end{alignat*}

We say that a set $A$ is a \defn{subset}{subset} of another set $B$, and write $A
\subseteq B$, if every element of $A$ is an element of $B$.  For example,
$\{2, 4, 6\} \subseteq \{1, 2, 3, 4, 5, 6\}$.  Note that if $A$ is equal to
$B$, it is still a subset of $B$, and that the empty set is always a subset
of any other set.  We say that $A$ is a \defn{proper subset}{subset!proper} of $B$ if $A
\subset B$ and $A \ne B$, and we denote this by $A \subset B$.

We can combine sets using a number of different \defn{set operations}{set operations}.  The
\defn{union}{union} of two sets $A$ and $B$ is the set containing all the elements
of both sets combined, ie.
\[
  A \union B = \{ x : x \in A \text{ or } x \in B\}.
\]
The \defn{intersection}{intersection} of $A$ and $B$ is the set containing the objects that
are elements of both of the sets, ie.
\[
  A \intersect B = \{ x : x \in A \text{ and } x \in B\}.
\]
Intersection and union are both \defn{commutative}{commutative} and \defn{associative}{associative}
operations, and are \defn{distributive}{distributive} with respect to one another:
\begin{align*}
  A \union B  &= B \union A\\
  A \intersect B  &= B \intersect A\\
  A \union (B \union C) &= (A \union B) \union C = A \union B \union C\\
  A \intersect (B \intersect C) &= (A \intersect B) \intersect C = A \intersect B \intersect
C\\
  A \union (B \intersect C) &= (A \union B) \intersect (A \union C)\\
  A \intersect (B \union C) &= (A \intersect B) \union (A \intersect C)\\
  A \union \emptyset &= A\\
  A \intersect \emptyset &= \emptyset
\end{align*}

If there is some natural \defn{universal set}{universal set} $U$ of elements which we are
considering, we can define the \defn{complement}{complement} of a set $A$ as the set of all
things in $U$ not in $A$, ie.
\[
  A^{c} = \{x \in U : x \notin A \}.
\]
The complement of the complement is the original set, and complements
interact with union and intersection via \defn{DeMorgan's laws}{DeMorgan's laws}:
\begin{align*}
  (A^{c})^{c} &= A\\
  (A \union B)^{c} &= A^{c} \intersect B^{c}\\
  (A \intersect B)^{c} &= A^{c} \union B^{c}\\
  \emptyset^{c} &= U \\
  U^{c} &= \emptyset.
\end{align*}
Note that sometimes the notation $\overline{A}$ is used for complements.

Even in the absence of a universal set, we can define the \defn{set
difference}{set difference} operation: $A \setminus B$ is everything in $A$ which is not in
$B$.  That is
\[
  A \setminus B = \{ x \in A : x \notin B\}.
\]
If complements make sense, then we have $A \setminus B = A \intersect
B^{c}$.  We can also define the \defn{symmetric difference}{symmetric difference} of $A$ and $B$
as the set of all things in either $A$ or $B$, but not in both,
\[
  A \symdiff B = \{x \in A \union B : x \notin A \intersect B\}
\]
or equivalently
\[
  A \symdiff B = (A \union B) \setminus (A \intersect B) = (A \setminus B)
\union (B \setminus A).
\]
Clearly $A \symdiff B = B \symdiff A$.

Perhaps the most important set operation for our purposes, since it appears
in just about every core definition in abstract algebra, is the \defn{cartesian product}{cartesian product}.  The product of two sets, $A \cross B$ is the set
consisting of tuples $(x,y)$, where $x \in A$ and $y \in B$, ie.
\[
  A \cross B = \{(x,y) : x \in A, y \in B\}.
\]
More generally, we define a product of $n$ sets to be the set of $n$-tuples:
\[
  A_{1} \cross A_{2} \cross \cdots \cross A_{n} = \{ (a_{1}, a_{2}, \ldots,
a_{n}) : a_{k} \in A_{k}, k = 1, 2, \ldots, n\}.
\]
We also define
\[
  A^{n} = \underbrace{A \cross A \cross \cdots \cross A}_{n\text{ times}}
\]
to be the set of all $n$-tuples of elements of $A$. This notation is familiar
from calculus, where $\reals^{n}$ is the set of all $n$-tuples of real numbers.
Note that $A \times B$ is not equal to $B \times A$ in general, although they
are clearly closely related.  \sidebar{Proving Equality of Sets}{Often we have
two sets, $A$ and $B$, which we want to show are equal.  A
very common technique to show that this is in fact the case is to show that
each set is a subset of the other.  We can then conclude that they are
equal.  In summary:\\
\hspace{2em}\fbox{\parbox{1in}{$A \subseteq B$ and $B \subseteq A$
implies $A = B$}} }

\subsection*{Exercises}

\begin{enumerate}
  \item In this section many identities are stated without proof.  Pick
    8 of them and show why they hold.  Be careful not to use any identity
    or fact which is dependent on what you are proving.
\end{enumerate}

\section{Functions}

A \defn{function}{function} $f$ from $A$ to $B$ is a rule which relates every element $x$
of $A$ to some unique element $y$ of $B$.  What is key here is that the
function associates $x$ with \emph{precisely} one element of $B$.  We write $y
= f(x)$.  More formally, we denote the function with the notation
\begin{align*}
  f : A & \to B \\
      x & \mapsto y.
\end{align*}
The set $A$ is the \defn{domain}{domain}, the set $B$ the \defn{codomain}{codomain}, while the
set
\[
  f(A) = \{ f(x) : x \in A \}
\]
is the \defn{range}{range} of the function.  The \defn{graph}{graph!of a function} of the function is
the subset
\[
  \mathcal{G}_{f} = \{(x, f(x)) : x \in A \}
\]
of $A \cross B$.

From time to time, we will wish to specify an abstract function without
specifying an exact formula or rule.  In this case, we will just write $f: A
\to B$, specifying the domain and codomain, but nothing else.  We will also
write $\mathcal{F}(A,B)$ for the set of all functions from $A$ to
$B$.

Given a function $f: A \to B$, and a subset $X \subseteq A$, we define the
\defn{image}{image} of $X$ to be the subset of $B$ given by
\[
  f(X) = \{f(x) : x \in B\}.
\]
If $Y \subseteq B$, we also define the \defn{inverse image}{image!inverse}
of $Y$ to be the subset of $A$ given by
\[
  f^{-1}(Y) = \{x \in A : f(x) \in Y\}.
\]
In other words $f^{-1}(Y)$ is the set of elements of $A$ whose value lies in
the set $Y$.

Given a function $g: A \to B$ and another function $f: B \to C$, we define
the \defn{composition}{composition!of two functions} of $f$ and $g$ to be
the function $f \circ g : A \to C$ defined by $(f \circ g)(x) = f(g(x))$.

A function is \defn{one-to-one}{one-to-one function} or \defn{injective}{injective function} if it satisfies the
condition
\[
  f(x_{1}) = f(x_{2}) \text{ implies } x_{1} = x_{2}.
\]
A function is \defn{onto}{onto function} or \defn{surjective}{surjective function} if the range equals the
entire codomain, or equivalently
\[
  f(A) = B.
\]
A function which is both injective and surjective is called a
\defn{bijective}{bijective function} function.

A bijective function automatically has an \defn{inverse
function}{function!inverse} $f^{-1}: B \to A$ defined by $f^{-1}(b) = a$ if
and only if $f(a) = b$.  The fact that $f$ is onto guarantees that $f^{-1}$
is defined on all of $B$, while the fact that $f$ is injective ensures that
$f^{-1}$ is a function.  It follows from the definition that $(f \circ
f^{-1})(x) = x$ and $(f^{-1} \circ f)(x) = x$.

\begin{proposition}\label{prop:functionfacts}
  Let $A$, $B$ $C$ and $D$ be sets, and $f : A \to B$, $g : B \to C$ and
  $h: C \to D$ be functions.  Then we have:
  \begin{theoremenum}
    \item Composition of functions satisfies an associative law:
      $(h \circ g) \circ f = h \circ (g \circ f)$.
    \item If $f$ and $g$ are both one-to-one, then so is $g \circ f$.
    \item If $f$ and $g$ are both onto, then so is $g \circ f$.
    \item If $f$ and $g$ are both bijections, then so is $g \circ f$.
    \item If $f$ is a bijection, then so is $f^{-1}$.
  \end{theoremenum}
\end{proposition}
\begin{proof}
  The proof is left as an exercise.
\end{proof}

\begin{example}
We could formally write the function $f(x) = \sqrt{x}
+ 1$ as:
\begin{align*}
  f : [0,\infty) &\to \reals \\
      x &\mapsto \sqrt{x} + 1.
\end{align*}
As you would expect, the domain is $[0,\infty)$, the codomain is $\reals$,
the range is $[1, \infty)$, and the graph is the set of points
\[
  \{(x, \sqrt{x} + 1) : x \in [0,\infty)\}.
\]
The function is one-to-one, but is not surjective or bijective.
\end{example}

\subsection*{Exercises}

\begin{enumerate}
  \item Prove Proposition~\ref{prop:functionfacts}.
\end{enumerate}

\include{intro}

\include{groups}

\include{structure}

\include{construction}

\chapter{Introduction}

In this section we will look at a number of concrete examples where we
extract an algebraic system from various mathematical concepts.  This will
hopefully give you some solid examples of the sorts of objects that we will
be discussing for the remained of the course, and why they are of significance
in pretty much all areas of science, mathematics, and even art.

\section{Symmetry}

You are probably familiar, in an informal way, with the idea of symmetry from
Euclidean geometry and calculus.  For example, the letter ``\textsf{A}'' has
reflective symmetry in its vertical axis, ``\textsf{E}'' has reflective
symmetry in its horizontal axis, ``\textsf{N}'' has rotational symmetry of
$\pi$ radians about its centre, and ``\textsf{H}'' has all three types of
symmetry.  And the letter ``\textsf{F}'' has none of these symmetries.

Symmetry is also important in understanding real world phenomena.  As some
examples:
\begin{itemize}
  \item The symmetries of molecules can affect possible chemical reactions.
    For example, many proteins and amino acids (the basic building blocks of
    life) have ``left-handed'' and ``right-handed'' versions which are
    reflections of one-another.  Life on earth uses the ``left-handed''
    versions almost exclusively.
    
  \item Crystals have very strong symmetries, largely determined by the
    symmetries of the atoms or molecules of which the crystal is built.
    
  \item Most animals and plants have some sort of symmetry in their
    body-shapes, although they are never perfectly symmetrical.  Most
    animals have bilateral symmetry, while plants often have five-fold
    or six-fold rotational symmetry.
  
  \item In art and design, symmetrical patterns are often found to be more
    pleasing to the eye than asymmetrical patterns, or simply more practical.
    
  \item waves in fluids, or the vibrations of a drumhead or string are often
    symmetrical, or built out of symmetric components.  These symmetries
    are usually inherent to the underlying equations that we use to model
    such systems, and understanding the symmetry can be crucial in finding
    solutions to these equations.
\end{itemize}

But what, precisely, do we mean by symmetry?

\begin{definition}
  Let $\Omega$ be a subset of $\reals^{n}$.  A \defn{symmetry}{symmetry} of
  $\Omega$ is a function $T: \reals^{n} \to \reals^{n}$ such that
  \begin{theoremenum}
    \item $T(\Omega) = \Omega$, and
    \item $T$ preserves distances between points
  \end{theoremenum}
\end{definition}

Functions which preserve distance in $\reals^{n}$ are sometimes called
\defn{Euclidean transforms}{Euclidean transform}.  We will see these again
later.

We also note that every set $\Omega$ has the trivial \defn{identity
symmetry}{symmetry!identity} $I(x) = x$.

\begin{proposition}\label{prop:symmetryfacts}
  Let $\Omega$ be a subset of $\reals^{n}$, and let $S$ and $T$ be
  symmetries of $\Omega$.  Then
  \begin{theoremenum}
    \item $T$ is one-to-one and onto.
    
    \item the inverse function $T^{-1}$ is a symmetry of $\Omega$
    
    \item the composition $T \circ S$ is a symmetry of $\Omega$

    \item the compositions $T \circ T^{-1}$ and $T^{-1} \circ T$ always
       equal the identity symmetry $I$.
  \end{theoremenum}
\end{proposition}
\begin{proof}
  If $T(x_{1}) = T(x_{2})$ then $d(T(x_{1}), T(x_{2})) = 0$ so the fact that
$T$ preserves distances means that $d(x_{1}, x_{2}) = 0$.  But this implies
that $x_{1} = x_{2}$, so $T$ is one-to-one.

  We also know that if $B_{r} = \{x \in \reals^{n} : d(x,0) \le r \}$ is the
$n$-dimensional ``ball'' of radius $r$ centred at the origin of $\reals^{n}$,
then $T(B_{r})$ must also be a ball of radius $r$ (since $T$ preserves
distances).  Let $c$ be the centre of the ball $T(B_{r})$, and given any point
$y \in \reals^{n}$ we have $y \in T(B_{r})$ for all $r \ge d(y,c)$.  Hence
there is some $x \in \reals^{n}$ such that $T(x) = y$, and so $T$ is onto.

  Since $T$ is one-to-one and onto, it has an inverse function $T^{-1}$.
 We observe that $T^{-1}(\Omega) = T^{-1}(T(\Omega)) = \Omega$, and also that
$d(T^{-1}(x), T^{-1}(y)) = d(T(T^{-1}(x)), T(T^{-1}(y))) = d(x,y)$.  Hence
$T^{-1}$ is a symmetry of $\Omega$.

  Parts (iii) and (iv) are left as a simple exercise.
\end{proof}

We\sidebar{Notation}{Many algebra texts write $ST$ for $T \circ S$, because
$S$ is applied first, then $T$.  In these notes, however, we will remain
consistent with the traditional function composition order, but you must
keep this clear in your head to avoid confusion.} will sometimes write the composed symmetry $T \circ S$ as simply $TS$. 
Remember that because function composition works from right to left, $TS$
means that the symmetry $S$ is applied first, followed by the symmetry $T$.

\begin{figure}\label{fig:symmetryofH}
  \vspace{1in}
  \caption{The set $\Omega$ of Example~\ref{eg:symmetryofH}}
\end{figure}

\begin{example}\label{eg:symmetryofH}
  Let $\Omega \subseteq \reals^{2}$ be the H-shaped set illustrated in
Figure~\ref{fig:symmetryofH}.  Then $\Omega$ has the following symmetries:
  \begin{alignat*}{4}
    I(x,y) &= (x,y) &\qquad& \text{(Identity)} \\
    H(x,y) &= (x,-y) && \text{(Reflection in the $x$-axis)} \\
    V(x,y) &= (-x,y) && \text{(Reflection in the $y$-axis)} \\
    R(x,y) &= (-x,-y) && \text{(Rotation by $\pi$ radians about the origin)}
  \end{alignat*}
  
  These are the only symmetries, as it turns out.  We can confirm by direct
calculation that $I^{-1} = I$, $H^{-1} = H$, $V^{-1} = V$ and $R^{-1} = R$. 
In other words, each of these transformations is its own inverse.  We also
have the following compositions of symmetries:
  \begin{alignat*}{6}
    H \circ H &= I & \qquad & H \circ V &= R & \qquad & H \circ R &= V\\
    V \circ H &= R && V \circ V &= I && V \circ R &= H\\
    R \circ H &= V && R \circ V &= H && R \circ R &= I
  \end{alignat*}
  In fact we can write this out as a ``multiplication table'' of sorts:
  
  \medskip
  \hspace{1.5in}\begin{tabular}{c|cccc}
    $\circ$ & $I$ & $H$ & $V$ & $R$ \\
    \hline
    $I$ & $I$ & $H$ & $V$ & $R$ \\
    $H$ & $H$ & $I$ & $R$ & $V$ \\
    $V$ & $V$ & $R$ & $I$ & $H$ \\
    $R$ & $R$ & $V$ & $H$ & $I$ \\
  \end{tabular}
  
  \medskip
  
  This sort of multiplication table is called a \defn{Cayley table}{Cayley
  table}.
  
  One can check that this ``multiplication'' of symmetries satisfies
associative and commutative laws.
\end{example}

There is nothing really special about the set $\Omega$ in the above example:
every set will have a collection of symmetries which give a ``multiplication
table'' which satisfies an associative law, although it turns out that it may
not satisfy a commutative law.

\begin{example}\label{eg:symmtriangle}
  Let $\Omega \subseteq \reals^{2}$ be an equilateral triangle centred at
  the origin and with one vertex at $(1,0)$.  Then $\Omega$ has the following
  symmetries:

  \begin{tabular}{lp{3.5in}}
    $I$ & Identity \\
    $R_{1}$ & Rotation by $2\pi/3$ radians clockwise \\
    $R_{2}$ & Rotation by $2\pi/3$ radians anticlockwise \\
    $H_{0}$ & Reflection in the $x$-axis \\
    $H_{1}$ & Reflection in the line through $(0,0)$ and $(-\sqrt{3}/2,1/2)$ \\
    $H_{2}$ & Reflection in the line through $(0,0)$ and $(-\sqrt{3}/2,-1/2)$
  \end{tabular}
  
  The precise formulas for these symmetries are an exercise.  A little thought
  tells us that $I^{-1} = I$, $R_{1}^{-1} = R_{2}$, $R_{2}^{-1} = R_{1}$,
  $H_{1}^{-1} = H_{1}$, $H_{2}^{-1} = H_{2}$, and $H_{3}^{-1} = H_{3}$.
  The Cayley table for these symmetries is:
    
  \medskip
  \hspace{1in}\begin{tabular}{c|cccccc}
    $\circ$ & $I$ & $R_{1}$ & $R_{2}$ & $H_{0}$ & $H_{1}$ & $H_{2}$ \\
    \hline
    $I$ & $I$ & $R_{1}$ & $R_{2}$ & $H_{0}$ & $H_{1}$ & $H_{2}$ \\
    $R_{1}$ & $R_{1}$ & $R_{2}$ & $I$ & $H_{1}$ & $H_{2}$ & $H_{0}$ \\
    $R_{2}$ & $R_{2}$ & $I$ & $R_{1}$ & $H_{2}$ & $H_{0}$ & $H_{1}$ \\
    $H_{0}$ & $H_{0}$ & $H_{2}$ & $H_{1}$ & $I$ & $R_{1}$ & $R_{2}$ \\
    $H_{1}$ & $H_{1}$ & $H_{0}$ & $H_{2}$ & $R_{2}$ & $I$ & $R_{1}$ \\
    $H_{2}$ & $H_{2}$ & $H_{1}$ & $H_{0}$ & $R_{1}$ & $R_{2}$ & $I$ \\
  \end{tabular}
  
  \medskip
  
  This operation is associative, but it is clearly \emph{not} commutative:
  $H_{0} \circ H_{1} = R_{1}$, but $H_{1} \circ H_{0} = R_{2}$, for example.
\end{example}

The reason that the composition operation of symmetries is always associative
is because it is really just composition of functions, and function composition
is an associative operation.

\begin{example}\label{eg:circlesymmetry}
  Let $\Omega$ be the unit circle.  Then $\Omega$ has infinitely many
  symmetries, which fall into two classes:
  
  \begin{tabular}{lp{3.5in}}
    $R_{\theta}$ & Rotation by $\theta$ radians clockwise,
      $0 \le \theta < 2\pi$ \\
    $H_{\varphi}$ & Reflection in the line which makes an angle $\varphi$
      to the $x$-axis at the origin, $0 \le \varphi < \pi$.
  \end{tabular}
  
  The identity is $R_{0}$, rotation by $0$ radians.  We can also check that
  the inverse of $R_{\theta}$ is $R_{2\pi - \theta}$ for $0 < \theta < 2\pi$,
  and the inverse of $H_{\varphi}$ is $H_{\varphi}$.
  
  Because the set of symmetries is infinite, we can't write down a Cayley
  table, but we can list how the generic symmetries compose:
  
  \begin{alignat*}{4}
    R_{\theta} \circ R_{\omega} &= R_{\theta + \omega} &\qquad&
    R_{\theta} \circ H_{\varphi} &= \\
    H_{\varphi} \circ R_{\theta} &= H_{\varphi - \theta/2}&&
    H_{\varphi} \circ H_{\psi} &= R_{2\varphi}
  \end{alignat*}
  
\end{example}

All the examples so far have used rotational and reflective symmetries, but
some regions have translational symmetry.

\begin{example}
  Let $\Omega$ be the $x$-axis in $\reals^{2}$.  Then $\Omega$ has symmetries
  of the form
  \[
    T_{c}(x,y) = (x + c,y),
  \]
  ie. right translation by $c$, for any $c \in \reals$.
  
  The identity symmetry is $T_{0}$, the inverse symmetry of $T_{c}$ is
  $T_{-c}$, and symmetries of this set compose by the rule
  \[
    T_{a} \circ T_{b} = T_{a+b}.
  \]
\end{example}

\subsection*{Exercises}

\begin{enumerate}
  \item Find the set of symmetries for each capital letter of the alphabet.
  
  \item Prove Proposition~\ref{prop:symmetryfacts} (iii-iv).
  
  \item Write down formulas for each of the symmetries in
    Example~\ref{eg:symmtriangle}.
    
    Hint 1: the point $(x,y) \in \reals^{2}$ rotated clockwise by an angle
    $\theta$ about the origin is $(x\cos \theta + y\sin \theta, -x\sin \theta +
    y\cos \theta)$.
    
    Hint 2: from the Cayley table, we have $H_{1} = R_{1} \circ H_{0}$ and
    $H_{2} = R_{2} \circ H_{0}$, and it is easy to find the formula of a
    composition of functions.
  
  \item Let $\Omega \subseteq \reals^{2}$ be a square, centred at the origin,
    with side length 1.
    Find all 8 symmetries of $\Omega$, and write down the formula for each. 
    Find the inverses of each symmetry.
    Write out the Cayley table for the symmetries of a square.
  
  \item\label{ex:symtetra} (*) Let $\Omega \subseteq \reals^{3}$ be a regular tetrahedron
    centred at the origin.  Show that $\Omega$ has 24 symmetries.
  
  \item (*) Let $\Omega = \integers^{2} \subseteq \reals^{2}$ be the integer
    lattice in the plane, ie.
    \[
      \integers^{2} = \{ (m,n) \in \reals^{2} : m, n \in \integers \}.
    \]
    Classify the symmetries of $\integers^{2}$.
    Find the inverses of each symmetry.
    As in Example~\ref{eg:circlesymmetry}, find the product of typical symmetries.
\end{enumerate}

\section{Permutations}

A \defn{permutation}{permutation} of a set $X$ is simply a re-arrangement of
the elements, or more precisely a function $p$ that maps each element of $X$ to
an element of $X$ with no two distinct elements being mapped to the same
element (and for infinite sets, we also need $p(X) = X$).  Another way of
saying this is that a permutation of $X$ is simply a bijection $p: X \to X$.

Normally we are interested only in permutations of finite sets, and we
really only care how many elements there are to permute.  Hence it is
customary to consider permutations of the set $\{1, 2, 3, ..., n\}$.

Since permutations are just functions,we can define them as we would any other
function, by specifying the value that the function takes at each point in the
domain.  Unfortunately, unlike the usual functions you see in a calculus course,
you usually can't specify permutations using a formula.

\begin{example}
  The following function $p$ is a permutation of the set $\{1,2,3,4,5,6,7,8\}$:
  \begin{alignat*}{8}
    p(1) &= 2 &\qquad&
    p(2) &= 4 &\qquad&
    p(3) &= 6 &\qquad&
    p(4) &= 8 \\
    p(5) &= 7 &&
    p(6) &= 5 &&
    p(7) &= 3 &&
    p(8) &= 1  
  \end{alignat*}
\end{example}

A more compact way of writing down a permutation is to write it as an array of
numbers, with $1$, through $n$ on the top row, and the respective image of each
in the second row, like so:
\[
  p = \begin{pmatrix}
    1 & 2 & 3 & \ldots & n \\
    p(1) & p(2) & p(3) & \ldots & p(n)
  \end{pmatrix}
\]

\begin{example}
  The permutation $p$ of the previous example can be written as follows:
  \[
    p = \begin{pmatrix}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
      2 & 4 & 6 & 8 & 7 & 5 & 3 & 1
    \end{pmatrix}
  \]
\end{example}

We denote the set of all permutations of $\{1,2,3,\ldots,n\}$ by $S_{n}$.

\begin{example}\label{eg:perm3part1}
  The set $S_{3}$ is
  \[
    \left\{\begin{pmatrix}
      1 & 2 & 3 \\
      1 & 2 & 3
    \end{pmatrix},
    \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 1 & 2
    \end{pmatrix},
    \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 3 & 1
    \end{pmatrix},
    \begin{pmatrix}
      1 & 2 & 3 \\
      1 & 3 & 2
    \end{pmatrix},
    \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 1 & 3
    \end{pmatrix},
    \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 2 & 1
    \end{pmatrix} \right\}
  \]
\end{example}

Note that, as in the above example, the \defn{identity
permutation}{permutation!identity} $p(k) = k$ is always a permutation.

Since every permutation is a one-to-one and onto function, there is an inverse
function $p^{-1}$ associated with every permutation $p$.

We can ``multiply'' two permutations by applying the first permutation, and
then using the second permutation to permute the result.  If $p$ and $q$ are
permutations of the same set, $pq(k)$ is the what you get from applying $q$
to $p(k)$, ie.\ $pq(k) = q(p(k))$, so $pq = q \circ p$ (note the reversal of
terms in the product versus the composition).

\begin{proposition}\label{prop:permgroup}
  Let $X$ be any set, and $p$ and $q$ be permutations of $X$, then
  \begin{theoremenum}
    \item $p^{-1}$ is a permutation of $X$,
    \item $pq$ is a permutation of $X$,
    \item the product satisfies an associative law: $(pq)r = p(qr)$.
  \end{theoremenum}
\end{proposition}
\begin{proof}
  These follow immediately from Proposition~\ref{prop:functionfacts}:
  the inverse
  function of a bijection is a bijection, proving (i); the composition
  of bijective functions is a bijective function, proving (ii); and
  composition of functions is associative, so 
  \[
    (pq)r = r \circ (q \circ p) = (r \circ q) \circ p = p(qr),
  \]
  proving (iii).
\end{proof}

\begin{example}
  Let
  \[
    p = \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 2 & 1
    \end{pmatrix}
    \qquad \text{and} \qquad
    q = \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 1 & 2
    \end{pmatrix}.
  \]
  We can find $pq$ fairly easily: for example if
  $k=1$, we know that $p(1) = 3$, and $q(3) = 2$, so $pq(1) = 2$. Repeating
  for $k = 2$ and $3$, we get So
  we have
  \[
    pq = \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 1 & 3
    \end{pmatrix}.
  \]
\end{example}

\begin{example}\label{eg:perm3part2}
  We listed all the elements of $S_{3}$ in Example~\ref{eg:perm3part1}.
  To simplify notation we will give each of these a symbol to identify it:
  \begin{alignat*}{6}
    p_{0} &= \begin{pmatrix}
      1 & 2 & 3 \\
      1 & 2 & 3
    \end{pmatrix} &\qquad&
    p_{1} &= \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 1 & 2
    \end{pmatrix} &\qquad&
    p_{2} &= \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 3 & 1
    \end{pmatrix}\\
    p_{3} &= \begin{pmatrix}
      1 & 2 & 3 \\
      1 & 3 & 2
    \end{pmatrix} &&
    p_{4} &= \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 1 & 3
    \end{pmatrix} &&
    p_{5} &= \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 2 & 1
    \end{pmatrix}
  \end{alignat*}
  It is easy to verify that $p_{0}^{-1} = p_{0}$, $p_{1}^{-1} = p_{2}$,
  $p_{2}^{-1} = p_{1}$, $p_{3}^{-1} = p_{3}$, $p_{4}^{-1} = p_{4}$, 
  and $p_{5}^{-1} = p_{5}$.
  
  Just as with symmetries, we can write out a Cayley table for the products
  of these permutations:
  \[
  \begin{array}{c|cccccc}
               & p_{0} & p_{1} & p_{2} & p_{3} & p_{4} & p_{5} \\
    \hline
    p_{0} & p_{0} & p_{1} & p_{2} & p_{3} & p_{4} & p_{5} \\
    p_{1} & p_{1} & p_{2} & p_{0} & p_{4} & p_{5} & p_{3} \\
    p_{2} & p_{2} & p_{0} & p_{1} & p_{5} & p_{3} & p_{4} \\
    p_{3} & p_{3} & p_{5} & p_{4} & p_{0} & p_{2} & p_{1} \\
    p_{4} & p_{4} & p_{3} & p_{5} & p_{1} & p_{0} & p_{2} \\
    p_{5} & p_{5} & p_{4} & p_{3} & p_{2} & p_{1} & p_{0} 
  \end{array}
  \]
  This product is not commutative.
  
  It's probably not immediately obvious, but if you look closely you will see
  that the pattern of this Cayley table is exactly the same as the pattern of
  the Cayley table of Example~\ref{eg:symmtriangle}, with the correspondences
    $p_{0} \leftrightarrow I$,
    $p_{1} \leftrightarrow R_{1}$,
    $p_{2} \leftrightarrow R_{2}$,
    $p_{3} \leftrightarrow H_{0}$,
    $p_{4} \leftrightarrow H_{1}$,
    $p_{5} \leftrightarrow H_{2}$.
  Indeed, the inverses of each element have the same pattern under these same
  correspondences.
  
  In other words, if we look at these two examples abstractly, we seem to be
  getting the same underlying mathematical object.
  
  This correspondence can be made even more concrete in the following way: if
  we label the vertices of the equilateral triangle of Example~\ref{eg:symmtriangle}
  with the numbers 1, 2 and 3, starting at $(0,0)$ and working clockwise, we
  find that the symmetries of the triangle permute the vertices in exactly
  the same way that the corresponding permutations permute the corresponding
  numbers.
\end{example}

\subsection{Cycles}

Even with the current notation, expressing and working with permutations can
be cumbersome.  There is another, alternative, notation which can speed up
the process of working with permutations.  This notation works by looking at
the \defn{cycles}{cycle} withing a permutation.  If $p$ is a permutation
of the set $X$, the cycle of an element $k$ of $X$ in $p$ is the sequence
of elements $(k, p(k), p^{2}(k), \ldots, p^{m}(k))$ (where $p^{l}$ is the product
of $p$ with itself $l$ times) such that $m$ is the smallest number such that,
$p^{m+1}(k) = k$.

Note that the order of the elements in a cycle is important, but not where we
start in the cycle.  For example, we regard $(k, p(k), p^{2}(k), \ldots, p^{m}(k))$,
$(p(k),$ $p^{2}(k),\ldots, p^{m}(k), k)$, $(p^{2}(k), \ldots, p^{m}(k), k, p(k))$, etc.\ as
representing the same cycle.  If $X$ is the set $\{1, 2, \ldots n\}$, it is
usual to write a cycle starting with the smallest number in the cycle.

A cycle with $m$ elements is called an \defn{$m$-cycle}{$m$-cycle}.  A 2-cycle
is sometimes called a \defn{transposition}{transposition}, since it transposes
two elements.

\begin{example}
  In the following permutation
  \[
    \begin{pmatrix}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
      2 & 4 & 6 & 8 & 7 & 5 & 3 & 1
    \end{pmatrix}
  \]
  we have $1 \to 2$, $2 \to 4$, $4 \to 8$ and $8 \to 1$, so $(1,2,4,8)$ is
  a cycle.  We could also write this cycle as $(2, 4, 8, 1)$, $(4,8, 1, 2)$,
  or $(8, 1, 2, 4)$.
  
  The smallest element not in this cycle is $3$, and we have
  $3 \to 6$, $6 \to 5$, $5 \to 7$ and $7 \to 3$, so $(3, 6, 5, 7)$ is another
  cycle.
  
  Since every element is in one of these two cycles, these are the only cycles
  in this permutation.
\end{example}

If we find all of the cycles of a permutation, we can represent the permutation
as a whole as a product of its cycles.

\begin{example}
  The permutation
  \[
    \begin{pmatrix}
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
      2 & 4 & 6 & 8 & 7 & 5 & 3 & 1
    \end{pmatrix}
  \]
  can be written as $(1, 2, 4, 8)(3, 6, 5, 7)$ or $(3, 6, 5, 7)(1, 2, 4, 8)$.
\end{example}

\begin{example}
  The elements of $S_{3}$ can be represented in cycle form as follows:
  \begin{alignat*}{6}
    \begin{pmatrix}
      1 & 2 & 3 \\
      1 & 2 & 3
    \end{pmatrix} &= (1)(2)(3) &\qquad&
    \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 1 & 2
    \end{pmatrix} &= (1, 3, 2) &\qquad&
    \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 3 & 1
    \end{pmatrix} &= (1, 2, 3)\\
    \begin{pmatrix}
      1 & 2 & 3 \\
      1 & 3 & 2
    \end{pmatrix} &= (1)(2, 3) &&
    \begin{pmatrix}
      1 & 2 & 3 \\
      2 & 1 & 3
    \end{pmatrix} &= (1, 2)(3)&&
    \begin{pmatrix}
      1 & 2 & 3 \\
      3 & 2 & 1
    \end{pmatrix} &= (1, 3)(2)
  \end{alignat*}
\end{example}

To work out how a product of cycles permutes a particular element $k$, all you
need do is work from left to right until you find the element in a cycle, and
then find the element which follows it in that cycle.  When you are finding
products of permutations (as we will see below), you continue on with the new
element in the remaining cycles until you reach the end of the product.

\begin{example}
  Consider the permutation $p = (1, 3, 5)(2)(4, 6)$ of the set
  $\{1, 2, 3, 4, 5, 6\}$.  We can calculate $p(1)$ be looking at the first
  cycle, where we see that the element after $1$ in that cycle is $3$, and we also
  note that $3$ does not occur in any cycle after the first, so $p(1) = 3$.
  Similarly, we have $p(2) = 2$, $p(3) = 5$, $p(4) = 6$, $p(5) = 1$ and
  $p(6) = 4$.  This permutation could also be written as
  \[
    \begin{pmatrix}
      1 & 2 & 3 & 4 & 5 & 6\\
      3 & 2 & 5 & 6 & 1 & 4
    \end{pmatrix}.
  \]
\end{example}

Notice that there would be no difference in the above example if the cycle
$(2)$ was omitted.  It is common practise to leave such single-element
cycles out, particularly when the set which is being permuted is clear.

\begin{example}
  Consider the product of cycles $p = (1, 3, 5)(2, 3)(4, 6, 5)$ in the set
  $\{1, 2, 3, 4, 5,$ $6\}$.  We can calculate $p(1)$ be looking at the first
  cycle, where we see that the element after $1$ in that cycle is $3$; however
  $3$ occurs in the second cycle, and the element after it in the cycle is $2$;
  and $2$ does not occur in the remaining cycle, so $p(1) = 2$.  Similarly,
  we have $3 \to 5$ in the first cycle, and $5 \to 4$ in the last cycle, so
  $p(3) = 4$.
  Calculating everything out, we have $p(2) = 3$, $p(4) = 6$, $p(5) = 1$ and
  $p(6) = 5$.  This permutation could also be written as
  \[
    \begin{pmatrix}
      1 & 2 & 3 & 4 & 5 & 6\\
      2 & 3 & 4 & 6 & 1 & 5
    \end{pmatrix},
  \]
  or more simply in cycle notation as $(1, 2, 3, 4, 6, 5)$.
\end{example}

We can then calculate the product of two permutations in cycle notation by
writing all the cycles as one long product of cycles, and then reducing to
the standard form of the cycles by the above process.

\begin{theorem}
  Every permutation of $S_{n}$ can be written as a product of disjoint cycles.
  (Two cycles are disjoint if they have not elements in common.)
\end{theorem}
\begin{proof}
  Let $p$ be a permutation of $S_{n}$.  We let $c_{1}$ be the cycle which
  includes $1$,
  \[
    c_{1} = \{1, p(1), p^{2}(1), \ldots, p^{m_{1}}(1)\},
  \]
  and we let $p_{1}$ be the permutation defined by
  \[
    p_{1}(k) = \begin{cases}
      k & \text{if $k \in c_{1}$,}\\
      p(k) & \text{otherwise}.
    \end{cases}
  \]
  Then it is clear that $p = c_{1}p_{1}$.
  
  Now if we have written $p = c_{1}\ldots c_{l}p_{l}$, where $c_{1}, \ldots,\
  c_{l}$ are disjoint cycles, and $p_{l}$ is a permutation which satisfies
  has $p_{l}(k) = k$ whenever $k$ is in one of the cycles, then one of two
  things must be true: either every element of $\{1, 2, \ldots, n\}$ is an
  element of one of the cycles, or there is some smallest element $k_{l}$
  which is not in any of the cycles.
  
  In the first case, we have that $p_{l}$ must be the identity permutation,
  so $p = c_{1}\ldots c_{l}$, and we are done.
  
  In the second case, we let $c_{l+1}$ be the cycle including $k_{l}$,
  \[
    c_{l+1} = \{k_{l}, p(k_{l}), p^{2}(k_{l}), \ldots, p^{m_{l}}(k_{l})\},
  \]
  and let $p_{l+1}$ be the permutation defined by
  \[
    p_{l+1}(k) = \begin{cases}
      k & \text{if $k$ is an element of any cycle $c_{1}$, $c_{2}, \ldots, c_{l+1}$}\\
      p(k) & \text{otherwise}.
    \end{cases}
  \]
  Then $p = c_{1}\ldots c_{l+1}p_{l+1}$.
  
  Since $\{1,2,3,\ldots, n\}$ is a finite set, an induction argument using
  this construction proves the result.
\end{proof}

\subsection{Parity}

Informally, if we compare the permuations
\[
  \begin{pmatrix}
    1 & 2 & 3\\
    3 & 1 & 2
  \end{pmatrix}
  \qquad \text{and} \qquad
  \begin{pmatrix}
    1 & 2 & 3\\
    3 & 2 & 1
  \end{pmatrix},
\]
we observe that the first ``rotates'' the elements to the right, while
the second ``reflects'' the elements.  Indeed, if we consider the
correspondence between these permutations and the symmetries of a triangle
discussed in Example~\ref{eg:perm3part2}, we see that the first corresponds
to a rotation, and the second to a reflection.  In this section, we will
generalize this idea to arbitrary permutations.

The starting point of this discussion is a comparison between the following
two products: if $p \in S_{n}$ we define
\[
  D_{n} = \prod_{1 \le i < j \le n} (j - i)
\]
and
\[
  D(p) = \prod_{1 \le i < j \le n} (p(j) - p(i)).
\]
Given any pair of distinct elements $k,l \in \{1, 2, \ldots, n\}$, both of
these products contain exactly one factor which is a difference of $k$ and $l$.
This is easy to see in the product $D_{n}$, but a little thought will convince
you that it is also the case for $D(p)$.  The difference between the two
products is that in $D(p)$ it may not necessarily be the larger term minus
the smaller term.  Hence $D_{n}$ and $D(p)$ have the same magnitude, but may differ
in sign.

\begin{definition}
  Let $p \in S_{n}$.  The \defn{parity}{parity} of $p$ is
  \[
    \parity(p) = \frac{D(p)}{D_{n}}.
  \]
\end{definition}

Clearly the parity of $p$ is $1$ if $D(p) > 0$ and $-1$ if $D(p) < 0$.

\begin{example}
  Consider the permutations
  \[
    p = \begin{pmatrix}
      1 & 2 & 3\\
      3 & 1 & 2
    \end{pmatrix}
    \qquad \text{and} \qquad
    q = \begin{pmatrix}
      1 & 2 & 3\\
      3 & 2 & 1
    \end{pmatrix}.
  \]
  In both cases
  \[
    D_{3} = (3 - 1)(3 - 2)(2 - 1) = 2 \times 1 \times 1 = 2.
  \]
  Now
  \[
    D(p) = (p(3) - p(1))(p(3) - p(2))(p(2) - p(1)) = (2 - 3)(2 - 1)(1 - 3)
      = -1 \times 1 \times -2 = 2,
  \]
  so
  \[
    \parity(p) = 2/2 = 1.
  \]
  On the other hand,
  \[
    D(q) = (q(3) - q(1))(q(3) - q(2))(q(2) - q(1)) = (1 - 3)(1 - 2)(2 - 3)
      = -2 \times -1 \times -1 = -2,
  \]
  so
  \[
    \parity(q) = -2/2 = -1.
  \]
\end{example}

Calculating the parity in the last example was fairly straightforward,
but calculating the parity of a general permutation can be quite time
consuming: a simple counting argument tells us that if $p \in S_{n}$ we
have $n(n-1)/2$ terms in the product $D(p)$.  We need a better way to
calculate the parity.

It turns out that there is nothing particularly special about $D_{n}$ in
the definition of parity.  Let $(x_{1}, x_{2}, \ldots, x_{n})$ be a sequence of distinct numbers, and $p$
a permutation of $\{1, 2, \ldots n\}$.  We define
\begin{equation}\label{eqn:permutationaction}
  p(x_{1}, x_{2}, \ldots, x_{n}) = (x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)}),
\end{equation}
and
\[
  D(x_{1}, x_{2}, \ldots, x_{n}) = \prod_{1 \le i < j \le n} (x_{j} - x_{i}).
\]
The following technical lemma shows that we can use these instead to find the
parity of $p$.

\begin{lemma}
  If $p$ is a permutation in $S_{n}$, then
  \[
    \parity(p) = \frac{D(x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)})}{D(x_{1}, x_{2},
    \ldots, x_{n})}.
  \]
  We say that $p$ is an \defn{even permutation}{permutation!even} if
  $\parity(p) = 1$, and $p$ is an \defn{odd permutation}{permutation!odd} if
  $\parity(p) = -1$.
\end{lemma}
\begin{proof}
  Given any number $k \in \{1, 2, \ldots, n\}$, let $a_{k} = p^{-1}(k)$.
  Then given any $k > l$, we have that $k = p(a_{k})$ and $l = p(a_{l})$.
  
  If $a_{k} > a_{l}$, in which case the corresponding terms in each of the
  sums $D_{n}$, $D(p)$, $D(x_{1}, \ldots, x_{n})$ and $D(x_{p(1)}, \ldots,
  x_{p(n)})$ are, respectively, $k - l$, $p(a_{k}) - p(a_{l})$, $x_{k} - x_{l}$,
  and $x_{p(a_{k})} - x_{p(a_{l})}$, with the first two being equal and the
  second two being equal, and so these terms in the quotients $D(p)/D_{n}$
  and $D(x_{p(1)}, \ldots, x_{p(n)})/D(x_{1}, \ldots, x_{n})$, respectively,
  cancel each other out.

  On the other hand, if $a_{k} < a_{l}$, the corresponding terms in each of the
  sums $D_{n}$, $D(p)$, $D(x_{1}, \ldots, x_{n})$ and $D(x_{p(1)}, \ldots,
  x_{p(n)})$ are, respectively, $k - l$, $p(a_{l}) - p(a_{k})$, $x_{k} - x_{l}$,
  and $x_{p(a_{l})} - x_{p(a_{k})}$, with the first two being negatives and the
  second two being negatives, and so these terms in the quotients $D(p)/D_{n}$
  and $D(x_{p(1)}, \ldots, x_{p(n)})/D(x_{1}, \ldots, x_{n})$, respectively,
  give a factor of $-1$.
  
  Hence the number of terms giving each of the factors $1$ and $-1$ in each
  quotient are equal, so
  \[
    \parity(p) = \frac{D(p)}{D_{n}}
      = \frac{D(x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)})}{D(x_{1}, x_{2}, \ldots, x_{n})}.
  \]
\end{proof}

Note that $D_{n} = D(1, 2, \ldots, n)$, and $D(p) = D(p(1), p(2), \ldots, p(n))$.

With this lemma in hand, we can easily prove the following important result:

\begin{theorem}
  Let $p$ and $q \in S_{n}$.  Then
  \[
    \parity(pq) = \parity(p)\parity(q).
  \]
\end{theorem}
\begin{proof}
  The key observation here is that if we have permutations $p$ and $q$,
  then
  \[
    \parity(p) = \frac{D(pq)}{D(q)}.
  \]
  Letting $a_{k} = q(k)$, so that
  \[
    D(pq) = D(q(p(1)), q(p(2)), \ldots, q(p(n))) = D(a_{p(1)}, \ldots, a_{p(n)}),
  \]
  and
  \[
    D(q) = D(a_{1}, \ldots, a_{n}),
  \]
  the lemma tells us that
  \[
    \parity(p) = \frac{D(a_{p(1)}, \ldots, a_{p(n)})}{D(a_{1}, \ldots, a_{n})}
     = \frac{D(pq)}{D(q)}.
  \]
  
  It is immediate form this that
  \[
    \parity(p) \times \parity(q) = \frac{D(pq)}{D(q)} \times \frac{D(q)}{D_{n}}
    = \frac{D(pq)}{D_{n}} = \parity(pq).
  \]
\end{proof}

Thinking in terms of cycles also helps us to calculate the parity of a
permutation, as this result shows:

\begin{theorem}
  Let $c = (k_{1}, k_{2}, \ldots, k_{m})$ be a cycle.  Then
  \[
    \parity(c) = \begin{cases}
      1 & \text{if $m$ is odd} \\
      -1 & \text{if $m$ is even}.
    \end{cases}
  \]
\end{theorem}
\begin{proof}
  First we observe that if $p = (1, 2)$, then all the factors in $D(p)$
  are positive, except for $p(2) - p(1) = 1 - 2 = -1$.  Hence $D(p)$ is
  negative, so $\parity(p) = -1$.
  
  Now if $i, j > 2$, and $i \ne j$, then simple checking shows that
  $(i,j) = (1,i)(2,j)(1,2)(1,i)(2,j)$,
  and, given this fact, the previous theorem tells us
  \begin{align*}
    \parity((i,j)) &= \parity((1,i)(2,j)) \times \parity(1,2) \times \parity((1,i)(2,j)) \\
    &= -\parity((1,i)(2,j))^{2}\\
    &= -1
  \end{align*}
  
  Finally, we observe that
  \begin{equation}\label{eqn:cycleproduct}
    c = (k_{1}, k_{2}, \ldots, k_{m}) = (k_{1}, k_{m})(k_{2}, k_{m})\cdots (k_{m-1}, k_{m}),
  \end{equation}
  and so
  \begin{align*}
    \parity(c) &= \parity((k_{1}, k_{m})) \times \parity((k_{2}, k_{m})) \times \cdots \times \parity((k_{m-1}, k_{m}))\\
    &= (-1)^{m-1} \\
    &= \begin{cases}
    1 & \text{if $m$ is odd} \\
    -1 & \text{if $m$ is even.}
    \end{cases}
  \end{align*}
\end{proof}

\begin{corollary}
  A permutation $p$ is even iff when it is expressed as a product of
  cycles there are an even number of commas in the expression.
\end{corollary}

Another interesting fact that can be squeezed out of the previous theorem
is the following:

\begin{proposition}
  Any permutation $p$ can be written as a product of $2$-cycles, and the
  number of $2$-cycles is even iff $p$ is even.
\end{proposition}
\begin{proof}
  The first fact follows from the fact that every permutation can be written
  as a product of cycles, and equation (\ref{eqn:cycleproduct}) shows that every cycle
  is a product of $2$-cycles.
  
  The second follows from the previous corollary, coupled with the fact that
  every $2$-cycle has a single comma.
\end{proof}

\begin{example}
  Let $p_{0}$, $p_{1}, \ldots, p_{5}$ be as in Example~\ref{eg:perm3part2}.
  Then $\parity(p_{0}) = \parity(p_{1}) = \parity(p_{2}) = 1$, and
  $\parity(p_{3}) = \parity(p_{4}) = \parity(p_{5}) = -1$.
  
  Observe that the ``reflections'' have parity -1, while the ``rotations''
  have parity 1.
\end{example}

\begin{example}
  The permutation
  \[
    p = \begin{pmatrix}
     1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
     3 & 5 & 2 & 7 & 8 & 6 & 1 & 4 & 10 & 9
    \end{pmatrix},
  \]
  can be written as $p = (1, 3, 2, 5, 8, 4, 7)(9, 10)$, and since it has $7$
  commas in the expression, it has parity $-1$.
\end{example}

\subsection{Permutation Matrices}

Another way of looking at permutations is very closely related to
Equation~\ref{eqn:permutationaction}.  Let $e_{k}$ be the $k$th standard
orthonormal basis vector in $\reals^{n}$, ie.\ $e_{k}$ is the vector with $0$
in every entry except the $k$th entry, which is $1$.


Since $x = (x_{1},x_{2},\ldots,x_{n})$ is a vector in $\reals^{n}$, the function
it implicitly defines, $T_{p}: \reals^{n} \to \reals^{n}$, where
\[
  T_{p}x = (x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)})
\]
is a linear transformation:
\begin{align*}
  T_{p}(x+y) &= (x_{p(1)} + y_{p(1)}, x_{p(2)} + y_{p(2)}, \ldots, x_{p(n)} + y_{p(n)})\\
    &= (x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)}) + (y_{p(1)}, y_{p(2)}, \ldots, y_{p(n)})
    = T_{p}x + T_{p}y
\end{align*}
and
\begin{align*}
  T_{p}(\lambda x) &= (\lambda x_{p(1)}, \lambda x_{p(2)}, \ldots, \lambda x_{p(n)})\\
    &= \lambda (x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)})
    = \lambda T_{p}x.
\end{align*}

By looking at the image of each standard basis vector $e_{k}$ under the
transformation $T_{p}$, we can find a corresponding $n \times n$ matrix
which we will also call $T_{p}$.
We note that $T_{p}e_{k} = e_{p(k)}$, so $T_{p}$ always takes basis vectors
to basis vectors. Hence every column in the matrix $T_{p}$ is a basis vector,
and every entry of each column is $0$, except for a $1$ in the $p(k)$th row.
Furthermore, since $p$ is a permutation $p(k) = p(j)$ if and only if $k = j$,
so each row is $0$, except for one entry which is $1$.

\begin{proposition}
  Let $p \in S_{n}$ be a permutation.  Then
  \begin{theoremenum}
    \item $T_{p}$ is an orthogonal matrix
    \item $T_{p}$ is the matrix with $1$s in the $p(k)$th row of the $k$th
      column, for $k = 1,2,\ldots,n$, and $0$ everywhere else.
    \item $T_{e} = I_{n}$.
    \item $T_{p}T_{q} = T_{p \circ q} = T_{qp}$.
    
  \end{theoremenum}
\end{proposition}

\subsection*{Exercises}

\begin{enumerate}
  \item Let
    \[
      p = \begin{pmatrix}
        1 & 2 & 3 & 4 & 5 & 6 \\
        4 & 2 & 5 & 1 & 6 & 3
      \end{pmatrix}
      \qquad \text{and} \qquad
      q = \begin{pmatrix}
        1 & 2 & 3 & 4 & 5 & 6 \\
        3 & 4 & 5 & 1 & 2 & 6
      \end{pmatrix}.
    \]
    Find $pq$ and $qp$.  Write both permutations using cycle notation.
    Determine the parity of $p$ and $q$.
  
  \item Let $p = (1, 5, 3, 2)(4, 6, 8)$ and $q = (1, 7, 4, 3)(8, 2)(5, 6)$.
    Find $pq$ and $qp$.  Write both permutations using array notation.
    Determine the parity of $p$ and $q$.

  \item How many distinct permutations are there of the set $\{1, 2,
    \ldots, n\}$? (Hint: they're called \emph{permutations}.)
  
  \item Let $p \in S_{3}$.  Use the Cayley table for $S_{3}$ to show that
    $p^{6}$ is always the identity permutation.
  
  \item Write down all the elements of $S_{4}$ in both array and cycle form.
    Calculate the parity of each element.
    Find the inverse of each element.
    Choose 5 pairs of non-identity elements, and calculate their product.
  
  \item Let $c = (k_{1}, k_{2}, \ldots, k_{m})$ be a cycle.  What is $c^{-1}$?
    Use your answer to calculate the inverse of the permutation
    $p = (1,3,4)(2,5)$.
  
  \item Show that $D_{n} = (n-1)! (n-2)! \ldots 2! 1!$.
  
  \item Show that exactly half the permutations of $S_{n}$ are even, and half
    are odd.
  
  \item (*) Show that $S_{4}$ and the set of symmetries of a regular tetrahedron
    (see Section~\ref{section:symmetry} Exercise~\ref{ex:symtetra}) correspond
    in the same way as $S_{3}$ and the set of symmetries of an equilateral
    triangle.
    
    Hint: you could do this by calculating all $576$ entries in the Cayley
    table of each, and comparing the two; however it is more practical
  
  \item (**) Write a computer program that calculates and prints out the
    Cayley table for $S_{4}$.  Generalize it to print out the Cayley table
    for $S_{n}$ for any $n$.
\end{enumerate}

\section{Modulo Arithmetic}

We say that two numbers $x$ and $y$ are \defn{equal (modulo $m$)}{modulo|equality} if $x$ and
$y$ differ by a multiple of $m$, and we write
\[
  x \equiv y \pmod m
\]
to denote this situation.  Another equivalent (and useful) way to think of
this situation is that $x$ and $y$ have the same remainder when you divide
by $m$.  Since any number greater than $m$ is equal (modulo $m$) to a number
less than $m$, it is customary when working modulo $m$ to reduce your answer
to a number in the range $[0,m)$.

For example
\[
  -1 \equiv 7 \equiv 1023 \pmod 8,
\]
and we would usually write any of these three numbers as $7 \mod 8$ if it
were the solution to a problem.

When we are working modulo $m$, we can perform the operations of addition,
multiplication and subtraction as normal, but we reduce our answers to the
range $[0,m)$.  Indeed, in complicated expressions, one can reduce at
intermediate steps to simplify calculations:
\[
  7 \times 6 + 4 \times 3 \equiv 42 + 12 \equiv 54 \equiv 6 \pmod 8
\]
could be instead calculated as
\[
  7 \times 6 + 4 \times 3 \equiv 42 + 12 \equiv 2 + 4 \equiv 6 \pmod 8.
\]

Division is a trickier topic, but since we are usually performing modulo
arithmetic with integers the na\"{i}ve way of defining modulo division does
not make sense in most cases.  Nevertheless, we will see later on that in
some cases division does make sense.

We can write out addition and multiplication tables for operations modulo
some base, and we call these Cayley tables, just as before.

\begin{example}\label{eg:mod6}
  The addition and multiplication tables, modulo 6 are as follows:
  \[
    \begin{array}{c|cccccc}
      + & 0 & 1 & 2 & 3 & 4 & 5 \\
      \hline
      0 & 0 & 1 & 2 & 3 & 4 & 5 \\
      1 & 1 & 2 & 3 & 4 & 5 & 0 \\
      2 & 2 & 3 & 4 & 5 & 0 & 1 \\
      3 & 3 & 4 & 5 & 0 & 1 & 2 \\
      4 & 4 & 5 & 0 & 1 & 2 & 3 \\
      5 & 5 & 0 & 1 & 2 & 3 & 4
    \end{array}
  \qquad
    \begin{array}{c|cccccc}
      \times & 0 & 1 & 2 & 3 & 4 & 5 \\
      \hline
      0 & 0 & 0 & 0 & 0 & 0 & 0 \\
      1 & 0 & 1 & 2 & 3 & 4 & 5 \\
      2 & 0 & 2 & 4 & 0 & 2 & 4 \\
      3 & 0 & 3 & 0 & 3 & 0 & 3 \\
      4 & 0 & 4 & 2 & 0 & 4 & 2 \\
      5 & 0 & 5 & 4 & 2 & 3 & 1
    \end{array}
  \]
\end{example}


\chapter{Groups}

Algebra concerns the abstraction of simple arithmetic operations to
situations where the quantities involved are unknown.  In developing rules
for algebra, we discover that there are certain rules which always apply,
such as the commutative and associative laws of addition and multiplication,
and that these laws allow us to manipulate and simplify algebraic
expressions. As we learnt more mathematics, we saw similar rules appear over
and over again.  For example, we know that addition of vectors, addition of
matrices, and multiplication of matrices also all satisfy associative laws, and
the first two are also commutative.

In the previous chapter, we also saw that products of symmetries and
permutations also follow an associative law, and sometimes are commutative as
well.

In abstract algebra, instead of concentrating on specific algebraic
settings (such as algebra with numbers, vectors or, now, permutations or
symmetries) we instead look
at the \emph{rules} of algebra and ask what we can infer from reasonable
collections of such rules.  We can then apply the knowledge so gained to a
surprisingly wide collection of concrete situations which happen to satisfy
such rules.

You may have already seen such an approach in linear algebra, where one
eventually considers abstract vector spaces (as opposed to concrete ones, such
as $\reals^{n}$).  One then finds that, for example, the theory applies to
differentiable functions, with differentiation being a linear operator,
giving new insight into calculus that you may not have had before.

The approach in this course is to start with the simplest reasonable
sets of rules, and work up to more complex situations.  Our starting point,
then will be the \defn{group}{group}, an object which encapsulates a reasonable set
of rules for a single algebraic operation.

\section{Binary Operations}

A \defn{binary operation}{binary operation} is a special type of function that we shall be
using with some regularity in this section.  A binary operation $\ast$
is a function
\begin{align*}
  \ast : A \cross B &\to C\\
         (x,y) &\mapsto x \ast y.
\end{align*}
Instead of using ``function-style'' notation $\ast(x,y)$, it is traditional to
write the operation ``in-line'' as $x \ast y$.  In this sense, binary
operations are no more than special notation for certain functions.  Often $A$,
$B$ and $C$ are the same set, in which case we say that a binary operation
$\ast : A \cross A \to A$ is a binary operation on $A$.

A binary operation is \defn{commutative}{commutative} if
\[
  x \ast y = y \ast x.
\]
It is \defn{associative}{associative} if
\[
  (x \ast y) \ast z = x \ast (y \ast z) = x \ast y \ast z.
\]
An element $e$ of $A$ is an \defn{identity}{identity} for the binary operation if
\[
  e \ast x = x \qquad \text{and} \qquad x \ast e = x
\]
for every $x \in A$.  More generally, one can have a \defn{left identity}{identity!left}
$e$ which merely satisfies
\[
  e \ast x = x
\]
for every $x$.  A \defn{right identity}{identity!right} is defined analagously.

\begin{lemma}
  If $\ast: A \cross A \to A$ is a binary operation, and $e$ is an identity for
  $\ast$, then it is the only identity element.
\end{lemma}
\begin{proof}
  Assume that there is another element $e'$ so that $e' \ast x = x \ast e' =
x$.  Then in particular, if we let $x = e$, we have $e' \ast e = e$.  But by
assumption, $e$ is an identity, and so $e' \ast e = e'$.  Hence $e = e'$.
\end{proof}

Notationally, if $\ast$ behaves in a ``multiplication-like'' fashion, or it
is clear from context which binary operation we are using, we will often simply
write $xy$ for $x \ast y$.

For example, the addition operation is a binary operation in the integers
\begin{align*}
  + : \integers \cross \integers &\to \integers\\
         (x,y) &\mapsto x + y.
\end{align*}
In this case we could write $+(2,3) = 2 + 3 = 5$.  Addition is, of course,
both associative and commutative.  $0$ is an identity for addition.  In fact
addition is also an associative and commutative binary operation on just about
any reasonable set of numbers you care to consider, and if $0$ is in the
set, then $0$ is an identity.

Multiplication is a binary operation on the set $\reals$, and it is associative
and commutative, and $1$ is an identity.  Again, like addition,
multiplication is communtative and associative on many reasonable sets of
numbers.

If we consider the set $M_{n}(\reals)$ of $n \times n$ real-valued matrices,
then matrix addition and matrix multiplication are binary operations.  Both
operations are associative, but only matrix addition is commutative.  The
zero matrix is an identity for addition, the identity matrix $I_{n}$ (the
matrix with $1$ down the diagonal and $0$ elsewhere) is an identity for matrix
multiplication.

We also have scalar multiplication as a binary operation $\reals \cross
M_{n}(\reals) \to M_{n}(\reals)$.  This cannot be commutative or
associative, but it does have $1$ as a left identity.

More generally, the inner or dot product on $\reals^{n}$ is a binary
operation $\cdot: \reals^{n} \cross \reals^{n} \to \reals$ which is
commutative, but cannot be associative (since the codomain is $\reals$, and
one cannot take a dot product of an element of $\reals$ and an element of
$\reals^{n}$).  Similarly, there is no identity element of any sort.

One can define arbitrary binary products which are of little or no interest.
For example, $x \ast y = e^{x}(x + \sin(y))$ is a binary product.  But it is
neither associative, commutative, nor has an identity.  So clearly simple
binary operations are not enough to encapsulate the sorts of rules that we
expect algebraic operations to have.

\subsection*{Exercises}

\begin{enumerate}
  \item Let $\ast: A \cross A \to A$ be a commutative binary operation.  If
$e$ is a left identity, show that it also a right identity (and hence simply
an identity).

  \item (*) Let $X$ be any set, and let $\powerset(X)$ be the power set of
$X$ (ie. the set of all subsets of $X$).  Show that $\union : \powerset(X)
\cross \powerset(X) \to \powerset(X)$ is an associative, commutative binary
operation, and that $\emptyset$ is an identity for this operation.

  Similarly, show that $\intersect : \powerset(X) \cross \powerset(X) \to
\powerset(X)$ is an associative, commutative binary operation, and that
$X$ is an identity for this operation.

\end{enumerate}

\section{Groups}

If you look carefully at the discussion of symmetries and permutations, you
will note that not only was there a binary operation, but there was an inverse.
We should have some model for this additional operation.

A \defn{group}{group}, $\mathbf{G} = (G, \ast, e)$, consists of a set $G$, a binary
operation $\ast: G \cross G \to G$, and an element $e \in G$
satisfying the following three conditions:
\begin{enumerate}
  \item $\ast$ is associative
  \item $e$ is an identity for $\ast$
  \item every element $x \in G$ has an \defn{inverse element}{inverse element} $x^{-1} \in G$
such that $x \ast x^{-1} = x^{-1} \ast x = e$.
\end{enumerate}
We call $\ast$ the \defn{group operation}{group operation}.

Note that there is no requirement that the group operation is commutative. 
If it does happen to be commutative, then we say that the group is an
\defn{commutative}{group!commutative} or \defn{Abelian group}{group!Abelian}.

This means that in general $x \ast y$ and $y \ast x$ are distinct elements,
but sometimes they are not.  If
\[
  x \ast y = y \ast x
\]
for a particular $x$ and $y \in G$, we say that $x$ and $y$ \defn{commute}{commuting elements}.

A number of different notations are used when working with groups elements. 
Most commonly we will omit the group operation entirely and simply write $xy$
for $x \ast y$, just as is done for multiplication.  In this case we use the
following clear notation for repeated applications of the group operations:
\[
  x^{k} = \underbrace{x x x ... x}_{k\text{ times}}
\]
for any natural number $k$.  To make this notation mesh nicely with the
expected behaviour of power laws, we define
\[
  x^{-k} = (x^{-1})^{k} \qquad \text{and} \qquad x^{0} = e.
\]
When then have the standard power laws
\[
  x^{m}x^{k} = x^{m+k} \qquad \text{and} \qquad (x^{m})^{k} = x^{mk},
\]
for any integers $m$ and $k$.  Its also not hard to see that $(x^{k})^{-1} =
x^{-k}$.  However, we have that
\[
  (xy)^{k} \ne x^{k}y^{k}
\]
in general.  In the case that $x$ and $y$ commute, then we do have equality.

In the case of Abelian groups, we will sometimes instead use an additive
notation.  We use $+$ for the group operation, and we customarily write the
identity element as $0$, and the inverse element of $x$ as $-x$. We then use
the notation
\[
  kx = \underbrace{x + x + \cdots + x}_{k\text{ times}}
\]
for any natural number $k$, and
\[
  -kx = k(-x) \qquad \text{and}  \qquad 0x = 0.
\]
We then have the natural rules that
\[
  kx + mx = (k + m)x, \qquad k(mx) = (km)x \qquad \text{and} \qquad kx + ky
= k(x+y)
\]
for any integers $k$ and $m$.

If the set $G$ has a finite number of elements, we say that the
\defn{order}{order!of a group} of the group is the number of elements of $G$. 
If $G$ is an infinite set, we say that the group has infinite order.  We denote
the order of the group by $|G|$.

\begin{example}[Addition and Multiplication]
  Since a principle motivation for the definition of groups are standard
  algebraic operations, it should be no surprise that the following are all
  Abelian groups:
  \begin{itemize}
    \item the additive group of real numbers $(\reals, +, 0)$
    \item the additive group of complex numbers $(\complex, +, 0)$
    \item the additive group of rational numbers $(\rationals, +, 0)$
    \item the additive group of integers $(\integers, +, 0)$
    \item the multiplicative group of real numbers $(\reals \setminus \{0\}, \times, 1)$
    \item the multiplicative group of complex numbers $(\complex \setminus \{0\}, \times, 1)$
    \item the multiplicative group of rational numbers $(\rationals \setminus \{0\}, \times, 1)$
    \item the multiplicative group of integers $(\integers \setminus \{0\}, \times, 1)$
    \item the multiplicative group of natural numbers $(\naturals, \times, 1)$
  \end{itemize}
  Note that for the multiplicative groups, we need to exclude $0$, since $0$
  has no multiplicative inverse.
  
  All of these groups have infinite order.
\end{example}

\begin{example}[Modulo Addition]
  If $m$ is any natural number, the additive group of integers modulo $m$ is
  the group $\integers_{m} = (\{0, 1, 2, \ldots, m-1\}, +, 0)$, where addition
  is performed modulo $m$.  To confirm that it is a group, we need to check
  that the axioms hold.
  
  Associativity follows from the fact that regular addition is associative and commutative.
  Given $x$, $y$ and $z$, we have $x + y = a + km$ for some $a$ and $k$, so
  $(x + y) + z \equiv a + z \pmod{m}$.  But $y = a - x + km$, so $y + z
  \equiv a - x + z \pmod{m}$, and hence $x + (y + z) \equiv x + a - x + z \equiv a
  + z \pmod{m}$.
  
  The fact that $0$ is an identity is trivial: $0 + x = x$, so $0 + x \equiv x \pmod{m}$
  follows immediately.
  
  If $x \in \{1, 2, \ldots, m-1\}$, we know that $-x \equiv m-x \pmod{m}$, and so
  $(m - x) + x \equiv 0 \pmod{m}$ and $x + (m - x) \equiv 0 \pmod{m}$.  Also
  $0$ is its own inverse. So every element has an inverse.
  
  These groups are also clearly Abelian, since regular addition is commutative.
  
  The order of $\integers_{m}$ is $m$.
\end{example}

The previous example shows that there are groups of all orders.

\begin{example}
  Multiplication modulo $m$ does not, in general, give a group structure.
  Multiplication modulo $m$ is associative, and $1$ is an identity.
  We have to exclude $0$ from the group, because it clearly does not
  have a multiplicative inverse, but even with this restriction, some other
  elements may not have multiplicative inverses.
  
  If you consider multiplication modulo $6$, as in Example~\ref{eg:mod6},
  you can see that there are no inverses for $2$, $3$, and $4$, since none
  of them have a number which you can multiply them by to give $1$.  Indeed,
  there is a somewhat deeper problem in that some products give $0$, which
  cannot be an element of the group.
  
  Multiplication modulo $m$ {\em does} sometimes give you a group, however.
  The multiplication table (omitting $0$) for multiplication modulo $5$ is
  as follows:
  \[
    \begin{array}{c|cccc}
      \times & 1 & 2 & 3 & 4 \\
      \hline
      1 & 1 & 2 & 3 & 4 \\
      2 & 2 & 4 & 1 & 3 \\
      3 & 3 & 1 & 4 & 2 \\
      4 & 4 & 3 & 2 & 1
    \end{array}
  \]
  A quick check shows that every element has an inverse.  Hence
  $(\{1, 2, 3, 4\}, \times, 1)$ is a group, where $\times$ is multiplication
  modulo $5$.
\end{example}

\begin{example}
  The \defn{symmetric group}{group!symmetric} is the group $S_{n} = (S_{n},
  \cdot, e)$ of all permutations, with the multiplication of permutations
  being the group operation, and $e(k) = k$ being the identity
  permutation.  That this is a group is largely the content of
  Proposition~\ref{prop:permgroup}.  The only thing that needs to be checked
  is that the identity permutation is in fact a group identity, and that is
  fairly straightforward: if $p$ is any permutation in $S_{n}$,
  \[
    (pe)(k) = e(p(k)) = p(k) \qquad \text{and} \qquad (ep)(k) = p(e(k)) = p(k),
  \]
  for all $k$, so $ep = pe = p$, and $e$ is therefore the identity for this
  group operation.
\end{example}

\begin{example}[Matrix Groups]
  Recall that a matrix $A$ is invertible if and only if $\det(A) \ne 0$.
  If we are going to find groups of matrices with matrix multiplication as
  the group operation, then they must be invertible at least.
  
  The following are all groups:
  \begin{itemize}
    \item the \defn{general linear group}{group!general linear} of $n \times n$ 
    matrices $(GL_{n}(\reals), \times, I_{n})$, where
    \[
      GL_{n}(\reals) = \{ A \in M_{n}(\reals) : \det(A) \ne 0\}.
    \]
    
    \item the \defn{orthogonal group}{group!orthogonal} of $n \times n$ 
    matrices $(O_{n}(\reals), \times, I_{n})$, where $O_{n}(\reals)$
    is the set of orthogonal matrices (ie.\ matrices whose columns form an
    orthonormal basis or, equivalently, which satisfy $A^{-1} = A^{t}$).
    
    \item the \defn{special linear group}{group!special linear} of $n \times
    n$ matrices $(SL_{n}(\reals), \times, I_{n})$, where
    \[
      SL_{n}(\reals) = \{ A \in M_{n}(\reals) : \det(A) = 1\}.
    \]
    
    \item the \defn{special orthogonal group}{group!special orthogonal} of
    $n \times n$ matrices $(SO_{n}(\reals), \times, I_{n})$, where $SO_{n}(\reals)$
    is the set of orthogonal matrices with determinant 1.
  \end{itemize}
  
  There isn't anything particularly special about $\reals$-valued matrices
  in the above.  Once can define $GL_{n}(\field)$,  $SL_{n}(\field)$, 
  $O_{n}(\field)$, and $SO_{n}(\field)$ for any field $\field$ (such as
  the complex numbers $\complex$, or the rational numbers $\rationals$).
  
  A \defn{unitary matrix}{matrix!unitary} is a complex-valued matrix which
  satisfies $A^{-1} = A^{*}$, where $A^{*}$ is the conjugate transpose matrix
  of $A$.  More precisely, if $A = [a_{i,j}]_{i,j=1}^{n}$, then
  \[
    A^{*} = [\overline{a_{i,j}}]^{t}.
  \]
  We then have two additional complex matrix groups
  \begin{itemize}
   \item the \defn{unitary group}{group!unitary} of $n \times n$ 
    matrices $(U_{n}(\complex), \times, I_{n})$, where $U_{n}$
    is the set of unitary matrices.
    
    \item the \defn{special unitary group}{group!special unitary} of
    $n \times n$ matrices $(SU_{n}(\complex), \times, I_{n})$, where $SU_{n}(\complex)$
    is the set of unitary matrices with determinant 1.
  \end{itemize}
\end{example}

\subsection*{Exercises}

\begin{enumerate}
  \item Let $(G, \ast, e)$ be a group, and let $x$ and $y$ be two elements
of $G$ which commute.  Prove that for any $k \in \integers$, $(xy)^{k} =
x^{k}y^{k}$.

  \item Give an example of a group and two elements of that group such that
  \[
    (xy)^{2} \ne x^{2}y^{2}.
  \]
  Provide concrete calculations to demonstrate this fact for your example.
\end{enumerate}

\subsection*{Extension: Less Than A Group}

There are algebraic objects which do not quite satisfy all the axioms of a
group, but which are nevertheless of interest.

\printindex

\end{document}
\end