-
A permutation of a set refers to a bijective mapping from the set to itself.
-
The orbit of an element
of a set under the permutation is the set defined as It is the set of all possible values that an element can be mapped to using only the permutation.
- The orbits of a permutation form an equivalence class.
-
A cycle permutation is a permutation with at most one orbit containing more than one element.
- (Fraleigh 9.8) All permutations can be expressed as the product of disjoint cycles. Each cycle corresponds to one orbit and the orbits are disjoint equivalent classes.
- The length of a cycle is defined as the number of elements in its largest orbit.
- Cycles can be expressed in Cycle Notation
where the cycle is understood to take to , to and so on, and to . Any other element of not included is understood to be fixed.
-
A transposition is a permutation which involves swapping exactly two elements.
- A transposition is a cycle of length
. - (Fraleigh 9.15) All permutations can either be expressed as the product of an even number of transpositions or an odd number of transpositions, but never both.
- If we use the corresponding permutation matrix, the determinant’s sign remains constant.
- The parity of a permutation is even if it needs an even number of transpositions and odd otherwise .
- A transposition is a cycle of length