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