transposition Transposition 2002-02-20 00:48:59 2004-09-25 22:13:27 Definition %\usepackage{graphicx} %\usepackage{xypic} \usepackage{bbm} \newcommand{\Z}{\mathbbmss{Z}} \newcommand{\C}{\mathbbmss{C}} \newcommand{\R}{\mathbbmss{R}} \newcommand{\Q}{\mathbbmss{Q}} \newcommand{\mathbb}[1]{\mathbbmss{#1}} 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)$. Example: If $X=\{a,b,c,d,e\}$ the function $\sigma$ given by \begin{eqnarray*} \sigma(a)&=&a\\ \sigma(b)&=&e\\ \sigma(c)&=&c\\ \sigma(d)&=&d\\ \sigma(e)&=&b \end{eqnarray*} is a transposition. One of the main results on symmetric groups states that any permutation can be expressed as composition (product) of transpositions, and for any two decompositions of a given permutation, the number of transpositions is always even or always odd.