0
$\begingroup$

Consider $i = \pi_a \pi_{a-1}\cdots \pi_2\pi_1 $ where $\pi_i$ are transpositions and $i$ is the identity permutation. My book claims $a$ is even and provides a proof based on the number of inversions. We start with $(1)(2)(3)\ldots(n)$. We know that applying $\pi_1$ results in odd number of inversions. As we apply each $\pi_i$, the number of inversions changes by an odd amount. Since the number of inversions at the start and at the end is zero, and since each transposition increases or decreases the number of inversions by an odd amount, the number of transpositions must be even.

There's a fair bit of technical parts to this proof which I understand. But I am having trouble understanding the heart of the argument: $0$ inversions + $k$ times odd number of inversions + $0$ inversions mean even number of transpositions. Can somebody elaborate why is it so, please.

$\endgroup$
1
$\begingroup$

Suppose that $n_1,\ldots,n_k$ are odd numbers. If $k=2m$ is even, we can pair them up: their sum is

$$(n_1+n_2)+(n_3+n_4)+\cdots+(n_{2m-1}+n_{2m})\;.\tag{1}$$

Each of the sums in parentheses is the sum of two odd numbers, so it’s even. Thus, we’re adding $m$ even numbers, and the sum of even numbers is even, so the sum in $(1)$ is even.

If $k=2m+1$ is odd, on the other hand, we end up with one term left over when we pair up the terms: the sum is now

$$\color{crimson}{(n_1+n_2)+(n_3+n_4)+\cdots+(n_{2m-1}+n_{2m})}+n_{2m+1}\tag{2}\;.$$

The red part is still a sum of even numbers, so it’s even, and the whole sum is therefore this even number plus the odd number $n_{2m+1}$. The sum of an even number and an odd number is odd, so the sum in $(2)$ is odd.

Thus, the sum of $k$ odd numbers is even if and only if $k$ is even. In your case you have a sum of odd numbers that must be $0$, since the net change in the number of inversions is $0$. $0$ is an even number, so your sum must have an even number of terms: the sum of an odd number of odd numbers is odd.

$\endgroup$
  • $\begingroup$ This is perfect. Thank you. $\endgroup$ – JJ WQ Nov 7 '16 at 0:41
  • $\begingroup$ @JJWQ: You’re welcome. $\endgroup$ – Brian M. Scott Nov 7 '16 at 0:41
  • $\begingroup$ such a great answer! thanks prof. scott $\endgroup$ – ILoveMath Nov 7 '16 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.