# Global Properties Unless otherwise noted, the functions in this section assume that a BSGS-representation for the group can be constructed. ## Group Order Unless the order is already known, each of the functions in this family will create a base and strong generating set for the group if one does not already exist. ### `IsFinite(G): GrpMat -> Bool, RngIntElt` Given a matrix group $G$, return whether $G$ is finite together with the order of $G$ if $G$ is finite. The function rigorously proves its result (i.e., the result is not probable). Let $R$ be the ring over which $G$ is defined, and let the degree of $G$ be $n$. If $R$ is finite, then the first return value is trivially `true`. If $R$ is the integer ring or rational field, then the function works as follows. The function successively generates random elements of $G$ and tests whether each element has infinite order via the function [`HasFiniteOrder`](operation-element.md#function-hasfiniteorder); if so, then the non-finiteness of $G$ is proven. Otherwise, at regular intervals, the function attempts to construct a positive definite form fixed by $G$ (see the function [`PositiveDefiniteForm`](../MatrixGroupsOverQAndZ/forms.md#function-grpmatqz-positivedefiniteform) in the chapter on matrix groups over ${\mathbb{Q}}$ and ${\mathbb{Z}}$), using a finite number of steps; if one is successively constructed, then the finiteness of $G$ is proven. The number of steps attempted for the positive definite form constructed is increased as the algorithm progresses; if $G$ is finite, such a form must exist and will be found when enough steps are tried, while if $G$ is infinite, an element of infinite order is found very quickly in practice. If $R$ is an algebraic number field of degree $d$ over ${\mathbb{Q}}$ (including cyclotomic and quadratic fields), then the standard companion matrix blowup is applied to the generators of $G$ to obtain an isomorphic matrix group of $(nd)$ over ${\mathbb{Q}}$, and the above algorithm is then applied to this matrix group. ### `Order(G): GrpMat -> RngIntElt` ### `# G: GrpMat -> RngIntElt` The order of the group $G$ as an integer. If the order is not currently known, a base and strong generating set will be constructed for $G$. If $G$ has infinite order, an error ensues. ### `FactoredOrder(G): GrpMat -> [ ]` The order of the group $G$ returned as a factored integer. The format is the same as for `FactoredIndex`. If the order of $G$ is not known, it will be computed. If $G$ has infinite order, an error ensues. ### `Exponent(G): GrpMat -> RngIntElt` The exponent of the group $G$. ### `Example: Order (ex-731a24)` ```magma > G := MatrixGroup<2,Integers()|[1,1,0,1],[0,1,-1,0]>; > IsFinite(G); false > G24, e := ChangeRing(G, Integers(24)); > Order(G24); 9216 > G.-1*G.2; [ 1 1] [-1 0] > (G.-1*G.2) @ e; [ 1 1] [23 0] > (G24.2^2) @@ e; [23 0] [ 0 23] ``` ## Membership and Equality ### `g in G: GrpMatElt, GrpMat -> BoolElt` Given a matrix $g$ and a matrix group $G$, return `true` if $g$ is an element of $G$, `false` otherwise. ### `g notin G: GrpMatElt, GrpMat -> BoolElt` Given a matrix $g$ and a matrix group $G$, return `true` if $g$ is not an element of $G$, `false` otherwise. ### `S subset G: { GrpMatElt }, GrpMat -> BoolElt` Given a matrix group $G$ and a set $S$ of matrices belonging to a group $H$, where $G$ and $H$ belong to the same generic group, return `true` if $S$ is a subset of $G$, `false` otherwise. ### `H subset G: GrpMat, GrpMat -> BoolElt` ### `IsSubgroup(H, G): GrpMat, GrpMat -> BoolElt` Given matrix groups $G$ and $H$ belonging to the same generic group, return `true` if $H$ is a subgroup of $G$, `false` otherwise. ### `S notsubset G: { GrpMatElt }, GrpMat -> BoolElt` Given a matrix group $G$ and a set $S$ of matrices belonging to a group $H$, where $G$ and $H$ belong to the same generic group, return `true` if $S$ is not a subset of $G$, `false` otherwise. ### `H notsubset G: GrpMat, GrpMat -> BoolElt` Given matrix groups $G$ and $H$ belonging to the same generic group, return `true` if $H$ is not a subgroup of $G$, `false` otherwise. ### `H eq G: GrpMat, GrpMat -> BoolElt` Given matrix groups $G$ and $H$ belonging to the same generic group, return `true` if $G$ and $H$ are the same group, `false` otherwise. ### `H ne G: GrpMat, GrpMat -> BoolElt` Given matrix groups $G$ and $H$ belonging to the same generic group, return `true` if $G$ and $H$ are distinct groups, `false` otherwise. ## Set Operations The creation of a base and strong generating set for a matrix 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. ### `NumberingMap(G): GrpMat -> 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): GrpMat -> Process` ```magma 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 [[Celler *et al.*, 1995](../../references.md#cite-randomelements)], 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): GrpMat -> GrpMatElt` ```magma Short: BoolElt Default: false ``` A randomly chosen element for the group $G$. If a BSGS is known for $G$, then the element chosen will be genuinely random. If no BSGS is known, then the *random* element is chosen by multiplying out a *random* word in the generators. Since it is not usually 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 -> GrpMatElt` 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)`. ### `Example: Random (ex-b51498)` We use the random function to sample the orders of elements in the group ${\operatorname{GL}}(20, 16)$. ```magma > G := GeneralLinearGroup(20, GF(16)); > RP := RandomProcess(G); > [ FactoredOrder(Random(RP)) : i in [1..20] ]; [ [ <3, 1>, <5, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61681, 1> ], [ <3, 1>, <5, 1>, <17, 1>, <23, 1>, <89, 1>, <257, 1>, <397, 1>, <683, 1>, <2113, 1> ], [ <3, 1>, <5, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61681, 1> ], [ <3, 1>, <31, 1>, <8191, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61681, 1> ], [ <3, 3>, <5, 1>, <7, 1>, <13, 1>, <17, 1>, <19, 1>, <29, 1>, <37, 1>, <43, 1>, <73, 1>, <109, 1>, <113, 1>, <127, 1>, <257, 1> ], [ <5, 1> ], [ <3, 1>, <5, 1> ], [ <3, 1>, <5, 2>, <11, 1>, <17, 1>, <31, 1>, <41, 1>, <53, 1>, <157, 1>, <1613, 1>, <2731, 1>, <8191, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <13, 1>, <17, 1>, <97, 1>, <241, 1>, <257, 1>, <673, 1> ], [ <3, 1>, <5, 1>, <17, 1>, <29, 1>, <43, 1>, <113, 1>, <127, 1>, <257, 1>, <65537, 1> ], [ <3, 1>, <5, 2>, <11, 1>, <29, 1>, <31, 1>, <41, 1>, <43, 1>, <113, 1>, <127, 1> ], [ <3, 1>, <5, 2>, <11, 1>, <17, 1>, <31, 1>, <41, 1>, <53, 1>, <157, 1>, <1613, 1>, <2731, 1>, <8191, 1> ], [ <3, 2>, <5, 2>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61, 1>, <151, 1>, <257, 1>, <331, 1>, <1321, 1> ], [ <3, 1>, <5, 1>, <11, 1>, <31, 1>, <41, 1>, <257, 1>, <61681, 1>, <4278255361, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61681, 1> ], [ <3, 1>, <5, 1>, <17, 1>, <23, 1>, <89, 1>, <257, 1>, <397, 1>, <683, 1>, <2113, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <23, 1>, <31, 1>, <41, 1>, <89, 1>, <397, 1>, <683, 1>, <2113, 1> ] ] ```