Permutations
Permutation
A permutation is a bijective map
, denoted by: or using the cycle notation: if are distinct elements from and if fixes the other elements (if any) and if then is called -cycle and denoted . Any permutation can be written (non-uniquely) as a product of cycles. Crucially, permutations are composed from right to left.
Cycle Decomposition
The cycle decomposition of permutation
is the product of the disjoint cycles in which can be expressed.
e.g. Consider the permutation
Proposition
Suppose
and are permutations then the cycle decomposition of the permutation can be obtained from that of by replacing each in the cycle decomposition of with , that is
Proof For any arbitrary
The Symmetric Group
Symmetric Group
The symmetric group
plays a fundamental role in finite group theory. It consists of permutations of a set with letters . In general, given a finite set , we have the group of permutations on set to be:
Theorem
The symmetric group
is generated by adjacent transpositions:
Even Permutation & Odd Permutation
A permutation is an even permutation if the number of cycles of even length is even. And it is an odd permutation if the number of cycles of even length is odd.
Proposition
The sign map
that sends an even permutation to , an odd permutation to is a group homomorphism.
Proof It is easy to see this by counting the number of transpositions. Even permutation has even number of transpositions, and odd permutation has odd number of transpositions. Thus, the product of two even permutations is even, the product of two odd permutations is even, and the product of an even and an odd permutation is odd.
Proposition
The order of
is
Proof Clearly, there are
Alternating Group
The alternating group
is the subgroup of consisting of all even permutations. In other words, it is the kernel of .
Def Permutation Matrices
Let