"What we have to learn to do, we learn by doing"
Aristotle, ETHICS
"Mathematics, springing up from the soil of basic human
experience with numbers and data and space and motion, builds
up a farflung architectural structure composed of theorems
which reveal insights into the reasons behind appearences and of
concepts which relate totally disparate concrete ideas."
Saunders MacLane,
AMER MATH MONTHLY, 1954
PERMUTATIONS
Let Tn = {1,2, ..., n} be the set of integers from 1 to some fixed
positive integer n. When n is fixed and there is no ambiguity
sometimes we will simply write T for Tn. A "permutation" of T is a
bijection from T to itself. (A "bijection" was defined on page 10.)
For example, on the 3x3 Rubik's cube there are 9x6=54 facets. If
you label them 1, 2, ..., 54 (in any way you like) then any move
of the Rubik's cube corresponds to a permutation of T54. In this
chapter we present some basic notation and properties of
permutations.
General notation: We may denote a permutation f : T> T by a
2xn array:
/ 1 2 ... n \
f <>  
\ f(1) f(2) ... f(n) /
Example: The "identity" permutation, denoted by I, is the
permutation which doesn't do anything:
/ 1 2 ... n \
I =  
\ 1 2 ... n /
Definition: Let e_f(i)=m if there are m j's less that i with f(j)>f(i+1),
and let e_f(i)=0 otherwise (for i = 1, 2, ..., n1). Let
swap(f)=e_f(1)+...+e_f(n1).
We call this the "swapping number" of the permutation f since it
counts the number of times f swaps the inequality in if(i+1). If we plot a bargraph of the function f then
swap(f) counts the number of times the bar at i is higher than the
bar at i+1, 1<=i<=n (i.e., it counts the number integers at which the
function is decreasing).
We call f "even" if swap(f) is even and we call f "odd" otherwise.
The number
sign(f) = (1)^(swap(f))
is called the "sign" of the permutation f.
Example: Let n=3, so T={1,2,3}. We may describe the permutation
f : T> T for which f(1)=2, f(2)=1, f(3) by a 2x3 array
[ 1 2 3 ]
[ 2 1 3 ]
or by a "crossing diagram":
1 1
\/
/\
2 2
3  3
The number of crosses in this diagram is the swapping number of f,
from which we can see that the permutation is odd.
Exercise: Express f : T > T given by f(1)=3, f(2)=1, f(3)=2,
as (a) a 2x3 array, (b) a crossing diagram. Find its swapping number
and sign.
Definition: Let f : T > T and g : T > T be two permutations. We
can compose them to get another permutation:
t > f(t) > g(f(t))
T > T > _ T
\ f g /
\_______________________/
fg
Notation: We shall follow standard convention and write our
compositions of permutations LEFTTORIGHT. (This is of
course in constrast to the righttoleft composition
of functions.) When a possible ambiguity may arise, we call
this type of composition "composition as permutations"
or "lefttoright composition".
When f=g then we write ff as f^2. In general, we write the
nfold composition f...f (n times) as f^n. Every permutation
f has the property that there is some integer N>0, which depends
on f, such that f^N = 1. (In other words, if you repeatedly
apply a permutation enough times you will eventually obtain
the identity permuation.)
Definition: The smallest integer N>0 such that f^N = 1 is
called the "order" of f.
Example: Let T = {1, 2, 3} and let
/ 1 2 3 \ / 1 2 3 \
f =   , g =   .
\ 2 1 3 / \ 3 1 2 /
We have
/ 1 2 3 \
fg =   .
\ 1 3 2 /
Exercise: Compute (a) fg and (b) the order of f and the
order of g, where
/ 1 2 3 \ / 1 2 3 \
(a) f =   , g =   .
\ 3 2 1 / \ 3 1 2 /
/ 1 2 3 \ / 1 2 3 \
(b) f =   , g =   .
\ 3 1 2 / \ 2 1 3 /
Exercise: If f, g, h are permutations of T, is
(fg)h=f(gh)? Explain why and be very precise and clear.
INVERSES
We can look at the graph of a function f : T > T and
determine
(a) if it is injective,
(b) if it is surjective,
(c) the inverse f^(1), if it exists.
Indeed, from the graph of f we can determine the image f(T)
and this determines if f is surjective or not. The inverse
exists only if f is injective (hence, in our case, surjective by
the last exercise in chapter 1). It's graph is determined
by "reflecting" the graph of f about the "diagonal, x=y".
Theorem: The following statements are equivalent:
(1) f : T > T is injective,
(2) f : T > T is surjective,
(3) f(T)=T.
proof: The equivalence of the first two statements is by the
exercise at the end of chapter 1. (2) is equivalent to (3),
by definition of surjectivity. QED
Example: The inverse of
[ 1 2 3 ]
[ 3 1 2 ]
is obtained by reflecting the graph
y

3  *

2  * graph of the
 permutation
1  * f : T > T

 x
 1 2 3


about the x=y line:
y

3  *

2  * graph of the
 permutation
1  * f^(1) : T > T

 x
 1 2 3


Exercise: Graph and deterine the inverses of the following
permutations:
/ 1 2 3 \
(a) f =   ,
\ 2 1 3 /
/ 1 2 3 4 \
(b) f =   ,
\ 2 3 4 1 /
/ 1 2 3 4 5 \
(c) f =   ,
\ 2 1 5 3 4 /
MATRIX NOTATION: There are two more commonly used ways of expressing
a permutation. The first is the "matrix notation": To a permutation
f : T > T, given by
[ 1 2 ... n ]
[ f(1) f(2) ... f(n) ]
we associate to it the matrix P(f) of 0's and 1's defined as follows:
the ijth entry of P(f) is 1 if j=f(i) and is 0 otherwise. A
matrix which has exactly one 1 per row and per column (as P(f)
does) is called a "permutation matrix".
Example: The matrix of the permutation f given by
[ 1 2 3 ]
[ 2 1 3 ]
is
[ 0 1 0 ]
P(f) = [ 1 0 0 ]
[ 0 0 1 ]
Note that matrix multiplication gives
[ 0 1 0 ][ 1 ] [ 2 ]
[ 1 0 0 ][ 2 ] = [ 1 ]
[ 0 0 1 ][ 3 ] [ 3 ]
from which we can recover the 2x3 array.
Theorem: If f : T > T is a permutation then
[ 1 ] [ f(1) ]
[ 2 ] [ f(2) ]
(a) P(f)[ . ] = [ . ].
[ . ] [ . ]
[ n ] [ f(n) ]
Furthermore, the inverse of the matrix of the permutation is the
matrix of the inverse of the permutation:
(b) P(f)^(1) = P(f^(1)).
The (relatively easy) proof of this Theorem will be omitted since
it will not be needed.
The matrix can be determined from the graph of the function
f : T > T as follows: in the nxn grid of integral points (x,y),
with x and y integers between 1 and n inclusive, fill in all the
plotted points with 1's and all the unplotted points with 0's
The resulting nxn array is the matrix P(f).
CYCLE NOTATION: The most common notation for a permutation is
probably the "cycle notation". The symbol
(a1 a2 ... ar) (some r less than or equal to n)
denotes the permutation f of T which is defined by
f(a1)=a2, f(a2)=a3, ... , f(ar)=a1,
and f(i)=i, if i is not equal to one of the a1, ..., ar. Such a
permutation is called "cyclic". The number r is called the "length"
of the cycle.
We call two such cycles (a1 a2 ... ar) and (b1 b2 ... bt)
"disjoint" if the sets {a1, a2, ..., ar} and {b1, b2, ..., bt}
are disjoint.
LEMMA: If f and g are disjoint cyclic permutations of T then fg=gf.
proof: This is clear since the permutations f and g of T affect
disjoint collections of integers, so the permutations may be
performed in either order. QED
LEMMA: The cyclic permutation (a1 a2 ... ar) has order r.
proof: Note f(a1)=a2, f^2(a1)=a3), ..., f^(r1)(a1)=ar,
f^r(a1)=a1, by definition of f. Likewise, for any i=1,...,r,
we have f^r(ai)=ai. QED
THEOREM: Every permutation f : T > T is the product of
disjoint cyclic permutations.
This product is called a "cycle decomposition" of f.
proof: Let f : T > T be a permutation. List all the elements
{c10=1, c11=f(1), c12=f^2(1), c13=f^3(1), ...},
(which must, of course, be finite in number but might also only
contain the single element c10=1). This is called the "orbit of 1
under f". Now list the elements in the "orbit of 2":
{c20=2, c21=f(2), c22=f^2(2), c23=f^3(2), ...},
and so on until we get to the "orbit of n":
{cn0=2, cn1=f(n), cn2=f^2(n), cn3=f^3(n), ... }.
If you pick any two of these n sets, they will
either be the same (up to ordering) or disjoint. Denote all
the distinct orbits which contain at least two elements
by O_1, ..., O_k. (It doesn't matter what order you write them in or
in what order you write the elements in each individual orbit.)
Suppose that
O_1 = {a{11}, ..., a{1,r1}} so O_1=r1,
O_2 = {a{21}, ..., a{2,r2}} so O_2=r2,
.
.
.
O_k = {a{k1}, ..., a{k,rk}} so O_k=rk.
In this case, r1 + r2 + ... + rk <= n, with equality if and only if
none of the orbits is a singleton. The "cycle notation" of f
is the expression
(a{11} a{12} ... a{1,r1})...(a{k1} a{k2} ... a{k,rk}).
QED
Example: The cycle notation for
[ 1 2 3 ]
[ 2 1 3 ]
is (1 2). The cycle notation for
[ 1 2 3 ]
[ 2 3 1 ]
is (1 2 3). The cycle notation for
[ 1 2 3 4 ]
[ 3 4 1 2 ]
is (1 3)(2 4)=(2 4)(1 3). The cycle notation for
[ 1 2 3 4 5 ]
[ 3 4 1 5 2 ]
is (1 3)(2 4 5)=(4 5 2)(1 3).
Exercise: Divide a square into 4 subsquares ("facets") and
label them 1, 2, 3, 4. For example,

  
 1  2 
  

  
 3  4 
  

Let r denote counterclockwise rotation by 90 degrees. Then,
as a permutation on the facets, r=(1 3 4 2). Let fx denote
reflection about the horizonal line dividing the square in
two, let fy denote reflection about the vertical line
dividing the square in two. Use the cycle notation to determine
the permutations of the facets
(a) r^2
(b) r^3,
(c) fx,
(d) fy,
(e) fx*r*fx,
(f) fx*fy.
Exercise: Label the 24 facets of the 2x2 Rubik's cube as
follows:
++
 1 2 
 u 
 3 4 
+++++
 5 6  9 10  13 14  17 18 
 l  f  r  b 
 7 8  11 12  15 16  19 20 
+++++
 21 22 
 d 
 23 24 
++
(You may want to xerox this page then cut this cube out and tape
it together for this exercise.) Let X denote rotation clockwise
by 90 degrees of the face labeled x, where x is one of r, l, f, b,
u, d (for example, if x=f then X=F). Use the cycle notation to determine
the permutations of the facets given by
(a) R,
(b) L,
(c) F,
(d) B,
(e) U,
(f) D.
LEMMA: A cyclic permutation is even if and only if the length of
its cycle is odd. A general permutation f : T > T is odd if
and only if the number of cycles of even length in its cycle
decomposition is odd.
We shall not prove this here. (For a proof, see Theorem 3.3 in
Gaglione [G], section 3.2.)
LEMMA: The order of a permutation is the least common multiple
(lcm) of the lengths r1, r2 , ..., rk of the disjoint cycles
in its cycle decomposition.
Example: The order of (1 3)(2 4) is 2. It is even.
The order of (1 3)(2 4 5) is 6. It is odd.