Basic Theorems Regarding Transpositions

Basic Theorems Regarding Transpositions

Recall from the Transposition Permutations page that a transposition $\sigma$ of the set $\{ 1, 2, ..., n \}$ is a cycle of length $2$ denoted $(ab)$ for $a, b \in \{1, 2, ..., n \}$, $a \neq b$ and such that $\sigma(a) = b$ and $\sigma(b) = a$ and where all other elements are mapped to themselves.

We will now look at some nice theorems regarding transposition permutations.

Theorem 1: If $(ab)$ is a transposition of the set $\{ 1, 2, ..., n \}$ and $\epsilon$ is the identity permutation then $(ab) \circ (ab) = \epsilon$.
  • Proof: Let $(ab)$ be a transposition of the set $\{ 1, 2, ..., n \}$. Then $a, b \in \{ 1, 2, ..., n \}$, $a \neq b$ and for all $x \in \{ 1, 2, ..., n \}$ we have that:
(1)
\begin{align} \quad (ab)(x) = \left\{\begin{matrix} a & \mathrm{if} \: x = b\\ b & \mathrm{if} \: x = a\\ x & \mathrm{if} \: x \neq a, b \end{matrix}\right. \end{align}
  • So the only difference between $\epsilon(x)$ and $(ab)(x)$ is that $(ab)$ maps $a$ to $b$ and $(ab)$ maps $b$ to $a$. If we apply $(ab)$ again, we get that $a$ is mapped back to $a$ and $b$ is mapped back to $b$ while all other $x$ are mapped back to themselves. Hence:
(2)
\begin{align} \quad (ab) \circ (ab) = \epsilon \quad \blacksquare \end{align}
Theorem 2: If $(ab)$ and $(bc)$ are transpositions of $\{1, 2, ..., n \}$ where $a \neq b \neq c$, then $(ab) \circ (bc) = (abc)$.
  • Proof: Let $(ab)$ and $(bc)$ be transpositions of $\{ 1, 2, ..., n \}$ where $a \neq b \neq c$. For each $x \in \{1, 2, ..., n \}$ we have that:
(3)
\begin{align} \quad (bc)(x) = \left\{\begin{matrix} b & \mathrm{if} \: x = c\\ c & \mathrm{if} \: x = b\\ x & \mathrm{if} \: x \neq b, c \end{matrix}\right. \end{align}
  • Similarly, $(ab)(x)$ is defined above in Theorem 1. So the only elements that are moved are $a$, $b$, and $c$ and this movement is depicted graphically below:
Screen%20Shot%202015-09-09%20at%208.31.17%20PM.png
  • Hence $[(ab) \circ (bc)](a) = b$, $[(ab) \circ (bc)](b) = c$, and $[(ab) \circ (bc)](c) = a$. But this is exactly what the cycle $(abc)$ does. Hence:
(4)
\begin{align} \quad (ab) \circ (bc) = (abc) \quad \blacksquare \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License