Transpositions

We return again to the general situation with $S_n$. Let $f \in S_n$. If $f$ is a cycle of length $2$, i.e., $f = (a_1,a_2)$ where $a_1,a_2\in A$, then $f$ is called a transposition. It is easy to see that any cycle can be written as a product of transpositions, namely

$$(a_1,...,a_k)=(a_1,a_k)(a_1,a_{k-1})...(a_1,a_2).$$ (3.3)

According to (3.2) any permutation can be written in terms of cycles, but the above (3.3) shows any cycle can be written as a product of transpositions. Thus we have the following result.

Theorem 3.2.1   Let $f \in S_n$ be any permutation of degree $n$. Then $f$ can be written as a product of transpositions.

Furthermore using (3.3) and (3.2), it is readily seen that if f is any permutation as in (3.2), then f can be written as a product of

$$W(f)=(k-1)+(j-1)+...+(t-1)$$ (3.4)

transpositions. The number $W(f)$ is uniquely associated with the permutation $f$ since $f$ is uniquely represented (up to order) as a product of disjoint cycles. However, there is nothing unique about the number of transpositions occurring in an arbitrary representation of $f$ as a product of transpositions, e.g., in $S_3$

$$(1,3,2) = (1,2) (1,3) = (1,2) (1,3) (1,2) (1,2),$$

since $(1,2) (1,2) = (1)$, the identity permutation of $S_3$. Although the number of transpositions is not unique in the representation of a permutation, $f$, as a product of transpositions, we shall show, however, that the parity (even or oddness) of that number is unique. Moreover, this depends solely on the number $W(f)$ uniquely associated with the representation of $f$ given in (3.2). More explicitly, we have the following result.

Theorem 3.2.2   If $f$ is a permutation written as a product of disjoint cycles and if $W(f)$ is the associated integer given by (3.4), then if $W(f)$ is even (odd) any representation of $f$ as a product of transpositions must contain an even (odd) number of transpositions.

Proof: We first observe the following:

$$(a,b) (b,c_1, ..., c_t) (a,b_1, ..., b_k) = (a,b_1, ... ,b_k,b,c_1, ... ,c_t),$$ (3.5)

$$(a,b) (a,b_1 ... ,b_k,b,c_1, ... ,c_t) = (a,b_1, ..., b_k) (b,c_1, ... ,c_t).$$ (3.6)

Suppose now that $f$ is represented as a product of disjoint cycles, where we include all the $1$-cycles of elements of $A$ which $f$ fixes, if any. If $a$ and $b$ occur in the same cycle in this representation for $f$, i.e.,

$$f = ... (a,b_1, ... ,b_k,b,c_1, ... ,c_t) ...,$$ (3.7)

as in (3.5), then in the computation of $W(f)$ this cycle contributes $k + t + 1$. Now consider $(a,b)f$. Since the cycles in (3.7) are disjoint and disjoint cycles commute,

$$(a,b)f = ... (a,b) (a,b_1 ... ,b_k,b,c_1, ..., c_t) ...$$

since neither $a$ nor $b$ can occur in any factor of $f$ other than $(a,b_1, ... ,b_k,b,c_1, ... ,c_t)$. So that using (3.5) $(a,b)$ cancels out and we find that $(a,b)f = ... (b,c_1, ... ,c_t) (a,b_1, ... ,b_k) ...$. Since $W((b,c_1, ... ,c_t)(a,b_1, ..., b_k)) = k + t$ but $W(a,b_1, ..., b_k,b,c_1, ..., c_t) = k + t + 1$, we have $W((a,b)f) = W(f) - 1$.

A similar analysis, using (3.6), shows that in the case where a and b occur in different cycles in the representation of $f$, then $W((a,b)f) = W(f) + 1$. (The reader should verify this!) Combining both cases, we have

$$W((a,b)f) = W(f) \pm 1.$$ (3.8)

Now let $f$ be written as a product of m transpositions, say

$$f = (a_1,b_1) (a_2,b_2) ... (a_m,b_m) .$$

Then

$$(a_m,b_m) ... (a_2,b_2) (a_1,b_1) f = 1.$$ (3.9)

Iterating (3.8), together with the fact that $W(1) = 0$, shows using (3.9) that

$$W(f) \pm 1 \pm 1 \pm ... \pm 1 = 0,$$

where there are m terms of the form $\pm 1$. Thus

$$W(f) = \pm 1 \pm 1 ... \pm 1,$$

$m$ times. Note if exactly $p$ are $+$ and $q = m - p$ are $-$ then $m = p + q$ and $W(f) = p - q$. Hence $m \equiv W(f)$ (mod $2$). (WHY?) Thus, $W(f)$ is even if and only $m$ is even and this completes the proof. $\Box$

It now makes sense to state the following definition since we know that the parity is indeed unique.

Definition 3.2.3   A permutation $f \in S_n$ is said to be even if it can be written as a product of an even number of transpositions. Similarly, $f$ is called odd if it can be written as a product of an odd number of transpositions.

We note that if $f$ and $g$ are even permutations then so are $fg$ and $f^{- 1}$ and also the identity permutation is even. Thus the set of all even permutation on $\{1, ... n\}$, denoted by $A_n$, is a subgroup of $S_n$. $A_n$ is called the alternating group. We know that $\vert S_n\vert = n!$. Let us compute $\vert A_n\vert$ .

Suppose $A_n = \{f_1, ..., f_k\}$ so $\vert A_n\vert = k$. Let $t$ be the number of odd permutations so $t + k = n!$. If $g$ is any odd permutation then $f_1g, ..., f_kg$ are certainly all odd permutations and are all distinct, since $f_ig = f_jg$ if and only $i = j$ (see Elementary Property 6). Therefore $k \leq t$. Similarly, if $\{g_1, ..., g_t\}$ designates the set of all odd permutations, and, again, if $g$ is any odd permutation, then $g_1g, ..., g_tg$ are all even and are all distinct. Therefore $t\leq k$. Thus $t = k$ and since $t + k = n!$, $k = A_n = n!/2$.