Friday, April 27, 2012

Calculation of a Permutation's Sign

Let \(\pi\in S_n\) be a permutation taken from the symmetrical group then it is easy to see that it can be expressed as the product of cyclic permutations \(c_i\in S_n\) as follows: \(\pi = \prod_{i=1}^k c_i\). And each cycle \(c_i\) can be expressed as a product of transpositions \(t^i_j:=(c_i^{j-1}(1) ~ c_i^j(1))\in S_n\) for \(j=1,2,...,|c_i|-1\) \[c_i=(1~c_i(1)~c_i^2(1)~... ~c_i^{|c_i|-1}(1))=(1~ c_i(1))(c_i(1)~ c_i^2(i))...(c_i^{|c_i|-2}(1)~ c_i^{|c_i|-1}(1))\] Here the expression \(|c_i|\) is the order (cardinality) of the group \(<c_i>\). Also note that \(c_i^{|c_i|}=\mathrm{id}\) where \(\mathrm{id}\) is the identity of \(S_n\).

A transposition \((i~j)\) has \(2(j-i)-1\) inversions. The inversions are the pairs \((i,k)\) for \(k=i+1,i+2,...,j\) and the pairs \((k',j)\) for \(k'=i+1,i+2,...,j-1\) so it all comes down to basic counting. Note that every other element besides \(i,j\) are fix points. Which means the sign of a (simple) transposition is \(-1\). 

The number of inversions of the identity is zero. Are there any other permutations besides the identity with no inversions? Let \(\alpha\in S_n\) have zero inversions but \(\alpha\neq\mathrm{id}\). Since this permutation doesn't have any inversions the chain \(\alpha(1) < \alpha(2) < ... < \alpha(n)\) must be valid because \(\alpha(i)<\alpha(j) \forall i<j\) is given by the definition of this permutation. In other words \(\alpha(1)\) must be thre smallest element of the sequence \((1,2,...,n)\) which is \(1\). \(\alpha(2)\) the second smallest element which is \(2\) and so on \(\Rightarrow \alpha=\mathrm{id}\). There are no permutations besides the identity with no inversions.

\(\pi\) is a permutation which is not the identity, so it has inversions. Can we find a simple transposition \(\tau\) such that \(\tau\pi\) has less inversions than \(\pi\)? If there would be such a simple transposition then there also exists a an inverse image \(i\) with \(\pi(i) > \pi(i+1)\). And this \(i\) has to exist because otherwise we would have \(\pi(i) < \pi(i+1)\) for all \(i=1,2,...,n-1\) which is only true for the idenity - contradiction to the assumptions \(\pi\neq \mathrm{id}\). Therefore we can find simple transpositions to non trivial permutations to reduce their inversion count by one. 

A transposition \((i~j)\) as seen above has \(2(j-i)-1\) inversions. Therefore it takes \(2(j-i)-1\) simple transpositions \(\tau_h\) such that \(\left(\prod_{h=1}^{2(j-i)-1}\tau_h\right) (i ~ j) = \mathrm{id}\) and such transpositions do exist. This also means that we can write every permutation as a product of simple transpositions.

The sign mapping \(\mathrm{sgn}:S_n\rightarrow \{-1,1\}\) is a group homomorphism. To show that we first need to realize that the sign of a permutation \(\pi\) changes when we multiply the permutation with a simple transposition \(\tau\) since we either add or remove a single inversion. \[\mathrm{sgn}(\pi\tau) = \mathrm{sgn}(\tau\pi)=-\mathrm{sgn}(\pi)=\mathrm{sgn}(\tau)\mathrm{sgn}(\pi)\] Especially we get for simple transpositions \(\tau_1, \tau_2\) \[\mathrm{sgn}(\tau_2\tau_1)=\mathrm{sgn}(\tau_2)\mathrm{sgn}(\tau_1)\]

Let \(\pi\pi'\in S_n\) be permutations which are not the identity. There exist \(N, N'\) simple transpositions \(\tau_i, \tau'_i\) such that \(\pi=\prod_{i=1}^N\tau_i\) and \(\pi'=\prod_{i=1}^{N'}\tau'_i\). This yields \[\mathrm{sgn}(\pi\pi')=\mathrm{sgn}\left(\left(\prod_{i=1}^N\tau_i\right)\left( \prod_{i=1}^{N'}\tau'_i\right)\right)=  \mathrm{sgn}\left(\prod_{i=1}^N\tau_i\right)  \mathrm{sgn}\left( \prod_{i=1}^{N'}\tau'_i\right) =\mathrm{sgn}(\pi)\mathrm{sgn}(\pi')\] 

Let's take a closer look at the permutation \(\pi\) as it is defined directly above. We come to the formula \[\mathrm{sgn}(\pi)=\prod_{i=1}^N\mathrm{sgn}(\tau_i)=(-1)^N\] This tells us that if \(pi\) is even than \(N\) must even as well. The same idea applies to \(\pi\) being an odd permutation.

Back to cyclic permutations. Every transposition is odd and therefore every odd cyclic permutation must be a product of an odd number of (simple) transpositions. The cycles \(c_i\) which we defined at the beginning are odd if \(|c_i|\) is even because we can express \(c_i\) with the product of \(|c_i|-1\) transpositions. The sign of \(pi\) is calculated as \[\mathrm{sgn}(\pi)=\prod_{i=1}^k\mathrm{sgn}(c_i)\] The signs on the right side of the equation which equal \(1\) can be discarded in the process of the calculation (neutral element). So we can come to the conclusion:

In Order to calculate the sign of a permutation \(\pi\) we express it as a product of cyclic permutations. Then we count the even cycles, let us assume there are \(K\) such cycles, and calculate the sign\[\mathrm{sgn}(\pi)=(-1)^K\]

This method is straight forward and not as error prone as to count each single inversion manually. 

No comments:

Post a Comment