Encyclopedia > Permutation group

  Article Content

Permutation group

In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose 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).

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.

Examples

Permutations are often written in cyclic form, 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.

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 = (12)(3)(4) = (12)
    • This permutation interchanges 1 and 2, and fixes 3 and 4.
  • b = (1)(2)(34) = (34)
    • Like the previous one, but exchanging 3 and 4, and fixing the others.
  • ab = (12)(34)
    • 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 ba'ba = e. So (G,M) forms a permutation group.

The group of all permutations of a set of n elements is the symmetric group Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).

The Rubik's Cube puzzle is another example of a permutation group. The underlying set being permuted is the colored 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 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 S, then we say that G and H are isomorphic as permutation groups if there exists a bijective map f : SS 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 s in S, (g o f)(s) = (f o hg)(s). 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.

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

See Also



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Christian Denominations

... Orthodox Church[?] Orthodox Church of Jerusalem[?] Orthodox Church of Mount Sinai[?] Polish Orthodox Church[?] Romanian Orthodox Church[?] Russian ...