The Identity Permutation

Definition: The Identity Permutation $\epsilon$ of elements from $\{ 1, 2, ..., n \}$ is defined to be $\epsilon = \begin{pmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{pmatrix}$.

For example, the identity permutation of elements from $\{1, 2, 3 \}$ is $\epsilon = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$.

Recall from the Even and Odd Permutations as Products of Transpositions page that a permutation is said to be even if it can be written as a product of an even number of transpositions, and is said to be odd if it can be written as a product of an odd number of transpositions.

One important property of the identity permutation is that it is an even permutation.

Theorem 1: Consider the finite $n$-element set $\{ 1, 2, ..., n \}$. If $\epsilon \in S_n$ is defined to be the identity permutation, then $\epsilon$ is an even permutation.

• Proof: Let $\epsilon \in S_n$ be the identity permutation. Then $\epsilon = \begin{pmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{pmatrix}$. Clearly $\epsilon$ can be written as a product of two transpositions since for all $a, b \in \{ 1, 2, ..., n \}$ where $a \neq b$ we have that:

(1)

\begin{align} \quad \epsilon = (ab) \circ (ba) \end{align}

• In other words, we first swap elements $b$ and $a$ (corresponding to applying $(ba)$, and then we swap elements $a$ and $b$ (corresponding to then applying $(ab)$) which returns us to our original permutation. Suppose that for $k \geq 3$ that $\epsilon$ can be written as the product of $k$ transpositions. Then:

(2)

\begin{align} \quad \epsilon = t_1 \circ t_2 \circ ... \circ t_k \quad (*) \end{align}

• If we can show that $\epsilon$ can also be written as the product of $k - 2$ transpositions then we will have also shown that $\epsilon$ must be the product of an even number of transpositions. To verify this, suppose that we can show that $\epsilon = t_1 \circ t_2 \circ ... \circ t_{k-2}$. Then for $t_1^{-1}, t_2^{-1}, ..., t_{k-2}^{-1}$ as inverse transpositions, we'd have:

(3)

\begin{align} \quad \epsilon = t_{k-2}^{-1} \circ ... \circ t_2^{-1} \circ t_1^{-1} \quad (**) \end{align}

• Therefore by composing $(*)$ and $(**)$ we get:

(4)

\begin{align} \quad \epsilon = \epsilon \circ \epsilon = (t_{k-2}^{-1} \circ ... \circ t_2^{-1} \circ t_1^{-1}) \circ (t_1 \circ t_2 \circ ... \circ t_k \quad ) = t_{k-1} \circ t_k \end{align}

• If $k$ were instead odd, then $\epsilon$ would equal a single transposition which would contradict $\epsilon$ being the identity permutation since a single transposition must swap two elements in the permutation.

• Now let $x$ be any number that appears in one of the transpositions $t_2, ..., t_k$. Since $t_2, ..., t_k$ is a finite list, there must exist a largest subscript $j \in \{ 1, 2, ..., k \}$ such that $t_j = (xa)$ for some $a \neq x$ and such that $x$ does not appear in the transpositions $t_{j+1}, t_{j+2}, ..., t_{k}$.

• Consider the transposition $t_{j-1} = (yb)$. There are four cases to consider.

• Case 1: Suppose that $t_{j-1} = (xa)$. Then $t_{j-1}t_j = \epsilon$ and so:

(5)

\begin{align} \quad \epsilon = \underbrace{t_1 \circ t_2 \circ ... \circ t_{j-1} \circ t_j \circ ... \circ t_k}_{k \: \mathrm{many \: transpositions}} = t_1 \circ t_2 \circ ... \circ \epsilon \circ ... \circ t_k = \underbrace{t_1 \circ t_2 \circ ... t_{j-2} \circ t_{j+1} \circ ... \circ t_k}_{k-2 \: \mathrm{many \: transpositions}} \end{align}

• Therefore $\epsilon$ can be written as the product of $k - 2$ transpositions.

• Case 2: Suppose that $t_{j-1} = (xb)$ where $b \neq x$ and $b \neq a$. By applying one of the theorems we saw on the Basic Theorems Regarding Transpositions page we see that:

(6)

\begin{align} \quad t_{j-1} \circ t_j = (xb) \circ (xa) = (bx) \circ (xa) = (bxa) = (xab) = (xa) \circ (ab) \end{align}

• Replace $t_{j-1} \circ t_j$ with $(xa) \circ (ab)$. Then $j - 1$ is the largest subscript in $\{1, 2, ..., k \}$ such that $x$ does not appear in the transpositions $t_j, t_{j+1}, ..., t_k$ for $\epsilon$.

• Case 3: Suppose that $t_{j-1} = (ya)$ where $y \neq x$ and $y \neq a$. Then:

(7)

\begin{align} \quad t_{j-1} \circ t_j = (ya) \circ (xa) = (ya) \circ (ax) = (yax) = (xya) = (xy) \circ (ya) \end{align}

• Replace $t_{j-1} \circ t_j$ with $(xy) \circ (ya)$. Then $j - 1$ is the largest subscript in $\{ 1, 2, ..., k \}$ such that $x$ does not appear in the transpositions $t_j, t_{j+1}, ..., t_k$.

• Case 4: Suppoe that $t_{j-1} = (yb)$ where $y \neq x$, $y \neq a$, $b \neq x$, $b \neq a$, and $y \neq b$. Then since $t_{j-1}$ and $t_j$ are disjoint transpositions we have that:

(8)

\begin{align} \quad t_{j-1} \circ t_j = (yb) \circ (xa) = (xa) \circ (yb) \end{align}

• Replace $t_{j-1} \circ t_j$ with $(xa) \circ (yb)$. Then $j - 1$ is the largest subscript in $\{ 1, 2, ..., k \}$ such that $x$ does not appear in the transpositions $t_j, t_{j+1}, ..., t_k$.

• In the cases 2-4 we repeat the repeat the procedure over again to which these three cases will eventually reduce to case 1 because if they did not, then eventually we would have that $x$ only appears in the transposition $t_1$ and so none of the other transpositions $t_2, t_3, ..., t_k$ could reverse the swap caused by $t_1$ implying that $\epsilon$ was not the identity permutation. Since cases 2-4 reduce to case 1, we see that $\epsilon$ can be written as the product of $k - 2$ transpositions and therefore $\epsilon$ must be an even transposition. $\blacksquare$

We can finally prove that every permutation of $\{ 1, 2, ..., n \}$ can be classified as either even or odd but not both.

Corollary 1: If $\sigma$ is a permutation of the elements in $\{ 1, 2, ..., n \}$ then $\sigma$ cannot be both an even and an odd permutation.

• Proof: Suppose that $\sigma$ was both an even and an odd permutation. Then $\sigma = t_1 \circ t_2 \circ ... \circ t_k$ and $\sigma = u_1 \circ u_2 \circ ... \circ u_j$ where $k$ is even and $j$ is odd. Notice that also:

(9)

\begin{align} \quad \sigma^{-1} = u_j^{-1} \circ u_{j-1}^{-1} \circ ... \circ u_2^{-1} \circ u_1 \end{align}

• Therefore:

(10)

\begin{align} \quad \epsilon = \sigma^{-1} \circ \sigma = (u_j^{-1} \circ u_{j-1}^{-1} \circ ... \circ u_2^{-1} \circ u_1) \circ (t_1 \circ t_2 \circ ... \circ t_k) \end{align}

• The equation above implies that the identity permutation can be written as the product of $k + j$ transpositions. But $k + j$ is odd by Theorem 1, and hence our assumption that $\sigma$ was both an even and odd permutation was false. $\blacksquare$