Transposition (mathematics)

In informal language, a transposition is a function that swaps two elements of a set. More formally, given a finite set $X=\{a\_1,a\_2,ldots,a\_n\}$, 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,\; b).$

For example, if $X=\{a,\; b,\; c,\; d,\; e\}$, the function $sigma$ given by

:

is a transposition.

Any permutation can be expressed as the composition (product) of transpositions. 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.

External links

* [http://www.cut-the-knot.org/Curriculum/Combinatorics/PermByTrans.shtml Permutations as a Product of Transpositions]

ee also

* Cycle (mathematics)
* Signature of a permutation