Permutation group

In group theory , a group of permutations of a finite set with the sequential execution as a group link is called a permutation group . The group of all permutations of is called its symmetric group . In this sense, the permutation groups are precisely the subgroups of the symmetrical groups. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle S(M)}$

According to Cayley's theorem , every finite group is isomorphic to a subgroup of the symmetric group, i.e. to a permutation group . In this respect, every finite group “is” a permutation group. If one regards the finite group as an abstract algebraic structure , then one says more precisely: operates as a permutation group on the set . This makes it clear that this true permutation representation is a clear description of the group structure, in addition to which other descriptions are also possible. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle M}$

Definitions

Definition through a group operation

Be a group with the neutral element . operates as a permutation group if and only if: ${\displaystyle (G,\cdot )}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle M}$

1. ${\displaystyle M}$ is a finite set.
2. ${\displaystyle G}$operates on , which means that there is a mapping that obeys the rules for all . ${\displaystyle M}$ ${\displaystyle G\times M\rightarrow M,(g,m)\mapsto g\circ m\in M}$ ${\displaystyle e\circ m=m,(g\cdot h)\circ m=g\circ (h\circ m)}$ ${\displaystyle m\in M;\;g,h\in G}$
3. The operation is true (ger .: faithful ), that is, it applies: If for all , then follows . Or it applies equally: for everyone , then follows . ${\displaystyle \circ }$ ${\displaystyle g\circ m=h\circ m}$ ${\displaystyle m\in M}$ ${\displaystyle g=h}$ ${\displaystyle g\circ m=m}$ ${\displaystyle m\in M}$ ${\displaystyle g=e}$

A group operation that only fulfills the 2nd and 3rd conditions is called faithful . So if and operates as a permutation on when the operation faithful and is finite. A group operation that meets only the first and the second condition is, as a permutation (ger .: permutation representation ) of referred. So if and operates as a permutation on when the group operation a loyal is permutation. ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle M}$

Definition by a group homomorphism

Equivalent description: operates as a permutation group if and only if is a finite set and an injective group homomorphism exists. Here is the set of all bijective self-images of the set . In this description, the operation from the first definition is given by, the requirement of injectivity is equivalent to the requirement that the operation be faithful. ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \phi :G\rightarrow S(M)}$ ${\displaystyle S(M)=\{\alpha \in M^{M}:\;\alpha \;{\text{ist bijektiv}}\}}$ ${\displaystyle M}$ ${\displaystyle \circ }$ ${\displaystyle g\circ m=(\phi (g))(m)}$

Note that in the case of the definitions given here for a permutation group, it is not necessary to require that the group be finite; this follows from the finiteness of . ${\displaystyle G}$ ${\displaystyle M}$

Isomorphism as permutation groups

For two groups and , which operate on two finite sets or as permutation groups, a tightening of the isomorphic term is defined: and are called isomorphic as permutation groups if and only if a group isomorphism and a bijection exist so that applies to all . One can show that two groups and , which operate faithfully on the same set , are isomorphic as permutation groups if and only if their picture groups in the symmetric group, determined by the group operations, are conjugated subgroups , that is, if they are conjugated to one another by conjugation with a fixed group element can be mapped. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle \sigma :G\rightarrow H}$ ${\displaystyle \psi :M\rightarrow N}$ ${\displaystyle \psi (g\circ m)=(\sigma (g))\circ \psi (m)}$ ${\displaystyle g\in G,m\in M}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle M=N=\{1,2,\ldots ,n\}}$ ${\displaystyle \phi _{1}(G),\phi _{2}(H)<S_{n}}$ ${\displaystyle S_{n}}$

Semi-regular and regular

• When operating on as a permutation group, this operation is called semiregular and semiregular permutation group if and only if the only element of that fixes any element of is the one element of . Formally: ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle \left(\exists m\in M:g\circ m=m\right)\Rightarrow g=e.}$

• The operation is said to be regular and is called if and a regular permutation on when the operation semi regular and transitive is. The operation is called transitive if every element of can be mapped onto any arbitrary element of by the operation . Formally: See for further possible transitivity properties of a permutation group group operation # Transitive group operation . ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \forall m,n\in M\exists g\in G:g\circ m=n.}$

Same words, but with a difference in meaning!

In the term (left-) regular representation and also in the group-specialized sense of this word, as it is described in the article Theorem by Cayley , regular describes as a homonym a property that neither specializes nor generalizes the one described here! In Cayley's Theorem "special regular representation" described, in which the group is via left multiplication surgery on yourself really - perhaps by accident - one but generally not the only "regular permutation" of the group. This special case is explained in the examples in this article .

properties

The properties described in this section can be found in the textbook Design Theory , which is mentioned in the literature. Trivial properties are demonstrated here or in the Examples and Counterexamples section of this article .

• Every finite group can be represented as a regular permutation group. Such a representation is given by the “left multiplication” of the group, see the examples.
• For any finite group, a permutation representation on any finite set can be explained as a group operation, for example the trivial operation is chosen . However, a true permutation representation requires a minimum number of elements that depends on the group structure . Then for every natural number that is not less than there is a faithful permutation representation on every set with elements. ${\displaystyle M}$ ${\displaystyle \circ :G\times M\rightarrow M:g\circ m:=m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$

• Only for the trivial one group is . ${\displaystyle \{e\}}$ ${\displaystyle m=1}$
• If the group contains an element of the order , where is a prime power , then is . ${\displaystyle G}$ ${\displaystyle p^{r}}$ ${\displaystyle p^{r}}$ ${\displaystyle m\geq p^{r}}$
• According to Cauchy's theorem , a special case of one of Sylow's theorems , then applies in particular : If the prime number divides the group order , then is . ${\displaystyle p}$ ${\displaystyle m\geq p}$

→ In Cayley's theorem # Minimal permutation representations , which means there are minimal regular representations as a permutation group in the parlance of this article, the question of the size of is deepened. ${\displaystyle m=m(G)}$

• Be a group, a subgroup. If operates on as a permutation group, then operates on as a permutation group via the operation restricted to this subgroup . ${\displaystyle G}$ ${\displaystyle H<G}$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle H}$ ${\displaystyle M}$

• If the operation is transitive, then it is also that of ; conversely, the operation of can be transitive, but the restricted operation of cannot. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$
• If, on the other hand, the operation of is semiregular, then it is also that of ; the converse does not have to apply here either. ${\displaystyle G}$ ${\displaystyle H}$

Examples and counterexamples

The ideas for the examples mentioned in this section can be found in the spirit of the textbook Design Theory , which is mentioned in the literature.

• Each finite group operates on itself through left multiplication . This operation is faithful and semi-regular (because of the truncation rule for groups) and transitive, so every finite group operates via left multiplication as a regular permutation group on the set of its elements and is therefore isomorphic to a transitive subgroup of the symmetric group if it contains elements. The right multiplication generally leads to a different embedding of the group , in addition, the group link must it be reversed: , so that the right multiplication satisfies the above rules (2) for an operation of the left or the rules need for surgery right be reformulated accordingly. ${\displaystyle (G,\cdot )}$ ${\displaystyle (M=G)}$ ${\displaystyle G\times M\rightarrow M:g\circ m:=g\cdot m}$ ${\displaystyle S_{n}}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle S_{n}}$ ${\displaystyle G\times M\rightarrow M:g\circ m:=m\cdot g}$ ${\displaystyle G^{\mathrm {op} }:h\cdot ^{\mathrm {op} }g:=g\cdot h,(g,h\in G)}$

• The cyclic residue class group operates regularly by left addition on itself and in the same way on the residues . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} ,+)\cong (C_{n},\cdot ),n\geq 2}$ ${\displaystyle g\circ m:=g+m}$ ${\displaystyle M=\{0,1,2,\ldots ,n-1\}}$

• The symmetric group on elements operates in its initial representation on faithful and transitive, but only for semi-regular. However, it operates on itself with left multiplication as a regular permutation group. ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle M=\{1,2,..n\}}$ ${\displaystyle n\leq 2}$
• A finite group operates on itself also through conjugation . However, this operation is generally not faithful. However, every finite, non-commutative , simple group operates via conjugation as a permutation group (i.e. faithfully) on itself. ${\displaystyle G}$ ${\displaystyle g\circ m:=g\cdot m\cdot g^{-1}}$
• The linear group ( prime power) operates as a permutation group . is the finite set of vectors in the -dimensional vector space over the finite field with elements. The operation is transitive on , but generally not semi-regular. ${\displaystyle G=\mathrm {GL} (n,q)}$ ${\displaystyle n\geq 2,q=p^{r}>1}$ ${\displaystyle M=(\mathbb {F} _{q})^{n}}$ ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle N=M\setminus \{0\}}$

• If a real linear subspace of and is the subgroup, which maps to itself as a whole, then operates transitively, but not as a permutation group , because the operation is not faithful. In contrast, the factor group , where is the subgroup of and , which fixes each individual element of , operates naturally transitive as a permutation group . ${\displaystyle M<(\mathbb {F} _{q})^{n}}$ ${\displaystyle (\mathbb {F} _{q})^{n},q,n>1}$ ${\displaystyle H<G=\mathrm {GL} (n,q)}$ ${\displaystyle M}$ ${\displaystyle H}$ ${\displaystyle N=M\setminus \{0\}}$ ${\displaystyle H/U}$ ${\displaystyle U=\{u\in H:\forall m\in M:u(m)=m\}}$ ${\displaystyle G}$ ${\displaystyle U}$ ${\displaystyle N}$ ${\displaystyle N}$
• For an infinite field (for example ) it operates faithfully and transitively, but not as a permutation group , because it is not finite. ${\displaystyle K}$ ${\displaystyle K=\mathbb {R} }$ ${\displaystyle \mathrm {GL} (n,K),(n\geq 2)}$ ${\displaystyle N=K^{n}\setminus \{0\}}$ ${\displaystyle N}$

• Be the Klein four-group as a subgroup of the symmetric group . operates as a regular permutation group . ${\displaystyle V_{4}=\{e,(12)(34),(13)(24),(14)(23)\}}$ ${\displaystyle S_{4}}$ ${\displaystyle V_{4}}$ ${\displaystyle M=\{1,2,3,4\}}$

• The group contains three further subgroups that are too isomorphic, e.g. B.  . Because , as defined herein, semi-regular on surgery, however, not because and the track of during the operation of contains only two elements, the two subgroups are not as permutation on isomorphic. On the other hand, it is isomorphic as a permutation group to the other two (from different!) Groups that are generated by two disjoint transpositions. ${\displaystyle S_{4}}$ ${\displaystyle V_{4}}$ ${\displaystyle U=\{e,(13),(24),(13)(24)\}}$ ${\displaystyle V_{4}}$ ${\displaystyle M}$ ${\displaystyle U}$ ${\displaystyle 1}$ ${\displaystyle U}$ ${\displaystyle M}$ ${\displaystyle U}$ ${\displaystyle V_{4}}$
• The subgroup is like transitive, but in contrast to is not semi-regular. ${\displaystyle H=V_{4}}$ ${\displaystyle G=S_{4}}$ ${\displaystyle G}$ ${\displaystyle H}$

• The cyclic group with six elements operates as a regular permutation group via left multiplication on itself, which corresponds to its usual permutation representation on . But it also operates as a permutation group on the set , but here not transitive and not semi-regular. For this group, the number is the minimum thickness for a set on which operates as a permutation group. The restricted operation of is semi-regular but not transitive. ${\displaystyle G\cong C_{6}\cong C_{2}\times C_{3}}$ ${\displaystyle G\cong <\xi =(123456)>}$ ${\displaystyle M=\{1,2,3,4,5,6\}}$ ${\displaystyle G\cong <(12)(345)>}$ ${\displaystyle N=\{1,2,3,4,5\}>}$ ${\displaystyle m=5}$ ${\displaystyle G}$ ${\displaystyle H\cong <\xi ^{3}=(14)(25)(36)>}$
• The cyclic group with three elements operates regularly on , its permutation representation can be seen as a restriction of the operation of the symmetric group whose subgroup is. But operates on transitive, but not semi-regular. ${\displaystyle H\cong C_{3}}$ ${\displaystyle M=\{1,2,3\}}$ ${\displaystyle G=S_{3}}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle M}$

Finite symmetry groups

In the geometry of many groups occur which thereby defined are that they represent a geometric figure as a whole up. For example, the group of movements of the three-dimensional visual space, which the unit cube (spanned by the three standard basis vectors) as a whole, is a typical symmetry group .

• The symmetry group of a (non-degenerate) polyhedron in the visual space operates as a permutation group on the (finite!) Set of vertices of the polyhedron.
• The symmetry group of a sphere in visual space operates transitively on the set of points on the spherical surface, but not on any set as a permutation group: Because the operation is transitive, it cannot be restricted to a finite set of points for the entire symmetry group . On the other hand, the symmetry group of the unit cube can be understood as a subgroup of , if one chooses the sphere circumscribed around the cube, i.e. the sphere through all corner points of the cube. ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle N\subseteq M}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle N}$ ${\displaystyle G}$
• The symmetry group of an equilateral triangle in the real plane operates as a transitive permutation group, but not semiregularly on the set of vertices of the triangle.
• More generally, the symmetry group of a regular corner operates as a transitive, non-semiregular permutation group on the set of vertices of the corner. This description can be used as a definition of the dihedral group (as a subgroup of the symmetrical group ). ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n\geq 3}$ ${\displaystyle \{1,2,\ldots n\}}$ ${\displaystyle n}$ ${\displaystyle n\geq 3}$ ${\displaystyle G=D_{n}}$ ${\displaystyle S_{n}}$
• The symmetry group of a segment on the real straight line (i.e. a real interval ) operates as a regular permutation group on its boundary points. It is the two-element group , with the reflection of the straight line at the middle of the interval . ${\displaystyle [a,b],a<b}$ ${\displaystyle \{e,s\}}$ ${\displaystyle s}$ ${\displaystyle (a+b)/2}$
• On the other hand, the symmetry group (in the sense described above) does not operate faithfully to a line in three-dimensional space and therefore not as a permutation group on the edge points of the line. This group is even infinite - note the rotations in which the line is on the axis! As in the example of a linear subspace in a finite vector space above, one has to move on to the factor group after the subgroup of movements that map each point of the segment onto itself. This brings you back to a group that is isomorphic to the group mentioned in the previous example. This canonical factor group is often referred to as the symmetry group (here: the segment). ${\displaystyle H}$ ${\displaystyle H/U}$ ${\displaystyle U}$

Automorphism groups of finite structures

The structure-preserving, bijective self-mapping of finite structures, for example finite incidence structures such as block plans , finite projective levels etc. operate as permutation groups on the finite set of "elements" of the structure (for incidence structures , i.e. the set of "points" together with the amount of "blocks"). In the most important cases, for example for all simple block plans (also for all “classical” finite geometries ), it is sufficient to use the point or block set as the set , since the automorphism groups already operate faithfully on at least one of these sets . Mostly the point set is used. The group of all structure-preserving, bijective self-mapping of the structure is referred to as a full automorphism group of the structure, each of its subgroups as an automorphism group . According to the construction, these groups operate as permutation groups on the set of structural elements, in the most important cases already on the point set. ${\displaystyle M}$ ${\displaystyle M={\mathfrak {p}}\cup {\mathfrak {B}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \mathrm {Aut} ({\mathcal {I}})}$

• The finite simple group operates as a permutation and full automorphism group transitively, but not regularly on the projective Fano plane , i.e. H. specifically on the amount of their seven points. In the article Fano-level the structure of this group and the faithful permutation representation described here as a subgroup of the alternating group is presented in detail. ${\displaystyle \mathrm {PGL} (3,2)}$ ${\displaystyle PG(2,2)}$ ${\displaystyle A_{7}}$
• The five sporadic math groups operate as permutation and full automorphism groups each on a Witt block diagram assigned to them - here too the point set is sufficient for a clear description.
• A somewhat artificial example of an incidence structure in which the full automorphism group operates as a permutation group neither on the point nor on the block set is with the sets . Here the automorphism group is the product , so it is isomorphic to Klein's group of four . But operates faithfully neither on the point nor on the block set! The same statements apply if, instead of this point and block set by the incidence by defined. ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle {\mathfrak {p}}=\{p_{1},p_{2}\},\;{\mathfrak {B}}=\{B_{1},B_{2}\},\;I=\emptyset ,\;{\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle G=\mathrm {Aut} ({\mathcal {I}})=<(p_{1}p_{2}),(B_{1}B_{2})>}$ ${\displaystyle G}$ ${\displaystyle G\cong C_{2}\times C_{2}}$ ${\displaystyle G}$ ${\displaystyle I=\emptyset }$ ${\displaystyle I'={\mathfrak {p}}\times {\mathfrak {B}}}$

Permutation representation

Linear representation associated with a permutation group

Let be a finite set on which the group operates. The group is then the group of all permutations of with the composition as a link. The operation of a group on a finite set is sometimes already considered sufficient for defining the permutation representation. But since we want to give examples of linear representations in which the group operates on a vector space and not on an arbitrary finite set, we choose the following approach: We construct the permutation representation to be associated as a representation of in a vector space whose basis with the elements out can be indexed and the property for each fulfilled. This clearly defines the linear maps . ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle {\text{Aut}}(X)}$ ${\displaystyle X}$

${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle \rho (s)e_{x}=e_{s.x}}$ ${\displaystyle s\in G,x\in X}$ ${\displaystyle \rho (s)}$

example

Let and Then operates on via The corresponding linear representation is where for ${\displaystyle X=\{1,2,3\}}$ ${\displaystyle G={\text{Per}}(3).}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle {\text{Aut}}(X)=G.}$
${\displaystyle \rho \colon G\to {\text{GL}}(V)\cong {\text{GL}}_{3}(\mathbb {C} ),}$ ${\displaystyle \rho (\sigma )e_{x}=e_{\sigma (x)}}$ ${\displaystyle \sigma \in G,x\in X.}$

Left and right regular representation

Let be a group with and be a vector space of the dimension whose base is indexed with the elements from . The left-regular representation is then a special case of the permutation representation in which we set. It applies to all forms Thus, the family of the images of a base from which we the neutral element of the group here with have referred. The degree of left-regular display corresponds to the group order. The right-regular representation is defined similarly: In this case, it operates from the right on the basis of indexed with elements from Here too, the images of the first basis vector under the operation form a basis of the vector space and the degree corresponds to the group order. The two representations are isomorphic to one another via . Therefore, one often only speaks of the regular representation here. A closer look reveals that any linear representation with the property that there is such that there is a basis of is isomorphic to the left regular representation. ${\displaystyle G}$ ${\displaystyle {\text{ord}}(G)=g}$ ${\displaystyle V}$ ${\displaystyle g,}$ ${\displaystyle (e_{t})_{t\in G}}$ ${\displaystyle G}$ ${\displaystyle X=G}$ ${\displaystyle \rho (s)e_{t}=e_{st}}$ ${\displaystyle s,t\in G.}$ ${\displaystyle (\rho (s)e_{1})_{s\in G}}$ ${\displaystyle e_{1}}$ ${\displaystyle V,}$ ${\displaystyle G}$ ${\displaystyle 1}$
${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle V:\rho (s)e_{t}=e_{ts^{-1}}.}$
${\displaystyle e_{s}\mapsto e_{s^{-1}}}$
${\displaystyle \rho \colon G\to {\text{GL}}(W)}$ ${\displaystyle w\in W}$ ${\displaystyle (\rho (s)w)_{s\in G}}$ ${\displaystyle W}$

example

Let and with basis The left-regular representation is then defined by for The right- regular representation is obtained analogously by for ${\displaystyle G=\mathbb {Z} /5\mathbb {Z} }$ ${\displaystyle V=\mathbb {R} ^{5}}$ ${\displaystyle e_{\overline {0}},\dotsc ,e_{\overline {4}}.}$ ${\displaystyle L_{\rho }\colon G\to {\text{GL}}(V)}$ ${\displaystyle L_{\rho }(k)e_{l}=e_{k+l}}$ ${\displaystyle k,l\in \mathbb {Z} /5\mathbb {Z} .}$
${\displaystyle R_{\rho }(k)e_{l}=e_{l-k}}$ ${\displaystyle k,l\in \mathbb {Z} /5\mathbb {Z} .}$

See also

• The cycle structure of a permutation group is summarized by the cycle pointer .
• Other unambiguous descriptions of a finite group are the linking table or the representation by generators and relations , with the latter not only finite, but more generally finitely generable groups can be described.
• For more ways to describe a finite group, see the article Representation Theory (Group Theory) .

literature

• Michael Artin : Algebra. Birkhäuser, Basel a. a. 1993, ISBN 3-7643-2927-0 , chapter 1.
• Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . 2nd Edition. BI Wissenschaftsverlag, London / New York / New Rochelle / Melbourne / Sidney 1999, ISBN 0-521-33334-2 .
• Günther Eisenreich: Lexicon of Algebra . Akademie-Verlag, Berlin 1989, ISBN 3-05-500231-8 .
• Thomas W. Hungerford: Algebra . 5th edition. Springer, Berlin / Heidelberg / New York 1989, ISBN 0-387-90518-9 , Chapter I Groups.

Web links

• Eric W. Weisstein : Permutation Group . In: MathWorld (English).

Individual evidence

1. ↑ Artin (1993)
2. ↑ ^{a b c} Beth, Jungnickel, Lenz, definition III.3.1
3. ↑ Beth, Jungnickel, Lenz, Definition III.3.8: English: semiregular permutation group
4. ↑ ^{a b} Beth, Jungnickel, Lenz
5. ↑ This means here: no three corner points lie on the same straight line and the set of all corner points does not lie in a common plane