Transposition (mathematics)
From Free net encyclopedia
In informal language, a transposition is a function that swaps two elements of a set. More formally, given a finite set <math>X=\{a_1,a_2,\ldots,a_n\}</math>, a transposition is a permutation (bijective function of <math>X</math> onto itself) <math>f,</math> such that there exist indices <math>i, j</math> such that <math>f(a_i) = a_j</math>, <math>f(a_j) = a_i</math> and <math>f(a_k) = a_k</math> for all other indices <math>k.</math> This is often denoted (in the cycle notation) as <math>(a, b).</math>
Example: If <math>X=\{a, b, c, d, e\}</math> the function <math>\sigma</math> given by
- <math>\begin{matrix} \sigma(a)&=&a\\ \sigma(b)&=&e\\ \sigma(c)&=&c\\ \sigma(d)&=&d\\ \sigma(e)&=&b \end{matrix}</math>
is a transposition.
One of the main results on symmetric groups states that any permutation can be expressed as the composition (product) of transpositions, and for any two decompositions of a given permutation, the number of transpositions is always even or always odd.