|
|
|
|
|
|
|
|
TranspositionsWith our earlier conventions, a permutation is a 1-1 correspondence
f: {1, 2, ..., n}  A fixed point forms a one-element (or trivial) cycle. A 2-element cycle Any permutation is a product of transpositions. As before, this means that f produces the same effect as consecutive application of a series of transpositions. Given a permutation f, first factor it into a product of cycles:
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 2Assume 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. Pemutations have an additional visualization in a circular fashion. Quite a convenience. References
Copyright © 1996-2009 Alexander Bogomolny |
{1, 2, ..., n}. Pick an 
{1,2,...n} and consider its 
| 33066417 |  |
