SolitaryRoad.com

Website owner:  James Miller


[ Home ] [ Up ] [ Info ] [ Mail ]

    PERMUTATIONS, PERMUTATION GROUPS, TRANSPOSITIONS, SYMMETRIC GROUP





The origins of group theory go back to the study of permutations. Permutations arise in connection with studies of various kinds of symmetries that occur in mathematics and especially in investigations of the question of whether a particular polynomial equation of the n-th degree is solvable by radicals. Permutations are closely connected with group theory and permutation groups play a big part in it.




Some definitions:



Permutation. An operation which replaces each of a set of objects by itself or another object in the set in a one-to-one manner. In essence, a permutation represents a mapping of a set of n objects onto itself. A permutation in which a is replaced by b, b is replaced by d, c is replaced by c, d is replaced by a and e is replaced by e in the set S = {a,b,c,d,e} is represented by the mapping


              ole.gif


and is denoted by


             ole1.gif


where the bottom row gives the images of the elements in the top row.




Cyclic permutation (cycle). A permutation of the form (m1m2 ... mk) is called a cyclic permutation (or cycle) of length k. By definition, (m1m2 ... mk) denotes the permutation that carries m1 into m2, m2 into m3, ... , mk-1 into mk and mk into m1 and leaves all the remaining elements of the set in question unchanged.


Example. The cyclic permutation


                         (abcd)


on the set S = {a,b,c,d} corresponds to the mapping


                         ole2.gif


or


                  ole3.gif



Syn. Cycle.





Permutation group. A group whose elements are permutations , the product of two permutations being the permutation resulting from applying each in succession.

Syn. substitution group




Products of permutations – examples.


1) The product of the permutation p1 = (abc), which takes a into b, b into c, and c into a, and the permutation p2 = (bc), which takes b into c and c into b, is p1p2 = (abc)(bc), which takes a into c and c into a. Graphically it can be expressed as:

.


             ole4.gif ole5.gif



2) The product of the permutations


                ole6.gif      


and


                ole7.gif


is


             ole8.gif

 


Graphically it corresponds to:


                      ole9.gif





Symmetric group Sn on n letters. The group of all permutations on n objects. It corresponds to the set of all possible mappings of a set S of n objects onto itself.


Q. How many mappings are there in the set Q of all mappings of a set S of n objects onto itself?


A. n! It is equal to the number of permutations of n things taken n at a time. Object 1 can be mapped into any of n objects, then object 2 can be mapped into any of n-1 objects, object 3 can be mapped into any of n-2 objects, etc. for all n objects. Thus the total number of mappings is


                                    n(n-1)(n-2) ... = n!


Thus the symmetric group Sn on n letters has n! elements.




Alternating group An on n letters. A group consisting of all even permutations on n objects. An is a subgroup of Sn. It contains n!/2 elements.






_________________________________________


CYCLIC PERMUTATIONS

_________________________________________




Def. Transposition. A cyclic permutation of length 2.


Example: (23) and (56) are transpositions.



Def. Disjoint cycles. Two or more cycles which have no element in common are called (mutually) disjoint.




Decomposition of a permutation into cycles. Every permutation can be represented in the form of a product of cycles without common elements (i.e. disjoint cycles) and this representation is unique to within the order of the factors..


Note. A permutation can also be represented as a product of cycles with common elements but this representation is not unique. 




Products of cycles without common elements. The order of the factors is immaterial in the case of products of cycles that are without common elements (i.e. disjoint cycles).


Example. The cycles (23) and (145) have no common elements so


                        (23)(145) = (145)(23)




Decomposition of a permutation into a product of transpositions. Every permutation can be factored into a product of transpositions e.g. (abc) = (ab)(ac) in the sense that the permutation (abc) has the same effect as the permutation (ab) followed by the permutation (ac). This factorization is not unique but, for a specific permutation, the number of transpositions (i.e. factors) will always be either even or odd.




Def. Even and odd permutations. A permutation is even or odd according as it can be written as the product of an even or odd number of transpositions.




Parity of products of even and odd permutations. The product of two even permutations is even; the product of two odd permutations is even; the product of an even and an odd permutation is odd. Moreover, the permutation inverse to an even or odd permutation is a permutation of the same parity.

 



Length of a cycle and its parity. A cycle of length m can be represented as a product of m-1 transpositions. Thus a cycle (a1a2 ... am) of length m is an odd permutation if m is even and an odd permutation if m is odd.





Generating elements for Sn and An.


The n-1 transpositions (12),(13), ... ,(1n) for n > 1 generate the symmetric group Sn.


The n-2 cyclic permutations on three digits (123), (124), ... , (12n) generate the alternating group An.



More from SolitaryRoad.com:

The Way of Truth and Life

God's message to the world

Jesus Christ and His Teachings

Words of Wisdom

Way of enlightenment, wisdom, and understanding

Way of true Christianity

America, a corrupt, depraved, shameless country

On integrity and the lack of it

The test of a person's Christianity is what he is

Who will go to heaven?

The superior person

On faith and works

Ninety five percent of the problems that most people have come from personal foolishness

Liberalism, socialism and the modern welfare state

The desire to harm, a motivation for conduct

The teaching is:

On modern intellectualism

On Homosexuality

On Self-sufficient Country Living, Homesteading

Principles for Living Life

Topically Arranged Proverbs, Precepts, Quotations. Common Sayings. Poor Richard's Almanac.

America has lost her way

The really big sins

Theory on the Formation of Character

Moral Perversion

You are what you eat

People are like radio tuners --- they pick out and listen to one wavelength and ignore the rest

Cause of Character Traits --- According to Aristotle

These things go together

Television

We are what we eat --- living under the discipline of a diet

Avoiding problems and trouble in life

Role of habit in formation of character

The True Christian

What is true Christianity?

Personal attributes of the true Christian

What determines a person's character?

Love of God and love of virtue are closely united

Walking a solitary road

Intellectual disparities among people and the power in good habits

Tools of Satan. Tactics and Tricks used by the Devil.

On responding to wrongs

Real Christian Faith

The Natural Way -- The Unnatural Way

Wisdom, Reason and Virtue are closely related

Knowledge is one thing, wisdom is another

My views on Christianity in America

The most important thing in life is understanding

Sizing up people

We are all examples --- for good or for bad

Television --- spiritual poison

The Prime Mover that decides "What We Are"

Where do our outlooks, attitudes and values come from?

Sin is serious business. The punishment for it is real. Hell is real.

Self-imposed discipline and regimentation

Achieving happiness in life --- a matter of the right strategies

Self-discipline

Self-control, self-restraint, self-discipline basic to so much in life

We are our habits

What creates moral character?


[ Home ] [ Up ] [ Info ] [ Mail ]