Transposition

In informal language, a transposition is a function that swaps two elements of a set. More formally, given a finite set , a transposition is a permutation (bijective function of X onto itself) f, such that there exist indices i,j such that f(a_i) = a_j, f(a_j) = a_i and f(a_k) = a_k for all other indices k. This is often denoted (in the cycle notation) as (a_i,a_j).

For example, if X = {a,b,c,d,e}, the function σ given by

is a transposition.

Properties

Any permutation can be expressed as the composition (product) of transpositions – formally, they are generators for the group. In fact, if one orders the set as in {1,2,3,4,5}, then any permutation can be expressed as a product of adjacent transpositions, meaning the transpositions (k,k + 1), in this case (12),(23),(34),(45). This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition (k,l) where k < l by moving k to l one step at a time, then moving l back to where k was, which interchanges these two and makes no other changes:

In fact, the symmetric group is a Coxeter group, meaning that it is generated by elements of order 2 (the adjacent transpositions), and all relations are of a certain form.

One of the main results on symmetric groups states that either all of the decompositions of a given permutation into transpositions have an even number of transpositions, or they all have an odd number of transpositions, that allows to define the parity of a permutation.

External links

• Permutations as a Product of Transpositions

See also

• Cycle (mathematics)
• Signature of a permutation

This article incorporates material from transposition on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.