Since \((1, 3)(1, 2) = (1, 2)(2, 3)\) ( \(=(1, 2, 3)\) ), we see that the representation of a permutation (even a cycle) as a product of transpositions is not necessarily unique. Since \[(1, 3) (1, 4) (1, 2) (3, 4) (3, 2) = (1, 4)(1, 3)(1, 2) \text{ ($=(1, 2, 3, 4)$)},\] we see that even the number of transpositions needed to factor a cycle is not necessarily unique. There is, nevertheless, something unique about the factorization, namely, whether the number of transpositions needed is even or odd. We proceed to state this result precisely, and to prove it.

Assume, for simplicity of notation, that \(k = 4\) . Let \(f\) be the polynomial (in four variables \(t_1\) , \(t_2\) , \(t_3\) , \(t_4\) ) defined by \[f(t_1, t_2, t_3, t_4) = (t_1 - t_2)(t_1 - t_3)(t_1 - t_4)(t_2 - t_3)(t_2 - t_4)(t_3 - t_4).\] (In the general case \(f\) is the product of all the differences \(t_i - t_j\) , with \(1 \leq i < j \leq k\) .) Each permutation \(\pi\) in \(\mathcal{S}_4\) converts \(f\) into a new polynomial, denoted by \(\pi f\) ; by definition \[(\pi f)(t_1, t_2, t_3, t_4) = f(t_{\pi(1)}, t_{\pi(2)}, t_{\pi(3)}, t_{\pi(4)}).\] In words: to obtain \(\pi f\) , replace each variable in \(f\) by the one whose subscript is obtained by allowing \(\pi\) to act on the subscript of the given one. If, for instance, \(\pi = (2, 4)\) , then \[(\pi f)(t_1, t_2, t_3, t_4) = (t_1 - t_4)(t_1 - t_3)(t_1 - t_2)(t_4 - t_3)(t_4 - t_2)(t_3 - t_2).\] If \(\sigma = (1, 3, 2, 4)\) , so that \(\sigma \pi = (1, 3, 2)\) , then both \((\sigma(\pi f))(t_1, t_2, t_3, t_4)\) and \(((\sigma \pi) f)(t_1, t_2, t_3, t_4)\) are equal to \[(t_3 - t_1)(t_3 - t_2)(t_3 - t_4)(t_1 - t_2)(t_1 - t_4)(t_2 - t_4).\] These computations illustrate, and indicate the proofs of, three important facts. (1) For every permutation \(\pi\) , the factors of \(\pi f\) are the same as the factors of \(f\) , except possibly for sign and order ; consequently \(\pi f = f\) or else \(\pi f = -f\) . The permutation \(\pi\) is called even if \(\pi f = f\) and odd if \(\pi f = -f\) . The signum (or sign ) of a permutation \(\pi\) , denoted by \(\text{sgn } \pi\) , is \(+1\) or \(-1\) according as \(\pi\) is even or odd, so that we always have \(\pi f = (\operatorname{sgn} \pi) f\) . The fact that \(\pi\) is even, or odd, is sometimes expressed by saying that the parity of \(\pi\) is even, or odd, respectively. (2) If \(\pi\) is a transposition, then \(\operatorname{sgn} \pi = -1\) , or, equivalently, every transposition is odd. The proof is the obvious generalization of the following reasoning about the special example \((2, 4)\) . Exactly one factor of \(f\) contains both \(t_2\) and \(t_4\) , and that one changes sign in the passage from \(f\) to \(\pi f\) . If a factor contains neither \(t_2\) nor \(t_4\) , it stays fixed. The factors containing only one of \(t_2\) and \(t_4\) come in pairs (such as the pair \((t_2 - t_3)\) and \((t_3 - t_4)\) , or the pair \((t_1 - t_2)\) and \((t_1 - t_4)\) ). Each factor in such a pair goes into the other factor, except possibly that its sign may change; if it changes for one factor, it will change for its mate. (3) If \(\sigma\) and \(\tau\) are permutations then \((\sigma \tau) f = \sigma (\tau f)\) ; consequently \(\sigma \tau\) is even if and only if \(\sigma\) and \(\tau\) have the same parity. Observe that \(\operatorname{sgn} (\sigma \tau) = (\operatorname{sgn} \sigma)(\operatorname{sgn} \tau)\) .

It follows from (2) and (3) that a product of a bunch of transpositions is even if and only if there are an even number of them, and it is odd otherwise. (Note, in particular, by looking at the proof of Section: Cycles , Theorem 2, that a \(p\) -cycle is even if and only if \(p\) is odd; in other words, if \(\sigma\) is a \(p\) -cycle, then \(\operatorname{sgn} \sigma = (-1)^{p+1}\) .) Conclusion: no matter how a permutation \(\pi\) is factored into transpositions, the number of factors is always even (this is the case if \(\pi\) is even), or else it is always odd (this is the case if \(\pi\) is odd).

The product of two even permutations is even; the inverse of an even permutation is even; the identity permutation is even. These facts are summed up by saying that the set of all even permutations is a subgroup of \(\mathcal{S}_k\) ; this subgroup (to be denoted by \(\mathcal{A}_k\) ) is called the alternating group of degree k .

EXERCISES