Transposition (mathematics)

From Wikipedia, the free encyclopedia

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 $σ$ given by

$\begin{matrix} \sigma(a)&=&a\\ \sigma(b)&=&e\\ \sigma(c)&=&c\\ \sigma(d)&=&d\\ \sigma(e)&=&b \end{matrix}$

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.