Expand/Contract All

Sign of Permutations

 
 

Sign of Permutation

Let _ X = \{ 1, ... , ~n \} . _ Define the number

prod{( ~j - ~i ),~i < ~j {;} ~i {,} ~j &in. X, _ } _ _ _ [ i.e. product over _ 1 =< ~i < ~j =< ~n ]

This product has as factors every positive difference of two positive integers less than or equal to ~n. Thus if ~n = 3 :

prod{( ~j - ~i ),~i < ~j ,} _ = _ ( 2 - 1 )( 3 - 1 )( 3 - 2 ) _ = _ 2

Suppose &theta. is a permutation of X, and consider the product

prod{( ~j&theta. - ~i&theta. ),~i < ~j {;} ~i {,} ~j &in. X ,}

This product will contain the same factors as before, but some of them may now be negative.

For example, if ~n = 3 and _ &theta. _ = _ matrix {1,2,3/3,2,1} , _ then

prod{( ~j&theta. - ~i&theta. ),~i < ~j ,} _ = _ ( 2&theta. - 1&theta. )( 3&theta. - 1&theta. )( 3&theta. - 2&theta. )

_ _ _ _ _ _ _ _ _ = _ ( 2 - 3 )( 1 - 3 )( 1 - 2 ) _ = _ -2

Note that _ _ _ _ prod{( ~j&theta. - ~i&theta. ),~i < ~j ,} _ = _ +- prod{( ~j - ~i ),~i < ~j ,}

The #~{sign} of the permutation is defined as

&theta.&sigma. _ #:= _ fract{prod{( ~j&theta. - ~i&theta. ),~i < ~j ,},prod{( ~j - ~i ),~i < ~j ,}} _ _ [ _ = _ +-1 ]

&theta. is said to be an #~{even permutation} _ if _ &theta.&sigma. = +1 , _ or an #~{odd permutation} if &theta.&sigma. = -1

We will write A_~n to denote the set of all even permutations on the set \{ 1 , ... , ~n \}.

Symetric Group Homomorphism

#{Theorem}: _ Let H be the group \{ 1 , -1 \} under multiplication: _ _ _ _ _ _ _

# 1 -1
1 1 -1
-1 -1 1

Consider the mapping _ _ &sigma. #: S_~n -> H , _ where &theta.&sigma. is the sign of the permutation as defined above, and S_~n is the on ~n elements, then &sigma. is a homomorphism.

Proof: _ Let &theta. &phi. &in. S_~n

prod{( ~j&theta.&phi. - ~i&theta.&phi. ),~i < ~j ,} _ = _ prod{( ( ~j&theta. )&phi. - ( ~i&theta. )&phi. ),~i < ~j ,}

Reversing the sign of those factors on the right hand side for which ~j&theta. < ~i&theta. introduces overall a factor &theta.&sigma. i.e.

prod{( ( ~j&theta. )&phi. - ( ~i&theta. )&phi. ),~i < ~j ,} _ = _ &theta.&sigma. prod{( ( ~j&theta. )&phi. - ( ~i&theta. )&phi. ),~i&theta. < ~j&theta. ,}

But since &theta. is a permutation on X = \{ 1, ... , ~n \}

prod{( ( ~j&theta. )&phi. - ( ~i&theta. )&phi. ),~i&theta. < ~j&theta. ,} _ = _ prod{( ~j&phi. - ~i&phi. ),~i < ~j ,} _ = _ &phi.&sigma. prod{( ~j - ~i ),~i < ~j ,}

Hence _ _ _ prod{( ~j&theta.&phi. - ~i&theta.&phi. ),~i < ~j ,} _ = _ &theta.&sigma. &phi.&sigma. prod{( ~j - ~i ),~i < ~j ,}

&therefore. _ _ &theta.&sigma. &phi.&sigma. _ = _ (&theta.&phi.)&sigma. , _ _ so &sigma. is a homomorphism.

Corollary: _ the set A_~n of all even permutations is a subgroup of S_~n.

For the set _ \{ 1 \} _ is a subgroup under multiplication of the group _ H = \{ 1 , -1 \}. _ But _ Im A_~n _ = _ \{ 1 \} _ under the homomorphism &sigma. , _ so A_~n is a subgroup of S_~n.