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 an odd number of transpositions.
Theorem 1: A permutation cannot be both even and odd, i.e. if a permutation is expected as a product of transpositions then the number of transpositions is either always even or always odd.
Proof: Let us consider the polynomial in distinct symbols
. It is defined as the product of
factor of the form
where
.
Thus
Now consider any permutation on
symbol
. By
we mean the polynomial obtained by permuting the subscript
of the
as prescribed by
.
For example, taking , we have
If , then
In particular if , we have
This shows that the effect of a transposition on is to change the sign of
.
In general, a transposition has the following effects on
.
(i) Any factor which involves neither the suffix nor
remains unchanged.
(ii) The single factor changes its sign.
(iii) The remaining factors which involve either the suffix or
but not both can be grouped into pairs of products,
where
or
and such a product remains unaltered when
and
are interchanged.
Hence the net effect of transposition on
is to change its sign, i.e.
operated upon by transposition
gives
.
Now the permutation is considered a product of
transposition when operated upon
and gives
so that
and is considered a product of
transposition when it gives
so that
.
Hence
Now this equation will hold only if and
are either both even or both odd. Hence this completes the theorem.
Theorem 2: Of the permutations on
symbols,
are even permutations and
are odd permutations.
Proof: Let the even permutations be and the odd permutations be
. Then
Now let be any transposition. Since
is evidently an odd permutation, we see that
are odd permutations and that
are even permutations. Since an odd permutation is never an even permutation, we have for any
;
. Furthermore, if
, then
by cancellation law. Similarly
if
.
It follows that all of the even permutations must appear in the list
, which are all distinct so that their number is
. Similarly, all of the
odd permutations must be in the list
, which are all distinct as shown above and their number of
.
Hence
NOTE:
(1) A cyclic containing an odd number of symbols is an even permutation, whereas a cycle containing an even number of symbols is an odd permutation, since a permutation on symbols can be expressed as a product of
transpositions.
(2) The inverse of an even permutation is an even permutation and the inverse of an odd permutation is an odd permutation.
(3) The 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.