next up previous contents
Next: Symmetries Up: MT2002 Algebra Previous: Modular arithmetic   Contents


Permutations

In Section 1 we considered the set $T(X)$ of all mappings $X\longrightarrow X$. We saw there that the composition of mappings is associative, and that the identity mapping $\id$ is an identity for composition. However, $T(X)$ is not a group, since not every mapping has an inverse, as the next example shows.


\begin{ex}
Choose two arbitrary distinct elements $a,b\in X$,
and let $f\st X\lo...
...particular $g\circ f\neq \id$, and hence $f$\ does not have
an inverse.
\end{ex}

As in the previous section, we can hope that the subset of all mappings which do have inverses will form a group. So we want to find out which mappings have inverses. To this end we have to recall certain special kinds of mappings.


\begin{de}
Let $f\st X\longrightarrow Y$\ be a mapping.
We say that $f$\ is an {...
...m one-one correspondence}) if it is both a surjection
and an injection.
\end{de}


\begin{exs}
The mapping $f\st {\mathbb{Z}}\longrightarrow {\mathbb{Z}}_2$defined...
...Z}}\longrightarrow{\mathbb{Z}}$\ defined by
$f(x)=-x$\ is a bijection.
\end{exs}


\begin{exc}
Prove that the composition of two bijections is again a bijection.
\end{exc}


\begin{thm}
For a mapping $f\in T(X)$\ there exists a mapping
$g\in T(X)$\ such that $f\circ g=g\circ f=\id$if and only if $f$\ is a bijection.
\end{thm}


\begin{proof}
($\Rightarrow$)
Assume that $f\circ g=g\circ f=\id$. Then for ever...
...$. It is now a routine matter to check that
$f\circ g=g\circ f=\id$.
\end{proof}


\begin{exc}
Prove that the inverse of a bijection is again a bijection.
\end{exc}


\begin{thm}
The set $S(X)$\ of all bijections $X\longrightarrow X$\ is a group
under the composition of mappings.
\end{thm}


\begin{proof}
% latex2html id marker 332Closure follows from Exercise \ref{exc...
... inverses follows from Theorem \ref{thm19}
and Exercise \ref{exc18}.
\end{proof}


\begin{de}
The group $S(X)$\ is called the {\em symmetric group} on $X$.
Its elements are called {\em permutations}.
\end{de}

If $X$ is a finite set of size $n$, then without loss of generality we may take $X=\{ 1,\ldots,n\}$. In this case we denote $T(X)$ by $T_n$ and $S(X)$ by $S_n$. A mapping $f\in T_n$ can be conveniently written as a $2\times n$ array of originals and their images:

\begin{displaymath}
f=\left(\begin{array}{cccc}
1&2&\ldots&n\\ f(1)&f(2)&\ldots&f(n)\end{array}\right).
\end{displaymath}

It is easy to see whether such a mapping is a permutation or not: just check whether the sequence of images $f(1),f(2),\ldots,f(n)$ contains every element of $\{1,2,\ldots,n\}$ (and so contains it only once). In particular, we see that a mapping from $T_n$ which is surjective must also be injective, and that a mapping that is injective must also be surjective. It is also easy to find the inverse of a permutation written in this way: you just swap the rows (and re-order, if you are tidy!):

\begin{displaymath}
f^{-1}=
\left(\begin{array}{cccc}
f(1)&f(2)&\ldots&f(n)\\ 1&2&\ldots&n\end{array}\right).
\end{displaymath}


\begin{ex}
Consider the mappings
\begin{displaymath}
f=\left(\begin{array}{ccccc...
...well,
from right to left.)
We see that the group $S_5$\ is not abelian.
\end{ex}


\begin{exc}
Prove that the group $S_n$\ is abelian only for $n=1,2$.
\end{exc}


\begin{exc}
Prove that the order of $S_n$\ is $n!(=n\cdot (n-1)\cdot\ldots\cdot 2\cdot 1)$.
\end{exc}

Now we describe another useful way of writing down permutations.


\begin{de}
Let $i_1,i_2,\ldots, i_k$\ be $k$\ distinct elements from
$\{1,\ldots...
... $i_1$, and leaving all the other elements
of $\{ 1,\ldots,n\}$\ fixed.
\end{de}


\begin{ex}
In $S_5$\ we have
\begin{displaymath}
(2\ 4\ 5)=
\left(\begin{array}{ccccc}
1&2&3&4&5\\ 1&4&3&5&2
\end{array}\right).
\end{displaymath}\end{ex}


\begin{de}
Two cycles $(i_1\ i_2\ \ldots\ i_k)$\ and
$(j_1\ j_2\ \ldots \ j_l)$\...
...\em disjoint}
if $\{ i_1,\ldots,i_k\}\cap\{j_1,\ldots,j_l\}=\emptyset$.
\end{de}


\begin{thm}
Every permutation can be written as a composition
of disjoint cycles...
...position is unique up to
the order of cycles and presence of 1-cycles.
\end{thm}

The proof of the above theorem, though not difficult, requires some technical attention, and it would probably not give you deeper insight then a particular example:


\begin{ex}
Consider the following permutation
\begin{displaymath}
\left(\begin{a...
...}and also
\begin{displaymath}
f=(5\ 7\ 8)(3\ 6\ 2\ 1).
\end{displaymath}\end{ex}


\begin{re}
Note that although disjoint cycles commute,
arbitrary cycles do not necessarily do so (find an appropriate
example).
\end{re}

You should be able to multiply permutations written as products of cycles, without reverting them into the two-row format. As for finding inverses, the following is of help:

\begin{displaymath}
(i_1\ i_2\ \ldots\ i_k)^{-1}=
(i_k\ \ldots \ i_2\ i_1).
\end{displaymath}


\begin{ex}
\begin{eqnarray*}
&&
(1\ 2\ 3)(4\ 5)(1\ 5)(2\ 4)=(1\ 4\ 3)(2\ 5)\\
&...
...)(4\ 5))^{-1}=(4\ 5)^{-1}(1\ 2\ 3)^{-1}=(5\ 4)(3\ 2\ 1).
\end{eqnarray*}\end{ex}


next up previous contents
Next: Symmetries Up: MT2002 Algebra Previous: Modular arithmetic   Contents

Edmund F Robertson

11 September 2006