Permutations as a Product of TranspositionsAs in the shuttle puzzle, the applet below allows you to connect any two poles with vertical "shuttles". Each such shuttle defines a transposition, i.e., a permutation that only involves swapping two elements. Several subsequent shuttles (counted from top to bottom) define a permutation that "follows the shuttles in the following manner: poles are numbered and each number appears just above the pole it names. For every pole in turn, start from the top, slide down till the first intersection with a shuttle, if any, to the end of the shuttle, from there again down to the first intersection with another shuttle, then follow this shuttle to the end, then down again, and so on. When eventually you reach a pole's bottom, this pole's number corresponds to the number of the pole where the descent has started. As we know, such a procedure indeed defines a permutation. This permutation is naturally treated as a product of successive transpositions.
The representation of a permutation as a product of transpositions is not unique, but the parity of the number of transpositions in the product is a feature of the permutation and does not depend on the representation. Any permutation can be represented as a product of cycles. Every cycle is shown to be a product of transpositions. Thus, every permutation can be represented as a product of transpositions. References
 Permutations
|Activities| |Contact| |Front page| |Contents| |Games| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 40608173 |
