## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 7. GROUPS OF PERMUTATIONS

In this chapter we continue our discussion of functions, but we confine our discussions to functions *from a set to itself*. In other words, we consider only functions *f* : *A* → *A* whose domain is a set *A* and whose range is in the same set *A*.

To begin with, we note that any two functions *f* and *g* (from *A* to *A*) are *equal* if and only if *f*(*x*) = *g*(*x*) for every element *x* in *A*.

If *f* and *g* are functions from *A* to *A*, their composite *f* ∘ *g* is also a function from *A* to *A*. We recall that it is the function defined by

[*f* ∘ *g*](*x*) = *f*(*g*(*x*)) *for every x in A* (1)

It is a very important fact that the *composition of functions is associative*. Thus, if *f*, *g*, and *h* are three functions from *A* to *A*, then

*f* ∘ (*g ∘ h*) = (*f ∘ g*) ∘ *h*

To prove that the functions *f* ∘ (*g* ∘ *h*) and (*f* ∘ *g*) ∘ *h* are equal, one must show that for every element *x* in *A*,

{*f* ∘ [*g* ∘ *h*]}(*x*) = {[*f* ∘ *g*] ∘ *h*}(*x*)

We get this by repeated use of __Equation (1)__:

By a *permutation*of a set *A* we mean a *bijective function from* *A* *to* *A*, that is, a one-to-one correspondence between *A* and itself. In elementary

algebra we learned to think of a permutation as a *rearrangement* of the elements of a set. Thus, for the set {1,2,3,4,5}, we may consider the rearrangement which changes (1,2,3,4,5) to (3,2,1,5,4); this rearrangement may be identified with the function

which is obviously a one-to-one correspondence between the set {1,2,3,4,5} and itself. It is clear, therefore, that there is no real difference between the new definition of permutation and the old. The new definition, however, is more general in a very useful way since it allows us to speak of permutations of sets *A* even when *A* has infinitely many elements.

In __Chapter 6__ we saw that the composite of any two bijective functions is a bijective function. Thus, *the composite of any two permutations of A is a permutation of A*. It follows that we may regard the operation ∘ of composition as *an operation on the set of all the permutations of A*. We have just seen that composition is an associative operation. Is there a neutral element for composition?

For any set *A*, the *identity function on A*, symbolized by *ε _{A}* or simply ε, is the function

*x*→

*x*which carries every element of

*A*to itself. That is, it is defined by

*ε*(*x*) = *x* for every element *x* ∈ *A*

It is easy to see that ε is a permutation of *A* (it is a one-to-one correspondence between *A* and itself); and if *f* is any other permutation of *A*, then

*f* ∘ *ε* = *f* and ε ∘ *f* = *f*

The first of these equations asserts that [*f* ∘ *ε*](*x*) = *f*(*x*) for every element *x* in *A*, which is quite obvious, since [*f* ∘ *ε*](*x*)= *f*(*ε*(*x*))= *f*(*x*). The second equation is proved analogously.

We saw in __Chapter 6__ that the inverse of any bijective function exists and is a bijective function. Thus, *the inverse of any permutation of A is a permutation of A*. Furthermore, if *f* is any permutation of *A* and *f*^{−}^{1} is its inverse, then

*f*^{−}^{1} ∘ *f*= *ε* and *f* ∘ *f*^{−}^{1} = *ε*

The first of these equations asserts that for any element *x* in *A*,

[*f*^{−}^{1} ∘ *f*](*x*) = *ε*(*x*)

that is, *f*^{−}^{1}(*f*(*x*)) = *x*:

This is obviously true, by the definition of the inverse of a function. The second equation is proved analogously.

Let us recapitulate: The operation ∘ of composition of functions qualifies as an operation on the set of all the permutations of *A*. This operation is associative. There is a permutation *ε* such that *ε* ∘ *f* = *f* and *f* ∘ *ε* = *f* for any permutation *f* of *A*. Finally, for every permutation *f* of *A* there is another permutation *f*^{−}^{1} of *A* such that *f* ∘ *f*^{−}^{1} = *ε* and *f*^{−}^{1} ∘ *f* = *ε*. Thus, *the set of all the permutations of A, with the operation ∘ of composition, is a group*.

For any set *A*, the group of all the permutations of *A* is called the *symmetric group on A*, and it is represented by the symbol *S _{A}*. For any positive integer

*n*, the symmetric group on the set {1, 2, 3,. . .,

*n*} is called the

*symmetric group on η elements*, and is denoted by

*S*.

_{n}Let us take a look at *S*_{3}. First, we list all the permutations of the set {1,2,3}:

This notation for functions was explained on page 57; for example,

is the function such that *β*(1) = 3, *β*(2) = 1, and *β*(3) = 2. A more graphic way of representing the same function would be

The operation on elements of *S*_{3} is composition. To find *α ∘ β*, we note that

Thus

Note that in *α* ∘ *β*, *β* is applied first and *α* next. A graphic way of representing this is

The other combinations of elements of *S*_{3} may be computed in the same fashion. The student should check the following table, which is the table of the group *S*_{3}:

By a *group of permutations* we mean any group *S _{A}* or

*S*, or any subgroup of one of these groups. Among the most interesting groups of permutations are the groups of symmetries of geometric figures. We will see how such groups arise by considering the

_{n}*group of symmetries of the square*.

We may think of a symmetry of the square as any way of moving a square to make it coincide with its former position. Every time we do this, vertices will coincide with vertices, so a symmetry is completely described by its effect on the vertices.

Let us number the vertices as in the following diagram:

The most obvious symmetries are obtained by rotating the square clockwise about its center *P*, through angles of 90°, 180°, and 270°, respectively. We indicate each symmetry as a permutation of the vertices; thus a clockwise rotation of 90° yields the symmetry

for this rotation carries vertex 1 to 2,2 to 3, 3 to 4, and 4 to 1. Rotations of 180° and 270° yield the following symmetries, respectively:

The remaining symmetries are flips of the square about its axes *A, B*, *C*, and *D:*

For example, when we flip the square about the axis *A*, vertices 1 and 3 stay put, but 2 and 4 change places; so we get the symmetry

In the same way, the other flips are

and

One last symmetry is the *identity*

which leaves the square as it was.

The operation on symmetries is composition: *R _{i}* ∘

*R*is the result of first performing

_{j}*R*, and then

_{j}*R*. For example,

_{i}*R*

_{1}∘

*R*

_{4}is the result of first flipping the square about its axis

*A*, then rotating it clockwise 90°:

Thus, the net effect is the same as if the square had been flipped about its axis *C*.

The eight symmetries of the square form a group under the operation ∘ of composition, called the *group of symmetries of the square*.

For every positive integer *n* ≥ 3, the regular polygon with *n* sides has a group of symmetries, symbolized by *D _{n}*, which may be found as we did here. These groups are called the

*dihedral groups*. For example, the group of the square is

*D*

_{4}, the group of the pentagon is

*D*

_{5}, and so on.

Every plane figure which exhibits regularities has a group of symmetries. For example, the following figure, has a group of symmetries consisting of two rotations (180° and 360°) and two flips about the indicated axes. Artificial as well as natural objects often have a surprising number of symmetries.

Far more complicated than the plane symmetries are the symmetries of objects in space. Modern-day crystallography and crystal physics, for example, rely very heavily on knowledge about groups of symmetries of three-dimensional shapes.

Groups of symmetry are widely employed also in the theory of electron structure and of molecular vibrations. In elementary particle physics, such groups have been used to predict the existence of certain elementary particles before they were found experimentally!

Symmetries and their groups arise everywhere in nature: in quantum physics, flower petals, cell division, the work habits of bees in the hive, snowflakes, music, and Romanesque cathedrals.

**EXERCISES**

**A. Computing Elements of S_{6}**

**1** Consider the following permutations *f*, *g*, and *h* in *S*_{6}:

Compute the following:

**2** *f* °(*g* ∘ *h*) =

**3** *g* ∘ *h*^{−}^{1} =

**4** *h* ∘ *g*^{−}^{1}° *f*^{−}^{1} =

**5** *g* ∘ *g* ∘ *g* =

**B. Examples of Groups of Permutations**

**1** Let *G* be the subset of *S*_{4} consisting of the permutations

Show that G is a group of permutations, and write its table:

**2** List the elements of the cyclic subgroup of *S*_{6} generated by

**3** Find a four-element abelian subgroup of *S*_{5}. Write its table.

**4** The subgroup of *S*_{5} generated by

has six elements. List them, then write the table of this group:

**C. Groups of Permutations of **

In each of the following, *A* is a subset of and *G* is a set of permutations of *A*. Show that *G* is a subgroup of *S _{A}*, and write the table of

*G*.

**1** *A* is the set of all *x* ∈ such that *x* ≠ 0,1. *G* = {*ε*, *f*, *g*}, where *f*(*x*) = 1 /(1 − *x*) and *g*(*x*) = (*x* − 1) /*x*.

**2** *A* is the set of all the nonzero real numbers. *G* = {*ε*, *f*, *g*, *h*}, where *f*(*x*) = 1/*x*, *g*(*x*) = −*x*, and *h*(*x*) = –1/*x*.

**3** *A* is the set of all the real numbers *x* ≠ 0, 1. *G* = {*ε*, *f*, *g*, *h*, *k*}, where *f*(*x*) = 1 − *x*, *g*(*x*) = 1/*x*, *h*(*x*) = 1/(1 − *x*), *j*(*x*) = (*x* − 1)/*x*, and *k*(*x*) = *x*/(*x* − 1).

**4** *A* is the set of all the real numbers *x* ≠ 0,1,2. *G* is the subgroup of *S _{A}* generated by

*f*(

*x*) = 2 −

*x*and

*g*(

*x*) = 2/

*x*. (

*G*has eight elements. List them, and write the table of

*G*.)

**† D. A Cyclic Group of Permutations**

For each integer *n*, define *f _{n}* by

*f*(

_{n}*x*) =

*x*+

*n*.

**1** Prove: For each integer *n, f _{n}* is a permutation of , that is,

*f*∈

_{n}*S*.

_{R}**# 2** Prove that

*f*∘

_{n}*f*=

_{m}*f*

_{n}_{ + m}and .

**3** Let *G* = {*f _{n}* :

*n*∈ }. Prove that

*G*is a subgroup of

*S*

_{R}.

**4** Prove that *G* is cyclic. (Indicate a generator of *G*.)

**† E. A Subgroup of S_{}**

For any pair of real numbers *a* ≠ 0 and *b*, define a function *f _{a,b}* as follows:

*f _{a,b}* (

*x*) =

*ax*+ b

**1** Prove that *f _{a, b}* is a permutation of , that is,

*f*∈

_{a,b}*S*

_{}.

**2** Prove *that f _{a,b}* ∘

*f*=

_{c,d}*f*

_{ac, ad}_{ + b}.

**# 3** Prove that .

**4** Let *G* = {*f _{a,b}* :

*a*∈ ,

*b*∈ ,

*a*≠ 0}. Show that

*G*is a subgroup of

*S*.

_{R}**F. Symmetries of Geometric Figures**

**1** Let *G* be the group of symmetries of the regular hexagon. List the elements of *G* (there are 12 of them), then write the table of *G*.

**2** Let *G* be the group of symmetries of the rectangle. List the elements of *G* (there are four of them), and write the table of *G*.

**3** List the symmetries of the letter **Z** and give the table of this group of symmetries. Do the same for the letters **V** and **H**.

**4** List the symmetries of the following shape, and give the table of their group.

(Assume that the three arms are of equal length, and the three central angles are equal.)

**G. Symmetries of Polynomials**

Consider the polynomial *p* = (*x*_{1} − *x*_{2})^{2} + (*x*_{3} − *x*_{4})^{2}. It is unaltered when the subscripts undergo any of the following permutations:

For example, the first of these permutations replaces *p* by

(*x*_{2} − *x*_{1})^{2} + (*x*_{3} − *x*_{4})^{2}

the second permutation replaces *p* by (*x*_{1} − *x*_{2})^{2} + (*x*_{4} − *x*_{3})^{2}; and so on. The *symmetries of a polynomial ρ* are all the permutations of the subscripts which leave *ρ* unchanged. They form a group of permutations.

List the symmetries of each of the following polynomials, and write their group table.

**1***p* = *x*_{1}*x*_{2} + *x*_{2}*x*_{3}

**2***p* = (*x*_{1} − *x*_{2})(*x*_{2} − *x*_{3})(*x*_{1} − *x*_{3})

**3***p* = *x*_{1}*x*_{2} + *x*_{2}*x*_{3} + *x*_{1}*x*_{3}

**4***p* = (*x*_{1} − *x*_{2})(*x*_{3} − *x*_{4})

**H. Properties of Permutations of a Set A**

**1** Let *A* be a set and *a* ∈ *A*. Let *G* be the subset of *S _{A}* consisting of all the permutations

*f*of

*A*such that

*f*(

*a*) =

*a*. Prove that

*G*is a subgroup of

*S*.

_{A}**# 2** If

*f*is a permutation of

*A*and

*a*∈

*A*, we say that

*f moves a*if

*f*(

*a*) ≠

*a*. Let

*A*be an infinite set, and let

*G*be the subset of

*S*which consists of all the permutations

_{A}*f*of

*A*which move

*only α finite number of elements*of

*A*. Prove that

*G*is a subgroup of

*S*.

_{A}**3** Let *A* be *a finite* set, and *B* a subset of *A*. Let *G* be the subset of *S _{A}* consisting of all the permutations

*f*of

*A*such that

*f*(

*x*) ∈

*B*for every

*x*∈

*B*. Prove that G is a subgroup of

*S*.

_{A}**4** Give an example to show that the conclusion of part 3 is not necessarily true if *A* is an infinite set.

**I. Algebra of Kinship Structures (Anthropology)**

Anthropologists have used groups of permutations to describe kinship systems in primitive societies. The algebraic model for kinship structures described here is adapted from *An Anatomy of Kinship* by H. C. White. The model is based on the following assumptions, which are widely supported by anthropological research:

(i)The entire population of the society is divided into *clans*. Every person belongs tö one, and only one, clan. Let us call the clans *k*_{1}, *k*_{2},..., *k _{n}*.

(ii)In every clan *k _{i}*, all the men must choose their wives from among the women of a specified clan

*k*. We symbolize this by writing

_{j}*w*(

*k*) =

_{i}*k*.

_{j}(iii)Men from two different clans cannot marry women from the same clan. That is, if *k _{i}* ≠

*k*, then

_{j}*w*(

*k*) ≠

_{i}*w*(

*k*).

_{j}(iv)All the children of a couple are assigned to some fixed clan. So if a man belongs to clan *k _{i}*, all his children belong to a clan which we symbolize by

*c*(

*k*).

_{i}(v)Children whose fathers belong to different clans must themselves be in different clans. That is, if *k _{i}* ≠

*k*, then

_{j}*c*(

*k*) ≠

_{i}*c*(

*k*).

_{j}(vi)A man cannot marry a woman of his own clan. That is, *w*(*k _{i}*) ≠

*k*.

_{i}Now let *K* = {*k*_{1},*k*_{2},. . ., *k _{n}*} be the set of all the distinct clans. By (ii),

*w*is a function from

*K*to

*K*, and by (iv),

*c*is a function from

*K*to

*K*. By (iii),

*w*is an injective function; hence (see

__Exercise F2__of

__Chapter 6__)

*w*is a permutation of

*K*. Likewise, by (v),

*c*is a permutation of

*K*.

Let *G* be the group of permutations generated by *c* and *w;* that is, *G* consists of *c*, *w*, *c*^{−}^{1}, *w*^{−}^{1}, and all possible composites which can be formed from these —for example, *c* ∘ *w* ∘ *w* ∘ *c*^{−}^{1} ∘ *w*^{−}^{1}. Clearly the identity function *ε* is in *G* since, for example, *ε* = *c* ∘ *c*^{−}^{1}. Here are two final assumptions:

(vii)Every person, in any clan, has a relation in every other clan. This means that for any *k _{i}* and

*k*in

_{j}*K*, there is a permutation

*α*in

*G*such that

*α*(

*k*) =

_{i}*k*

_{j}(viii)Rules of kinship apply uniformly to all clans. Thus, for any *α* and *β* in *G*, if *α*(*k _{j}*) =

*β*(

*k*) for some specific clan

_{j}*k*, it necessarily follows that

_{j}*α*(

*k*) =

_{i}*β*(

*k*) for every clan

_{i}*k*

_{i}Prove parts 1–3:

**1** Let *α* ∈ *G*. If *α*(*k _{i}*) =

*k*for any given

_{i}*k*, then

_{i}*α*= ε.

**2** Let *a* α *G*. There is a positive integer *m* ≤ *n* such that *α ^{m}* = ε.

[*α ^{m}* =

*α*∘

*α*∘ ··· ∘

*α*(

*m*factors of

*α*). HINT: Consider

*α*(

*k*

_{1}),

*α*

^{2}(

*k*

_{1}), etc.]

**3** The group *G* consists of exactly *n* permutations.

Explain parts 4–9.

**4** If a person belongs to clan *k _{i}*, that person’s father belongs to clan

*c*

^{−}

^{1}(

*k*). If a woman belongs to clan

_{i}*k*, her husband belongs to clan

_{j}*w*

^{−}

^{1}(

*k*).

_{j}**5** If any man is in the same clan as his son, then *c* = ε. If any woman is in the same clan as her son, then *c* = *w*.

**6** If a person belongs to clan *k _{i}*, the son of his mother’s sister belongs to clan

*c*∘

*w*

^{−}

^{1}∘

*w*∘

*c*

^{−}

^{1}(

*k*). Conclude that marriage between matrilateral parallel cousins (marriage between a woman and the son of her mother’s sister) is prohibited.

_{i}**7** Marriage between a man and the daughter of his father’s sister is prohibited.

**8** If matrilateral cross-cousins may marry (that is, a woman may marry the son of her mother’s brother), then *c* ∘ *w* = *w*^{−}^{1} ∘ *c*.

**9** If patrilateral cross-cousins may marry (a woman may marry the son of her father’s sister), then *c* and *w*^{−}^{1} commute.