Citizendia

In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In several fields of Mathematics the term permutation is used with different but closely related meanings In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property Note that the group of all permutations of a set is the symmetric group; the term permutation group is usually restricted to mean a subgroup of the symmetric group. In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of The symmetric group of n elements is denoted by Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).

The application of a permutation group to the elements being permuted is called its group action; it has applications in both the study of symmetries, combinatorics and many other branches of mathematics and physics. In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. Symmetry generally conveys two primary meanings The first is an imprecise sense of harmonious or aesthetically-pleasing proportionality and balance such that it reflects beauty or Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and

Contents

Closure properties

As a subgroup of a symmetric group, all that is necessary for a permutation group to satisfy the group axioms is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition of its permutations. In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, a composite function represents the application of one function to the results of another A general property of finite groups implies that a subset of a finite symmetric group is again a group if and only if it is closed under the group operation.

Examples

Permutations are often written in cyclic form, e. g. during cycle index computations, so that given the set M = {1,2,3,4}, a permutation g of M with g(1) = 2, g(2) = 4, g(4) = 1 and g(3) = 3 will be written as (1,2,4)(3), or more commonly, (1,2,4) since 3 is left unchanged; if the objects are denoted by a single letter or digit, commas are also dispensed with, and we have a notation such as (1 2 4). In Mathematics, and in particular in the field of Combinatorics, cycle indices are used in Combinatorial enumeration when symmetries are to be taken into

Consider the following set of permutations G of the set M = {1,2,3,4}:

G forms a group, since aa = bb = e, ba = ab, and baba = e. So (G,M) forms a permutation group.

The Rubik's Cube puzzle is another example of a permutation group. The Rubik's Cube is a Mechanical puzzle invented in 1974 by Hungarian Sculptor and Professor of Architecture Ernő Rubik The underlying set being permuted is the coloured subcubes of the whole cube. Each of the rotations of the faces of the cube is a permutation of the positions and orientations of the subcubes. Taken together, the rotations form a generating set, which in turn generates a group by composition of these rotations. In Abstract algebra, a generating set of a group G is a Subset S such that every element of G can be expressed as the The axioms of a group are easily seen to be satisfied; to invert any sequence of rotations, simply perform their opposites, in reverse order. In Mathematics, a group G,*> is defined as a set G and a Binary operation on G, called product and denoted

The group of permutations on the Rubik's Cube does not form a complete symmetric group of the 20 corner and face cubelets; there are some final cube positions which cannot be achieved through the legal manipulations of the cube.

More generally, every group G is isomorphic to a permutation group by virtue of its regular action on G as a set; this is the content of Cayley's theorem. In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. In Group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a Subgroup

Isomorphisms

If G and H are two permutation groups on the same set X, then we say that G and H are isomorphic as permutation groups if there exists a bijective map f : X → X such that r \mapsto f −1 o r o f defines a bijective map between G and H; in other words, if for each element g in G, there is a unique hg in H such that for all x in X, (g o f)(x) = (f o hg)(x). In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective This is equivalent to G and H being conjugate as subgroups of SX. In this case, G and H are also isomorphic as groups. In Abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in

Notice that different permutation groups may well be isomorphic as abstract groups, but not as permutation groups. For instance, the permutation group on {1,2,3,4} described above is isomorphic as a group (but not as a permutation group) to {(1)(2)(3)(4), (12)(34), (13)(24), (14)(23)}. Both are isomorphic as groups to the Klein group V4. In Mathematics, the Klein four-group (or just Klein group or Vierergruppe, often symbolized by the letter V) is the group Z2

If (G,M) and (H,M) such that both G and H are isomorphic as groups to Sym(M), then (G,M) and (H,M) are isomorphic as permutation groups; thus it is appropriate to talk about the symmetric group Sym(M) (up to isomorphism). In Mathematics, the phrase " up to xxxx" indicates that members of an Equivalence class are to be regarded as a single entity for some purpose

Transpositions, simple transpositions, inversions and sorting

A 2-cycle is known as a transposition. In informal language a transposition is a function that swaps two elements of a set A simple transposition in Sn is a 2-cycle of the form (i  i + 1).

An inversion of a permutation p in Sn is a pair (i  i + 1) such that p(i) > p(i + 1). Viewing permutations as lists, an inversion expresses that the items at position i and i + 1 are out of order.

It can be shown that every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in Sn can be the number of inversions of p and if the number of inversions in p is odd or even the number of transpositions in p will also be odd or even corresponding to the oddness of p, and that it is possible to find such a product—in fact, this is what insertion sort does implicitly (instead of giving the simple transpositions as output, it applies them to the input list). Insertion sort is a simple Sorting algorithm, a Comparison sort in which the sorted array (or list is built one entry at a time

See also

References

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org