every permutation is either even or odd,but not both

How we can show every permutation is either even or odd,but not both......I can't arrive at a proof for this ..... Can anybody give me the proof...

Thanks in advance...

Solution 1:

One way is to define the sign of a permutation $\sigma$ using the polynomial $\Delta = \Pi (x_i-x_j)$ with $1\le i < j \le n$.

It is easy to see that $\sigma(\Delta) = \Pi (x_{\sigma(i)}-x_{\sigma(j)})$ satisfies $\sigma(\Delta)=\pm\Delta$. Now define the sign by $sign(\sigma)=\frac{\Delta}{\sigma(\Delta)}$

With a little more work you can show that this function is a homomorphism of groups, and that on transpositions it return -1. Therefore, if $\sigma=\tau_1\cdots\tau_k$ is a way to write $\sigma$ as a product of transpositions, we have $sign(\sigma)=(-1)^k$ and so for even permutations (permutations whose sign is 1) k must always be even, and for odd permutations (whose sign is -1) it must always be odd.

Solution 2:

There is a proof given here: An Historical Note on the Parity of Permutations, T. L. Bartlow, American Mathematical Monthly Vol. 79, No. 7 (Aug. - Sep., 1972), pp. 766-769.

Here's an outline of Bartlow's proof (it matches the proof given in Ted's answer).

• Divide $S_n$ (the symmetric group on $n$ letters) into two classes according to the parity of the number of cycles (fixed points counted as 1-cycles) in their unique decomposition into disjoint cycles. [E.g. in $S_5$ the permutation $(1,2,3)(4)(5)$ has 3 disjoint cycles.]

• These classes are thus well-defined and disjoint, and the identity permutation belongs to exactly one class (since it decomposes into $n$ disjoint cycles, and $n$ is either even or odd).

• He showed that by multiplying a permutation in one class by a transposition, will result in a permutation in the other class.

• He concludes that the two classes are, in fact, the sets of even and odd permutations in $S_n$.

(NB. In earlier versions of this answer I incorrectly labelled this proof as faulty. In fact, this is an excellent proof, and doesn't rely on any auxiliary functions or unrelated concepts.)

I claim all three "proofs" of this result (currently) on wikipedia are incomplete. Let's begin with the observation that, assuming that identity permutation is not an odd permutation, then the result follows fairly easily.

Theorem: Assuming the identity permutation is not an odd permutation, then all permutations are either even xor odd.

Proof: Let $\sigma$ be both an even and an odd permutation. Then there exists transpositions $t_i$ and $s_j$ such that \[\sigma=t_1 \circ t_2 \circ \cdots \circ t_k=s_1 \circ s_2 \circ \cdots \circ s_m\] where $k$ is even and $m$ is odd. Note that \[\sigma^{-1}=s_m \circ s_{m-1} \circ \cdots \circ s_1.\]

Then the identity permutation $\sigma \circ \sigma^{-1}$ is the odd permutation \[t_1 \circ t_2 \circ \cdots \circ t_k \circ s_m \circ s_{m-1} \circ \cdots \circ s_1,\] giving a contradiction. Thus completing the proof of the theorem.

The problem is that we cannot just assume that the identity permutation not an odd permutation (yes, it's an even permutation, but what's to stop it being an odd permutation also?), it does not follow from the definition and it is the base case of the "induction". To prove it, we need to show that the identity permutation cannot be decomposed into an odd number of transpositions (without using the theorem itself).

However, we can deduce from the above theorem that either (a) all permutations are both even and odd or (b) all permutations are either even xor odd.

On wikipedia: Proof 1 states that the identity permutation is an even permutation (which it is) then assumes that the identity permutation is not also an odd permutation (this is analogous to assuming that a closed set is not an open set). Proof 2 essentially says that we can switch signs by multiplying by a transposition (which is fine, if you know a priori that there exists some permutation that is not even or not odd). Proof 3 neglects the possibility that an even-length word might be equal to an odd-length word.

Keith Conrad also gave a proof that the identity permutation is not an odd permutation here. It is almost a page long (and is the majority of the proof of the result in question).

Solution 3:

It is enough to show that the product of an odd number of transpositions cannot be the identity.

Every permutation of a finite set $S$ is a unique product of disjoint cycles in which every element of $S$ occurs exactly once (where we include fixed points as 1-cycles). Let $p$ be any permutation of $S$, let $(ij)$ be a transposition ($i,j \in S$), and let $q=p \cdot (ij)$. It is easy to check that if $i$ and $j$ are in the same cycle in $p$, then that cycle splits into two in $q$; if $i$ and $j$ are in different cycles in $p$, then those cycles merge into one in $q$. Cycles of $p$ not containing either $i$ or $j$ remain the same in $q$. Therefore, $q$ has either one more or one less cycle than $p$ does.

Now let $t$ be any product of an odd number of transpositions. Then by the above, multiplying any permutation by $t$ changes the parity of the number of cycles in the permutation. Therefore $t$ cannot be the identity.

Solution 4:

This is overkill, but it follows from general facts about Coxeter groups as outlined here. In particular, it follows from the fact that $S_n$ has presentation $s_i^2 = 1, (s_i s_{i+1})^3 = 1, s_i s_j = s_j s_i, |i - j| \ge 2$ (which follows from the faithfulness of the geometric representation) that the homomorphism $s_i \to -1$ is well-defined.