Permutation group


Permutation group

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"). 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. 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.

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. 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).

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

* "e" = (1)(2)(3)(4)
**This is the identity, the trivial permutation which fixes each element.
* "a" = (1 2)(3)(4) = (1 2)
**This permutation interchanges 1 and 2, and fixes 3 and 4.
* "b" = (1)(2)(3 4) = (3 4)
**Like the previous one, but exchanging 3 and 4, and fixing the others.
* "ab" = (1 2)(3 4)
**This permutation, which is the composition of the previous two, exchanges simultaneously 1 with 2, and 3 with 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 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. The axioms of a group are easily seen to be satisfied; to invert any sequence of rotations, simply perform their opposites, in reverse order.

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.

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 "h""g" in "H" such that for all "x" in "X", ("g" o "f")("x") = ("f" o "h""g")("x"). This is equivalent to "G" and "H" being conjugate as subgroups of "SX". In this case, "G" and "H" are also isomorphic as groups.

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 "V"4.

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).

Transpositions, simple transpositions, inversions and sorting

A 2-cycle is known as a transposition. 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).

See also

* Primitive group
* Oligomorphic group

References

* John D. Dixon and Brian Mortimer. "Permutation Groups". Number 163 in Graduate Texts in Mathematics. Springer-Verlag, 1996.
* Akos Seress. "Permutation group algorithms". Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
* Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller and Peter M. Neumann. "Notes on Infinite Permutation Groups". Number 1698 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
* Alexander Hulpke. GAP Data Library [http://www.gap-system.org/Datalib/trans.html "Transitive Permutation Groups"] .
* Peter J. Cameron. "Permutation Groups". LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
* Peter J. Cameron. "Oligomorphic Permutation Groups". Cambridge University Press, Cambridge, 1990.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • permutation group — kėlinių grupė statusas T sritis fizika atitikmenys: angl. permutation group vok. Permutationsgruppe, f rus. группа перестановок, f pranc. groupe de permutations, m …   Fizikos terminų žodynas

  • permutation group — noun : a group of which the elements are permutations and in which the product of two permutations is a permutation whose effect is the same as the successive application of the first two * * * a mathematical group whose elements are permutations …   Useful english dictionary

  • permutation group — noun Date: 1904 a group whose elements are permutations and in which the product of two permutations is a permutation whose effect is the same as the successive application of the first two …   New Collegiate Dictionary

  • permutation group — a mathematical group whose elements are permutations and in which the product of two permutations is the same permutation as is obtained by performing them in succession. [1900 05] * * * …   Universalium

  • Primitive permutation group — In mathematics, a permutation group G acting on a set X is called primitive if G preserves no nontrivial partition of X . In the other case, G is imprimitive. An imprimitive permutation group is an example of an induced representation; examples… …   Wikipedia

  • Group theory — is a mathematical discipline, the part of abstract algebra that studies the algebraic structures known as groups. The development of group theory sprang from three main sources: number theory, theory of algebraic equations, and geometry. The… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Group action — This article is about the mathematical concept. For the sociology term, see group action (sociology). Given an equilateral triangle, the counterclockwise rotation by 120° around the center of the triangle acts on the set of vertices of the… …   Wikipedia

  • permutation — [pʉr΄myo͞o tā′shən] n. [ME permutacion < MFr < L permutatio < permutare: see PERMUTE] 1. any radical alteration; total transformation 2. a) a complete rearrangement, esp. by interchanging b) Math. any of the total number of groupings, or …   English World dictionary

  • Permutation matrix — In mathematics, in matrix theory, a permutation matrix is a square (0,1) matrix that has exactly one entry 1 in each row and each column and 0 s elsewhere. Each such matrix represents a specific permutation of m elements and, when used to… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.