“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 far-flung architectural structure composed of theorems which reveal insights into the reasons behind appearances 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 previously.) For example, on the 3×3 Rubik’s cube there are 9×6=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 post 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, …, n-1). Let swap(f)=e_f(1)+…+e_f(n-1). We call this the swapping number of the permutation f since it counts the number of times f swaps the inequality in i<i+1 to f(i)>f(i+1). If we plot a bar-graph 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 2×3 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 2×3 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 LEFT-TO-RIGHT. (This is of course in contrast to the right-to-left composition of functions.) When a possible ambiguity may arise, we call this type of composition “composition as permutations” or “left-to-right composition”. When f=g then we write ff as f^2. In general, we write the n-fold 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 permutation.)
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 determine 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 ij-th 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 2×3 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),
for some r l<= n, denotes that 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 and 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^(r-1)(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 (unique) disjoint cyclic permutations.
This product is called a cycle decomposition of f. Except for the claim of uniqueness, this theorem is proven below.
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 2×2 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.
Yet Another Mathblog 