Computing structural information for a matrix group G requires, in most cases, a representation of the set of elements of G. Magma represents this set by means of a base and strong generating set, or BSGS for G. Suppose the group G has the natural module M. A base B for G is a sequence of distinct elements and submodules of M with the property that the identity is the only element of G that fixes B pointwise. A base B of length n determines a sequence of subgroups G(i), 1 ≤i ≤n + 1, where G(i) is the stabilizer of the first i - 1 points of B. Given a base B for G, a subset S of G is said to be a strong generating set for G if G(i) = < S ∩G(i) >, for i = 1, ..., n.
Unlike permutation groups, however, the orbits of the i-th base point under the stabilizer G(i) are not bounded by the degree, but rather, by (where the base point is a 1-dimensional subspace) (qn - 1)/(q - 1) where q is the cardinality of the coefficient field and n is the degree of G. Clearly, it is essential to find small orbits if one is to compute with matrix groups in this manner. Unfortunately, there are no methods which are guaranteed to find short orbits. There are, however, some heuristics developed by Scott Murray and Eamonn O'Brien which often find good base points. These heuristics are used in Magma if the most likely standard base point would generate an orbit longer than 10000 (this bound may be changed).
Note also, that for matrix groups over a finite field, there is an alternative function LMGBase described in Section Finding a Base that starts by computing a composition tree (Section Composition Trees for Matrix Groups) for G.
Given the difficulties in automatically finding a good base for a matrix group, it is possible to apply the Murray-O'Brien base point selection procedure and preset a suitable base manually.
Apply the Murray--O'Brien base point selection procedure and return a sequence of vectors or subspaces according to the parameters. The procedure computes and sorts a collection of eigenspaces [V1, ..., Vm] for a generating set for the matrix group G. The default action is then to return [V1.1, ..., Vm.1, V1.2, ... ] where each new vector is only added if it is not in the span of the preceding vectors.Slots: RngIntElt Default: 10Expand the number of generators to work with to Slots matrices by adding random words in the generators of G.NoCycle: RngIntElt Default: falseIf NoCycle := true, instead of cycling through the eigenspaces, return the sequence [V1.1, ..., V1.((dim) V1), V2.1, ... ], with the addition of each vector subject to the same condition above.Eigenspaces: RngIntElt Default: falseIf Eigenspaces := true, then return the subsequence of the eigenspaces where all the eigenspaces have dimension d leq10. If there are no such eigenspaces, all the eigenspaces are returned.
Set the base of the matrix group G to be [B[1], ..., B[n]] where the tuple B has n components. An error will be reported if the matrix group G already has a base set.
Return whether the matrix group G has a base set, and if so, the base.
Set the limit for the size of the first basic orbit to be n. If n is non-zero and the orbit of the first base point (a 1-dimensional subspace generated by a standard basis vector) has length exceeding n, then the Murray-O'Brien base point selection procedure is used to find a point more likely to have a short orbit. This assertion will affect all matrix groups. If n = 1 then use of the Murray-O'Brien procedure is guaranteed.
Get the limit for the size of the first basic orbit. This will always return true and the limit.
The functions described below give user control of the construction of a base and strong generating set (BSGS) of a finite matrix group.
Many functions described in this chapter require a group to have a BSGS. In case the given group does not have a BSGS, then one will be constructed using the default algorithm, which is equivalent to using the BSGS procedure described below.
It should be noted that if the user constructs a BSGS for a group G using the RandomSchreier procedure, then other functions that require a BSGS will assume that the random BSGS is a complete BSGS. If this is not the case then results will be unpredictable.
The general procedure for constructing a base and strong generating set for the matrix group G. This version uses the default algorithm choices. Currently this is as follows: if the order of the group is known to the program then a BSGS is constructed using the random Schreier algorithm, if not then the Sims-Todd-Coxeter-Schreier procedure is used. If str is the name of a sporadic group, we assume that G is a representation for this group and choose base points specific to this group. This should ensure better performance. Information on the progress of these algorithms may be obtained by setting the verbose flags RandomSchreier and STCS true.
Run: RngIntElt Default: 40
Construct a probable base and strong generating set for the group G. The strong generators are constructed from a set of randomly chosen elements of G. The expectation is that if sufficiently many random elements are taken then, upon termination, the algorithm will have produced a BSGS for G. If the attribute Order is defined for G, the random Schreier will continue until a BSGS defining a group of the indicated order is obtained (except when the Run parameter is set - see below). In such circumstances this method is the fastest method of constructing a base and strong generating set for G. This is particularly so for groups of large degree. If nothing is known about G, the random Schreier algorithm provides a cheap way of obtaining lower bounds on the group's order. This procedure has one associated parameter Run, which takes a positive integer value. If the value of Run is n, then the algorithm terminates after n consecutive random elements are found to lie in the set defined by the current BSGS (default 40). This will happen even if the Order attribute is defined for G. It should be emphasized that unpredictable results may arise if the user uses the base and strong generators produced by this algorithm, when, in fact, it does not constitute a complete BSGS for G. The Verify procedure, described below, may be used to check the completeness of the BSGS constructed by this function.If str is the name of a sporadic group, we assume that G is a representation for this group and choose base points specific to this group. This should ensure better performance.
Information on the progress of this algorithm may be obtained by setting the verbose flag RandomSchreier to true.
Causes a RandomSchreier to be attempted on G, with basic orbit lengths limited to at most L. If this limit is exceeded (for any one orbit) then the attempt is abandoned and false is returned. If true is returned then the result is the same as RandomSchreier applied to G.
Construct a BSGS for the matrix group G using the Sims-Todd-Coxeter-Schreier algorithm. Information on the progress of this algorithm may be obtained by setting the verbose flag STCS to true.
Given a matrix group G for which a possible BSGS is stored, verify the correctness of the BSGS. If it is not complete, proceed to complete it. The Sims-Todd-Coxeter-Schreier method is used.If G has no BSGS stored, then use of Verify is equivalent to using the BSGS procedure described above.
Information on the progress of these algorithms may be obtained by setting the verbose flags RandomSchreier and STCS true.
Define the order of the matrix group G to be the integer n (factored integer Q).
If the boolean variable b is true, the existing pseudo strong generators for the matrix group G (possibly created by RandomSchreier) are to be taken as correct.
Returns true iff the order of the group G is known. In that case, the order is also returned as the second value of the function.
Returns true iff the matrix group G has a verified set of strong generators.
A base for the matrix group G. The base is returned as a sequence of points of Ω. If a base is not known, one will be constructed.
The i-th base point for the matrix group G. A base and strong generating set must be known for G.
The basic orbit at level i as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G.
The length of the basic orbit at level i as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G.
The lengths of the basic orbits as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G. The lengths are returned as a sequence of integers.
Given a matrix group G for which a base and strong generating set are known, and an integer i, where 1 ≤i ≤k with k the length of the base, return the subgroup of G which fixes the first i - 1 points of the base.
Given a matrix group G, return the stabilizer chain defined by the base as a sequence of subgroups of G. If a BSGS is not already known for G, it will be created.
The number of elements in the current strong generating set for the matrix group G.
A set of strong generators for the matrix group G. If they are not currently available, they will be computed.