Namespaces
Variants
Actions

Difference between revisions of "Symmetric group"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
The group of all permutations (self-bijections) of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916701.png" /> with the operation of composition (see [[Permutation group|Permutation group]]). The symmetric group on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916702.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916703.png" />. For equipotent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916704.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916705.png" /> the groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916706.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916707.png" /> are isomorphic. The symmetric group of a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916708.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s0916709.png" />. Every abstract group is isomorphic to a subgroup of the symmetric group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167010.png" /> of some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167011.png" /> (Cayley's theorem).
+
<!--
 +
s0916701.png
 +
$#A+1 = 100 n = 2
 +
$#C+1 = 100 : ~/encyclopedia/old_files/data/S091/S.0901670 Symmetric group
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167012.png" /> be a finite set. Every permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167013.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167014.png" /> can be uniquely described as a product of disjoint cycles (the (disjoint) cycle decomposition of a permutation); the sequence of integers
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167015.png" /></td> </tr></table>
+
The group of all permutations (self-bijections) of a set  $  X $
 +
with the operation of composition (see [[Permutation group|Permutation group]]). The symmetric group on a set  $  X $
 +
is denoted by  $  S ( X) $.
 +
For equipotent  $  X $
 +
and  $  X  ^  \prime  $
 +
the groups  $  S ( X) $
 +
and  $  S ( X  ^  \prime  ) $
 +
are isomorphic. The symmetric group of a finite set  $  X = \{ 1 \dots n \} $
 +
is denoted by  $  S _ {n} $.  
 +
Every abstract group is isomorphic to a subgroup of the symmetric group  $  S ( X) $
 +
of some set  $  X $(
 +
Cayley's theorem).
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167016.png" /> is the number of cycles of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167017.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167018.png" />, is called the cycle type (or cycle index) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167019.png" />. Two permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167021.png" /> are conjugate in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167022.png" /> if and only if they have the same cycle type. Permutations with cycle type
+
Let  $  X $
 +
be a finite set. Every permutation  $  \pi $
 +
on  $  X $
 +
can be uniquely described as a product of disjoint cycles (the (disjoint) cycle decomposition of a permutation); the sequence of integers
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167023.png" /></td> </tr></table>
+
$$
 +
z ( \pi )  = ( a _ {1} \dots a _ {n} ),
 +
$$
  
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" />.
+
where  $  a _ {i} $
 +
is the number of cycles of length  $  i $
 +
of $  \pi $,
 +
is called the cycle type (or cycle index) of $  \pi $.  
 +
Two permutations  $  \pi $
 +
and  $  \pi  ^  \prime  $
 +
are conjugate in  $  S _ {n} $
 +
if and only if they have the same cycle type. Permutations with cycle type
  
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.
+
$$
 +
\{ n - 2, 1, 0 \dots 0 \}
 +
$$
  
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" />.
+
are called transpositions; they form a system of generators for  $  S _ {n} $.  
 +
The set of transpositions  $  \Sigma = \{ ( i, i + 1) : i = 1 \dots n - 1 \} $
 +
is a minimal set of generators for $  S _ {n} $.  
 +
In general, a set  $  \Delta = \{ ( i _ {k} , j _ {k} ) : i _ {k} \neq j _ {k} \} $
 +
generates  $  S _ {n} $
 +
if the graph with  $  X $
 +
as set of vertices and the pairs  $  ( i _ {k} , j _ {k} ) $
 +
as edges is a [[Tree|tree]] [[#References|[2]]]. The number of such generating sets is $  n ^ {n - 2 } $.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167076.png" /> be an infinite set. The group of all permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167077.png" /> that move only a finite number of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167078.png" /> is called the finitary, or restricted, symmetric group on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167079.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167080.png" />; its subgroup of even permutations is called the finite, or restricted, alternating group on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167081.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167082.png" />. The subgroups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167084.png" /> are normal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167085.png" />. More generally, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167086.png" /> be the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167087.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167088.png" /> be an infinite cardinal; the set of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167089.png" /> which move at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167090.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167091.png" /> is a subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167092.png" />, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167093.png" />. Along with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167095.png" />, the groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167096.png" /> are normal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167097.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167098.png" />, and in fact there are no other non-trivial normal subgroups in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s09167099.png" /> (the Schreier–Ulam–Baer theorem, see [[#References|[3]]]).
+
The [[Alternating group|alternating group]]  $  A _ {n} $
 +
is a normal subgroup of  $  S _ {n} $.
 +
If  $  n \neq 4 $,
 +
$  A _ {n} $
 +
is the unique non-trivial proper normal subgroup, and  $  S _ {4} $
 +
contains only one other non-trivial normal subgroup — the Klein four-group:  $  K _ {4} = \{ 1, ( 1  2)( 3, 4), ( 1  3)( 2  4), ( 1  4) ( 2  3) \} $.
 +
For  $  n \leq  4 $
 +
the group  $  S _ {n} $
 +
is solvable, but for  $  n \geq  5 $
 +
it is not solvable and  $  A _ {n} $
 +
is a simple non-Abelian group. Hölder's theorem: For  $  n \neq 2, 6 $,
 +
the group  $  S _ {n} $
 +
is complete (see [[Complete group|Complete group]]). The group  $  S _ {2} $
 +
is commutative, and  $  S _ {6} $
 +
has an [[outer automorphism]] of order 2.
 +
 
 +
All maximal intransitive and imprimitive subgroups in  $  S _ {n} $
 +
are known. For each partition  $  n = m _ {1} + m _ {2} $,
 +
$  m _ {1} \neq m _ {2} $,
 +
the only maximal intransitive subgroups in  $  S _ {n} $
 +
are the subgroups  $  S _ {m _ {1}  } \times S _ {m _ {2}  } $.
 +
The only transitive imprimitive maximal subgroups in  $  S _ {n} $
 +
are the wreath products (cf. [[Wreath product|Wreath product]]) of  $  S _ {m _ {1}  } $
 +
with  $  S _ {m _ {2}  } $(
 +
for every decomposition  $  n = m _ {1} m _ {2} $).
 +
The primitive maximal subgroups in  $  S _ {n} $
 +
have not yet been described (1992), but certain infinite series of them are known. For example,  $  S _ {n} $
 +
acts naturally on the set  $  B _ {n}  ^ {m} $
 +
of all subsets of  $  m $
 +
elements of  $  \{ 1 \dots n \} $;
 +
for  $  n \neq 2m $
 +
this determines a primitive group of permutations of  $  B _ {n}  ^ {m} $.
 +
It is maximal in  $  S ( B _ {n}  ^ {m} ) $
 +
if  $  ( m, n) \neq ( 2, 6) $,
 +
$  ( 2, 8) $,
 +
$  ( 3, 10) $,
 +
$  ( 4, 12) $,
 +
$  ( m, 2m) $,
 +
$  ( m, 2m + 1) $(
 +
see [[#References|[1]]]). Another series is obtained by considering the group  $  \Gamma L _ {n} ( q) $
 +
of semi-linear transformations of the  $  n $-
 +
dimensional vector space over the finite field of  $  q $
 +
elements. This group defines a primitive group of permutations of the [[Grassmann manifold|Grassmann manifold]]  $  G _ {n,m} ( q) $,
 +
$  1 \leq  m \leq  n - 1 $,
 +
which is maximal in  $  S ( G _ {n,m} ( q)) $
 +
for  $  n \geq  3 $.
 +
 
 +
Let  $  X $
 +
be an infinite set. The group of all permutations of $  X $
 +
that move only a finite number of elements of $  X $
 +
is called the finitary, or restricted, symmetric group on $  X $,  
 +
and is denoted by $  \mathop{\rm SF} ( X) $;  
 +
its subgroup of even permutations is called the finite, or restricted, alternating group on $  X $,  
 +
and is denoted by $  \mathop{\rm AF} ( X) $.  
 +
The subgroups $  \mathop{\rm SF} ( X) $
 +
and $  \mathop{\rm AF} ( X) $
 +
are normal in $  S ( X) $.  
 +
More generally, let $  \alpha $
 +
be the cardinality of $  X $
 +
and let $  \beta \leq  \alpha $
 +
be an infinite cardinal; the set of permutations of $  X $
 +
which move at most $  \beta $
 +
elements of $  X $
 +
is a subgroup of $  S ( X) $,  
 +
denoted by $  S _  \beta  ( X) $.  
 +
Along with $  \mathop{\rm SF} ( X) $
 +
and $  \mathop{\rm AF} ( X) $,  
 +
the groups $  S _  \beta  ( X) $
 +
are normal subgroups in $  S ( X) $
 +
for all $  \beta \leq  \alpha $,  
 +
and in fact there are no other non-trivial normal subgroups in $  S ( X) $(
 +
the Schreier–Ulam–Baer theorem, see [[#References|[3]]]).
  
 
See also the references to [[Permutation of a set|Permutation of a set]].
 
See also the references to [[Permutation of a set|Permutation of a set]].
Line 21: Line 132:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O. Ore,  "Theory of graphs" , Amer. Math. Soc.  (1962)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  B.I. Plotkin,  "Groups of automorphisms of algebraic systems" , Wolters-Noordhoff  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.A. Ustimenko-Bakumovskii,  "Maximality of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s091670100.png" /> acting on subspaces of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s091670101.png" />"  ''Soviet Math. Dokl.'' , '''19''' :  3  (1978)  pp. 769–772  ''Dokl. Akad. Nauk SSSR'' , '''240''' :  6  (1978)  pp. 1305–1308</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O. Ore,  "Theory of graphs" , Amer. Math. Soc.  (1962)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  B.I. Plotkin,  "Groups of automorphisms of algebraic systems" , Wolters-Noordhoff  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.A. Ustimenko-Bakumovskii,  "Maximality of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s091670100.png" /> acting on subspaces of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s091670101.png" />"  ''Soviet Math. Dokl.'' , '''19''' :  3  (1978)  pp. 769–772  ''Dokl. Akad. Nauk SSSR'' , '''240''' :  6  (1978)  pp. 1305–1308</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
A [[Complete group|complete group]], i.e. a group without centre and outer automorphisms, is also called a perfect group.
+
See also [[#References|[a1]]] for a result on the structure of subgroups of $  S _ {n} $.
 
 
See also [[#References|[a1]]] for a result on the structure of subgroups of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091670/s091670102.png" />.
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I.M. Aschbacher,  L.L. Scott,  "Maximal subgroups of finite groups"  ''J. Algebra''  (1985)  pp. 44–80</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)  (Translated from German)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D. Passman,  "Permutation groups" , Benjamin  (1968)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I.M. Aschbacher,  L.L. Scott,  "Maximal subgroups of finite groups"  ''J. Algebra''  (1985)  pp. 44–80</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)  (Translated from German)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D. Passman,  "Permutation groups" , Benjamin  (1968)</TD></TR></table>

Latest revision as of 08:24, 6 June 2020


The group of all permutations (self-bijections) of a set $ X $ with the operation of composition (see Permutation group). The symmetric group on a set $ X $ is denoted by $ S ( X) $. For equipotent $ X $ and $ X ^ \prime $ the groups $ S ( X) $ and $ S ( X ^ \prime ) $ are isomorphic. The symmetric group of a finite set $ X = \{ 1 \dots n \} $ is denoted by $ S _ {n} $. Every abstract group is isomorphic to a subgroup of the symmetric group $ S ( X) $ of some set $ X $( Cayley's theorem).

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

$$ z ( \pi ) = ( a _ {1} \dots a _ {n} ), $$

where $ a _ {i} $ is the number of cycles of length $ i $ of $ \pi $, is called the cycle type (or cycle index) of $ \pi $. Two permutations $ \pi $ and $ \pi ^ \prime $ are conjugate in $ S _ {n} $ if and only if they have the same cycle type. Permutations with cycle type

$$ \{ n - 2, 1, 0 \dots 0 \} $$

are called transpositions; they form a system of generators for $ S _ {n} $. The set of transpositions $ \Sigma = \{ ( i, i + 1) : i = 1 \dots n - 1 \} $ is a minimal set of generators for $ S _ {n} $. In general, a set $ \Delta = \{ ( i _ {k} , j _ {k} ) : i _ {k} \neq j _ {k} \} $ generates $ S _ {n} $ if the graph with $ X $ as set of vertices and the pairs $ ( i _ {k} , j _ {k} ) $ as edges is a tree [2]. The number of such generating sets is $ n ^ {n - 2 } $.

The alternating group $ A _ {n} $ is a normal subgroup of $ S _ {n} $. If $ n \neq 4 $, $ A _ {n} $ is the unique non-trivial proper normal subgroup, and $ S _ {4} $ contains only one other non-trivial normal subgroup — the Klein four-group: $ K _ {4} = \{ 1, ( 1 2)( 3, 4), ( 1 3)( 2 4), ( 1 4) ( 2 3) \} $. For $ n \leq 4 $ the group $ S _ {n} $ is solvable, but for $ n \geq 5 $ it is not solvable and $ A _ {n} $ is a simple non-Abelian group. Hölder's theorem: For $ n \neq 2, 6 $, the group $ S _ {n} $ is complete (see Complete group). The group $ S _ {2} $ is commutative, and $ S _ {6} $ has an outer automorphism of order 2.

All maximal intransitive and imprimitive subgroups in $ S _ {n} $ are known. For each partition $ n = m _ {1} + m _ {2} $, $ m _ {1} \neq m _ {2} $, the only maximal intransitive subgroups in $ S _ {n} $ are the subgroups $ S _ {m _ {1} } \times S _ {m _ {2} } $. The only transitive imprimitive maximal subgroups in $ S _ {n} $ are the wreath products (cf. Wreath product) of $ S _ {m _ {1} } $ with $ S _ {m _ {2} } $( for every decomposition $ n = m _ {1} m _ {2} $). The primitive maximal subgroups in $ S _ {n} $ have not yet been described (1992), but certain infinite series of them are known. For example, $ S _ {n} $ acts naturally on the set $ B _ {n} ^ {m} $ of all subsets of $ m $ elements of $ \{ 1 \dots n \} $; for $ n \neq 2m $ this determines a primitive group of permutations of $ B _ {n} ^ {m} $. It is maximal in $ S ( B _ {n} ^ {m} ) $ if $ ( m, n) \neq ( 2, 6) $, $ ( 2, 8) $, $ ( 3, 10) $, $ ( 4, 12) $, $ ( m, 2m) $, $ ( m, 2m + 1) $( see [1]). Another series is obtained by considering the group $ \Gamma L _ {n} ( q) $ of semi-linear transformations of the $ n $- dimensional vector space over the finite field of $ q $ elements. This group defines a primitive group of permutations of the Grassmann manifold $ G _ {n,m} ( q) $, $ 1 \leq m \leq n - 1 $, which is maximal in $ S ( G _ {n,m} ( q)) $ for $ n \geq 3 $.

Let $ X $ be an infinite set. The group of all permutations of $ X $ that move only a finite number of elements of $ X $ is called the finitary, or restricted, symmetric group on $ X $, and is denoted by $ \mathop{\rm SF} ( X) $; its subgroup of even permutations is called the finite, or restricted, alternating group on $ X $, and is denoted by $ \mathop{\rm AF} ( X) $. The subgroups $ \mathop{\rm SF} ( X) $ and $ \mathop{\rm AF} ( X) $ are normal in $ S ( X) $. More generally, let $ \alpha $ be the cardinality of $ X $ and let $ \beta \leq \alpha $ be an infinite cardinal; the set of permutations of $ X $ which move at most $ \beta $ elements of $ X $ is a subgroup of $ S ( X) $, denoted by $ S _ \beta ( X) $. Along with $ \mathop{\rm SF} ( X) $ and $ \mathop{\rm AF} ( X) $, the groups $ S _ \beta ( X) $ are normal subgroups in $ S ( X) $ for all $ \beta \leq \alpha $, and in fact there are no other non-trivial normal subgroups in $ S ( X) $( 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

See also [a1] for a result on the structure of subgroups of $ S _ {n} $.

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