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 results regarding transposition permutations.

Proposition 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}

Proposition 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 Proposition 1. So the only elements that are moved are $a$, $b$, and $c$ and this movement is depicted graphically below:

• 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}