3.17 The sign homomorphism
In this section, \(n\) is a positive integer and \([n] = \{ 1,\ldots , n\} \).
Suppose \(A\) and \(B\) are sets. The symmetric difference of \(X\) and \(Y\) is \(A\triangle B = A\setminus B \cup B\setminus A\).
Suppose \(X\) is a set. Then the binary operation \(\triangle \) on the power set \(\mathcal{P}(X)\) gives \(\mathcal{P}(X)\) the structure of an abelian group with \(\emptyset \) as the identity element and with \(A\triangle A = \emptyset \). Moreover, if \(A\) and \(B\) are finite subsets of \(X\), then \(A\triangle B\) is finite, and we have
In particular, if \(|X| {\lt}\infty \), then the map \(s:\mathcal{P}(X)\to \mathbb {Z}/2\mathbb {Z}\) given by \(A\mapsto |A| + 2\mathbb {Z}\) is a group homomorphism.
Exercise.
Let’s write \([n]_2 = \{ T\in \mathcal{P}([n]) : |T| = 2\} \). So \([n]_2\) is the set of all two element subsets of \([n]\). We can write any element of \([n]_2\) uniquely in the form \(\{ i,j\} \) with \(1 \leq i {\lt} j\leq n\). In particular, \([n]_2\) has \(\binom {n}{2} = n(n-1)/2\) elements.
The group \(S_n\) action on \([n]\). So it has an (obvious) action on \(\mathcal{P}([n])\) (by \(\sigma (S) = \{ \sigma (i): i\in S\} \)) and \([n]_2\) is a sub-\(S_n\)-set. So \(S_n\) acts on \([n]_2\).
Suppose \(\sigma \in S_n\). The inversion set of \(\sigma \) is \(\operatorname{\mathrm{Inv}}\sigma = \{ \{ i,j\} \in [n]_2: i {\lt} j\, \& \, \sigma (i) {\gt} \sigma (j)\} \). We set \(\operatorname{\mathrm{inv}}\sigma = |\operatorname{\mathrm{Inv}}\sigma |\) and \(\operatorname{\mathrm{sgn}}\sigma = (-1)^{\operatorname{\mathrm{inv}}\sigma }\).
Suppose \(\sigma ,\tau \in S_n\). Then
Suppose \(1 \leq i {\lt} j\leq n\). We have \(\{ i,j\} \in \operatorname{\mathrm{Inv}}\sigma \tau \) if and only if \(\sigma \tau (j) {\lt} \sigma \tau (i)\). This happens if and only if one of the following two statements hold:
\(\{ i,j\} \in \operatorname{\mathrm{Inv}}\tau \) and \(\{ \tau (j), \tau (i)\} \not\in \operatorname{\mathrm{Inv}}\sigma \);
\(\{ i,j\} \not\in \operatorname{\mathrm{Inv}}\tau \) and \(\{ \tau (i), \tau (j)\} \in \operatorname{\mathrm{Inv}}\sigma \).
We have \(\{ \tau (i),\tau (j)\} \in \operatorname{\mathrm{Inv}}\sigma \Leftrightarrow \tau \{ i,j\} \in \operatorname{\mathrm{Inv}}\sigma \Leftrightarrow \{ i,j\} \in \tau ^{-1}\operatorname{\mathrm{Inv}}\sigma \). So we can rewrite conditions (a) and (b) above as
\(\{ i,j\} \in \operatorname{\mathrm{Inv}}\tau \setminus \tau ^{-1}\operatorname{\mathrm{Inv}}\sigma \).
\(\{ i,j\} \in \tau ^{-1}\operatorname{\mathrm{Inv}}\sigma \setminus \operatorname{\mathrm{Inv}}\tau \).
This show that \(\operatorname{\mathrm{Inv}}\sigma \tau = \operatorname{\mathrm{Inv}}\tau \triangle \tau ^{-1}\operatorname{\mathrm{Inv}}\sigma \) as desired.
The map \(\operatorname{\mathrm{sgn}}:S_n\to \{ \pm 1\} \) is a group homomorphism.
Suppose \(\sigma ,\tau \in S_n\). Then,
So, applying \(\operatorname{\mathrm{sgn}}\), we get the desired result.
A transposition is a \(2\)-cycle in \(S_n\).
Every \(k\)-cycle with \(k {\gt} 1\) can be written as a product \(\tau _1\ldots \tau _k\) with the \(\tau _i\) transpositions.
We induct on \(k\). It’s clear when \(k = 1\). So assume \(k {\gt} 1\) and \(\sigma = (i_1\ldots i_k)\) is a \(k\)-cycle. Then \(\sigma = (i_1 i_2) (i_2\ldots i_k)\) as you can see by multiplying out. So, by induction on \(k\) we’re done.
Conjugate permutations have the same sign.
Suppose \(\sigma = \tau \sigma \tau ^{-1}\). Then \(\operatorname{\mathrm{sgn}}\sigma = \operatorname{\mathrm{sgn}}(\tau )\operatorname{\mathrm{sgn}}(\sigma )\operatorname{\mathrm{sgn}}(\sigma )^{-1} = \operatorname{\mathrm{sgn}}(\sigma )\) as \(\{ \pm 1\} \) is commutative.
Suppose \(i\in [n-1]\). And let \(\tau _i\) denote the transposition \((i (i+1))\). Then \(\operatorname{\mathrm{Inv}}\tau _i = \{ i, i+1\} \).
Exercise.
If \(\tau \) is a transposition, we have \(\operatorname{\mathrm{sgn}}\tau = -1\).
We can assume \(\tau = (12)\). Then \(\operatorname{\mathrm{Inv}}\tau = \{ 1,2\} \). So \(\operatorname{\mathrm{sgn}}\tau = (-1)^1 = -1\).
The sign of a \(k\)-cycle is \((-1)^k\). Moreover, if \(\sigma \in S_n\) is a permutation of type \(\lambda = (\lambda _1,\ldots , \lambda _k)\), then \(\operatorname{\mathrm{sgn}}\sigma = \prod _{i=1}^k (-1)^{\lambda _i - 1}\).