Definition: The set of all permutations of a set S is denoted by Sym(S).
The set of all permutations of the set {1,2,...,n} is denoted by Sn
Proposition. If S is any nonempty set, then Sym(S) is a group under the operation of composition of functions.
Theorem. Every permutation in Sn can be written as a product of disjoint cycles. The cycles that appear in the product are unique.
Proposition. If a permutation in Sn is written as a product of disjoint cycles, then its order is the least common multiple of the lengths of its cycles.
Definition. Any subgroup of the symmetric group Sym(S) on a set S is called a permutation group or group of permutations.
Definition. A permutation is called even if it can be written as a product of an even number of transpositions, and odd if it can be written as a product of an odd number of transpositions.
Proposition. The set of all even permutations of Sn is a subgroup of Sn.
Definition. The set of all even permutations of Sn is called the alternating group on n elements, and will be denoted by An.
Among the most interesting entities in abstract algebra is the permutation group In this post we look at some basic examples to get a handle on these groups.
a) Write out all the members of G
b) Show that G obeys group properties and determine whether or not it is Abelian
Solution:
We first determine how many members G has using the fact the number of elements will be n = 3!
= 3 x 2 x 1 = 6.
The components to the elements can then be found:
(1,2, 3), (1, 3, 2), (3, 2, 1), (3, 1, 2), (2, 1, 3) and (2, 3, 1)
These are not the elements themselves, which must be written as (2 x 3) matrices. For example, the identity element will be: e =
[1 2 3]
[1 2 3]
The other elements we can write:
s1 =
[1 2 3]
[2 3 1]
s2 =
[1 2 3]
[3 1 2]
t1 =
[1 2 3]
[1 3 2]
t2 =
[1 2 3]
[3 2 1]
t3 =
[1 2 3]
[2 1 3]
We can now prepare a group table to show the operation is binary and G meets the Group definition. We have for G = {The set of all permutations on S}:
e---- s1--- s2--- t1 --- t2 --- t3
--------------------------------------------------
e -- e ---s1--- s2 --- t1 --- t2--- t3
s1 --s1--- s2--- e ----t2 ----t3 ----t1
s2 --s2----e ---s1--- t3--- t1---- t2
t1 --- t1- t3- t2 --- e --- s2 -----s1
t2 ----t2--- t1-- t3- - s1--- e------ s2
t3 -----t3 ---t2 ---t1 ---- s2 --- s1---- e
------------------------------------------
The shaded highlights shown are intended to emphasize the symmetries in the table (which can also be found for the s elements).
Is G Abelian? If we check any two elements and find they don’t meet the commutative property (4) then the answer is no. By inspection:
t1 • t2 = s1 =
[1 2 3]
[2 3 1]
but t2 • t21 = s2 =
[1 2 3]
[3 1 2]
So, the commutative property is not met, and G is not Abelian.
Other examples: Groups of permutations related to 1:1 mappings (functions).
Let A be a set and let s and t be permutations of A so that s and t are both one-to-one functions mapping A onto A. Then the composite function is s t and will be a permutation if it is one-to-one and onto A.
Definitional illustrations:
A)If a1(s t) = a2(s t), then (a1s ) t = (a2 s ) t and (a1s) = (a1s ) (since t is 1:1) and a1 = a2.
Hence (s t) is 1:1.
B) Let a Î A , then since t is onto A, $ a’ Î A such that a’t = a. Since s is onto A, $ a" Î A such that a’ = a” s. Then, a = a’t = (a” s ) t = a” (s t).
Example: Let A = {1, 2, 3, 4, 5} and
s =
[1 2 3 4 5]
[4 2 5 3 1]
In this case: 1s = 4, 2s = 2, 3s = 5, 4s = 3, and 5s = 1
Now, let:
t =
[1 2 3 4 5]
[3 5 4 2 1]
Then: 1t = 3, 2t = 5, 3t = 4, 4t = 2, and 5t = 1
Then we can find st by matrix multiplication (for details of matrix multiplication, see http://brane-space.blogspot.com/2010/05/looking-at-matrix-groups.html ).
The result will be:
[1 2 3 4 5]
[2 5 1 4 3]
Which the reader should be able to verify!
Suggested Problem:
Find: 1 t, 2t , 3t , 4t, and 5t
No comments:
Post a Comment