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 permutationof 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 SA. 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 Sn.
Let us take a look at S3. 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 S3 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 S3 may be computed in the same fashion. The student should check the following table, which is the table of the group S3:
By a group of permutations we mean any group SA or Sn, 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 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: Ri ∘ Rj is the result of first performing Rj, and then Ri. For example, R1 ∘ R4 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 Dn, which may be found as we did here. These groups are called the dihedral groups. For example, the group of the square is D4, the group of the pentagon is D5, 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 S6
1 Consider the following permutations f, g, and h in S6:
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 S4 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 S6 generated by
3 Find a four-element abelian subgroup of S5. Write its table.
4 The subgroup of S5 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 SA, 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 SA 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 fn by fn(x) = x + n.
1 Prove: For each integer n, fn is a permutation of , that is, fn ∈ SR.
# 2 Prove that fn ∘ fm = fn + m and .
3 Let G = {fn : n ∈ }. Prove that G is a subgroup of SR.
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 fa,b as follows:
fa,b (x) = ax + b
1 Prove that fa, b is a permutation of , that is, fa,b ∈ S.
2 Prove that fa,b ∘ fc,d = fac, ad + b.
# 3 Prove that .
4 Let G = {fa,b : a ∈ , b ∈ , a ≠ 0}. Show that G is a subgroup of SR.
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 = (x1 − x2)2 + (x3 − x4)2. It is unaltered when the subscripts undergo any of the following permutations:
For example, the first of these permutations replaces p by
(x2 − x1)2 + (x3 − x4)2
the second permutation replaces p by (x1 − x2)2 + (x4 − x3)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.
1p = x1x2 + x2x3
2p = (x1 − x2)(x2 − x3)(x1 − x3)
3p = x1x2 + x2x3 + x1x3
4p = (x1 − x2)(x3 − x4)
H. Properties of Permutations of a Set A
1 Let A be a set and a ∈ A. Let G be the subset of SA consisting of all the permutations f of A such that f(a) = a. Prove that G is a subgroup of SA.
# 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 SA which consists of all the permutations f of A which move only α finite number of elements of A. Prove that G is a subgroup of SA.
3 Let A be a finite set, and B a subset of A. Let G be the subset of SA consisting of all the permutations f of A such that f(x) ∈ B for every x ∈ B. Prove that G is a subgroup of SA.
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 k1, k2,..., kn.
(ii)In every clan ki, all the men must choose their wives from among the women of a specified clan kj. We symbolize this by writing w(ki) = kj.
(iii)Men from two different clans cannot marry women from the same clan. That is, if ki ≠ kj, then w(ki) ≠ w(kj).
(iv)All the children of a couple are assigned to some fixed clan. So if a man belongs to clan ki, all his children belong to a clan which we symbolize by c(ki).
(v)Children whose fathers belong to different clans must themselves be in different clans. That is, if ki ≠ kj, then c(ki) ≠ c(kj).
(vi)A man cannot marry a woman of his own clan. That is, w(ki) ≠ ki.
Now let K = {k1,k2,. . ., kn} 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 ki and kj in K, there is a permutation α in G such that α(ki) = kj
(viii)Rules of kinship apply uniformly to all clans. Thus, for any α and β in G, if α(kj) = β(kj) for some specific clan kj, it necessarily follows that α(ki) = β(ki) for every clan ki
Prove parts 1–3:
1 Let α ∈ G. If α(ki) = ki for any given ki, then α = ε.
2 Let a α G. There is a positive integer m ≤ n such that αm = ε.
[αm = α ∘ α ∘ ··· ∘ α (m factors of α). HINT: Consider α(k1), α2(k1), etc.]
3 The group G consists of exactly n permutations.
Explain parts 4–9.
4 If a person belongs to clan ki, that person’s father belongs to clan c−1(ki). If a woman belongs to clan kj, her husband belongs to clan w−1(kj).
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 ki, the son of his mother’s sister belongs to clan c ∘ w−1 ∘ w ∘ c−1(ki). Conclude that marriage between matrilateral parallel cousins (marriage between a woman and the son of her mother’s sister) is prohibited.
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.