Sign of Permutation on n Letters is Well-Defined

From ProofWiki
Jump to navigation Jump to search

Theorem

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

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

Let $\rho \in S_n$ be a permutation in $S_n$.

Let $\map \sgn \rho$ denote the sign of $\rho$.


Then $\map \sgn \rho$ is well-defined, in that it is either $1$ or $-1$.


Proof

What is needed to be proved is that for any permutation $\rho \in S_n$, $\rho$ cannot be expressed as the composite of both an even number and an odd number of transpositions.


Consider the permutation formed by composing $\rho$ with an arbitrary transposition $\tau$.

Let $\rho$ be expressed as the composite of disjoint cycles whose lengths are all greater than $1$.

By Disjoint Permutations Commute, the order in which the various cycles of $\rho$ are composed does not matter.

Let $\tau = \begin {bmatrix} a & b \end {bmatrix}$ for some $a, b \in \set {1, 2, \ldots, n}$ where $a \ne b$.


There are three cases:


$(1): \quad$ Neither $a$ nor $b$ appear in the expression for $\rho$.

That is, $\tau$ and $\rho$ are disjoint.

Then $\rho \circ \tau$ can be expressed as the same set of disjoint cycles as $\rho$, but with an extra cycle $\begin {bmatrix} a & b \end {bmatrix}$ appended.


$(2): \quad$ Just one of $a$ and $b$ occurs in the expression for $\rho$.

Without loss of generality, let $a$ appear in the expression for $\rho$.

Let $a$ appear in the cycle $\rho_0$.

Then:

\(\ds \rho_0 \circ \tau\) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m \end {bmatrix} \circ \begin {bmatrix} a & b \end {bmatrix}\)
\(\ds \) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m b \end {bmatrix}\)

Thus composing $\rho$ with $\tau$ results in adding an extra element to one cycle and leaving the others as they are.


$(3): \quad$ Both $a$ and $b$ occur in the expression for $\rho$.

If $a$ and $b$ both occur in the same cycle $\rho_0$, the operation of composition goes like this:

\(\ds \rho_0 \circ \tau\) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m & b & c_1 & c_2 & \cdots c_k \end {bmatrix} \circ \begin {bmatrix} a & b \end {bmatrix}\)
\(\ds \) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m \end {bmatrix} \circ \begin {bmatrix} b & c_1 & c_2 & \cdots c_k \end {bmatrix}\)


If $a$ and $b$ appear in different cycles $\rho_1$ and $\rho_2$, we have:

\(\ds \rho_1 \circ \rho_2 \circ \tau\) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m \end {bmatrix} \circ \begin {bmatrix} b & c_1 & c_2 & \cdots c_k \end {bmatrix} \circ \begin {bmatrix} a & b \end {bmatrix}\)
\(\ds \) \(=\) \(\ds \begin {bmatrix} a & b_1 & b_2 & \cdots & b_m & b & c_1 & c_2 & \cdots c_k \end {bmatrix}\)

Thus in case $(3)$, composition with $\tau$ results in the number of cycles either increasing or decreasing by $1$, while the total number of elements in those cycles stays the same.


For all $\rho \in S_n$, Let $\rho$ be expressed in cycle notation as a composite of $n$ cycles containing $m_1, m_2, \ldots, m_n$ elements respectively, where each $m_i \ge 2$.

Let the mapping $P: S_n \to \set {1, -1}$ be defined as follows:

$\forall \rho \in S_n: \map P \rho = \paren {-1}^{m_1 - 1} \paren {-1}^{m_1 - 1} \cdots \paren {-1}^{m_n - 1}$

where $\map P {I_{S_n} } = 1$.

From the above, it can be seen that $\map P {\rho \circ \tau} = -\map P \rho$.


Let $\rho$ be expressible as the composite of $r$ transpositions.

By an inductive proof it can be shown that $\map P \rho = \paren {-1}^r$.

But $\map P \rho$ is independent of the actual transpositions that are used to build $\rho$.

Thus $\map P \rho = 1$ for one such expression if and only if $\map P \rho = 1$ for all such expressions.

That is, $\rho$ cannot have an expression in cycle notation as the composite of an even number of transpositions and at the same time have an expression in cycle notation as the composite of an odd number of transpositions.

Hence the result.

$\blacksquare$


Sources