3.4 Signs of permutations
The notion of the sign (aka signature) of a permutation is a simple consequence of that of its length; moreover, it is rather well-known, due to its role in the definition of a determinant. Thus we will survey its properties quickly and without proofs.
3.4.1 Definition and basic properties
Let \(n \in \mathbb {N}\). The sign of a permutation \(\sigma \in S_n\) is defined to be the integer \((-1)^{\ell (\sigma )}\).
It is denoted by \((-1)^{\sigma }\) or \(\operatorname {sgn}(\sigma )\) or \(\operatorname {sign}(\sigma )\) or \(\varepsilon (\sigma )\). It is also known as the signature of \(\sigma \).
Let \(n \in \mathbb {N}\).
(a) The sign of the identity permutation \(\operatorname {id} \in S_n\) is \((-1)^{\operatorname {id}} = 1\).
(b) For any two distinct elements \(i\) and \(j\) of \([n]\), the transposition \(t_{i,j} \in S_n\) has sign \((-1)^{t_{i,j}} = -1\).
(c) For any positive integer \(k\) and any distinct elements \(i_1, i_2, \ldots , i_k \in [n]\), the \(k\)-cycle \(\operatorname {cyc}_{i_1, i_2, \ldots , i_k}\) has sign \((-1)^{\operatorname {cyc}_{i_1, i_2, \ldots , i_k}} = (-1)^{k-1}\).
(d) We have \((-1)^{\sigma \tau } = (-1)^{\sigma } \cdot (-1)^{\tau }\) for any \(\sigma \in S_n\) and \(\tau \in S_n\).
(e) We have \((-1)^{\sigma _1 \sigma _2 \cdots \sigma _p} = (-1)^{\sigma _1} (-1)^{\sigma _2} \cdots (-1)^{\sigma _p}\) for any \(\sigma _1, \sigma _2, \ldots , \sigma _p \in S_n\).
(f) We have \((-1)^{\sigma ^{-1}} = (-1)^{\sigma }\) for any \(\sigma \in S_n\). (The left hand side here has to be understood as \((-1)^{(\sigma ^{-1})}\).)
(g) We have
(The product sign “\(\prod _{1 \leq i {\lt} j \leq n}\)” means a product over all pairs \((i,j)\) of integers satisfying \(1 \leq i {\lt} j \leq n\). There are \(\binom {n}{2}\) such pairs.)
(h) If \(x_1, x_2, \ldots , x_n\) are any elements of some commutative ring, and if \(\sigma \in S_n\), then
Most of this follows easily from what we have proved above, but here are references to complete proofs:
(a) This is [ Grinbe15 , Proposition 5.15 (a) ] , and follows easily from \(\ell (\operatorname {id}) = 0\).
(d) This is [ Grinbe15 , Proposition 5.15 (c) ] , and follows easily from Corollary 3.85 (a).
(b) This is [ Grinbe15 , Exercise 5.10 (b) ] , and follows easily from the fact that a permutation has even length if and only if it has an even number of even-length cycles.
(c) This is [ Grinbe15 , Exercise 5.17 (d) ] , and follows easily from the fact that a cycle of length \(\ell \) has exactly \(\ell - 1\) inversions, combined with Proposition 3.110 (d).
(e) This is [ Grinbe15 , Proposition 5.28 ] , and follows by induction from Proposition 3.110 (d).
(f) This is [ Grinbe15 , Proposition 5.15 (d) ] , and follows easily from Proposition 3.110 (d) or from Proposition 3.54.
(h) This is [ Grinbe15 , Exercise 5.13 (a) ] (or, rather, the straightforward generalization of [ Grinbe15 , Exercise 5.13 (a) ] to arbitrary commutative rings). Each factor \(x_{\sigma (i)} - x_{\sigma (j)}\) on the left hand side appears also on the right hand side, albeit with a different sign if \((i,j)\) is an inversion of \(\sigma \). Thus, the products on both sides agree up to a sign, which is precisely \((-1)^{\ell (\sigma )} = (-1)^{\sigma }\).
(g) This is [ Grinbe15 , Exercise 5.13 (c) ] , and is a particular case of Proposition 3.110 (h).
3.4.2 The sign homomorphism
Let \(n \in \mathbb {N}\). The map
is a group homomorphism from the symmetric group \(S_n\) to the order-\(2\) group \(\{ 1, -1\} \). (Of course, \(\{ 1, -1\} \) is a group with respect to multiplication.)
This map is known as the sign homomorphism.
3.4.3 Even and odd permutations
Let \(n \in \mathbb {N}\). A permutation \(\sigma \in S_n\) is said to be
even if \((-1)^{\sigma } = 1\) (that is, if \(\ell (\sigma )\) is even);
odd if \((-1)^{\sigma } = -1\) (that is, if \(\ell (\sigma )\) is odd).
- σ.IsEven = (Equiv.Perm.sign σ = 1)
- σ.IsOdd = (Equiv.Perm.sign σ = -1)
Every permutation \(\sigma \) is either even or odd.
\((-1)^{\sigma } \in \{ 1, -1\} \).
A permutation cannot be both even and odd.
\(1 \neq -1\).
The identity permutation is even.
By Proposition 3.110 (a), \((-1)^{\operatorname {id}} = 1\).
A transposition of two distinct elements is an odd permutation.
By Proposition 3.110 (b), \((-1)^{t_{i,j}} = -1\).
A permutation \(\sigma \) is even if and only if \(\sigma \in A_n\).
This follows directly from the definition of \(A_n\) as the kernel of the sign homomorphism: \(\sigma \in A_n\) iff \(\operatorname {sign}(\sigma ) = 1\) iff \(\sigma \) is even.
A permutation \(\sigma \) is odd if and only if \(\sigma \notin A_n\).
3.4.4 The alternating group
Let \(n \in \mathbb {N}\). The set of all even permutations in \(S_n\) is a normal subgroup of \(S_n\).
This subgroup is known as the \(n\)-th alternating group (commonly called \(A_n\)).
The set of all even permutations in \(S_n\) is the kernel of the group homomorphism \(S_n \to \{ 1, -1\} \) from Corollary 3.111. Thus, it is a normal subgroup of \(S_n\) (since any kernel is a normal subgroup).
3.4.5 Counting even and odd permutations
Let \(n \geq 2\). Then,
The symmetric group \(S_n\) contains the simple transposition \(s_1\) (since \(n \geq 2\)). If \(\sigma \in S_n\), then by Prop. 3.110 (d), we get
where the underbrace uses Prop. 3.110 (b). Hence, a permutation \(\sigma \in S_n\) is even if and only if \(\sigma s_1\) is odd. Hence, the map
is well-defined. This map is furthermore a bijection (since \(S_n\) is a group). Thus, the bijection principle yields
Both sides of this equality must furthermore equal \(n!/2\), since they add up to \(|S_n| = n!\). This proves Corollary 3.120. (See [ Grinbe15 , Exercise 5.4 ] for details.)
As a consequence of Corollary 3.120, we see that
(Indeed, the sum \(\sum _{\sigma \in S_n} (-1)^{\sigma }\) can be rewritten as
since the addends corresponding to the even permutations \(\sigma \in S_n\) are equal to \(1\) whereas the addends corresponding to the odd permutations \(\sigma \in S_n\) are equal to \(-1\).)
For \(n \geq 2\), \(\displaystyle \sum _{\sigma \in S_n} (-1)^{\sigma } = 0\).
This is a restatement of 11.
3.4.6 Sign for permutations of arbitrary finite sets
We note that the sign can be defined not only for a permutation \(\sigma \in S_n\), but also for any permutation of any finite set \(X\) (even if the set \(X\) has no chosen total order on it, as the set \([n]\) has). Here is one way to do so:
Let \(X\) be a finite set. We want to define the sign of any permutation of \(X\).
Fix a bijection \(\phi : X \to [n]\) for some \(n \in \mathbb {N}\). (Such a bijection always exists, since \(X\) is finite.) For every permutation \(\sigma \) of \(X\), set
Here, the right hand side is well-defined, since \(\phi \circ \sigma \circ \phi ^{-1}\) is a permutation of \([n]\). Now:
(a) This number \((-1)_{\phi }^{\sigma }\) depends only on the permutation \(\sigma \), but not on the bijection \(\phi \). (In other words, if \(\phi _1\) and \(\phi _2\) are two bijections from \(X\) to \([n]\), then \((-1)_{\phi _1}^{\sigma } = (-1)_{\phi _2}^{\sigma }\).)
Thus, we shall denote \((-1)_{\phi }^{\sigma }\) by \((-1)^{\sigma }\) from now on. We refer to this number \((-1)^{\sigma }\) as the sign of the permutation \(\sigma \in S_X\). (When \(X = [n]\), this notation does not clash with Definition 3.109, since we can pick the bijection \(\phi = \operatorname {id}\) and obtain \((-1)_{\phi }^{\sigma } = (-1)^{\operatorname {id} \circ \sigma \circ \operatorname {id}^{-1}} = (-1)^{\sigma }\).)
(b) The identity permutation \(\operatorname {id} : X \to X\) satisfies \((-1)^{\operatorname {id}} = 1\).
(c) We have \((-1)^{\sigma \tau } = (-1)^{\sigma } \cdot (-1)^{\tau }\) for any two permutations \(\sigma \) and \(\tau \) of \(X\).