Subsections

• Construction of the Symmetric Group
• Construction of a Permutation
• Coercion
• Arithmetic with Permutations

SymmetricGroup(n) : RngIntElt -> GrpPerm

Given an integer n >= 1, create the generic permutation group acting on the natural G-set Omega = { 1, 2, ..., n }, i.e. the symmetric group Sym(Omega). Initially, only a structure table is created for 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 Sym(n). If structural computation is attempted with the group created by Sym(n), then generators will be created dynamically. The alternative function SymmetricGroup(GrpPerm, n) will create generators for Sym(n) at the outset.

Sym(X) : Set -> GrpPerm

SymmetricGroup(X) : Set -> GrpPerm

Given a finite set X of cardinality n >= 1, create the generic group G of permutations of X -- the symmetric group Sym(X). Initially, only a structure table is created for 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 Sym(X). If structural computation is attempted with the group created by Sym(X), then generators will be created dynamically. The alternative function SymmetricGroup(GrpPerm, X) will create generators for Sym(X) at the outset. 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, ..., n }. Translation between X and Omega is done at input/output time.

Return a group H isomorphic to G, but acting on the standard set { 1, ..., n }. 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. A mapping giving the correspondence between the G-set for G and that for H is also returned.

• 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 }

• We define the symmetric group of degree 10 acting on the set { 0, 1, ..., 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 }

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, ..., x_n} of cardinality n >= 1, and a list L of distinct elements a_1, a_2, ..., a_n of X, construct the element g of G defined by x_i -> a_i, for i = 1, ..., 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.

Given a permutation group G defined as acting on the set X = { x_1, ..., x_n} of cardinality n >= 1, and a sequence Q = [a_1, a_2, ..., a_n] of distinct elements of X, construct the permutation g of X defined by x_i -> a_i, for i = 1, ..., 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, ..., 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 and Magma .

Id(G) : Grp -> GrpPermElt

G ! 1 : Grp, RngIntElt -> GrpPermElt

Construct the identity permutation in the permutation group G.

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.

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

Given a subgroup G of Sym(X) and a permutation g belonging to Sym(X) that is contained in G, embed g in G. Thus this operator changes the parent of g into G.

Given a group H whose natural G-set X is a subset of the natural G-set Y for the group G, embed H as a subgroup of G. The operator fails if the image of H in Sym(Y) is not a subgroup of G.

Product of permutation g and permutation h, where g and h belong to the same generic group U. If g and h both belong to the same proper subgroup G of U, then the result will be returned as an element of G; if g and h belong to subgroups H and K of a subgroup G of U, then the product is returned as an element of G. Otherwise, the product is returned as an element of U.

The n-th power of the permutation g, where n is a positive, negative or zero integer.

Product of the permutation g by the inverse of the permutation h, i.e. the element g * h^(-1). Here g and h must belong to the same generic group U. The rules for determining the parent group of g / h are the same as for g * h.

Conjugate of the permutation g by the permutation h, i.e. the element h^(-1) * g * h. Here g and h must belong to the same generic group U. The rules for determining the parent group of g^h are the same as for g * h.

Commutator of the permutations g and h, i.e. the element g^(-1) * h^(-1) * g * h. Here g and h must belong to the same generic group U. The rules for determining the parent group of (g, h) are the same as those for g * h.

Given r permutations g_1, ..., g_r belonging to a common group, return their commutator. Commutators are left-normed, so they are evaluated from left to right.

Given permutations g and h belonging to the same generic group, return true if g and h are the same element, false otherwise.

Given permutations g and h belonging to the same generic group, return true if g and h are distinct elements, false otherwise.

IsIdentity(g) : GrpPermElt -> BoolElt

True if the permutation g is the identity permutation.

Given a permutation g belonging to a group of degree n, return the partition of n corresponding to the cycles of g. This partition is returned in the form of a sequence Q of pairs, where the terms of Q correspond to the distinct cycle lengths of g. The value of the term Q[i] is a tuple < l_i, n_i > belonging to Z x Z. Here l_i is the length of a cycle of g and n_i is the number of cycles of length l_i.

Given a permutation g, return the degree of g, i.e. the number of points moved by g.

True if the permutation g is an even permutation, false otherwise.

Order of the permutation g.

• We illustrate the permutation operations by applying them to some elements of Sym(9).

> G := Sym(9);
> x := G ! (1,2,4)(5,6,8)(3,9,7);
> y := G ! (4,5,6)(7,9,8);
> x*y;
(1, 2, 5, 4)(3, 8, 6, 7)
> x^-1;
(1, 4, 2)(3, 7, 9)(5, 8, 6)
> x^2;
(1, 4, 2)(3, 7, 9)(5, 8, 6)
> x / y;
(1, 2, 6, 9, 8, 4)(3, 7)
> x^y;
(1, 2, 5)(3, 8, 9)(4, 7, 6)
> (x, y);
(1, 7, 3, 6)(4, 5, 9, 8)
> x^y eq y^x;
false
> CycleStructure(x^2*y);
[ <6, 1>, <2, 1>, <1, 1> ]
> Degree(y);
6
> Order(x^2*y);
6