Permutations

Coercion

G ! g: GrpPerm, GrpPermElt -> GrpPermElt: Given a subgroup \(G\) of \({\operatorname{Sym}}(X)\) and a permutation \(g\) belonging to \({\operatorname{Sym}}(X)\) that is contained in \(G\), embed \(g\) in \(G\). Thus, this operator changes the parent of \(g\) to be \(G\).

G !! H: GrpPerm, GrpPerm -> GrpPerm: 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 \({\operatorname{Sym}}(Y)\) is not a subgroup of \(G\).

Arithmetic with Permutations

g * h: GrpPermElt, GrpPermElt -> GrpPermElt: 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\).

g ^ n: GrpPermElt, RngIntElt -> GrpPermElt: The \(n\)-th power of the permutation \(g\), where \(n\) is a positive, negative, or zero integer.

g / h: GrpPermElt, GrpPermElt -> GrpPermElt: 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\).

g ^ h: GrpPermElt, GrpPermElt -> GrpPermElt: 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\).

(g, h): GrpPermElt, GrpPermElt -> GrpPermElt: 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\).

(g₁, ..., gᵣ): GrpPermElt, ..., GrpPermElt -> GrpPermElt: Given \(r\) permutations \(g_1, \ldots, g_r\) belonging to a common group, return their commutator. Commutators are left-normed, so they are evaluated from left to right.

Properties of Permutations

CycleStructure(g): GrpPermElt -> [ <RngIntElt, RngIntElt> ]: 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 \({\mathbb{Z}}\times {\mathbb{Z}}\). Here \(l_i\) is the length of a cycle of \(g\) and \(n_i\) is the number of cycles of length \(l_i\).

Degree(g): GrpPermElt -> RngIntElt: Given a permutation \(g\), return the degree of \(g\), i.e. the number of points moved by \(g\).

IsEven(g): GrpPermElt -> BoolElt: Returns true if the permutation \(g\) is an even permutation, false otherwise.

Sign(g): GrpPermElt -> RngIntElt: Return 1 if the permutation \(g\) is even, return -1 if \(g\) is odd.

Order(g): GrpPermElt -> RngIntElt: Order of the permutation \(g\).

Predicates for Permutations

g eq h: GrpPermElt, GrpPermElt -> BoolElt: Given permutations \(g\) and \(h\) belonging to the same generic group, return true if \(g\) and \(h\) are the same element, false otherwise.

g ne h: GrpPermElt, GrpPermElt -> BoolElt: Given permutations \(g\) and \(h\) belonging to the same generic group, return true if \(g\) and \(h\) are distinct elements, false otherwise.

IsId(g): GrpPermElt -> BoolElt
IsIdentity(g): GrpPermElt -> BoolElt: Returns true if the permutation \(g\) is the identity permutation.

Example: Arithmetic with Permutations (ex-531aba)

Run in calculator (opens in a new tab)

We illustrate the permutation operations by applying them to some elements of \({\operatorname{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

Run in calculator (opens in a new tab)

Set Operations

The creation of a base and strong generating set (BSGS) for a permutation group \(G\) provides us with a very compact representation of the set of elements of \(G\). A particular BSGS imposes an order on the elements of \(G\) (lexicographic ordering of base images). It thus makes sense to talk about the ‘number’ of a group element relative to a particular BSGS.

G * H: GrpPerm, GrpPerm -> { GrpPermElt }: Given permutation groups \(G\) and \(H\), where \(G\) and \(H\) both belong to the same generic group, form the set product \(\{ g*h | g\in G, h\in H \}\) as a set of group elements.

ElementSet(G, H): GrpPerm, GrpPerm -> { GrpPermElt }: Given a group \(G\) and a subgroup \(H\) of \(G\), return the elements of \(H\) in the form of a set of elements of \(G\). This function is only applicable to very small groups.

NumberingMap(G): GrpPerm -> Map: A bijective mapping from the group \(G\) onto the set of integers \(\{ 1 \ldots |G| \rbrace\). The actual mapping depends upon the base and strong generating set chosen for \(G\).

RandomProcess(G): GrpPerm -> Process

Slots   : RngIntElt                    Default: 10
Scramble: RngIntElt                    Default: 20

Create a process to generate randomly chosen elements from the finite group \(G\). The process is based on the product-replacement algorithm of [CLGM+95], modified by the use of an accumulator. At all times, \(N\) elements are stored where \(N\) is the maximum of the specified value for Slots and Ngens\((G) + 1\). Initially, these are just the generators of \(G\). As well, one extra group element is stored, the accumulator. Initially, this is the identity. Random elements are now produced by successive calls to Random(P), where \(P\) is the process created by this function. Each such call chooses one of the elements in the slots and multiplies it into the accumulator. The element in that slot is replaced by the product of it and another randomly chosen slot. The random value returned is the new accumulator value. Setting Scramble := m causes \(m\) such operations to be performed before the process is returned.

Random(G: parameters): GrpPerm -> GrpPermElt

Short: BoolElt                    Default: false

A randomly chosen element for the group \(G\). If a BSGS is known for \(G\), then the distribution will be uniform over \(G\). If no BSGS is known, then the random element is chosen by multiplying out a random word in the generators. Since it is usually not practical to choose words long enough to properly sample the elements of \(G\), the element returned will usually be biased. The boolean-valued parameter Short is used in this situation to indicate that a short word will suffice. Thus, if Random is invoked with Short assigned the value true then the element is constructed using a short word.

Random(P): Process -> GrpPermElt: Given a random element process \(P\) created by the function RandomProcess(G) for the finite group \(G\), construct a random element of \(G\) by forming a random product over the expanded generating set constructed when the process was created. For large degree groups, or groups for which a BSGS is not known, this function should be used in preference to Random(G).

Representative(G): GrpPerm -> GrpPermElt
Rep(G): GrpPerm -> GrpPermElt: An element chosen from the permutation group \(G\).

Example: Multiplication Table of a Dihedral Group (ex-80e2ef)

Run in calculator (opens in a new tab)

We use the function NumberingMap to construct the multiplication table for the dihedral group of order \(12\).

> G := DihedralGroup(GrpPerm, 6);
> f := NumberingMap(G);
> [ [ f(x*y) : y in G ] : x in G ];
[
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ],
    [ 2, 3, 4, 5, 6, 1, 12, 7, 8, 9, 10, 11 ],
    [ 3, 4, 5, 6, 1, 2, 11, 12, 7, 8, 9, 10 ],
    [ 4, 5, 6, 1, 2, 3, 10, 11, 12, 7, 8, 9 ],
    [ 5, 6, 1, 2, 3, 4, 9, 10, 11, 12, 7, 8 ],
    [ 6, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 7 ],
    [ 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6 ],
    [ 8, 9, 10, 11, 12, 7, 6, 1, 2, 3, 4, 5 ],
    [ 9, 10, 11, 12, 7, 8, 5, 6, 1, 2, 3, 4 ],
    [ 10, 11, 12, 7, 8, 9, 4, 5, 6, 1, 2, 3 ],
    [ 11, 12, 7, 8, 9, 10, 3, 4, 5, 6, 1, 2 ],
    [ 12, 7, 8, 9, 10, 11, 2, 3, 4, 5, 6, 1 ]
]

Run in calculator (opens in a new tab)

Example: Random Elements of a Wreath Product (ex-6247bb)

Run in calculator (opens in a new tab)

We illustrate the use of the function Random using the wreath product of the symmetric group of degree \(4\) and the cyclic group of order \(6\).

> G := WreathProduct( Sym(4), CyclicGroup(GrpPerm, 6));
> G;
Permutation group G acting on a set of cardinality 24
    (1, 5, 9, 13, 17, 21)(2, 6, 10, 14, 18, 22) (3, 7, 11, 15, 19, 23)
        (4, 8, 12, 16, 20, 24)
    (1, 2, 3, 4)
    (1, 2)
> Order(G);
1146617856
> Random(G);
(1, 17, 12, 4, 18, 10, 3, 20, 9, 2, 19, 11)(5, 22, 13, 6, 21, 15)
    (7, 24, 16)(8, 23, 14)

We display the cycle structures of 10 random elements of \(G\).

> R := [ CycleStructure(Random(G)) : i in [1..10] ];
> R;
[
    [ <6, 1>, <3, 6> ],
    [ <9, 1>, <6, 2>, <3, 1> ],
    [ <9, 2>, <3, 2> ],
    [ <12, 1>, <9, 1>, <3, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <12, 1>, <6, 2> ],
    [ <6, 3>, <2, 3> ],
    [ <6, 1>, <4, 3>, <2, 3> ],
    [ <6, 3>, <3, 2> ]
]

Run in calculator (opens in a new tab)

Permutations#

Coercion#

Arithmetic with Permutations#

Properties of Permutations#

Predicates for Permutations#

Set Operations#

Permutations

Coercion

Arithmetic with Permutations

Properties of Permutations

Predicates for Permutations

Set Operations