Permutations

 
 

Permutation

A #~{permutation} is a bijective mapping from a finite set to itself.

Let _ &theta. #: X -> X _ be a permutation on X, where X = \{ ~s_1, ~s_2, ... ~s_n \} , _ then this is related to a permutation _ &theta.#~' on \{ 1, 2, ... ~n \} , _ in the sense that _ ~s_~i&theta. = ~s_{~i&theta.#~'} . _ (Note that the exact permutation depends on the order of indexing the elements of X). _ So we only need to consider permutations on sets of the form \{ 1, ... ~n \} _{~n &in. &naturals.}. _ Dropping the prime ( #~' ), we can represent the original permutation on X by

matrix{ ~s_1 , ~s_2 , ... , ~s_~n / ~s_{1&theta.} , ~s_{2&theta.} , ... , ~s_{~n&theta.} } _ _ or _ _ matrix{ 1 , 2 , ... , ~n / {1&theta.} , {2&theta.} , ... , {~n&theta.} }

Examples of permutations on the set \{ 1, 2, 3 \} are:

&theta. _ = _ matrix{1,2,3/3,2,1} , _ _ &phi. _ = _ matrix{1,2,3/2,3,1}

Symmetric Group

The composition of two permutations is itself a permutation, in the above example:

&theta.&phi. _ = _ matrix{1,2,3/3,2,1} matrix{1,2,3/2,3,1} _ = _ matrix{1,2,3/1,3,2}

The set of permutations on the set \{ 1, ... ~n \} is a group under composition, known as the #~{symmetric group} on ~n elements, and is denoted S_~n.

Proof: _ Composition of (bijective) mappings is , the is the group identity, and the inverse of a permutation is just the mapping

Cycle

As we shall show, a permutation can be written as a product (i.e. composition) of cycles. A #~{cycle} on X is a permutation that can be represented by an ordered subset of X, in the sense that if _ A = \{ ~s_1 , ~s_2 , ... , s_~r \} &subseteq. X , _ then the permutation where

~s_~n &theta. _ = _ ~s_{~n+1} , _ _ ~n = 1 , ... , ~r - 1
~s_~r &theta. _ = _ ~s_1
~s &theta. _ = _ ~s , _ _ ~s &nin. A

is a cycle. We will represent this cycle by _ ( ~s_1 -> ~s_2 -> ... -> s_~r ) _ [ note that the full set X must also be specified ]. This representation is not unique, as the cycle can also be represented by _ ( ~s_~n -> ~s_{~n+1} -> ... ~s_~r -> ~s_1 -> ... -> s_~{~n{-}1} ) _ any ~n = 1, ... ~r.

A cycle with ~r elements is said to be a cycle of #~{length} ~r .

#{Examples}: _ let _ X = \{ 1 , 2 , 3 , 4 , 5 , 6 \}

( 1 -> 2 -> 3) _ _ represents the permutation _ _ matrix{1,2,3,4,5,6/2,3,1,4,5,6}

( 1 -> 3 -> 2) _ _ represents the permutation _ _ matrix{1,2,3,4,5,6/3,1,2,4,5,6}

Note that these two are ~{not} the same permutation, although the cycles have the same elements. Note also that although the representation is not unique, when specifying cycles on the set of the form \{ 1 , .... , ~n \}, it is usual to choose the least element in the cycle as the first element of the representation, i.e. we write ( 1 -> 2 -> 3 ) rather than ( 3 -> 1 -> 2 ) or ( 2 -> 3 -> 1 ). This effectively makes the representation unique.

Disjoint Cycle

The cycles _ &theta._1 , &theta._2 , ... , &theta._~q _ on a set X _ are said to be #~{disjoint} if

~x&theta._~i != ~x _ => _ ~x&theta._~j = ~x , _ ~j != ~i , _ _ _ &forall. ~x &in. X

i.e. if ~x is an element of the cycle &theta._~i , then it is not an element of any of the other cycles. A simpler way of expressing it is to say that the sets of elements ~{moved} by the cycles are disjoint.

So if _ X = \{ 1 , 2 , ... , 10 \} , _ then _ ( 1 -> 3 -> 7 ) and ( 2 -> 5 -> 4 ) are disjoint, while _ ( 1 -> 3 -> 7 ) and ( 2 -> 5 -> 3 ) are not.

If &theta. , &phi. are disjoint cycles, then _ &theta.&phi. _ = _ &phi.&theta.

For suppose _ ~x&theta. != ~x , _ then _ ~x&phi. = ~x _ (by definition of disjoint), and as ~x is moved by &theta., and therefore so is ~x&theta. , i.e. ( ~x&theta. )&phi. = ~x&theta. , _ so _

~x&theta.&phi. _ = _ ~x&theta. _ = _ ~x&phi.&theta.

Similar argument if _ ~x&phi. != ~x . _ If _ ~x&theta. = ~x _ and _ ~x&phi. = ~x , _ the result follows trivially.

Product of Disjoint Cycle

Not every permutation is a cycle, however we have the following result:

#{Theorem}: _ Every permutaion of a set X is a product of disjoint cycles

Proof: _ Let &theta. be a permutation of X. Consider the elements

1 , _ 1&theta. , _ 1&theta.^2 , _ 1&theta.^3 , _ ...

Since X is finite, these elements cannot all be distinct. Let _ 1&theta. ^~r _ be the first term in the sequence which has already appeared in the sequence. Then _ 1&theta. ^~r = 1 , _ for if _ 1&theta. ^~r = 1&theta. ^~q , _ 0 < ~q < ~r , _ then _ 1&theta. ^{~r{-}1} = 1&theta. ^{~q{-}1} _ since &theta. is injective, contradicting choice of ~r. _ Put _ &tau._1 _ = _ ( 1 -> 1&theta. -> ... -> 1&theta.^{~r - 1} ).

Now choose the least ~s in X not moved by &tau._1 , and apply the above argument to _ ~s , _ ~s&theta. , _ ~s&theta.^2 , _ ~s&theta.^3 , _ ... _ _ Let _ ~s&theta.^~m _ be the first repeated element, _ ~s&theta.^~m = ~s , _ put _ &tau._2 _ = _ ( ~s -> ~s&theta. -> ... -> ~s&theta.^{~m - 1} ).

&tau._1 and &tau._2 are disjoint. _ For if _ ~s&theta.^~i = 1&theta. ^~j , _ some integers ~i < ~r , ~j < ~m , _ then either

~j >= ~i , _ _ in which case _ _ ~s = ~s&theta.^~i&theta.^{-~i} = 1&theta.^{ ~j - ~i}, _ contradicting choice of ~s, as _ ~j - ~i < ~r , _ _ or

~j < ~i , _ _ in which case _ ~s&theta.^~i = 1&theta. ^{~r + ~j} , _ ~s = ~s&theta.^~i&theta.^{-~i} = 1&theta.^{ ~r + ~j - ~i}, _ contradicting choice of ~s, as _ ~r + ~j - ~i < ~r

Continuing, choose the least element in X not moved by &tau._1 or &tau._2. Since X is finite the process must stop, and we are left with a sequence _ &tau._1 , &tau._2 , ... , &tau._~k _ of disjoint cycles, and

&theta. _ = _ &tau._1 &tau._2 ... &tau._~k

This representation of &theta. is unique apart from the order of the cycles, as disjoint cycles are commutative.

#{Example}

&theta. _ = _ matrix{1,2,3,4,5,6,7,8/8,5,1,7,4,6,2,3} _ = _ (1 -> 8 -> 3) ( 2 -> 5 -> 4 -> 7 ) ( 6 )

Cycles of length 1 can be dropped as they are equal to &iota._X , _ so

&phi. _ = _ matrix{1,2,3,4,5,6,7,8,9/8,3,7,4,5,9,2,6,1} _ = _ (1 -> 8 -> 6 -> 9 ) ( 2 -> 3 -> 7 )

Order of Permutation

The order of a permutation is the least common multiplier of the lengths of its cycles, thus the order of _ (1 -> 3) ( 2 -> 4 -> 7 ) _ is 6, and the order of _ ( 2 -> 5 ) ( 3 -> 8 -> 6 -> 7 ) _ is 4.

Transposition

A #~{transposition} is a cycle of length 2.

#{Theorem}: _ Every permutation can be represented as a product of transpositions.

Any cycle _ ( ~a_1 -> ~a_2 -> ~a_3 -> ... -> ~a_~r ) _ = _ ( ~a_1 -> ~a_2 ) ( ~a_1 -> ~a_3 ) ... ( ~a_1 -> ~a_~r ) . _ So, as a permutation is the product of disjoint cycles, the theorem is proved.