Even and odd permutationsMarch 7, 2008Let S be a finite set. Recall that any permutation σ ∈ Sym(S) can bewritten as a product of disjoint cycles:σ = γ1γ2· · · γr.Furthermore this expression is unique up to reordering. (Here we don’t allowany γito be the identity permuation.) Recall also that if γ is a cycle of length` > 0, then γ can be written as a product of ` − 1 transpositions.Definition 1 Let σ be a permuation of a finite set S, and write σ as a productof disjoint cycles:σ = γ1γ2· · · γr.ThenN(σ) := (`1− 1) + (`2− 1) + · · · + (`r− 1) = `1+ · · · + `r− r,where `iis the length of γi.Thus if `iis the length of the cycle γiabove, then σ can be written as aproduct of N(σ) transpositions. However, such an expression is not unique, andin fact even the number of transpositions in such an expression is not unique.However, the following is true.Theorem 1 Suppose that σ is written as a product of m transpositionsσ = τ1τ2· · · τm.Then m ≡ N (σ) (mod 2).Since congruence is an equivalence relation, it follows that if σ is also writtenas a product of m0transpositions: σ = τ01τ02· · · τ0m0, then m ≡ m0(mod 2).Theorem 1 follows from the following more suggestive result.Theorem 2 If α and β are permuations of S, thenN(αβ) ≡ N (α) + N (β) (mod 2).1Indeed, note that if τ is a transposition, then N (τ ) = 1. Hence it follows fromTheorem 2 thatN(σ) = N(τ1τ2· · · τm) ≡ 1 + 1 + · · · + 1 ≡ m (mod 2).Note that in fact we only needed to apply Theorem 2 when β was a transposition,but in fact the general case of Theorem 2 follows by induction from this caseanyway. (Hint: write β as a product of transpositions and use the associativelaw.)Let us prepare for the proof of Theorem 2 by means of some calculations.Lemma 1 If γ1and γ2are two cycles with exactly one element in common,then γ1γ2is a cycle of length `1+ `2− 1, where `iis the length of γi.Proof: Actually I think it is convincing enough to compute a typical example:(1 2 3 4)(4 5 6 7) = (1 2 3 4 5 6 7).Lemma 2 If τ is a transposition (a b) and γ is a cycle containing both a andb, then γτ is a product of disjoint cycles γ1γ2, where `1+ `2= ` (the length ofγ).Proof: Again, an example should be convincing:(1 2 3 4 5 6 7 8)(2 5) = (1 2 6 7 8)(3 4 5)Proof of Theorem 2: It suffices to prove the theorem when β is a transpositionτ. Since N (τ ) = 1, we have to prove that N (ατ) ≡ N(α) + 1 (mod ()2).Write α as a product of disjoint cycles α = γ1γ2· · · γr, so by definition, N (α) =`1− 1 + · · · `r− 1.Case 1: τ is disjoint from all the γi.Then ατ = γ1γ2· · · γrτ is a product of disjoint cycles, and so by definition:N(ατ ) = `1− 1 + · · · `r− 1 + (2 − 1) = N(α) + 1.Case 2: τ meets just one of the γi’s, in just one element.We might as well assume that τ meets γrand no other. Then by Lemma 1,γrτ is a cycle γ0rof length of `r+ 1. Then ατ = γ1γ2· · · γr−1γ0ras a product ofdisjoint cycles, soN(ατ ) = `1− 1 + `2− 1 + · · · `r−1− 1 + `0r− 1= `1− 1 + `2− 1 + · · · `r−1− 1 + `r+ 1 − 1= N(α) + 1.2Case 3: τ meets two of the γi’s. Again we may as well assume that it meetsγr−1and γr; necessarily it meets each in exactly one element. Then γ0r:= γrτis a cycle of length `0r= `r+ 1, which now contains τ . Hence γ0r−1:= γr−1γ0risa cycle of length `r−1+ `0r− 1 = `r−1+ `r. Hence ατ = γ01· · · γ0r−1as a productof disjoint cycles, andN(ατ ) = `01− 1 + · · · + `0r−1− 1= `1− 1 · · · + `r−1+ `r− 1= `1− 1 + · · · + `r−1− 1 + `r= N(α) + 1.Case 4: τ meets one of the γi’s in two elements. Thus, we assume thatτ := (a b) where a and b both occur in γi, and we may as well assume thati = r. Then γrτ is a product of two disjoint cycles γ0rγ0r+1, and `0r+ `0r+1= `r.HenceN(ατ ) = `1− 1 + · · · + `0r− 1 + `0r+1− 1= `1− 1 + · · · + `r− 2 = N (α) − 1.Since N(α) − 1 ≡ N(α) + 1 (mod 2), the result holds in this case