14 1. INTRODUCTION
matrices
0
@
1 0 0
0 1 0
0 0 1
1
A
;
0
@
0 1 0
1 0 0
0 0 1
1
A
;
0
@
0 0 1
0 1 0
1 0 0
1
A
;
0
@
1 0 0
0 0 1
0 1 0
1
A
;
0
@
0 1 0
0 0 1
1 0 0
1
A
; and
0
@
0 0 1
1 0 0
0 1 0
1
A
: (1.8)
ey form the symmetric group S
3
. Above, the element
1 0 0
0 1 0
0 0 1
is the trivial permutation
which maps each object to itself. In other words, by this permutation, no object is “moved.” is
element is the identity element i of the group. Its matrix representation is a diagonal matrix,
with exclusively 1’s in the diagonal: the 3 3 unit matrix.
1.8 A PERMUTATION DECOMPOSITION
If n is not prime, a powerful permutation decomposition exists [9, 12]. Let n be an integer,
in other words, the number of objects in the set f1,2,…,ng. Let p be a divisor of n, that is,
we have n D pq, with both p and q integers (greater than 1). We arrange the n objects into
q rows, each of p objects, the arrangement being called a Young tableau [13]. We consider an
arbitrary permutation a of the n objects. Figure 1.1a shows the permutation a as a mapping in
the Young tableau for
n
D
35
,
p
D
7
, and
q
D
5
. e tableau consists of the five sets
f
1,2,…,7
g
,
f8,9,…,14g, …, and f29,30,…,35g, each of seven objects. We see here how 1 is mapped to 1,
how 2 is mapped to 2, how 3 is mapped to 23, and so on.
eorem 1.1 Each permutation a can be decomposed as
a D h
1
v h
2
; (1.9)
where both h
1
and h
2
only permute objects within rows of the Young tableau and where v only permutes
objects within columns of the tableau.
Figures 1.1b, 1.1c, and 1.1d show the permutations h
1
, v, and h
2
to be performed succes-
sively.
• e vertical permutation v (Figure 1.1c) is found as follows: the cycles of a are projected
onto columns, yielding one or more vertical cycles.
• e horizontal permutation h
1
(Figure 1.1b) merely consists of horizontal arrows which
map the arrow tails of vertical and oblique arrows in Figure 1.1a to the corresponding
arrow tails of Figure 1.1c. Subsequently, additional horizontal arrows are added in order
to form closed horizontal cycles.
1.8. A PERMUTATION DECOMPOSITION 15
(a)
(b) (c) (d)
Figure 1.1: Decomposition of (a) an arbitrary permutation of 35 objects into (b) a first “hori-
zontal” permutation, (c) a “vertical” permutation, and (d) a second “horizontal” permutation.
• Finally, the horizontal permutation h
2
(Figure 1.1d) simply equals v
1
h
1
1
a.
e fact that it is always possible to construct an appropriate vertical permutation v is a
consequence of Birkhoff ’s theorem [14, 15] on doubly stochastic matrices, more specifically the
integer case [16, 17] of Birkhoff ’s theorem.
We conclude: If an integer n can be factorized as p q, then any permutation of n objects
can be performed by applying, subsequently,
• q permutations, each of p objects,
• p permutations, each of q objects, and
• q permutations, each of p objects.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.