These comments are designed to help with the proof that: If a permutation, say f, may be represented as an even number of transpositions then f can ONLY be represented by an even number of transpositions and if f may be represented as an odd number of transpositions then f can ONLY be represented by an odd number of transpositions. (As noted in class the representation can not be unique as we can always add (a,b)(a,b)).

We start by representing f as a product of disjoint cycles. This is unique up to order. Then we get an integer W(f) by representing each cycle as a product of transpositions in the “canonical” way seen on page 37, formula 3.3.

Next we consider a new permutation (a,b)f . We do a calculation based on the fact that (a,b)f will differ from f in at most two cycles and find that:

W((a,b)f) = W(f)1

(This last calculation is not shown here but is based on formulas 3.5 and 3.6 in the text. You should be able to check the correctness of these formulas).

We now consider f as ANY product of transpositions.

f=(a₁,b₁)(a₂,b₂)...(a_m,b_m) so that

(a_m,b_m) ... (a₂,b₂) (a₁,b₁)f = (1)

Note that (1) is the identity for permutations.

Also note that I’ve used the following two elementary facts:

· A transposition is its own inverse.

· The inverse of ab...z is z^-1...b^-1a^-1

W((a₁,b₁)f)= W(f)1

Let (a₁,b₁)f = g so that W((a₁,b₁)f )= W(g), and consider (a₂,b₂)g.

W((a₂,b₂)g)=W(g) 1 = W(f) 1 1

Thus W((a_m,b_m) ... (a₂,b₂) (a₁,b₁)f)= W(f) 1 1 ... 1 (m signs) = W(1) = 0

Now let p = number of plus signs and let q=m-p be the number of minus signs. So W(f)+p-q=0 . Thus W(f) is odd iff p-q is odd; and W(f) is even iff p-q is even. Also oserve that: m=p+q=(p-q)+2q.

We now put all this together by calculating mod 2. In this next expression(and below), by “” we mean “ mod 2”. W(f)p-qp+qm , where the first congruence was proven in the paragraph above.

Since W(f)m we’ve shown that any representation of f as m transpositions will have the same parity as W(f), which is uniquely determined by f itself. QED