# 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...

-
There are three well explained answers to this question on en.wikipedia.org/wiki/Parity_of_a_permutation –  alext87 Sep 16 '10 at 10:44
Unless I'm having a particularly daft day... I question the validity of the first two proofs on wikipedia: they don't seem to eliminate the possibility that every permutation is both even and odd. –  Douglas S. Stones Sep 16 '10 at 10:56
The identity permuation is even. –  alext87 Sep 16 '10 at 11:19
Depends on your definition of parity of the permutation. If you simply define it as the parity of number of inversion pairs, this is a no-brainer. –  Aryabhata Sep 16 '10 at 18:26
See my answer here: math.stackexchange.com/questions/46403/… –  Grumpy Parsnip Feb 18 '12 at 23:51

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).

-
I think that the Wikipedia article is technically correct, because it is explicit that the well-definedness of the transposition-based definition is assumed (with a reference). However, I cannot see the point of stating a proof of the equivalence of the inversion-based definition and the transposition-based definition in the article without stating a proof of the well-definedness of the latter. As is often the case with Wikipedia, I do not know whom the article is intended for. –  Tsuyoshi Ito Sep 16 '10 at 12:32
@Douglas: The wiki page has this definition: "Parity of permutation is the parity of the number of inversion pairs". This trivially implies that a permutation cannot be both even and odd. –  Aryabhata Sep 16 '10 at 18:26
A permutation can be written as the composition of transpositions in an infinite number of ways... how do you check all infinity of them? [besides, the alarm bells should be going off: you're claiming that the OP's theorem is trivial from the definition] –  Douglas S. Stones Sep 17 '10 at 1:37
@Douglas: What I am claiming is that it depends on the definition. OP never provided one. The wiki page provided one in terms of inversion pairs (transpositions was proven equivalent) and so is probably correct (I didn't go through the whole thing) in assuming it is either even or odd, but not both. The question asked by OP is trivial under the definition in terms of inversion pairs. I do agree, if we go via transpositions, we have work to do. –  Aryabhata Sep 17 '10 at 5:01
Hmm... I equated "inversion pairs" with "transpositions" in the earlier comment (which is incorrect). But there's still an infinite number of ways to write a permutation as the composition of inversion pairs. I'm might be missing something obvious here, but why is this now a no-brainer? –  Douglas S. Stones Sep 17 '10 at 5:39

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.

-
I've often wondered why people use that polynomial instead of simply the integer $\prod_{1\le i<j\le n} (i-j)$, which seems to me more elementary than using a polynomial in several variables. –  lhf Sep 16 '10 at 13:56
I can't see a reason myself. It might be because algebraists are used to working with symmetric polynomials, and this is a private case. –  Gadi A Sep 16 '10 at 14:08
@lhf: The symmetric group cannot act on that integer per se; it acts on the form in which you have expressed it! Thus you are computing with it as if it were a polynomial in which the indexes are names for the variables. –  whuber Sep 16 '10 at 15:14
I think this is proof is really interesting because it's not very difficult and provides an easy way to see that the definition with inversion pairs is equivalent to the one with transpositions. –  Joel Cohen Oct 14 '11 at 12:03
@JoelCohen- good point! You have totally demystified the inversion-pairs definition for me. –  Ben Blum-Smith Feb 19 '12 at 0:15

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.

-
Another general fact about Coxeter groups (the first proposition at qchu.wordpress.com/2010/07/08/the-strong-exchange-condition) also implies that this definition agrees with the definition by inversion number. –  Qiaochu Yuan Sep 16 '10 at 19:49

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.

-
Excellent answer. Gallian uses this argument. –  Stefan Smith Jan 9 '13 at 14:42