Even and Odd Permutations

A permutation is said to be an even permutation if it can be expressed as a product of an even number of transpositions, otherwise, it is said to be an odd permutation i.e. it has odd number transpositions.

Theorem 1: A permutation cannot be both even and odd, i.e. if a permutation f is expected as a product of transpositions then the number of transposition is either always even or always odd.

Proof: Let us consider the polynomial A in distinct symbols {x_1},{x_2},...,{x_n}. It is defined as the product of \frac{1}{{2n\left( {n - 1} \right)}} factor of the form {x_i} - {x_j} where i < j.


A = \prod\limits_{i \leqslant j = 1}^n {\left( {{x_i} - {x_j}} \right)}

\begin{gathered} A = \left( {{x_1} - {x_2}} \right)\left( {{x_1} - {x_3}} \right)\left( {{x_1} - {x_4}} \right) \cdots \left( {{x_1} - {x_n}} \right) \\ \,\,\,\,\,\,\,\,\,\,\left( {{x_2} - {x_3}} \right)\left( {{x_2} - {x_4}} \right)\left( {{x_2} - {x_5}} \right) \cdots \left( {{x_2} - {x_n}} \right) \\ \,\,\,\,\,\,\,\,\,\,\left( {{x_3} - {x_4}} \right) \cdots \left( {{x_3} - {x_n}} \right) \cdots \cdots \cdots \left( {{x_{n - 1}} - {x_n}} \right) \\ \end{gathered}

Consider now any permutation P on n symbol 1,2,3, \ldots ,n. By AP we mean the polynomial obtained by permuting the subscript 1,2,3, \ldots ,nof the {x_i} as prescribed by P.

For Example, taking n = 4, we have

A = \left( {{x_1} - {x_2}} \right)\left( {{x_1} - {x_3}} \right)\left( {{x_1} - {x_4}} \right)\left( {{x_2} - {x_3}} \right)\left( {{x_2} - {x_4}} \right)\left( {{x_3} - {x_4}} \right)

If P\left( {1\,3\,4\,2} \right), then

AP = \left( {{x_3} - {x_1}} \right)\left( {{x_3} - {x_4}} \right)\left( {{x_3} - {x_2}} \right)\left( {{x_1} - {x_4}} \right)\left( {{x_1} - {x_2}} \right)\left( {{x_4} - {x_3}} \right)

In particular if P = \left( {1\,2} \right), we have

AP = \left( {{x_2} - {x_1}} \right)\left( {{x_2} - {x_3}} \right)\left( {{x_2} - {x_4}} \right)\left( {{x_1} - {x_3}} \right)\left( {{x_1} - {x_4}} \right)\left( {{x_3} - {x_4}} \right) = - A

This shows that the effect of a transposition on Ais to change sign of A.

In general a transposition \left( {i,j} \right),\,\,i < jhas the following effects on A.
(i). Any factor which involves neither the suffix i nor j remains unchanged.
(ii). The single factor \left( {{x_i} - {x_j}} \right) changes its sign.
(iii). The remaining factors which involves either the suffix i or j but not both can be grouped into pairs of products,  \pm \left( {{x_m} - {x_i}} \right)\left( {{x_m} - {x_j}} \right) where m \ne i or j and such a product remains unaltered when {x_i} and {x_j} are interchanged.

Hence the net effect of transposition i,j on A is to change its sign, i.e. A operated upon by transposition \left( {i,j} \right)gives  - A.

Now the permutation P considered as a product of s transposition when operated upon A gives {\left( { - 1} \right)^s}A so that AP = {\left( { - 1} \right)^s}A and considered as a product of t transposition gives {\left( { - 1} \right)^t}A so that AP = {\left( { - 1} \right)^t}A.


{\left( { - 1} \right)^s}A = {\left( { - 1} \right)^t}A

{\left( { - 1} \right)^s} = {\left( { - 1} \right)^t}

Now this equation will hold only if s and t are either both even or both odd. Hence this completes the theorem.

Theorem 2: Of the n{!} permutations on n symbols, \frac{1}{{2n!}} are even permutations and \frac{1}{{2n!}} are odd permutations.

Proof: Let the even permutation be {e_1},{e_2}, \ldots ,{e_m} and the odd permutations be {o_1},{o_2}, \ldots ,{o_k}. Then m + k = n{!}

Now let t be any transposition. Since t is evidently an odd permutation, we see that t{e_1},t{e_2}, \ldots ,t{e_m} are odd permutations and that t{o_1},t{o_2}, \ldots ,t{o_k} are even permutations. Since an odd permutation is never an even permutation, we have for anyi = 1,2, \ldots ,m; j = 1,2, \ldots ,k. Furthermore, if t{e_i} = t{e_j}, then {e_i} = {e_j} by cancellation law. Similarly t{o_i} \ne t{o_j} if i \ne j.

It follows that all of the m even permutations must appear in the list t{o_1},t{o_2}, \ldots ,t{o_k} which are all distinct so that their number is m. Similarly, all of the k odd permutations must be in the list t{e_1},t{e_2}, \ldots ,t{e_m} which are all distinct as shown above and their number of k.

Hence m = k = \frac{1}{{2n!}}

(1). A cyclic containing an odd number of symbols is even permutation, whereas a cycle containing an even number of symbols is an odd permutation, since a permutation on n symbols can be expressed as a product of \left( {n - 1} \right) transpositions.
(2). Inverse of an even permutation is an even permutation and the inverse of an odd permutation is an odd permutation.
(3). Product of two permutations is an even permutation if either both the permutations are even or both are odd and the product is an odd permutation if one permutation is odd and the other even.