12 1. INTRODUCTION
1.7 PERMUTATION GROUPS
Permutation groups take a special place in group theory because any finite group is isomorphic
to some permutation group. A permutation group consists of a set of permutations together with
the operation of cascading. Tables 1.7a and 1.7b show two different permutations of the eight
objects 1, 2, 3, 4, 5, 6, 7, and 8. Table 1.7c gives the permutation resulting from the cascading
of the previous two permutations. In order to deduce Table 1.7c from Tables 1.7a and 1.7b, we
proceed as follows: the first row of Table 1.7a tells “1 is mapped to 2,” whereas the second row
of Table 1.7b tells “2 is mapped to 3.” Together this yields “1 is mapped to 3,” to be filled in, in
the first row of Table 1.7c. We may equally well say: according to Table 1.7a, “2 is the image of
1,” whereas according to Table 1.7b, “3 is the image of 2.” Together this yields: “3 is the image
of the image of 1,” to be filled in, in the first row of Table 1.7c. Subsequently proceeding like
this for all eight rows of Table 1.7a yields the full Table 1.7c.
Permutations of n objects can be represented by permutation matrices, i.e., n n matrices
with all entries either equal to 0 or equal to 1 and all line sums equal to 1. By definition, a line
sum is either a row sum or a column sum. In a permutation matrix almost all entries are 0. In
each row, one and only one entry equals 1; in each column, one and only one entry equals 1. For
example, Table 1.7a is represented by the matrix
0
B
B
B
B
B
B
B
B
B
B
B
@
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
1
C
C
C
C
C
C
C
C
C
C
C
A
: (1.7)
Each row of the correspondence Table 1.7a is translated into a corresponding column of the
permutation matrix. For example, because 2 is mapped to 3, the second column has a 1 in the
third row. Table 1.7c, being the cascade of the Tables 1.7a and 1.7b, can be written as a matrix
product:
1.7. PERMUTATION GROUPS 13
0
B
B
B
B
B
B
@
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
1
C
C
C
C
C
C
A
0
B
B
B
B
B
B
@
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
1
C
C
C
C
C
C
A
D
0
B
B
B
B
B
B
@
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
1
C
C
C
C
C
C
A
:
Observe that, in the above matrix product, the matrix (1.7) representing the permutation ap-
plied first is written to the right of the matrix representing the permutation applied afterwards.
Indeed, mathematicians apply matrices from right to left. It is no surprise this sometimes leads
to confusion and/or errors.
Table 1.7: Correspondence table of three different permutations of 8 objects
A P A P A P
1
2
3
4
5
6
7
8
2
3
1
4
6
5
7
8
1
2
3
4
5
6
7
8
1
3
2
8
6
5
7
4
1
2
3
4
5
6
7
8
3
2
1
8
5
6
7
4
(a) (b) (c)
As an example of a permutation group, we consider the group of all permutations of three
objects 1, 2, and 3. It has order 3Š D 6. Its six elements are represented by the six permutation
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.