Basic definitions and facts

Syllabus: In this section we give the precise definition of an abstract group and recall some basic examples. We also recall basic properties of permutations and do first steps in computing with groups, using MAPLE.

Notation: Let $\Omega$ be a set and $\Omega^\Omega$ the set of functions from $\Omega$ to itself. We will use the convention that such a function f is written to the right of its argument, i.e. $\omega\mapsto (\omega)f$. The main advantage of this notation is, that composition of functions is written in the `right order', i.e. $f\circ g$ is the function in which first f and then g is applied. This coincides for example with the way composition of permutations is implemented in MAPLE.

Let $\Sigma_\Omega \subseteq \Omega^\Omega$ be the subset of bijective functions. Then for $\sigma, \tau\in \Sigma_\Omega$, the composition $\sigma\circ \tau$ is again an element in $\Sigma_\Omega$. One says that $\Sigma_\Omega$ is closed under composition. Moreover this `product' is associative, i.e.

$$\forall \sigma,\tau,\delta\in \Sigma_\Omega:\ \sigma\circ (\tau\circ \delta) = (\sigma\circ\tau)\circ \delta$$

and there is a unique neutral element $id_\Omega\in \Sigma_\Omega$ satisfying

$$\sigma\circ id_\Omega = id_\Omega\circ \sigma = \sigma,\ \forall\sigma\in \Sigma_\Omega.$$

The most distinguished property of bijective functions is their invertibility: for each $\sigma\in \Sigma_\Omega$ there is a unique inverse $\sigma^{-1}\in \Sigma_\Omega$ satisfying

$$\sigma^{-1}\circ \sigma = \sigma\circ \sigma^{-1} = id_\Omega.$$

The mathematical notion of a group is a straightforward generalization of this:

Definition 1.2.1   A set G is called a group if there is a `multiplication'

$$\cdot\ :\ G\times G \to G,\ (h,g)\mapsto h\cdot g = hg$$

satisfying the following axioms:
(i): h(gf) = (hg)f for any $f,g,h\in G$ (associative law).
(ii): There is a unique neutral element $e\in G$ with $g\ e = e\ g =g$ for all $g\in G$.
(iii): For each $g\in G$ there is a unique `two sided inverse' $g^{-1}\in G$ such that $g\ g^{-1} = g^{-1}\ g = e$.

If moreover $g\ h = h\ g$ for any $h,g\in G$, one calls G a   commutative or   abelian group. If the set G is finite, one says that G is a   finite group of order |G|.

We have seen, that the set $\Sigma_\Omega$ together with the composition is a group, which is called the symmetric group on $\Omega$. If $\Omega$ is a finite set of order $\vert\Omega\vert=n$ then $\Sigma_\Omega$ is a finite group of order

$$\vert\Sigma_\Omega\vert = n! := n(n-1)(n-2)\cdots 2\cdot 1.$$

The cardinality $n=\vert\Omega\vert$ is called the degree of $\Sigma_\Omega$. Notice that for n>2 there are elements $\sigma, \tau\in \Sigma_\Omega$ such that $\sigma\circ \tau \ne \tau\circ \sigma$ and $\Sigma_\Omega$ is not an abelian group.

Examples 1.2.2  

1.

The set $\mathbb{Z}$ with $a\circ b := a+b$, e=0 and a^-1:= -a for each $a\in \mathbb{Z}$ is an infinite abelian group.

2.

The set $\mathbb{N}$ with $a\circ b := a+b$ is not a group; there are neither neutral element nor inverse elements in $\mathbb{N}$.

3.

Let $n\in \mathbb{Z}$; the set $\mathbb{Z} _n:= \{ a+n\mathbb{Z}\ \vert\ a\in \mathbb{Z}\}$ with

$$(a + n\mathbb{Z} ) + (b+ n\mathbb{Z} ) := (a + b) + n\mathbb{Z}$$

(arithmetic modulo n) is a finite abelian group of order n.

4.

The set $\mathbb{Q}\backslash \{0\}$ of nonzero rational numbers, with $m/n \circ r/s := mr/ns$, e:= 1 and (m/n)^-1:= n/m is an infinite abelian group.

5.

Let p be a prime number; the set $\mathbb{Z} _p\backslash \{0 + p\mathbb{Z}\}$ with $(a+p\mathbb{Z} )\cdot (b+p\mathbb{Z} ) := (a\cdot b) + p\mathbb{Z}$ and $e:= (1) + p\mathbb{Z}$ is a finite abelian group of order p-1 (prove this!).

6.

The set $\{-1,1\}\times \mathbb{Z}$ with

$$(\epsilon, a)\circ (\delta,b):= (\epsilon\cdot \delta, \delta\cdot a+ b)$$

is an infinite group, which is not abelian. (check this!)

For small groups, one way to define the multiplication explicitly is, by writing down the full multiplication table:

$\circ$	g1	g2	$\cdots$	gi	$\cdots$
g1	g12	g1 g2	$\cdots$	g1 gi	$\cdots$
g2	g2 g1	g22	$\cdots$	g2 gi	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
gi	gi g1	gig2	$\cdots$	gi2	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

The following table defines the multiplication in $\Sigma_3$, with $\sigma:= (\ 1\mapsto 2,\ 2\mapsto 3,\ 3\mapsto 1) \in \Sigma_3$ and $\tau:= (\ 1\mapsto 2,\ 2\mapsto 1,\ 3\mapsto 3) \in \Sigma_3$.

$\circ$	id	$\sigma$	$\sigma^2$	$\tau$	$\tau\sigma$	$\tau\sigma^2$
id	id	$\sigma$	$\sigma^2$	$\tau$	$\tau\sigma$	$\tau\sigma^2$
$\sigma$	$\sigma$	$\sigma^2$	id	$\tau\sigma^2$	$\tau$	$\tau\sigma$
$\sigma^2$	$\sigma^2$	id	$\sigma$	$\tau\sigma$	$\tau\sigma^2$	$\tau$
$\tau$	$\tau$	$\tau\sigma$	$\tau\sigma^2$	id	$\sigma$	$\sigma^2$
$\tau\sigma$	$\tau\sigma$	$\tau\sigma^2$	$\tau$	$\sigma^2$	id	$\sigma$
$\tau\sigma^2$	$\tau\sigma^2$	$\tau$	$\tau\sigma$	$\sigma$	$\sigma^2$	id

Notice that the rows and similarly the columns in this table form six different permutations of the six elements in $\Sigma_3$ . This phenomenon will be explained later.

We look a little closer at the group $\Sigma_\Omega$ of bijections of the finite set $\Omega$. If $\vert\Omega\vert=n$, we can replace $\Omega$ by ${\bf n}:=\{1,2,\cdots,n\}$, because it does not matter how the elements of $\Omega$ are named. Usually the group $\Sigma_{\bf n}$ of bijections on n is denoted by $\Sigma_n$ and is called the `group of permutations on n letters'. An element $\sigma\in \Sigma_n$ is called a permutation of ${\bf n}$.

Permutations

A permutation $\sigma\in \Sigma_n$ can be written in form of a `matrix'

$$\left( \begin{array}{cccccc} 1& 2& 3& \dots& n-1& n\\ (1)\... ...3)\sigma& \dots& (n-1)\sigma& (n)\sigma\\ \end{array} \right).$$

A shorter notation is the list notation, where only the second line of the matrix is displayed:

$$\sigma = [ \ (1)\sigma, (2)\sigma, (3)\sigma, \dots, (n)\sigma\ ].$$

For example $\sigma = \left( \begin{array}{cccccc} 1&2&3&4&5\\ 2&3&5&1&4\\ \end{array} \right) \in \Sigma_5$ will be denoted by [2, 3, 5, 1, 4 ]. If $\tau = [3, 1, 2, 5, 4] \in \Sigma_5$, then $\sigma\ \tau = [1, 2, 4, 3, 5]$.

The most useful notation is the disjoint cycle notation:

$$(a_1\ a_2\ a_3\ \cdots\ a_i) (b_1\ b_2\ b_3\ \cdots\ b_j)\cdots$$

where a single cycle, as $(1\ 3\ 2\ 5) \in \Sigma_6$ for example, denotes the function

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

For example the element $\sigma=\left( \begin{array}{cccccccc} 1& 2& 3& 4& 5& 6& 7& 8\\ 3& 6& 2& 4& 5& 1& 8& 7\\ \end{array} \right)\in \Sigma_8$ can be written as the product of the following cycles $(1\ 3\ 2\ 6)(7\ 8)$. A cycle of length i is called an `i - cycle'. Notice that 1 - cycles (i.e. `fixed points' of the function) are not listed in the cycle notation.
Two elements $\sigma,\tau\in \Sigma_n$ are called `disjoint', if the sets of ciphers that occur in their cycle representations are disjoint. For example the elements $\sigma := (1 3 2) (4 5)$ and $\tau := (6 8) ( 7 9)$ are disjoint in $\Sigma_8$, but $\sigma$ and $\lambda := (1 4 6 8)(3 2)$ are not disjoint. If $\sigma$ and $\tau$ are disjoint and $\ell\in {\bf n}$ appears in a cycle of $\sigma$, then so does $(\ell)\sigma$ and $\ell$ as well as $(\ell)\sigma$ are fixed under $\tau$. Hence

$$(\ell)\sigma\circ \tau = (\ell)\sigma = (\ell)\tau\circ \sigma .$$

Similarly, if $\ell$ appears in $\tau$ we see that $(\ell)\sigma\circ \tau = (\ell)\tau\circ \sigma .$ In other words, if $\sigma$ and $\tau$ are disjoint, then $\sigma\tau=\tau\sigma$ and one says $\sigma$ and $\tau$ `commute'.

Examples 1.2.3   The cycle notation of all the elements in $\Sigma_3$ and $\Sigma_4$ is given as follows:

$$\Sigma_3 = \{ id, (12), (13), (23), (123), (132)\}.$$

$$\Sigma_4 =\{ id, (12), (13), (14), (23), (24), (34), (123), (124), (132), (134), (142), (143), (234), (243),$$

$$(12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432) \}$$

The representation of an element $\sigma\in \Sigma_n$ as a product of disjoint cycles is not unique. As we have seen, disjoint cycles commute, so changing their order in the product does not change $\sigma$. Moreover the i - cycle $(a_1\ a_2\ \cdots\ a_i)$ is the same as the i - cycle $(a_2\ a_3\ \cdots\ a_i\ a_1)$. But these are the only ambiguities, so up to permutation of cycles and `cyclic shifts' of ciphers inside the cycles, the representation of elements as a product of disjoint cycles is unique.

Example 1.2.4   The elements (123)(45) and $(54)(231)\in \Sigma_5$ are identical, whereas the element (132)(45) is different.

Before we continue, we want to see how we can use the computer algebra system MAPLE to carry out computations in $\Sigma_n$.

The standard way of representing permutations in MAPLE is, by using the list notation. MAPLE V also provides a package, called `group', which contains special functions, used in group theory. In particular we can use this package to convert list and disjoint cycle notations of permutations. Trying this out in a short MAPLE session could look as follows:

with(group);

lst:= [3,1,6,5,4,2];

convert(lst,disjcyc);

dc:=[[1,3,6,2],[4,5]];

convert(dc,permlist,6);

Notice that a product of disjoint cycles is given as a list of cycles. Notice also that in order to convert a product of disjoint cycles into the list notation, the degree has to be specified, to distinguish for example $(1,2,3) = [2,3,1] \in \Sigma_3$ from the element $(1,2,3) = [2,3,1,4,5]\in \Sigma_5$.

dc:=[[1,2,3]];

convert(dc,permlist);

Error, (in convert/permlist) invalid arguments

convert(dc,permlist,3);

convert(dc,permlist,5);

The group package of MAPLE also provides functions to multiply permutations that are given in disjoint cycle notation. If we want the permutations and their product in list notation, we have to convert them into disjoint cycle notation and then reconvert the product:

s:=[2,3,1,7,6,5,4]; t:=[3,7,4,6,5,1,2];



dcs:=convert(s,disjcyc); dct:=convert(t,disjcyc);



dcst:=mulperms(dcs,dct);

st:=convert(dcst,permlist,7);



Or in one line:

st:=convert(mulperms(convert(s,disjcyc), convert(t,disjcyc)),permlist,7);

Conjugation Two elements g,h in a group G are called conjugate if g = x^-1hx with some element $x\in G$. It is easy to see, that the relation on G:

` $g\sim h \iff$ g and h are conjugate'

is an equivalence relation (`reflexive, symmetric, transitive'). The corresponding equivalence classes are called the conjugacy classes of G and form a partition of the set G. Notice that $x^{-1}\cdot 1\cdot x = 1$, so the singleton $\{1\}$ always is a conjugacy class of G.

If $G = \Sigma_n$, conjugation can be described very easily: recall that every element $\sigma\in \Sigma_n$ can be written as a product of `disjoint cycles'. This decomposition is unique up to the order of the cycles and up to `cyclic permutations' of letters inside the cycles (e.g. $(1\ 2\ 3\ 4) (5\ 6) = (2\ 3\ 4\ 1) (6\ 5)$). If the decomposition of $\sigma$ involves c_i cycles of length i, one says $\sigma$ is of cycle type $(c_1,c_2,\cdots,c_n)$ or $1^{c_1}\ 2^{c_2} \cdots i^{c_i}\cdots$ with $\sum_i c_ii=n$. Notice that the $(c_1,c_2,\cdots,c_n)$ can also be interpreted as partitions of the number n i.e. different ways to write n as a sum of weakly increasing natural numbers

$$n = 1+ \cdots 1 + 2+ \cdots 2 + \cdots \cdots$$

where the number i appears c_i times. If $\pi = (a_1\ a_2\ \cdots \ a_i)$ is an i - cycle and $\sigma\in \Sigma_n$ an arbitrary element, then we have

$$\pi^\sigma:= \sigma^{-1}\circ \pi \circ \sigma = ( a_1^{\sigma}\ a_2^{\sigma}\ \cdots\ a_i^\sigma).$$

Hence it is easy to see that $\sigma,\tau\in G$ are conjugate if and only they are of the same cycle type, so the set of conjugacy classes in $\Sigma_n$ is in bijection with the set of partitions of the number n.

Example 1.2.5   Let x:= (123)(67), $g:=(17)(2356)\in \Sigma_7$, then the conjugate element x^-1gx can be determined by just applying the permutation x, viewed as a bijective function on $\{1,2,3,4,5,6,7\}$, to the letters inside the cycles of g. Hence

x^-1gx = (26)(3157).

Transpositions

A permutation $\tau\in \Sigma_n$ is called a transposition if it swaps two letters and keeps the other ones fixed, or in other words, if $\tau$ is a two - cycle. Let $a_1,a_2,\cdots, a_k$ denote n - pairwise different numbers in ${\bf n}:=\{1,2,\cdots,n\}$ and consider the k - cycle $(a_1,a_2,\cdots,a_k) \in \Sigma_n$. It is straightforward to check that

$$(a_1,a_2,\cdots,a_k) = (a_k,a_{k-1})\circ (a_{k-1},a_{k-2}) \circ \cdots \circ (a_2,a_1).$$

Since we already know that every permutation can be written as a product of disjoint cycles, we conclude:

every $\sigma\in \Sigma_n$ is a product of transpositions.

For example (1532)(476) = (23)(35)(51)(67)(74), or (123) = (32)(21) = (31)(32) = (31)(21)(31)(21). These examples show, that the representation of permutations as products of transpositions is far from being unique. What is unique though, is whether we need an even or an odd number of transpositions.

To see this let us first look at a second method to decompose a given permutation into a product of transpositions:

Let $\sigma\in \Sigma_n$ be a permutation. We call a pair $(i,j)\in {\bf n}\times {\bf n}$ a misplacement of $\sigma$, if i<j, but $(i)\sigma > (j)\sigma$ (see 1.1).

Thus $\tau:= (1532)(476) = \left( \begin{array}{ccccccc} 1& 2& 3& 4& 5& 6& 7\\ 5& 1& 2& 7& 3& 4& 6\\ \end{array} \right)\in \Sigma_7$ has the seven misplacements $(1,2),\ (1,3),\ (1,5),\ (1,6),\ (4,5),\ (4,6),\ (4,7)$.

Obviously the product $\tau \circ (5\ 1)$ has only six misplacements, $\tau \circ (5\ 1)\circ (5\ 2)$ has only five misplacements and so on. Finally we see that $\tau \circ (5\ 1)\circ (5\ 2)\circ (5\ 3)\circ (5\ 7)\circ (5\ 4)\circ (5\ 7)\circ (6\ 7)$ has no misplacement at all, therefore it is the identity. Thus we obtain

$$\tau = (6\ 7)\circ (5\ 7)\circ (5\ 4)\circ (5\ 7)\circ (5\ 3)\circ (5\ 2)\circ (5\ 1).$$

For $\sigma\in \Sigma_n$ we consider the product ${\rm sgn}(\sigma) := (-1)^{{\rm number\ of\ misplacements\ of\ }\sigma} =$

   $$\prod_{i,j\in {\bf n}, i<j}\ \frac{(i)\sigma-(j)\sigma}{i-j} ... ...-3}\cdots \frac{(i)\sigma-(j)\sigma}{i-j}\cdots \in \{\pm 1\}.$$

For example if $\sigma:= (1\ 3\ 2)$, then

$${\rm sgn}(\sigma) = \frac{3-1}{1-2}\cdot \frac{3-2}{1-3}\cdot \frac{1-2}{2-3} = (-1)(-1) = (-1),$$

$${\rm sgn}((1\ 3)) = \frac{3-2}{1-2}\cdot \frac{3-1}{1-3}\cdot \frac{2-1}{2-3}= (-1)^3 = -1.$$

Certainly ${\rm sgn}({\rm id}) = 1$, but more than that, the function ${\rm sgn}:\ \Sigma_n\to =\{\pm 1\}$ is multiplicative, i.e.

$${\rm sgn}(\sigma\circ \tau) = \prod_{i,j\in {\bf n}, i<j}\ \frac{(i)\sigma\tau-(j)\sigma\tau}{i-j}=$$

$$(\prod_{i,j\in {\bf n}, i<j}\ \frac{(i)\sigma-(j)\sigma}{i-j}... ...(i)\sigma-(j)\sigma}) = {\rm sgn}(\sigma)\cdot {\rm sgn}(\tau).$$

One says,

$${\rm sgn}:\ \Sigma_n\to =\{\pm 1\}$$

is a homomorphism of groups, where $\{\pm 1\}$ is considered as a finite group of order two.

As a consequence of this property of sgn, we have

$${\rm sgn}(\sigma^{-1} \tau \sigma) = ({\rm sgn}(\sigma))^{-1}... ...gma))^{-1} {\rm sgn}(\sigma) {\rm sgn}(\tau) = {\rm sgn}(\tau):$$

conjugate permutations have the same sign.

In particular every transposition has negative sign. Now, if $\sigma\in \Sigma_n$ is written as a product of transpositions in two different ways, then both products must yield the same sign, which is determined by $\sigma$. Hence both products must involve either an odd or an even number of transpositions.

An element $\sigma\in \Sigma_n$ with ${\rm sgn}(\sigma)=1$ is called an even permutation  , see 1.1.