Creation of a Permutation Group#

Construction of the Symmetric Group#

Sym(n): RngIntElt -> GrpPerm#
SymmetricGroup(n): RngIntElt -> GrpPerm#: Given an integer \(n \geq 1\), create the generic permutation group acting on the natural \(G\)-set \(\Omega = \{ 1, 2, \ldots, n \}\), i.e. the symmetric group \({\operatorname{Sym}}(\Omega)\). Initially, only a structure table is created for \({\operatorname{Sym}}(n)\), so that, in particular, generators are not defined. This function is normally used to provide a context for the creation of elements and subgroups of \({\operatorname{Sym}}(n)\). If structural computation is attempted with the group created by Sym(n), then generators will be created dynamically.

Sym(X): Set -> GrpPerm#
SymmetricGroup(X): Set -> GrpPerm#: Given a finite set \(X\) of cardinality \(n \geq 1\), create the generic group \(G\) of permutations of \(X\) – the symmetric group \({\operatorname{Sym}}(X)\). Initially, only a structure table is created for \({\operatorname{Sym}}(X)\), so that, in particular, generators are not defined. This function is normally used to provide a context for the creation of elements and subgroups of \({\operatorname{Sym}}(X)\). If structural computation is attempted with the group created by Sym(X), then generators will be created dynamically. Although the group \(G\) is defined on the set \(X\), \(G\) is represented internally as a group of permutations of the set \(\Omega = \{ 1, 2, \ldots, n \}\). Translation between \(X\) and \(\Omega\) is done at input/output time. The precise representation can be found by using the Labelling function. If \(X\) is an indexed set then the indexing of elements of \(X\) determines the correspondence.

StandardGroup(G): GrpPerm -> GrpPerm, Map#: Return a group \(H\) isomorphic to \(G\), but acting on the standard set \(\lbrace 1, \ldots, n \rbrace\). This function is useful when the natural \(G\)-set for \(G\) is not the standard set. If the natural \(G\)-set for \(G\) is the standard set, \(G\) is returned. The isomorphism from \(G\) to \(H\) is also returned.

Example: Sym (ex-667d16)#

We define the symmetric group on the set of strings { "a" "b" "c" "d" }:

> S4 := Sym({ "a", "b", "c", "d" });
> S4;
Symmetric group S4 acting on a set of cardinality 4
Order = 24 = 2^3 * 3
> GSet(S4);
GSet{@ c, b, a, d @}

Run in calculator

We define the symmetric group of degree \(10\) acting on the set \(\{ 0, 1, \ldots,9\}\).

> G := Sym({ 0..9 });
> G;
Symmetric group G acting on a set of cardinality 10
Order = 3628800 = 2^8 * 3^4 * 5^2 * 7
> GSet(G);
GSet{@ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 @}

Run in calculator

Construction of a Permutation#

Throughout this subsection we shall assume that the permutation group \(G\) has natural \(G\)-set \(X\).

elt< G | L >: GrpPerm, List(Elt) -> GrpPermElt#: Given a permutation group \(G\) defined as acting on the set \(X = \{ x_1,\ldots, x_n\}\) of cardinality \(n \geq 1\), and a list \(L\) of distinct elements \(a_1, a_2, \ldots, a_n\) of \(X\), construct the element \(g\) of \(G\) defined by \(x_i \rightarrow a_i\), for \(i = 1,\ldots, n\). Unless \(G\) is known to be the generic permutation group of degree \(n\), the permutation will be tested for membership of \(G\), and if \(g\) is not an element of \(G\), the function will fail. If \(g\) does lie in \(G\), \(g\) will have \(G\) as its parent. Since the membership test may involve constructing a base and strong generating set for \(G\), this constructor may occasionally be very costly. Hence, a permutation \(g\) should be defined as an element of a subgroup of the generic group only when membership of \(G\) is required by subsequent operations involving \(g\).

G ! Q: GrpPerm, [ Elt ] -> GrpPermElt#: Given a permutation group \(G\) defined as acting on the set \(X = \{ x_1,\ldots, x_n\}\) of cardinality \(n \geq 1\), and a sequence \(Q = [a_1, a_2, \ldots, a_n]\) of distinct elements of \(X\), construct the permutation \(g\) of \(X\) defined by \(x_i \rightarrow a_i\), for \(i = 1,\ldots, n\). This permutation will have \(G\) as its parent structure. As in the case of the elt-constructor, the operation will fail if \(g\) is not an element of \(G\) and the same observations concerning the cost of membership testing apply.

G ! (...)(...)...(...): GrpPerm, Cycles -> GrpPermElt#: Given a permutation group \(G\) defined as acting on the set \(X=\{x_1\), \(x_2, \dots, x_n\}\), construct the permutation \(g\) corresponding to the given product of cycles. Adjacent letters must be separated by commas. Further, cycles of length one must be omitted. The coercion operator ! may be omitted only within the context of the standard constructors sub<>, ncl<> and quo<>. Once the permutation \(g\) has been constructed, it will be tested for membership in \(G\). If it is not a member, the construction fails.

G ! \(...)(...)...(...): GrpPerm, LiteralCycles -> GrpPermElt#: Given a permutation group \(G\) defined as acting on the set \(X=\{1 .. n\}\), construct the permutation \(g\) corresponding to the given product of literal cycles of integers. Adjacent integers must be separated by commas. Once the permutation \(g\) has been constructed, it will be tested for membership in \(G\). If it is not a member, the construction fails. This construction is strongly recommended when creating large permutations to avoid overhead in constructing unnecessarily large parse trees by Magma.

G ! Q: GrpPerm, SeqEnum[SetIndx] -> GrpPermElt#: Given a permutation group \(G\) defined as acting on the set \(X=\{1 .. n\}\), construct the permutation \(g\) corresponding to the given product of cycles. The indexed sets in \(Q\) must be disjoint subsets of \(X\), which are interpreted as the disjoint cycles of the permutation being constructed. Cycles of length 1 may be omitted, but do not have to be omitted. Once the permutation \(g\) has been constructed, it will be tested for membership in \(G\). If it is not a member, the construction fails. Note that the Cycle function produces results suitable for use as members of \(Q\).

ElementToSequence(g): GrpPermElt -> [ Elt ]#
Eltseq(g): GrpPermElt -> [ Elt ]#: The sequence \(Q\) of images of the \(G\)-set of g. In particular, it has the property that Parent(g)!Eltseq(g) eq g.

Identity(G): Grp -> GrpPermElt#
Id(G): Grp -> GrpPermElt#
G ! 1: Grp, RngIntElt -> GrpPermElt#: Construct the identity permutation in the permutation group \(G\).

Example: Permutations (ex-ffdb2d)#

The three different constructions are illustrated by the following code, which assigns to each of the variables \(x\), \(y\) and \(z\) the permutation (1)(2,3)(4,5,6).

> S6 := Sym(6);
> x := elt<S6 | 1,3,2,5,6,4>;
> x;
(2, 3)(4, 5, 6)
> y := S6![1,3,2,5,6,4];
> y;
(2, 3)(4, 5, 6)
> z := S6!(2,3)(4,5,6);
> z;
(2, 3)(4, 5, 6)
> S6!1;
Id(S6)

Run in calculator

Construction of a General Permutation Group#

PermutationGroup< X | L >: Set, List -> GrpPerm#

Suppose that the cardinality of the set \(X\) is \(n\). Construct the permutation group \(G\) acting on the set \(X\) generated by the permutations defined by the list \(L\). A term of the list \(L\) must be an object of one of the following types:

(a): A sequence of \(n\) elements of \(X\) defining a permutation of \(X\) (note that this is only well-defined when \(X\) is an indexed set);
(b): A set or sequence of sequences of type (a);
(c): An element of \({\operatorname{Sym}}(X)\);
(d): A set or sequence of elements of \({\operatorname{Sym}}(X)\);
(e): A subgroup of \({\operatorname{Sym}}(X)\);
(f): A set or sequence of subgroups of \({\operatorname{Sym}}(X)\).

Each element or group specified by the list must belong to the same generic permutation group. The group \(G\) will be constructed as a subgroup of some group which contains each of the elements and groups specified in the list. The generators of \(G\) consist of the elements specified by the terms of the list \(L\) together with the stored generators for groups specified by terms of the list. The PermutationGroup constructor is shorthand for the two statements:

   SX := Sym(X);
   G := sub< SX | L >;

where sub< ... > is the subgroup constructor described in the next subsection.

PermutationGroup< n | L >: RngIntElt, List -> GrpPerm#: Construct the permutation group \(G\) acting on the set \(X = \{ 1, 2, \ldots, n \rbrace\) generated by the permutations defined by the list \(L\). The possibilities for the terms of the list \(L\) are the same as for the constructor PermutationGroup< X | L >.

Example: Hessian (ex-1e0f19)#

The Hessian group generated by the permutations \((1,2,4)(5,6,8)(3,9,7)\) and \((4,5,6)(7,9,8)\) may be created by the statement:

> H := PermutationGroup< 9 | (1,2,4)(5,6,8)(3,9,7), (4,5,6)(7,9,8) >;
> H;
Permutation group H acting on a set of cardinality 9
       (1, 2, 4)(3, 9, 7)(5, 6, 8)
       (4, 5, 6)(7, 9, 8)

Run in calculator