Part 1: Algebraic Preliminaries

Chapter 3: Permutations

In chapter 3 the concept of a permutation is explained and how they form groups.

Definition: Apermutationis a one-to-one map from a set to itself.

Example 1:

Given the set {1,2} the possible one-to-one maps ( permutations ) are:

1->1, 2->2 and

1->2, 2->1.

Example 2:

For sets of three elements there are 6 = 3! possible permutations.

If we put all the permutations of a set in a set by itself and add the composition of permutations as the operation then this set becomes a group. Permutation groups are among the most important objects in group theory because every finite group is a subgroup of some permutation group.

There are two possible ways of notation when it comes to permutations. Let's consider the set {1,2,3,4} which has 24 possible permutations.

The permutation 1->1, 2->2, 3->4 and 4->3 can be written as [1 2 4 3] and also as (1)(2)(3 4) or short (3 4) this is the so calledcycle notation. Thus (1 2 3) and [2 3 1] represent the same permutation. Clearly the cycle notation is more efficient, especially when considering permutations of large sets.

The composition of permutations means permuting one after the other. Unfortunately in some books it is done from left to right, in others from right to left.

Exercise 1:

Show that (ab)(cde)*(ae)(bc)(d)=(ac)(bde).

( I would solve it as follows: )

`Right hand side:`

A B C D E

_ D _ E B Apply (bde)

C D A E B Apply (ac)

Left hand side:

A B C D E

_ _ _ D _ Apply (d)

_ C B D _ Apply (bc)

E C B D A Apply (ae)

E C B D A

C D _ E _ Apply (cde)

C D A E B Apply (ab)

And it shows that LHS = RHS

Sets of permution form a group under composition because:

- composition leads to a new permutation ( closure )

- the neutral element is the do-nothing permutation, i.e. (1)(2)(3).

- every permutation has an inverse because it can be permuted back to the original positions.

- composition of permutations is associative.

Note that the composition of permutations is NOT ( always ) commutative.

To be continued with 4. Modular Arithmetic

Information

ReplyDeleteInformatics Advanced World collects and shares highly scalable Informatics Data and organizes it for good interpretation, simple and understandable presentation so that any one can easily analyze and spread such Information.