Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Parity of a permutation
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, when <i>X</i> is a <a href="/facts/Finite_set/za1newlP">finite set</a> with at least two elements, the <a href="/facts/Permutation/JSw9ukmv">permutations</a> of <i>X</i> (i.e. the <a href="/facts/Bijective_function/j4gTuTmW">bijective functions</a> from <i>X</i> to <i>X</i>) fall into two classes of equal size: the even permutations and the odd permutations. If any <a href="/facts/Total_ordering/xnTtmuYJ">total ordering</a> of <i>X</i> is fixed, the parity (oddness or evenness) of a permutation σ {\displaystyle \sigma } of <i>X</i> can be defined as the parity of the number of <a href="/facts/Inversion_(discrete_mathematics)/TR7RxJ07">inversions</a> for <i>σ</i>, i.e., of pairs of elements <i>x</i>, <i>y</i> of <i>X</i> such that <i>x</i> < <i>y</i> and <i>σ</i>(<i>x</i>) > <i>σ</i>(<i>y</i>). </p><p>The sign, signature, or signum of a permutation <i>σ</i> is denoted sgn(<i>σ</i>) and defined as +1 if <i>σ</i> is even and −1 if <i>σ</i> is odd. The signature defines the alternating <a href="/facts/Character_(mathematics)/M46SyYUp">character</a> of the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> S<i>n</i>. Another notation for the sign of a permutation is given by the more general <a href="/facts/Levi-Civita_symbol/WBKUA3Tw">Levi-Civita symbol</a> (<i>ε</i><i>σ</i>), which is defined for all maps from <i>X</i> to <i>X</i>, and has value zero for <a href="/facts/Bijection/j4gTuTmW"> non-bijective maps</a>. </p><p>The sign of a permutation can be explicitly expressed as </p> sgn(<i>σ</i>) = (−1)<i>N</i>(<i>σ</i>) <p>where <i>N</i>(<i>σ</i>) is the number of <a href="/facts/Inversion_(discrete_mathematics)/TR7RxJ07">inversions</a> in <i>σ</i>. </p><p>Alternatively, the sign of a permutation <i>σ</i> can be defined from its decomposition into the product of <a href="/facts/Transposition_(mathematics)/UndoYWpl">transpositions</a> as </p> sgn(<i>σ</i>) = (−1)<i>m</i> <p>where <i>m</i> is the number of transpositions in the decomposition. Although such a decomposition is not unique, the parity of the number of transpositions in all decompositions is the same, implying that the sign of a permutation is <a href="/facts/Well-defined/GAc0XbWz">well-defined</a>. </p>