Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone fill the gap in the following proof, that the parity of the number of adjacent transpositions which yield a permutation $\pi$ is fixed ?

In a course I took this was done in the following way: Let $\pi=\tau_1\ldots\tau_n = \sigma_1\ldots\sigma_m$ be two different ways to write $\pi$ using adjacent transposition. Since we know, that a the number of inversions of $\pi$, $\mathrm{inv} (\pi)$, composed with an adjacent transposition, $(i,i+1)$, is $\mathrm{inv} (\pi) \pm 1$ (in short: $\mathrm{inv} (\pi \circ (i,i+1))=\mathrm{inv} (\pi) \pm 1$), it thus follows [this is the step that I don't understand! Why does it follow], that $n+m \equiv 0 \mod 2$ which is equivalent to $n \equiv m \mod 2$, so the parity is the same.

Are there also different proofs for this fact?

share|improve this question
1  
You can have a look here math.stackexchange.com/questions/46403/… for different proofs. –  Martin Sleziak Sep 3 '11 at 7:20

1 Answer 1

up vote 2 down vote accepted

You can build up $\tau_1\dotsc\tau_n$ one by one from the identity. The identity has zero inversions. If you compose it with $\tau_1$, you now have an odd number of inversions. Every time you tack on another $\tau_i$, you change the parity of the number of inversions, since you either add or remove one inversion. So the parity of the number of inversions is the parity of the number of adjacent transpositions composed. Since the parity of the number of inversions depends only on the end result $\pi$, it follows that the parity of the number of adjacent transpositions composed depends only on $\pi$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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