Namespaces
Variants
Actions

Difference between revisions of "Symmetric group"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
Line 11: Line 11:
 
are called transpositions; they form a system of generators for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167024.png" />. The set of transpositions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167025.png" /> is a minimal set of generators for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167026.png" />. In general, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167027.png" /> generates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167028.png" /> if the graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167029.png" /> as set of vertices and the pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167030.png" /> as edges is a [[Tree|tree]] [[#References|[2]]]. The number of such generating sets is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167031.png" />.
 
are called transpositions; they form a system of generators for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167024.png" />. The set of transpositions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167025.png" /> is a minimal set of generators for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167026.png" />. In general, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167027.png" /> generates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167028.png" /> if the graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167029.png" /> as set of vertices and the pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167030.png" /> as edges is a [[Tree|tree]] [[#References|[2]]]. The number of such generating sets is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167031.png" />.
  
The [[Alternating group|alternating group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167032.png" /> is a normal subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167033.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167035.png" /> is the unique non-trivial proper normal subgroup, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167036.png" /> contains only one other non-trivial normal subgroup — the Klein four-group: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167037.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167038.png" /> the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167039.png" /> is solvable, but for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167040.png" /> it is not solvable and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167041.png" /> is a simple non-Abelian group. Hölder's theorem: For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167042.png" />, the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167043.png" /> is complete (see [[Complete group|Complete group]]). The group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167044.png" /> is commutative, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167045.png" /> has an outer automorphism of order 2.
+
The [[Alternating group|alternating group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167032.png" /> is a normal subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167033.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167035.png" /> is the unique non-trivial proper normal subgroup, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167036.png" /> contains only one other non-trivial normal subgroup — the Klein four-group: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167037.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167038.png" /> the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167039.png" /> is solvable, but for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167040.png" /> it is not solvable and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167041.png" /> is a simple non-Abelian group. Hölder's theorem: For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167042.png" />, the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167043.png" /> is complete (see [[Complete group|Complete group]]). The group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167044.png" /> is commutative, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167045.png" /> has an [[outer automorphism]] of order 2.
  
 
All maximal intransitive and imprimitive subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167046.png" /> are known. For each partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167048.png" />, the only maximal intransitive subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167049.png" /> are the subgroups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167050.png" />. The only transitive imprimitive maximal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167051.png" /> are the wreath products (cf. [[Wreath product|Wreath product]]) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167052.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167053.png" /> (for every decomposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167054.png" />). The primitive maximal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167055.png" /> have not yet been described (1992), but certain infinite series of them are known. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167056.png" /> acts naturally on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167057.png" /> of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167058.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167059.png" />; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167060.png" /> this determines a primitive group of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167061.png" />. It is maximal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167062.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167068.png" /> (see [[#References|[1]]]). Another series is obtained by considering the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167069.png" /> of semi-linear transformations of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167070.png" />-dimensional vector space over the finite field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167071.png" /> elements. This group defines a primitive group of permutations of the [[Grassmann manifold|Grassmann manifold]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167073.png" />, which is maximal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167074.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167075.png" />.
 
All maximal intransitive and imprimitive subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167046.png" /> are known. For each partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167048.png" />, the only maximal intransitive subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167049.png" /> are the subgroups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167050.png" />. The only transitive imprimitive maximal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167051.png" /> are the wreath products (cf. [[Wreath product|Wreath product]]) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167052.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167053.png" /> (for every decomposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167054.png" />). The primitive maximal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167055.png" /> have not yet been described (1992), but certain infinite series of them are known. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167056.png" /> acts naturally on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167057.png" /> of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167058.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167059.png" />; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167060.png" /> this determines a primitive group of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167061.png" />. It is maximal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167062.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167068.png" /> (see [[#References|[1]]]). Another series is obtained by considering the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167069.png" /> of semi-linear transformations of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167070.png" />-dimensional vector space over the finite field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167071.png" /> elements. This group defines a primitive group of permutations of the [[Grassmann manifold|Grassmann manifold]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167073.png" />, which is maximal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167074.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167075.png" />.

Revision as of 18:06, 29 November 2014

The group of all permutations (self-bijections) of a set with the operation of composition (see Permutation group). The symmetric group on a set is denoted by . For equipotent and the groups and are isomorphic. The symmetric group of a finite set is denoted by . Every abstract group is isomorphic to a subgroup of the symmetric group of some set (Cayley's theorem).

Let be a finite set. Every permutation on can be uniquely described as a product of disjoint cycles (the (disjoint) cycle decomposition of a permutation); the sequence of integers

where is the number of cycles of length of , is called the cycle type (or cycle index) of . Two permutations and are conjugate in if and only if they have the same cycle type. Permutations with cycle type

are called transpositions; they form a system of generators for . The set of transpositions is a minimal set of generators for . In general, a set generates if the graph with as set of vertices and the pairs as edges is a tree [2]. The number of such generating sets is .

The alternating group is a normal subgroup of . If , is the unique non-trivial proper normal subgroup, and contains only one other non-trivial normal subgroup — the Klein four-group: . For the group is solvable, but for it is not solvable and is a simple non-Abelian group. Hölder's theorem: For , the group is complete (see Complete group). The group is commutative, and has an outer automorphism of order 2.

All maximal intransitive and imprimitive subgroups in are known. For each partition , , the only maximal intransitive subgroups in are the subgroups . The only transitive imprimitive maximal subgroups in are the wreath products (cf. Wreath product) of with (for every decomposition ). The primitive maximal subgroups in have not yet been described (1992), but certain infinite series of them are known. For example, acts naturally on the set of all subsets of elements of ; for this determines a primitive group of permutations of . It is maximal in if , , , , , (see [1]). Another series is obtained by considering the group of semi-linear transformations of the -dimensional vector space over the finite field of elements. This group defines a primitive group of permutations of the Grassmann manifold , , which is maximal in for .

Let be an infinite set. The group of all permutations of that move only a finite number of elements of is called the finitary, or restricted, symmetric group on , and is denoted by ; its subgroup of even permutations is called the finite, or restricted, alternating group on , and is denoted by . The subgroups and are normal in . More generally, let be the cardinality of and let be an infinite cardinal; the set of permutations of which move at most elements of is a subgroup of , denoted by . Along with and , the groups are normal subgroups in for all , and in fact there are no other non-trivial normal subgroups in (the Schreier–Ulam–Baer theorem, see [3]).

See also the references to Permutation of a set.

References

[1] L.A. Kaluzhnin, M.Kh. Klin, "On certain maximal subgroups of symmetric and alternating groups" Math. USSR Sb. , 16 : 1 (1972) pp. 95–123 Mat. Sb. , 87 : 1 (1972) pp. 91–121
[2] O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)
[3] B.I. Plotkin, "Groups of automorphisms of algebraic systems" , Wolters-Noordhoff (1972)
[4] V.A. Ustimenko-Bakumovskii, "Maximality of the group acting on subspaces of dimension " Soviet Math. Dokl. , 19 : 3 (1978) pp. 769–772 Dokl. Akad. Nauk SSSR , 240 : 6 (1978) pp. 1305–1308


Comments

A complete group, i.e. a group without centre and outer automorphisms, is also called a perfect group.

See also [a1] for a result on the structure of subgroups of .

References

[a1] I.M. Aschbacher, L.L. Scott, "Maximal subgroups of finite groups" J. Algebra (1985) pp. 44–80
[a2] H. Wielandt, "Finite permutation groups" , Acad. Press (1964) (Translated from German)
[a3] D. Passman, "Permutation groups" , Benjamin (1968)
How to Cite This Entry:
Symmetric group. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Symmetric_group&oldid=35102
This article was adapted from an original article by L.A. Kaluzhnin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article