Idea and definition
As an example, we can write 1,2,3 in six ways:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
This is the idea.
A permutation re-arranges something, such as a,b,c,d,e being re-arranged to b, d, c, a, e.
This looks like re-ordering a set – but sets are not ordered. Instead a permutation is a mapping, relating each element in a set to another element in the same set. A permutation is a type of function.
Definition
A permutation is a bijective function from a set to itself.
For example the diagram shows a function on the set S={a,b,c} to S:
The function is one to one (not two to one), so is injective, and onto, so is surjective – so it is a bijection.
This permutation maps a→b, b→c and c→a
Two line notation
There are different ways of writing down a permutation.One is called ‘two line notation’.
For example,
This permutation is a function on the set {a,b,c}. It maps a to b, b to c, and c to a, as in the diagram above. We could also write this as
But it is usual to have the top line ‘in order’, so here, a,b,c
If we labelled a b and c as 1 2 and 3, we could write this as
This means the permutation maps 1 to 2, 2 to 3, and 3 to 1. The ‘2’ is just a label – it does not mean the 2nd element. After applying the permutation, ‘2’ is the first element. This might be just a way of labelling the set elements, or we might be talking about the natural numbers. Its still the same permutation.
If the permutation is
then p, q .. z cannot contain any duplicates. This is because the a..g are n distinct labels, and p..z is a re-arrangement of them, so again is a set of n distinct labels. Each of a..z must appear precisely once in the set p..z. A permutation is a bijection, so cannot be two to one. In other words two different things on the top line cannot map to the same thing twice on the bottom line. So,
for example, is not a permutation.
Permutations on Sn
Sn is the set {1,2,3..n} (or, it might be the symmetric group on that set – see later)
We talk about permutations on Sn. For example,
is a permutation on S3. We use 1,2,3.. simply as labels for the set elements.
Permutations as functions
A permutation is a bijective function from a set to itself.
A more familiar type of function is ℝ→ℝ, with a formula, such as f(x)=2x+1. Here the domain and image is the set ℝ. We apply the function to an element of ℝ, say 3, and get the element mapped to : 7. The formula, 2x+1, summarises what the set does, and we can use it to work out what any element of the domain maps to.
For a permutation it makes no difference what the domain is, except for how many elements are in it. For convenience we take it as Sn, with a label for each element (1,2,3..n). There is usually no formula like 2x+1 to summarise the function, so we need to show explicitly what each domain element maps to – like
shows that 1 maps to 5, 2 maps to 1 and so on. We apply the permutation to single elements of Sn, and get another element as the value mapped to. But we typically show the function in two line notation, displaying the effect of applying the function to every element of the domain.
Identity permutation
This is
In other words, it ‘does nothing’, mapping x to x for all x. This is often written as e.
Products of permutations
Permutations are functions. We combine two permutations, or ‘multiply’ them, by composing the functions – that is, apply one, then apply the other to the result.
For example, say p is
and q is
Suppose we apply p, then q. What do we get? p maps 1 to 2, and q maps 2 to 3. So the product maps 1 to 3. p maps 2 to 3, then q goes 3 to 2. So the product goes 2 to 2. And 3 to 1 then 1 to 1, so 3 to 1. So the product is
If we have a product a•b, which goes first? For functions the composition of f and g is written f•g and means first apply g, then f. But many people write permutation products in reverse. So p•q often means p first, then q. It makes a difference.
Inverse permutation
The inverse of a permutation p is a permutation q such that q(p(x)) = p(q(x)) = x for all x∈Sn.
A permutation is a bijective function, so it is invertible – the inverse function exists. Diagrammatically:
Permutation and inverse
For example the inverse of
is
which would normally be written
Powers of permutations
Suppose p is
Then p•p means applying it twice. That would take 1 to 2 then to 3, 2 to 3 then to 1, 3 to 1 then to 2. So
p•p =
. We can write this as p2.
Then p3=p•p•p =
The inverse of p can be written as p-1, so the ususal ‘law of indicies’ applies, and p p-1 =e.
Order of a permutation
As in the last section,
the identity. So the order of p is 3. Clearly p6 would also take us back to e.
Definition
The order of a permutation p is the smallest n such that pn = e, the identity permutation.
n! permutations on Sn
How many possible permutations of S = {1,2,3} are there? The 1 can map to 1, 2 or 3, For each of those possibilities, 2 can map to one of the 2 values left. Then the 1 can map just to the one remaining element. So the possibilities are [1 2 3], [1 3 2], [2 1 3], [2 3 1, [3 1 2], [3 2 1]. That is, 3 X 2 X 1 permutations. On a set with n elements, there are n x (n-1) x (n-2)..x 1 = n! Permutations.
Orbits and cycles
Think about the permutation:
Element 5 goes to 2, 2 goes to 1, 1 goes to 5. So 5 2 1 is the orbit of 5. We have 5 2 1 as a cycle – 1 goes back to 5 and the sequence repeats.
Definition
The orbit of a permutation element is the sequence of elements it is mapped to by successive applications of the permutation, until the sequence returns to the initial element
Definition
A cycle is a subset of a permutation whose elements are the orbit of any of its elements
3 goes to 4 and 4 to 3. So this is a two element cycle, called a transposition.
6 goes to 6 – a cycle just one element long. 6 is a fixed point.
Here are the possibilities of orbit shapes. First a cycle of length 4:
Or a transposition:
or a fixed point:
What is not possible is this:
That is, an orbit which leads to a cycle which does not return to the first element. This is because we have two elements (red and blue) which both map to the same element (green). That would mean the permutation (as a function) is two to one. But a permutation is a bijection, so must be injective – one to one.
Since it is a cycle, we can start anywhere. So (1,2,3) is the same as (2,3,1) and (3,1,2). It is usual to start lowest first – so (1,2,3).
Cycle notation
We can factor a permutation into cycles.
has a cycle 1 – 2 – 3, and another 4 – 5. These can be written as ( 1 2 3 ) and (4 5), and we can write this as (1 2 3)(4 5)
Another example –
can be written as 3 cycles – (1 6)(2 3 5)(4).
Permutations look different as cycles and in two line form. For example the cycle (1 4 2 3) in two lines is
We can write any permutation as a product of cycles, as follows:
Pick an element, write an ( and the element
Write down the orbit of the element until we get back to the starting element. Then close )
Pick another starting element and repeat
Until all elements chosen
For example
is written (a d) (b e ) (c).
Single element cycles might be omitted. So
might be written (1 2), and the (3) understood.
Since it is a cycle, the end wraps around to the beginning, so where we start writing does not matter. In other words, (1 2 3) is the same as (2 3 1)
Disjoint cycles
Cycles are disjoint if they have no elements in common (like disjoint sets). So (1 2 3) and (4 5) are disjoint sets.
Disjoint cycles commute. For example if we apply (1 2 3) to S5 we get (2 3 1 4 5), then apply (4 5) we get (2 3 1 5 4). And if we first apply (4 5) we get (1 2 3 5 4), then (1 2 3) get (2 3 1 5 4).
But cycles that are not disjoint will not commute. For example (1 2 3) and (3 4 5). If we do (1 2 3) first we get (2 3 1 4 5), then (3 4 5) get (2 4 1 5 3). But (3 4 5) first gives (1 2 4 5 3), then (1 2 3) gives (2 3 4 5 1).
The order of a permutation is the LCM of the orders of its cycles.
For example if the permutation is
We can decompose this into cycles (1 5 6) (2 7) (3 8 4 10 )(9). For example the first cycle says 1 goes to 5, 5 goes to 6, and 6 goes to 1.
The lengths of these cycles are 3, 2 and 4. The (1 5 6) set returns to ( 1 5 6) after 3 applications, and also after 6, 9, 12, 15 applications – multiples of 3. The (2 7) set returns after 2, 4, 6.. multiples of 2. And (3 8 4 10) after multiples of 4.
The whole set first returns after the first number which is a multiple of 3,2 and 4 – in other words the LCM of 3,2,4 = 12.
This is the order of this permutation.
Fixed points
In
the 2 maps to 2. This is a fixed point. In cycle notation we might write (1 3)(2). But it is common to miss out fixed points, and just write (1 3).
Cyclic permutation
A cyclic permutation has one cycle, and zero or more fixed points. For example
If a permutation has two or more cycles, it is not a cyclic permutation – for example
Some people do not allow any fixed points in a cyclic permutation.
One line notation
If the underlying set elements have a natural order, this is used as the top line equivalent, understood. So on {1,2,3}
is written (3 1 2)
Beware confusing the one line permutation (3 1 2) with the cycle (3 1 2), which is
Transpositions
Definition:
A transposition is a two element cycle
So a transposition is a simple swap. For example
where the permutation exchanges 1 and 2. As a cycle this would be simply (1 2)
Check the 6 permutations on S3:
| Single line notation | Cycle notation | Transpositions | Transposition count |
| (1 2 3) | 0 | ||
| (1 3 2) | ( 2 3) | (2 3) | 1 |
| (2 1 3) | (1 2) | (1 2) | 1 |
| (2 3 1) | (1 2 3) | (1 2)(1 3) | 2 |
| (3 1 2) | (1 3 2) | (1 3)(1 2) | 2 |
| (3 2 1) | (1 3) | (1 3) | 1 |
Theorem
Any permutation can be written as the product of transpositions.
For example for
– starting with 1 2 3 4 5, we can swap 1 and 5:
5 2 3 4 1
then swap 2 and 4
5 4 3 2 1
then 2 and 3
5 4 2 3 1
then 3 and 1
5 4 2 1 3
so the permutation is (1 5)(2 4)(2 3)(3 1). These are not disjoint, and this is left first.
Each transposition can put an element into its final place. So at most, n-1 transpositions are needed for n elements – if n-1 are correct, the nth must be correct.
Permutation factored into transpositions
We can factor any permutation into disjoint cycles, so we only need to write a cycle as transpositions.
If the cycle is (a b c d e .. n) as transpositions this is (a b)(a c)(a d)..(a n)
For example
As a cycle this is (1 5 3 2 4). As transpositions this is (1 5) (1 3)(1 2)(1 4):
| Transposition | Note | |||||
| 1 | 2 | 3 | 4 | 5 | ||
| (1 5) | 5 | 2 | 3 | 4 | 1 | 5 in final position |
| (1 3) | 5 | 2 | 1 | 4 | 3 | 3 in final position |
| (1 2) | 5 | 1 | 2 | 4 | 3 | |
| (1 4) | 5 | 4 | 2 | 1 | 3 | All correct |
Why does this work? Each transposition of the form (1 a) puts a in its final position, and no further transposition will refer or move a. We have 4 transpositions, placing 4 in the correct location, so the 5th must also be correct.
But this is a cycle, so is the same as (5 3 2 4 1), for example, with transposition sequence (5 3)(5 2)(5 4)(5 1):
| Transposition | Note | |||||
| 1 | 2 | 3 | 4 | 5 | ||
| (5 3) | 1 | 2 | 5 | 4 | 3 | 3 in final position |
| (5 2) | 1 | 5 | 2 | 4 | 3 | 2 in final position |
| (5 4) | 1 | 4 | 2 | 5 | 3 | |
| (5 1) | 5 | 4 | 2 | 1 | 3 | All correct |
The cycle has 5 elements, so can be written in 5 different ways (different starting points), so we can have 5 different transposition sequences. In particular, there are several possible transposition sequences.
Another method for the cycle (a b c d.. n) is (n..)..(d c)(c b)(b a).
For example the cycle (1 5 3 2 4) is (4 2)(2 3)(3 5)(5 1)
| Transposition | Note | |||||
| 1 | 2 | 3 | 4 | 5 | ||
| 4 2 | 1 | 4 | 3 | 2 | 5 | 4 in final position |
| 2 3 | 1 | 4 | 2 | 3 | 5 | 2 in final position |
| 3 5 | 1 | 4 | 2 | 5 | 3 | |
| 5 1 | 5 | 4 | 2 | 5 | 3 | All correct |
Odd and even permutations – parity
An even permutation can be decomposed to an even number of transpositions. An odd permutation has an odd number of transpositions. The parity of a permutation means whether it is odd or even.
For example
We start with 1 2 3 4 5 6, working from the left, and if an element is in the wrong place (compared with 3 2 5 6 4 1, swap it so it is.
At the left we have 1, and we want 3 – so swap 1 and 3 ( 3 2 1 4 5 6)
Next the 2 is already correct. The 1 is where 5 should be, so swap 1 and 5 ( 3 2 5 4 1 6 )
Next swap 4 and 6 ( 3 2 5 6 1 4 )
Finally swap 4 and 1 ( 3 2 5 6 4 1 )
so this is four transpositions, so it is an even permutation.
Permutation matrices
We can represent a permutation as a matrix. It is square, with all members 0 except for one 1 in each row and each column. For example
so the matrix corresponds to the permutation (2 3 4 1) in cycle notation.
A 1 on the leading diagonal is a fixed point, and a pair of 1s across the leading diagonal are transpositions, such as
Abstract Algebra 