Next: Symmetries Up: MT2002 Algebra Previous: Modular arithmetic Contents

Permutations

In Section 1 we considered the set 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, 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 is a finite set of size , then without loss of generality we may take $X=\{ 1,\ldots,n\}$ . In this case we denote by and by . 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

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: Symmetries Up: MT2002 Algebra Previous: Modular arithmetic Contents

Edmund F Robertson

11 September 2006