%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Groups, and other algebraic structures (section 8.1)}


\section{Introduction}

A mathematical structure is a formal model which capture common properties
or behavior of different sets.

It consists of an abstract set, together with operations and relations
which obey certain rules.

For example the set of tasks to build a house, and the set of all
courses available at CSM have something in common: the notion of prerequisite.
This notion can be formalized using a structure of partially ordered
set.

We will introduce here certain algebraic structures, which are useful
to model arithmetic, as well as to the study of symmetries.


\section{Permutations}

\begin{defn*}
Let $A$ be a set. A \emph{permutation} of $A$ is a bijection from
$A$ to $A$.

Let $S_{A}$ be the set of all permutations of $A$.

Let $S_{n}$ be the set of all permutations of $\{1,\ldots n\}$.
\end{defn*}
A permutation $\sigma$ of $S_{n}$ can be written in \emph{array
form} as follow: \[
\sigma:=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 1 & 4 & 5 & 3 & 6\end{array}\right),\]


meaning that $\sigma(1)=2$, $\sigma(2)=1$, $\sigma(3)=4$, and so
on.

\begin{xca}
Write all permutations in $S_{1}$, $S_{2}$, and $S_{3}$.

What is the size of $S_{n}$?
\end{xca}

\subsection{Operation on $S_{n}$}

$S_{n}$ as a set is not very interesting. 

Can we define operations on $S_{n}$?

%

%

%

%

%

%%

\begin{prop*}
The composition $\bullet$is an operation of $S_{n}$. 
\end{prop*}
Indeed, the composition of two permutations is still a permutation.

We also call this operation product of permutations.

\begin{xca}
Compute the following:

\[
\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 5 & 1 & 6 & 3 & 4\end{array}\right)^{-1}=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]
\[
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
5 & 3 & 4 & 1 & 2\end{array}\right)\bullet\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
3 & 1 & 4 & 2 & 5\end{array}\right)=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
\end{array}\right)\]
\[
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
5 & 3 & 4 & 1 & 2\end{array}\right)\bullet\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 4 & 5 & 1\end{array}\right)=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
\end{array}\right)\]


\[
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 4 & 5 & 1\end{array}\right)^{5}=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
\end{array}\right)\]

\end{xca}
The permutation above produces a \emph{cycle}: $1\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow1$ 

\begin{defn*}
By $(a,b,c,d)$, we denote the permutation $\sigma$ such that $\sigma(a)=b$,
$\sigma(b)=c$, $\sigma(c)=d$, $\sigma(d)=a$, and $\sigma(x)=x$
for any other element $x$. 

Such a permutation is called a \emph{cycle}.

A cycle $(i,j)$ of length two is called a \emph{transposition}.

A transposition $(i,i+1)$ is called \emph{elementary transposition.}
\end{defn*}
\begin{xca}
Write $(3,4,2,1)$ and $(2,1,3,4)$ in array notation.

Write the following permutations in array notation:

\[
(3,4,2,1)=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
\end{array}\right)\]


\[
(2,1,3,4)=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
\end{array}\right)\]


\[
(1,2,3)\bullet(4,5)=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]


\[
(4,5)\bullet(1,2,3)=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]


\[
(1,2,3)\bullet(3,4)=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]


\[
(3,4)\bullet(1,2,3)=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]

\end{xca}
\begin{prop*}
The product of two disjoint cycles is commutative.

This is not the case for non-disjoint cycles.
\end{prop*}
\begin{xca}
Are the following permutations cycles?

\[
\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5\\
5 & 3 & 4 & 1 & 2\end{array}\right)\]


\[
\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 1 & 4 & 5 & 3 & 6\end{array}\right)\]

\end{xca}
%

%

%

%

%

%%

\begin{problem}
So there are permutations that are not cycles.

Would it be possible to write them using only cycles?
\end{problem}
%

%

%

%

%

%%

\begin{thm*}
Any permutation can be written as a product of disjoint cycles.

This product is unique, up to the order.
\end{thm*}
\begin{xca}
Compute the following permutations

\[
(2,3,1,5,4)^{5}=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
\end{array}\right)\]


\[
\left(\begin{array}{cccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
5 & 10 & 2 & 1 & 6 & 4 & 8 & 3 & 7 & 9\end{array}\right)^{131}=\left(\begin{array}{cccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\end{array}\right)\]

\end{xca}
Writting a permutation in cycle notation is a good way to compute
powers of this permutation.


\subsection{Generators of $S_{n}$}

If you have a list, you can use a permutation to change its order. 

Well, $S_{n}$ is pretty big, so this makes quite a lot of possible
operations. 

However, some operations can be obtained by combining other operations.

Could we try to reduce the size of $S_{n}$?

\begin{defn*}
A subset $G$ of $S_{n}$ \emph{generates} $S_{n}$ if any permutation
can be written as a product of elements of $G$.
\end{defn*}
\begin{problem}
Find a set of generators of $S_{n}$ as small as possible.
\end{problem}
%

%

%

%

%

%

%%

\begin{problem}
Does the set of all cycles generate $S_{n}$?
\begin{problem}
How many cycles are there ?
\end{problem}
Can you do better?
\end{problem}
%

%

%

%

%

%%

\begin{problem}
Does the set of all transpositions generate $S_{n}$?

How many transpositions are there?

Can you do better?
\end{problem}
%

%

%

%

%

%%

\begin{problem}
Does the set of all elementary transposition generate $S_{n}$?

How many elementary transpositions are there ?

By the way, how many elementary transpositions at most do you need
to express a permutation?

Can you do better than $n-1$ generators?
\end{problem}

\section{Groups}


\subsection{Definitions and examples}

The notation $[A,\bullet]$ denote a set $A$ together with an operation
$\bullet$.\char`\"{}

\begin{problem}
Is there anything in common between $[S_{n},\bullet]$ and $[\Z\,+]$.
\end{problem}
%

%

%

%

%

%

%%

\begin{defn*}
Let $A$ be a set with an operation $\bullet$
\end{defn*}
\begin{itemize}
\item The operation $\bullet$ is \emph{associative} if:\[
(\forall x)(\forall y)(\forall z)\textrm{ }x\bullet(y\bullet z)=(x\bullet y)\bullet z\]

\item The operation $\bullet$ is \emph{commutative} if:\[
(\forall x)(\forall y)\textrm{ }x\bullet y=y\bullet x\]

\item $i\in A$ is an \emph{identity element} if:\[
(\forall x)\textrm{ }x\bullet i=i\bullet x=x\]

\item Assume $[A,\bullet]$ has an identity element $i$. Then $y\in A$
is an inverse for $x\in A$ if\[
y\bullet x=x\bullet y=i\]

\end{itemize}
What are the properties of $[\Z,+]$?

%

%

%

%

%

%

%

%%

\begin{itemize}
\item $+$ associative;
\item $+$is commutative;
\item $0$ is an identity element;
\item If $x$ is an integer, then$-x$ is an inverse for $x$.
\end{itemize}
What are the properties of $[\R^{*},\cdot]$?

%

%

%

%

%

%%

Those structures have many common properties.

\begin{defn*}
$[G,\bullet]$ is a \emph{group} if $G$ is a non empty set, and $\bullet$is
a binary operation on $G$ such that:
\begin{enumerate}
\item $\bullet$ is associative
\item an identity element exists (in $G$).
\item each element of $G$ has an inverse (in $G$) with respect to $\bullet$.
\end{enumerate}
If the operation $\bullet$is commutative, $G$ is called a \emph{commutative
group}.
\end{defn*}
\begin{xca}
Which of the following are groups ? 
\begin{enumerate}
\item $[\Z,+]$
\item $[\N,+]$ 
\item $[\Z,-]$
\item $[\{ true,false\},\wedge\}$
\item $[\R,+]$
\item $[\R,\cdot]$
\item $[S_{n},\bullet]$
\item $[n\Z,+]$ 
\end{enumerate}
\end{xca}
What's the point ?

\begin{itemize}
\item Many structures, coming in particular from arithmetics, are groups.
\item If you prove a property for groups in general, you have proved this
property for all of those structures.
\item Group theory is a vast field, and there are hundreds of theorems about
groups waiting for you to apply them on your favorite structure.
\item Basic tool to study the Rubicks Cube.
\end{itemize}

\subsection{Just some examples of results and questions about groups}

\begin{thm*}
The identity of a group is unique.

The inverse of an element is unique.

The equations $a\bullet x=b$ and $x\bullet a=b$ have a unique solution.

The inverse of a product can be computed by $(x\bullet y)^{-1}=y^{-1}\bullet x^{-1}$.
\end{thm*}
\begin{defn*}
Let $[G,\bullet]$ be a group, and $A\subseteq G$.

Then $[A,\bullet]$ is a \emph{subgroup} of $[G,\bullet]$ if $[A,\bullet]$
itself is a group.
\end{defn*}
\begin{thm*}
The size of a subgroup divides the size of the group.
\end{thm*}
\begin{problem}
Common problems about a group:
\end{problem}
\begin{itemize}
\item Find a minimal set of generators
\item Express an element of the group as product of generators
\item Efficient computations
\item Find all subgroups
\item Are two groups structurally the same (are they isomorphic?)
\end{itemize}
For playing with groups, there is a very nice program: 

\url{http://www-history.mcs.st-and.ac.uk/~gap/} 


\subsection{Groups and Symmetries}

One common use of groups if for the study of problems with symmetries.

\begin{example*}
Computing the temperature in a house with a heater in the middle.
\end{example*}
\begin{itemize}
\item Case 1: the house has a random shape;
\item Case 2: the house is round;
\item Case 3: the house is square.
\end{itemize}
Most of the time, a problem with symmetry has a symmetric solution.

Using this can save a LOT of time.

Problem: finding the orbits

The set of all symmetries is a group, so group theory can help you.


\subsection{Groups and isomorphy of graph}

\begin{defn*}
The two following structures are labelled graphs:
\end{defn*}
\begin{center}\includegraphics[%
  height=5cm]{graph-0000111110} $\textrm{ }$\includegraphics[%
  height=5cm]{graph-0010011101}\end{center}

If you exchange the nodes $3$ and $4$ of the first graph, you get
the second.

The group $S_{n}$ \emph{acts} on graphs on $n$ nodes.

Structurally, except for the numbering, there is no difference between
them:

They are \emph{isomorphic}.

\begin{problem}
Testing if two graphs are isomorphic.
\end{problem}
This is an important but very difficult problem.

\begin{defn*}
The following structure is an \emph{unlabelled graph}:

\vspace{0.3cm}
\begin{center}\includegraphics[%
  height=5cm]{ugraph-0010011101}\end{center}
\vspace{0.3cm}

It can be defined as an equivalence class of labelled graphs.
\end{defn*}
\begin{problem}
How many labelled graphs on $n$ nodes ?

How many unlabelled graphs on $n$ nodes ?
\end{problem}
Group theory provides a tool (Pólya enumeration) for this.


\section{Conclusion}

\begin{itemize}
\item Groups are an abstract model for many common structures
\item Results about groups apply to all of those structures
\item Groups are a powerful tool to study problems with symmetries
\item Groups often occurs when dealing with unlabeled structures
\end{itemize}

\end{document}
