2.2 Transformation and permutation groups

All groups in the above examples are abelian. The most common examples of noncommutative groups are found in a class called transformation groups. We recall from Section 1.4 that a transformation of a set X is a map $g:X\to X$ that is one-to-one and onto. The map $g$ then has an inverse $g^{-1}:X\to X$ such that $g^{-1}\circ g=g\circ g^{-1}={\mathrm{id}}_X$ Let the product of two transformations g and h be defined as their functional composition $gh=g\circ h$

$$(gh)(x)=g\circ h(x)=g(h(x)).$$

The set of all transformations of X forms a group, denoted Transf(X):

Closure: if g and h are transformations of X then so is $gh$ ;

Associative law: $f(gh)=(fg)h$ ;

Identity: $e={\mathrm{id}}_X\in \mathrm{Transf}(X);$

Inverse: $\mathrm{if}g$ is a transformation of X then so is $g^{-1}$

Closure follows from the fact that the composition of two transformations (invertible maps) results in another invertible map, since $(f\circ g{)}^{-1}=g^{-1}\circ f^{-1}$ . The associative law holds automatically for composition of maps, while the identity and inverse are trivial. By a transformation group of X is meant any subgroup of Transf(X).

IfX is a finite set ofcardinality n then the transformations ofX are called permutations of the elements ofX. The group ofpermutations of $X=\{1,2,\dots ,n\}$ is called the symmetric group of order n, denoted $S_n$ . Any subgroup of $S_n$ is called a permutation group. A permutation $\pi$ on n elements can be represented by the permutation symbol

$$\pi =\left(\begin{array}{cccc}1& 2& \dots & n\\ a_1& a_2& \dots & a_n\end{array}\right)$$

where $a_1=\pi (1),a_2=\pi (2)$ , etc. The same permutation can also be written as

$$\pi =\left(\begin{array}{cccc}{b}_1& b_2& \dots & b_n\\ c_1& c_2& \dots & c_n\end{array}\right)$$

where $b_1,b_2,\dots ,b_n$ are the numbers 1, $2,\dots ,n$ in an arbitrary order and $c_1=\pi (b_1),c_2=$ $\pi (b_2),\dots ,c_n=\pi (b_n)$ . For example, the permutation $\pi$ that interchanges the elements 2 and 4 from a four-element set can be written in several ways,

$$\pi =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 4& 3& 2\end{array}\right)=\left(\begin{array}{cccc}2& 3& 1& 4\\ 4& 3& 1& 2\end{array}\right)=\left(\begin{array}{cccc}4& 1& 2& 3\\ 2& 1& 4& 3\end{array}\right),\text{etc.}$$

In terms of permutation symbols, if

$$\sigma =\left(\begin{array}{cccc}1& 2& \dots & n\\ a_1& a_2& \dots & a_n\end{array}\right)\text{ and }\pi =\left(\begin{array}{cccc}{a}_1& a_2& \dots & a_n\\ b_1& b_2& \dots & b_n\end{array}\right)$$

then their product is the permutation $\pi \sigma =\pi \circ \sigma$ ,

$$\pi \sigma =\left(\begin{array}{cccc}1& 2& \dots & n\\ b_1& b_2& \dots & b_n\end{array}\right).$$

Note that this product involves first performing the permutation $\sigma$ followed by π, which is opposite to the order in which they are written; conventions can vary on this point. Since the product is a functional composition, the associative law is guaranteed. The identity permutation is

$${\mathrm{id}}_n=\left(\begin{array}{cccc}1& 2& \dots & n\\ 1& 2& \dots & n\end{array}\right),$$

while the inverse of any permutation is given by

$${\pi }^{-1}={\left(\begin{array}{cccc}1& 2& \dots & n\\ a_1& a_2& \dots & a_n\end{array}\right)}^{-1}=\left(\begin{array}{cccc}{a}_1& a_2& \dots & a_n\\ 1& 2& \dots & n\end{array}\right).$$

The symmetric group $S_n$ is a finite group of order $n!.!$ , the total number of ways n objects may be permuted. It is not abelian in general. For example, in $S_3$

$$\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)=\left(\begin{array}{ccc}2& 1& 3\\ 3& 1& 2\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$$

while

$$\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)=\left(\begin{array}{ccc}1& 3& 2\\ 2& 3& 1\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)=\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right).$$

A more compact notation for permutations is the cyclic notation. Begin with any element to be permuted, say $a_1$ . Let $a_2$ be the result of applying the permutation $\pi$ to $a_1$ , and let $a_3$ be the result of applying it to $a_2.$ , etc. Eventually the first element $a_1$ must reappear, say as $a_{m+1}=a_1$ . This defines a cycle, written $(a_1{a}_2\dots a_m)$ . If $m=n$ , then $\pi$ is said to be a cyclic permutation. Ifm $<n$ then take any element $b_1$ not appearing in the cycle generated by $a_1$ and create a new cycle $(b_1{b}_2\dots b_m)$ of successive images of $b_1$ under $\pi .$ . Continue until all the elements 1, 2, … , n are exhausted. The permutation π may be written as the product of its cycles; for example,

$$\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 4& 5& 3& 7& 2& 1& 6\end{array}\right)=(1476)(25)(3).$$

Note that it does not matter which element of a cycle is chosen as the first member, so that $(1476)=(7614)$ and $(25)=(52)$

Cycles of length 1 such as (3) merely signify that the permutation π leaves the element 3 unchanged. Nothing is lost if we totally ignore such 1-cycles from the notation, writing

$$(1476)(25)(3)=(1476)(25).$$

The order in which cycles that have no common elements is written is also immaterial,

$$(1476)(25)=(25)(1476).$$

Products ofpermutations are easily carried out by following the effect ofthe cycles on each element in succession, taken in order from right to left. For example,

$$(137)(542)(12)(3467)(146)=(1654)(23)(7)$$

follows from $146,6125,54,4671,\mathrm{etc}.$

Exercise

Express each permutation on 1, 2, 3 in cyclic notation and write out the $6\times 6$ multipli cation table for $S_3$

Cycles of length 2 are called interchanges. Every cycle can be written as a product of interchanges,

$$(a_1{a}_2{a}_3\dots a_n)=(a_2{a}_3)(a_3{a}_4)\dots (a_{n-1}{a}_n)(a_n{a}_1),$$

and since every permutation π is a product of cycles, it is in turn a product of interchanges. The representation of a permutation as a product of interchanges is not in general unique, but the number of interchanges needed is either always odd or always even. To prove this, consider the homogeneous polynomial

$$\begin{array}{c}f(x_1,x_2,\dots ,x_n)={\prod }_{i<j}(x_i-x_j)\\ =(x_1-x_2)(x_1-x_3)\dots (x_1-x_n)(x_2-x_3)\dots (x_{n-1}-x_n).\end{array}$$

If any pair of variables $x_i$ and $x_j$ are interchanged then the factor $(x_i-x_j)$ changes sign and the factor $(x_i-x_k)$ is interchanged with $(x_j-x_k)$ for all $k\ne i,j$ . When $k<i<j$ or $i<j<k$ neither factor changes sign in the latter process, while if $i<k<j$ each factor suffers a sign change and again there is no overall sign change in the product of these two factors. The net result of the interchange of ${\dot{\mathbf{x}}}_i$ and $x_j$ is a change of sign in the polynomia $f(x_1,x_2,\dots ,x_n)$ . Hence permutations may be called even or odd according to whether f is left unchanged, or changes its sign. In the first case they can be written as an even, and only an even, number of interchanges, while in the second case they can only be written as an odd number. This quality is called the parity of the permutation and the quantity

Figure 2.1 Symmetries of the square

$$(-1{)}^{\pi }=\{\begin{array}{ll}+1& \text{ if }\pi \text{ is even },\\ -1& \text{ if }\pi \text{ is odd },\end{array}$$

is called the sign of the permutation. Sometimes it is denoted sign $\pi$ .

Exercise

Show that

$$(-1{)}^{\pi \sigma }=(-1{)}^{\sigma \pi }=(-1{)}^{\pi }(-1{)}^{\sigma }.\text{\hspace{1em}(2.1)}$$

Example 2.7

In the Euclidean plane consider a square whose corners are labelled 1, 2, 3 and 4. The group of symmetries of the square consists of four rotations (clockwise by 0◦, 90◦, 180◦ and 270◦), denoted $R_0,R_1,R_2$ and $R_3$ respectively, and four reflections $S_1,S_2,S_3$ and $S_4$ about the axes in Fig. 2.1.

This group is not commutative since, for example, $R_1{S}_1=S_4\ne S_1{R}_1=S_3$ – remember, the rightmost operation is performed first in any such product! A good way to do these calculations is to treat each of the transformations as a permutation of the vertices; for example, in cyclic notation $R_1=(1234)$ $R_2=(13)(24)$ $S_1=(14)(23)$ , $S_3=(13)$ , etc. Thus the symmetry group ofthe square is a subgroup oforder 8 ofthe symmetric group $S_4$

Exercise

Show that the whole group can be generated by repeated applications of $R_1$ and $S_1$ .

Example 2.8

An important subgroup of $S_n$ is the set ofall even permutations, $(-1{)}^{\pi }=1$ known as the alternating group, denoted $A_n$ . The closure property, that the product of two even permutations is always even, follows immediately from Eq. (2.1). Furthermore, the identity permutation ${\mathrm{id}}_n$ is clearly even and the inverse of an even permutation π must be even since

$$1=(-1{)}^{{\mathrm{id}}_n}=(-1{)}^{\pi {\pi }^{-1}}=(-1{)}^{\pi }(-1{)}^{{\pi }^{-1}}=(-1{)}^{{\pi }^{-1}}.$$

Hence $A_n$ is a subgroup of $S_n$ . Its order is $n!/2$

Example 2.9

Let π be any permutation of1, 2, … , n. Since there are a total ofn! permutations of n objects, successive iterations ${\pi }^2,{\pi }^3,\dots$ . must eventually arrive at repetitions, say ${\pi }^k={\pi }^l$ , whence ${\pi }^{l-k}={\mathrm{id}}_n$ . The smallest m with the property ${\pi }^m={\mathrm{id}}_n$ is called the order of the permutation π. Any cycle of length k evidently has order $k,$ and since every permutation can be written as a product of cycles, the order of a permutation is the lowes common multiple of its cycles. For example, the order of (1 2 3)(4 5) is the lowest common multiple of 3 and 2, which is 6. The set of elements $\{{\mathrm{id}}_n,\pi ,{\pi }^2,\dots ,{\pi }^{m-1}={\pi }^{-1}\}$ form a subgroup of $S_n$ , called the subgroup generated by π. It is clearly a cyclic group.

Problems

Problem 2.1

Show that the only finite subgroup of the additive reals is the singleton 0 , while the only finite subgroups of the multiplicative reals are the sets 1 and $\{1,-1\}$

Find all finite subgroups of the multiplicative complex numbers $\dot{\mathbb{C}}.$

Problem 2.2

Write out the complete $8\times 8$ multiplication table for the group of symmetries of the square $D_4$ described in Example 2.7. Show that $R_2$ and $S_1$ generate an abelian subgroup and write out its multiplication table.

Problem 2.3

(a) Find the symmetries of the cube, Fig. 2.2(a), which keep the vertex 1 fixed. Write these symmetries as permutations of the vertices in cycle notation.

(b) Find the group of rotational symmetries of the regular tetrahedron depicted in Fig. 2.2(b).

(c) Do the same for the regular octahedron, Fig. 2.2(c).

(a)
Figure 2.2

(b)

(c)

Problem 2.4

Show that the multiplicative groups modulo a prime $G_7,G_{11},G_{17}$ and $G_{23}$ are cyclic. In each case find a generator of the group.

Problem 2.5

Show that the order of any cyclic subgroup of $S_n$ is a divisor of $n!$ .