Permutation groups

GROUP THEORY
The multiplication table for this set of six functions has all the necessary properties to show that they form a group. Further, if the symbols f1 , f2 , f3 , f4 , f5 , f6 are
replaced by I, A, B, C, D, E respectively the table becomes identical to table 28.8.
This justifies our earlier claim that this group of functions, with argument substitution as the law of combination, is isomorphic to the group of reflections and
rotations of an equilateral triangle.
28.4 Permutation groups
The operation of rearranging n distinct objects amongst themselves is called a
permutation of degree n, and since many symmetry operations on physical systems
can be viewed in that light, the properties of permutations are of interest. For
example, the symmetry operations on an equilateral triangle, to which we have
already given much attention, can be considered as the six possible rearrangements
of the marked corners of the triangle amongst three fixed points in space, much
as in the diagrams used to compute table 28.7. In the same way, the symmetry
operations on a cube can be viewed as a rearrangement of its corners amongst
eight points in space, albeit with many constraints, or, with fewer complications,
as a rearrangement of its body diagonals in space. The details will be left until
we review the possible finite groups more systematically.
The notations and conventions used in the literature to describe permutations
are very varied and can easily lead to confusion. We will try to avoid this by using
letters a, b, c, . . . (rather than numbers) for the objects that are rearranged by a
permutation and by adopting, before long, a ‘cycle notation’ for the permutations
themselves. It is worth emphasising that it is the permutations, i.e. the acts of
rearranging, and not the objects themselves (represented by letters) that form
the elements of permutation groups. The complete group of all permutations of
degree n is usually denoted by Sn or Σn . The number of possible permutations of
degree n is n!, and so this is the order of Sn .
Suppose the ordered set of six distinct objects {a b c d e f} is rearranged by
some process into {b e f a d c}; then we can represent this mathematically as
θ{a b c d e f} = {b e f a d c},
where θ is a permutation of degree 6. The permutation θ can be denoted by
[2 5 6 1 4 3], since the first object, a, is replaced by the second, b, the second
object, b, is replaced by the fifth, e, the third by the sixth, f, etc. The equation
can then be written more explicitly as
θ{a b c d e f} = [2 5 6 1 4 3]{a b c d e f} = {b e f a d c}.
If φ is a second permutation, also of degree 6, then the obvious interpretation of
the product φ • θ of the two permutations is
φ • θ{a b c d e f} = φ(θ{a b c d e f}).
1056
28.4 PERMUTATION GROUPS
Suppose that φ is the permutation [4 5 3 6 2 1]; then
φ • θ{a b c d e f} = [4 5 3 6 2 1][2 5 6 1 4 3]{a b c d e f}
= [4 5 3 6 2 1]{b e f a d c}
= {a d f c e b}
= [1 4 6 3 5 2]{a b c d e f}.
Written in terms of the permutation notation this result is
[4 5 3 6 2 1][2 5 6 1 4 3] = [1 4 6 3 5 2].
A concept that is very useful for working with permutations is that of decomposition into cycles. The cycle notation is most easily explained by example. For
the permutation θ given above:
the
the
the
the
1st object, a, has been replaced by the 2nd, b;
2nd object, b, has been replaced by the 5th, e;
5th object, e, has been replaced by the 4th, d;
4th object, d, has been replaced by the 1st, a.
This brings us back to the beginning of a closed cycle, which is conveniently
represented by the notation (1 2 5 4), in which the successive replacement
positions are enclosed, in sequence, in parentheses. Thus (1 2 5 4) means 2nd
→ 1st, 5th → 2nd, 4th → 5th, 1st → 4th. It should be noted that the object
initially in the first listed position replaces that in the final position indicated in
the bracket – here ‘a’ is put into the fourth position by the permutation. Clearly
the cycle (5 4 1 2), or any other that involved the same numbers in the same
relative order, would have exactly the same meaning and effect. The remaining
two objects, c and f, are interchanged by θ or, more formally, are rearranged
according to a cycle of length 2, a transposition, represented by (3 6). Thus the
complete representation (specification) of θ is
θ = (1 2 5 4)(3 6).
The positions of objects that are unaltered by a permutation are either placed by
themselves in a pair of parentheses or omitted altogether. The former is recommended as it helps to indicate how many objects are involved – important when
the object in the last position is unchanged, or the permutation is the identity,
which leaves all objects unaltered in position! Thus the identity permutation of
degree 6 is
I = (1)(2)(3)(4)(5)(6),
though in practice it is often shortened to (1).
It will be clear that the cycle representation is unique, to within the internal
absolute ordering of the numbers in each bracket as already noted, and that
1057
GROUP THEORY
each number appears once and only once in the representation of any particular
permutation.
The order of any permutation of degree n within the group Sn can be read off
from the cyclic representation and is given by the lowest common multiple (LCM)
of the lengths of the cycles. Thus I has order 1, as it must, and the permutation
θ discussed above has order 4 (the LCM of 4 and 2).
Expressed in cycle notation our second permutation φ is (3)(1 4 6)(2 5), and
the product φ • θ is calculated as
(3)(1 4 6)(2 5) • (1 2 5 4)(3 6){a b c d e f} = (3)(1 4 6)(2 5){b e f a d c}
= {a d f c e b}
= (1)(5)(2 4 3 6){a b c d e f}.
i.e. expressed as a relationship amongst the elements of the group of permutations
of degree 6 (not yet proved as a group, but reasonably anticipated), this result
reads
(3)(1 4 6)(2 5) • (1 2 5 4)(3 6) = (1)(5)(2 4 3 6).
We note, for practice, that φ has order 6 (the LCM of 1, 3, and 2) and that the
product φ • θ has order 4.
The number of elements in the group Sn of all permutations of degree n is
n! and clearly increases very rapidly as n increases. Fortunately, to illustrate the
essential features of permutation groups it is sufficient to consider the case n = 3,
which involves only six elements. They are as follows (with labelling which the
reader will by now recognise as anticipatory):
I = (1)(2)(3)
C = (1)(2 3)
A = (1 2 3) B = (1 3 2)
D = (3)(1 2) E = (2)(1 3)
It will be noted that A and B have order 3, whilst C, D and E have order 2. As
perhaps anticipated, their combination products are exactly those corresponding
to table 28.8, I, C, D and E being their own inverses. For example, putting in all
steps explicitly,
D • C{a b c} = (3)(1 2) • (1)(2 3){a b c}
= (3)(12){a c b}
= {c a b}
= (3 2 1){a b c}
= (1 3 2){a b c}
= B{a b c}.
In brief, the six permutations belonging to S3 form yet another non-Abelian group
isomorphic to the rotation–reflection symmetry group of an equilateral triangle.
1058