7
$\begingroup$

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

  • 0
    There are three well explained answers to this question on http://en.wikipedia.org/wiki/Parity_of_a_permutation2010-09-16
  • 1
    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.2010-09-16
  • 1
    The identity permuation is even.2010-09-16
  • 3
    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.2010-09-16
  • 0
    See my answer here: http://math.stackexchange.com/questions/46403/alternative-proof-that-the-parity-of-permutation-is-well-defined/46476#464762012-02-18

4 Answers 4

12

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.

  • 1
    I've often wondered why people use that polynomial instead of simply the integer $\prod_{1\le i2010-09-16
  • 0
    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.2010-09-16
  • 3
    @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.2010-09-16
  • 1
    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.2011-10-14
  • 0
    @JoelCohen- good point! You have totally demystified the inversion-pairs definition for me.2012-02-19
11

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

  • 1
    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.2010-09-16
  • 0
    @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.2010-09-16
  • 0
    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]2010-09-17
  • 0
    @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.2010-09-17
  • 0
    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?2010-09-17
  • 0
    @Douglas: Say the objects are 1,2,..n. Then the number of inversion pairs in a permutation pi, is the number of pairs (i,j) such that i < j but pi(i) > pi(j). So it is well defined and easy to compute.2010-09-17
  • 0
    @Douglas: I looked at the paper by Bartlow that you list and I don't see how "the same problem arises" there. There is a place where Bartlow writes "Of course, $\alpha$ cannot be in both classes", but the classes there are the two sets of permutations in $S_n$ in which the number of disjoint cycles is even or is odd. (Bartlow unfortunately often writes "cycles" when "disjoint cycles" is meant.) He is not ignoring the kind of error you mention in your answer.2012-02-18
  • 0
    You're right, I'll fix my answer.2012-02-18
  • 0
    What are $t_{n}$ and $s_{m}$? Specific transpositions? What is $\sigma^{-1}$?2015-03-03
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.

  • 0
    Another general fact about Coxeter groups (the first proposition at http://qchu.wordpress.com/2010/07/08/the-strong-exchange-condition/) also implies that this definition agrees with the definition by inversion number.2010-09-16
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.

  • 0
    Excellent answer. Gallian uses this argument.2013-01-09