Transposition is of Odd Parity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S_n$ denote the set of permutations on $n$ letters.

Let $\pi \in S_n$ be a transposition.

Then $\pi$ is of odd parity.


Proof

Let $\pi = \begin{pmatrix} 1 & 2 \end{pmatrix}$ be a transposition.

Let $\Delta_n$ be defined as Product of Differences.

Then $\forall n \in \N_{>0}: \pi \cdot \Delta_n$ produces only one sign change in $\Delta_n$, that is, the one occurring in the factor $\paren {x_1 - x_2}$.

Thus:

$\begin{pmatrix} 1 & 2 \end{pmatrix} \cdot \Delta_n = - \Delta_n$

and thus $\begin{pmatrix} 1 & 2 \end{pmatrix}$ is odd.


From Conjugates of Transpositions:

$\begin{pmatrix} 1 & k \end{pmatrix} = \begin{pmatrix} 2 & k \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & k \end{pmatrix}$

Thus as $\begin{pmatrix} 2 & k \end{pmatrix}$ is self-inverse:

$\begin{pmatrix} 1 & k \end{pmatrix} = \begin{pmatrix} 2 & k \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & k \end{pmatrix}^{-1}$


But from Parity of Conjugate of Permutation:

$\map \sgn {\begin{pmatrix} 2 & k \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & k \end{pmatrix}^{-1} } = \sgn {\begin{pmatrix} 1 & 2 \end{pmatrix} }$

Thus:

$\sgn {\begin{pmatrix} 1 & k \end{pmatrix} } = \sgn {\begin{pmatrix} 1 & 2 \end{pmatrix} }$

and thus $\begin{pmatrix} 1 & k \end{pmatrix}$ is odd.


Finally:

\(\ds \begin{pmatrix} h & k \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 1 & h \end{pmatrix} \begin{pmatrix} 1 & k \end{pmatrix} \begin{pmatrix} 1 & h \end{pmatrix}\) Conjugates of Transpositions
\(\ds \) \(=\) \(\ds \begin{pmatrix} 1 & h \end{pmatrix} \begin{pmatrix} 1 & k \end{pmatrix} \begin{pmatrix} 1 & h \end{pmatrix}^{-1}\) Transposition is Self-Inverse


But from Parity of Conjugate of Permutation:

$\map \sgn {\begin{pmatrix} 1 & h \end{pmatrix} \begin{pmatrix} 1 & k \end{pmatrix} \begin{pmatrix} 1 & h \end{pmatrix}^{-1} } = \sgn {\begin{pmatrix} 1 & k \end{pmatrix} }$

Thus:

$\sgn {\begin{pmatrix} h & k \end{pmatrix} } = \sgn {\begin{pmatrix} 1 & k \end{pmatrix} }$

and thus $\begin{pmatrix} h & k \end{pmatrix}$ is odd.

$\blacksquare$


Sources

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