Transpositions
With our earlier conventions, a permutation is a 1-1 correspondence
A fixed point forms a one-element (or trivial) cycle. A 2-element cycle
Theorem 1
Any permutation is a product of transpositions. (The representation as a product of transpositions is not unique.)
Remark
As before, this means that f produces the same effect as consecutive application of a series of transpositions.
Proof of Theorem 1
Given a permutation f, first factor it into a product of cycles:
(1) | (x_{1} x_{2} ... x_{k}) = (x_{1} x_{k})(x_{1} x_{k-1}) ... (x_{1} x_{2}) |
The product is not symmetric and the transpositions are performed from right to left. We can apply this argument to all the cycles g and then execute all thus obtained transpositions sequentially.
Representation of a permutation as a product of (disjoint) cycles is unique. Its representation as a product of transpositions is not. However, one quantity related to a permutation is invariant under its various representations as a product of transpositions. This is the parity of the number of transpositions in the representation.
Theorem 2
Assume that for a permutation f,
Thus there are even and odd permutations. The former are obtained as a product of an even number of transpositions; the latter are formed by an odd number of terms. Multiplying a permutation by a transposition obviously changes its parity. As a consequence, parity of the product (consecutive execution) of two or, for that matter, any number of permutations obeys the laws of the arithmetic modulo 2. In other words, the product of two permutations (which is definitely another permutation) will be even iff the component permutations are either both even or both odd.
The parity of a permutation is often referred to as its sign or signatue.
Pemutations have an additional visualization in a circular fashion. Quite a convenience.
References
- J. Landin, An Introduction to Algebraic Structures, Dover, NY, 1969.
Permutations
- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
67809466