Difference between revisions of "Symmetric group"
(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 ![]() ![]() |
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) |
Symmetric group. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Symmetric_group&oldid=19180