Sunday, February 9, 2014

Set Algebra: Signature of a Permutation: The Easy and Long Way

Hi everyone, I am blogging from a very crowded Coffee Klatch Cafè in San Dimas. Sorry I haven't posted in so long.

Signatures of a Set

In my recent adventures with my calculator, I discovered a function on the HP Prime called signature.

The signature, symbolized as sgn, function returns:

-1 if the permutation has an odd amount of transpositions and
+1 if the permutation has an even amount of transpositions.

It has been a while since I have studied set theory.

When using set theory, we are usually looking at sets like {1}, {1,2}, {1,2,3}, and the like. The basic format is {1,2,3,4...n} where n is a positive integer.

A permutation of a set is just the act of rearranging the set's elements to a different order. For a this type of set, there are n! (n factorial) permutations. For instance, there are 3!, or 6 permutations of the set {1,2,3}.


The permutations of the set {1,2,3} are {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,2,1}, and {3,1,2}.

A transposition of a set is just switching two elements.

Example:

From the set {1,2,3,4,5}, a transposition is made when 1 and 5 are switched:
{5, 2, 3, 4, 1}

We can cause another transposition by switching 3 and 4 from the last result:
{5, 2, 4, 3, 1}

Another transposition can be created, let's switch 2 and 4 this time:
{5, 4, 2 , 3, 1}

Determining the signature of each can be determined as follows:

We start out with {1,2,3,4,5}. Nothing has been done, so signature({1,2,3,4,5})=1.

With {5,2,3,4,1}, 1 transposition happened, hence signature({5,2,3,4,1})=-1.

With {5,2,4,3,1}, 2 transpositions took place, and signature({5,2,4,3,1})=1.

Finally 3 transpositions were needed to get {5,4,2,3,1}, so signature({5,4,2,3,1)}=-1.

Do this manually, one should start from the basic permutation {1,2,3,...n}. Simple, but also can cause a lot of work without extensive theory or software.

More information, including way more element mathematics and theory can be found here:

http://en.wikipedia.org/wiki/Parity_of_a_permutation

Have a great day and I will talk to you soon!

Eddie


This blog is property of Edward Shore. 2014

No comments:

Post a Comment

Expanding Linear Regression

Expanding Linear Regression Introduction – Linear Regression All scientific calculators that have two-variable dimensions has cu...