Parity of a Permutation

Table of contents
  1. Permutation
    1. Identity permutation
  2. Parity
  3. Even and odd permutations

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$