Parity of a Permutation
Table of contents
Permutation
Let $X$ be a finite set of $n > 1$ elements.
A permutation $\sigma$ is a bijection from $X$ to $X$.
Given a set $\{a, b, c\}$, the permutation $\{b, c, a\}$ is:
\[\begin{gather*} \sigma(a) = b \\ \sigma(b) = c \\ \sigma(c) = a \end{gather*}\]It is often denoted in the following form:
\[\sigma = \begin{pmatrix} a & b & c \\ b & c & a \end{pmatrix}\]Identity permutation
The identity permutation is the permutation that maps every element to itself.
\[\begin{pmatrix} a & b & c \\ a & b & c \end{pmatrix}\]Parity
The parity of a permutation $\sigma$ is the parity of the number of paired inversions in $\sigma$ required to transform it into the identity permutation.
The parity or the sign of a permutation $\sigma$ is denoted:
$$ \operatorname{sgn}(\sigma) = (-1)^{\text{number of inversions}} $$
Continuing with the example above, the number of inversions need for
\[\begin{pmatrix} a & b & c \\ b & c & a \end{pmatrix}\]would be 2:
- Invert $a$ and $c$
- Invert $a$ and $b$
Therefore, the parity of the permutation is $(-1)^2 = 1$.
Even and odd permutations
The set of permutations of $X$ can be partitioned into two subsets:
- Even permutations: $\operatorname{sgn}(\sigma) = 1$
- Odd permutations: $\operatorname{sgn}(\sigma) = -1$