An Overview on Permutation Groups

A permutation of a set is defined for finite sets only. A permutation of a finite set is a bijective relation from itself to itself. A bijective relation refers to one-one mapping.

If the cardinal number (the total number of elements in a set) of a finite set is n, then n is also called the degree of permutation of the set. The permutation group of a set can be defined as a set containing all the possible permutations that can be created for the original set. If there are n numbers in the original set, then its cardinal number is also n, and the number of elements in its permutation group equals n!

Definition of Permutation Group

A permutation group of a set is another set which contains all possible permutations that can be created from the original set. A permutation of a set is the one-one onto mapping of the set to itself, that is, bijective mapping. Let us assume that a set B has the following elements {9,8,7,6,5}. A permutation of it can be formed by mapping each element of B with another element taken from B itself in a way that it is one-one fashion. For example:

{ 9,8,7,6,5} is a permutation of set B. The total number of permutations 9,7,6,5,8 possible for B is 5! As its cardinal number is 5 and it equals 30. In this case, n=5. Thus the number of permutations possible is 5!=30.

An identity permutation is a type of permutation in which every element of the set maps with itself. For example, let B={8,11,22,4,13}; the identity permutation of this set will be the set itself, that is , {8,11,22,4,13}. The identity permutation of every set is unique as there is only one single way for the set to map with itself. It is an important property of permutations and is often used in higher studies. 

Multiplication of Permutations

We will now learn about the multiplication of permutations. It is not similar to matrix multiplication or scalar multiplications, but the multiplication of permutations is very similar to the formation of composite functions. Recall that here, if f(x) and g(x) are two functions then the function f.g(x) is given by f(g(x)) or fog(x) and the function g.f(x) is given by g(f(x)) or gof(x). Let us multiply two permutations, A and B and see how it is done in an easy and simple manner. 

Let A={ 2 3 4 5 1} and B={2 3 4 5 1} are two permutations that we need to multiply

3 4 2 5 1 2 4 5 1 3

Then the product A.B={2 3 4 5 1} .{2 3 4 5 1} ={ 2 3 4 5 1}

 3 4 2 5 1 2 4 5 1 3 4 5 2 1 3

Let us try to look into what is happening here. Try to observe the pattern. We can see that in the permutation A 2 goes to 3 and in B 4 goes to 4; thus, in A.B 2 goes to 4. Similarly, in A 3 goes to 4 and in B 4 goes to 5 so in A.B 2 goes to 5. In A 4 goes to 2 and in B 2 goes to 2 so in A.B 4 goes to 2. In A 5 goes to 5 and in B 5 goes to 1 so in A.B 5 goes to 1 and finally in A 1 goes to 1 and in B 1 goes to 4 so in A.B 1 goes to 3.

Even and Odd Permutations

A permutation which can be formed using an odd number of transpositions is called an odd permutation. In contrast, a permutation formed by using an even number of permutations is known as an even permutation.

A look at the properties of even and odd permutations:

1) Given that p1 and p2 are two permutations of different sets or the same set such that both p1 and p2 are either even or odd, then the product of these permutations p1.p2 is even.

Proof

Case 1: Given that p1 and p2 are two permutations of the same set or two different sets such that both of them are even, then p1 and p2 are both results of 2a and 2b transpositions, respectively. This means that the product p1.p2 results from 2a+2b transpositions which is an even number, so the product p1.p2 is also even.

Case 2: Given that p1 and p2 are two permutations of the same set or two different sets such that both of them are odd, then p1 and p2 are both results of 2a+1 and 2b+1 transpositions, respectively, and thus their product p1.p2 is the result of 2(a+b+1) transpositions which is also an even number. Thus we can conclude that the product p1.p2 is also even.

2) If p1 and p2 are permutations such that only one out of p1 and p2 is odd, then the product p1.p2 is odd.

Proof-

Let us assume that only one of p1 or p2 is odd and thus is the result of 2m+1 transpositions while the other is the result of 2n transpositions. Thus the product p1.p2 results from 2m+2n+1 transpositions, which is an odd number. Hence the product p1.p2 is an odd permutation.

3) The identity permutation is always even.

Proof-

The identity permutation of a set can always be expressed as a product of two even permutations and thus, by the use of the first property, is always even.

4) Let p1 be an even permutation. The inverse of p1 will also be an even permutation.

Proof-

If p1 is an even permutation and p2 is its inverse permutation, then p1.p2=I is the identity permutation. Since p1 and I are both even so, by using property 1, we can conclude that the permutation p2 is also even.

5) Let p1 be an odd permutation, and then the inverse of p1 will also be an odd permutation.

Proof-

If p1 is an odd permutation and p2 is its inverse, then p1.p2=I is the identity permutation. Since p1 is odd and I is even, so by property 1, the permutation p2 is also an even permutation.

Conclusion

Permutations of a set are bijective mappings (one-one onto mappings)on the set by itself. If a set contains n elements, then we can say that the cardinal number of the set is n, and this number is also known as the degree of the permutation. The set of all the permutations of a set for which permutations are defined is called the permutation group of the set. If there are n numbers in a set, the number of elements in its permutation group equals n. Multiplication of permutations is very similar to the formation of composite functions. Recall that here, if f(x) and g(x) are two functions then f.g(x) is given by f(g(x)) and g.f(x) is given by g(f(x)). A permutation formed by using even transpositions is called an even permutation, and a permutation made by using odd transpositions is called an odd permutation.