Sign of Permutation is Plus or Minus Unity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \N$ be a natural number.

Let $\N_n$ denote the set of natural numbers $\set {1, 2, \ldots, n}$.

Let $S_n$ denote the symmetric group on $n$ letters.

Let $\sequence {x_k}_{k \mathop \in \N_n}$ be a finite sequence in $\R$.

Let $\pi \in S_n$.

Let $\map {\Delta_n} {x_1, x_2, \ldots, x_n}$ be the product of differences of $\tuple {x_1, x_2, \ldots, x_n}$.


Let $\map \sgn \pi$ be the sign of $\pi$.


Let $\pi \cdot \map {\Delta_n} {x_1, x_2, \ldots, x_n}$ be defined as:

$\pi \cdot \map {\Delta_n} {x_1, x_2, \ldots, x_n} := \map {\Delta_n} {x_{\map \pi 1}, x_{\map \pi 2}, \ldots, x_{\map \pi n} }$


Then either:

$\pi \cdot \Delta_n = \Delta_n$

or:

$\pi \cdot \Delta_n = -\Delta_n$


That is:

$\map \sgn \pi = \begin{cases}

1 & :\pi \cdot \Delta_n = \Delta_n \\ -1 & : \pi \cdot \Delta_n = -\Delta_n \end{cases}$


Thus:

$\pi \cdot \Delta_n = \map \sgn \pi \Delta_n$


Proof

If $\exists i, j \in \N_n$ such that $x_i = x_j$, then $\map {\Delta_n} {x_1, x_2, \ldots, x_n} = 0$ and the result follows trivially.

So, suppose all the elements $x_k$ are distinct.


Let us use $\Delta_n$ to denote $\map {\Delta_n} {x_1, x_2, \ldots, x_n}$.

Let $1 \le a < b \le n$.

Then $x_a - x_b$ is a divisor of $\Delta_n$.

Then $x_{\map \pi a} - x_{\map \pi b}$ is a factor of $\pi \cdot \Delta_n$.


There are two possibilities for the ordering of $\map \pi a$ and $\map \pi b$:

Either $\map \pi a < \map \pi b$ or $\map \pi a > \map \pi b$.

If the former, then $x_{\map \pi a} - x_{\map \pi b}$ is a factor of $\Delta_n$.

If the latter, then $-\paren {x_{\map \pi a} - x_{\map \pi b} }$ is a factor of $\Delta_n$.

The same applies to all factors of $\Delta_n$.

Thus:

\(\ds \pi \cdot \Delta_n\) \(=\) \(\ds \pi \cdot \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_i - x_j}\)
\(\ds \) \(=\) \(\ds \pm \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_i - x_j}\)
\(\ds \) \(=\) \(\ds \pm \Delta_n\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sign_of_Permutation_is_Plus_or_Minus_Unity&oldid=676453"