Section 1.2. Permutations 13 Proof. Let α = τ1 · · · τm and β = σ1 · · · σn, where the τ and σ are transpositions, so that αβ = τ1 · · · τmσ1 · · · σn has m + n factors. If α is even, then m is even if α is odd, then m is odd. Hence, m+n is even when m, n have the same parity and αβ is even. Suppose that α is even and β is odd. If αβ were even, then β = α−1(αβ) is even, being a product of evenly many transpositions, and this is a contradiction. Therefore, αβ is odd. Similarly, αβ is odd when α is odd and β is even. Definition. If α Sn and α = β1 · · · βt is a complete factorization into disjoint cycles, then signum α is defined by sgn(α) = (−1)n−t. Theorem 1.6 shows that sgn is well-defined, for the number t is uniquely de- termined by α. Notice that sgn(ε) = 1 for every 1-cycle ε because t = n. If τ is a transposition, then it moves two numbers, and it fixes each of the n 2 other numbers therefore, t = (n 2) + 1 = n 1, and so sgn(τ) = (−1)n−(n−1) = −1. Lastly, observe that if α Sn, then sgn(α) does not change when α is viewed in Sn+1 by letting it fix n +1. If the complete factorization of α in Sn is α = β1 · · · βt, then its complete factorization in Sn+1 has one more factor, namely, the 1-cycle (n + 1). Thus, the formula for sgn(α) in Sn+1 is (−1)(n+1)−(t+1) = (−1)n−t. Theorem 1.13. For all α, β Sn, sgn(αβ) = sgn(α) sgn(β). Proof. If k, 0 and the letters a, b, ci, dj are all distinct, then it is easy to check (FCAA, p. 120) that (a b)(a c1 . . . ck b d1 . . . d ) = (a c1 . . . ck)(b d1 . . . d ) multiplying this equation on the left by (a b) gives (a b)(a c1 . . . ck)(b d1 . . . d ) = (a c1 . . . ck b d1 . . . d ). These equations show that sgn(τα) = sgn(α) for every α Sn, where τ is the transposition (a b). If α Sn has a factorization α = τ1 · · · τm, where each τi is a transposition, then sgn(αβ) = sgn(α) sgn(β) for every β Sn is proved by induction on m (the base step has just been proved). Theorem 1.14. (i) Let α Sn if sgn(α) = 1, then α is even, and if sgn(α) = −1, then α is odd. (ii) A permutation α is odd if and only if it is a product of an odd number of transpositions.
Previous Page Next Page