Permutation Groups

    One-to-one and onto mappings from a set to itself are called permutations and the collection of all permutations on a set is a group (called a permutation group) under the operation of composition of mappings. In this topic, many examples are given to explain the importance of permutation groups when the underlying set is a finite set of counting numbers; and the matrix form and cycle notation of such permutations are detailed so as to fully explore the groups of permutations of finite sets of counting numbers (called symmetric groups). But it is important to realize that permutation groups, in general, can be collections of permutations of any type of set.

Definition (Permutations) A permutation of a nonempty set is a bijective mapping from to itself. The set of all permutations on is denoted by

    Under composition of mappings, is a group because compositions of bijective mappings are bijective, composition is an associative operation, bijective mappings are invertible, and the identity mapping is This group is sometimes denoted by

Definition (Permutation Groups) In general, any group whose elements are permutations, with composition as the operation, is a permutation group. When then the group is commonly denoted by  

    A permutation on assigns to each a value by (which is read as "α sends to " or as "under goes to ) or in arrow form Another way of specfiying a permutation is matrix form. For example, take the permutation on defined by and This permutation is written in an equivalent (matrix) form by



In general, if is a permutation that maps where is a permutation of , then

    Composition (multiplication) of permutations expressed in matrix form is carried out from right to left by going from top to bottom, then top to bottom. For example, let


then


Warning: some authors compose permutations from left to right.

Proposition (Symmetric Group)

    (i) The order of is
    
    (ii) If then is not Abelian.
    
    Proof. (i): Consider the matrix form of a permutation,



There are ways to fill in the first position, ways to fill in the second position, and so on until the last position will be determined to be the one remaining element of . The counting principle says the total number of ways this can be done is
    (ii):  If and are defined by
    


respectively. Then and so is not Abelian  for

    Introduced by Cauchy in 1815, cyclic notation is more compact than matrix notation and has some theoretical advantages in that certain important properties of permutations can be readily determined when cyclic notation is used. Let be a permutation of and start by choosing Then let   Eventually there will be an such that because the set is finite. We write



where means that that is; (called the first cycle) has not exhausted In that case we start with a new element, say not in the first cycle, to create a new cycle; that is and so on until there is some such that This new cycle will have no elements in common with the first cycle and we continue this process until all of is exhausted with cycles obtaining possible many cycles, and  



In this way we see that every permutation can be written as a succession of disjoint cycles. An example is,


and

Note that also,

Definition (Standard Form For Cyclic Notation) The standard form for the identity is The standard form for a cycle is where is the least of Other elements of are in standard form when, if then,  



where each cycle is in standard form, and  

Example (Symmetric Group of Order 6) Write out the Cayley table for the symmetric group using cyclic notation.  

Definition (Cycles and Transpositions) Two different cycles are disjoint if they have no elements in common. If is a subset of elements chosen from and is a permutation on given by   
    (i) if
    (ii) for and
Then is represented by and is called a k-cycle or a cycle of length . A 2-cycle is also called a transposition.

Proposition (Permutation Properties)
    (i) Every element of is a product of disjoint cycles.
    (ii) Every element of is a product of transpositions.
    (iii) Disjoint cycles commute.
    
    Proof. (i): The way to write a permutation as a product of disjoint cycles is as follows: let and then there is a smallest such that This yields the cycle Two such cycles are either equal or disjoint. Thus, is a product of disjoint cycles as required.
    (ii): The identity can be expressed as so it is a product of two cycles. Every permutation can be written in the form.  
    


A direct computation shows that this is the same as  



as required.
    (iii): For definiteness, let and be disjoint cycles and suppose that and are permutations on the set   
    


where the are the symbols left fixed by both and For the first case, if is one of the then so is and so, since fixes all Similiarily, Hence and agree for all A similiar argument show that and agree for all as well. For the last case, assume that is one of the Then since both and fix it follows,   



as desired.  

• print this page
• pages linking here
• related pages

Cite this as:
Permutation Groups
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/permutation-groups.html