Permutation group
Encyclopedia
In mathematics
, a permutation group is a group
G whose elements are permutation
s 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
, physics and chemistry.
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 finite subset of a symmetric group is again a group if and only if it is closed under the group operation.
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 G of permutations 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 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 subgroup of a permutation group by virtue of its regular action on G as a set; this is the content of Cayley's theorem
.
as permutation groups if there exists a bijective map f : X → X such that r 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). This is equivalent to G and H being conjugate as subgroups of Sym(X). 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 V4.
For a permutation p in Sn, a pair (i , j)∈In is a permutation inversion, if when i<j , we have p(i) > p(j).
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a permutation group is a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
G whose elements are permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s 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
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
; the term permutation group is usually restricted to mean a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
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
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
; it has applications in both the study of symmetries
Symmetry
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 perfection...
, combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and many other branches of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, physics and chemistry.
Closure properties
As a subgroupSubgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of a symmetric group, all that is necessary for a permutation group to satisfy the group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
axioms is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition
Function composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
of its permutations. A general property of finite groups implies that a finite subset of a symmetric group is again a group if and only if it is closed under the group operation.
Examples
Permutations are often written in cyclic formCycle notation
In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles. This is also called circular notation and the permutation called a cyclic or circular permutation....
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 G of permutations of the set M = {1,2,3,4}:
- e = (1)(2)(3)(4)= (1)
- 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
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
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
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
, 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 subgroup of a permutation group by virtue of its regular action on G as a set; this is the content of Cayley's theorem
Cayley's theorem
In group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group acting on G...
.
Isomorphisms
If G and H are two permutation groups on the same set X, then we say that G and H are isomorphicIsomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
as permutation groups if there exists a bijective map f : X → X such that r 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). This is equivalent to G and H being conjugate as subgroups of Sym(X). In this case, G and H are also isomorphic as groups
Group isomorphism
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 a way that respects the given group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic...
.
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.
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).For a permutation p in Sn, a pair (i , j)∈In is a permutation inversion, if when i<j , we have p(i) > p(j).
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.