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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.