3
$\begingroup$

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?

  • 1
    You can $h$ave a look here http://math.stackexchange.com/questions/464$0$3/alternative-proof-that-the-parity-of-permutation-is-well-defined for different proofs.2011-09-03

1 Answers 1

2

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