1

I am trying to understand this lemma.

I'll use variables $a$ and $b$ in the same way they are used in the linked proof.

First we write down the identity permutation as a composition of transpositions.

Then, take one of the transpositions which itself is an identity permutation (meaning no inversions) and compose it with another transposition. This adds or removes an odd number of inversions. As we keep composing transpositions, the number of inversions will vary like this: $0$ + odd number - odd number + odd number .... + $0 = 0$. Since $a$ and $b$ switch places each time we apply a new transposition, it prevents adding/subtracting an odd number of inversions more than once in a row.

Does it make sense so far?

edit:

Lemma: If the identity permutation is written as a composition of transpositions, then that composition must use an even number of transpositions.

Passport
  • 25
  • 1
    Hi, it would be best if you included the lemma itself here in text, so that people don't hae to search for it. I am having trouble finding the statement of the lemma in the wall of text. – Caleb Stanford Nov 10 '14 at 00:33

0 Answers0