Permutations, cyclic permutations (cycles), permutation groups, transpositions. Even and odd permutations. Symmetric and alternating groups. Decomposition of a permutation group into cycles and a product of transpositions.

SolitaryRoad.com

Website owner:  James Miller

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

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. The word “permutation” can have either of the following meanings:

Def. Permutation. n. (1) An ordered arrangement or sequence of all or part of a set of things. If we are given a set of n different objects and arrange r of them in a definite order, such an ordered arrangement is called a permutation of the n objects r at a time. The number of different permutations of n things taken r at a time is denoted by _nP_r and is given by the formula

_nP_r = n(n-1)(n-2) ... (n - r + 1) .

The total number of different permutations of n things taken n at a time is n!.

(2) An operation that replaces a set of n objects by one of its n! permutations. 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

and is denoted by

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

Def. Cyclic permutation (cycle). A permutation of the form (m₁m₂ ... m_k) is called a cyclic permutation (or cycle) of length k. By definition, (m₁m₂ ... m_k) denotes the permutation that carries m₁ into m₂, m₂ into m₃, ... , m_k-1into m_k and m_k into m₁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

Syn. Cycle.

Products of permutations – examples.

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

2) The product of the permutations

and

Graphically it corresponds to:

_________________________________________

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.

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.

Let x₁, x₂, .... , x_n ben indeterminants and let D be the product (x₁ - x₂)(x₁ - x₃) .... (x_n-1 - x_n) of all differences x_i - x_j, where i < j. A permutation of the subscripts 1, 2, .... , n is even or odd according to whether it leaves the sign of D unchanged or changes the sign of D.

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 (a₁a₂ ... a_m) of length m is an odd permutation if m is even and an odd permutation if m is odd.

Let us now consider an important concept, the concept of a group of transformations. The term “transformation” means the same as function. The terms are used interchangeably.

Def. Group of Transformations on a set S. Any set G of one-to-one transformations (i.e. functions) of a set S onto itself which meets the axiomatic conditions for being a group i.e.

1) Closure (if transformations f and g are in G, so is their product fg)

2) The associative law holds i.e. f(gh) = (fg)h

3) Existence of an identity element

4) Existence of inverses i.e. if transformation f is in G, so is its inverse f ^-1

Note that group G may be either a finite group or an infinite group.

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

Symmetric group S_n on n letters. The group consisting of all possible permutations on n objects (or letters). It contains n! elements. The number of elements is equal to the number of possible permutations of n things taken n at a time which is n!.

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

Generating elements for S_n and A_n.

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

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