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)), 0 <= i <= n, 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 intersect 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) (q^n - 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).
Controlling selection of a Base
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.
GoodBasePoints(G: parameters) : GrpMat -> []
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 [V_1, ..., V_m] for a generating set for G. The default action is then to return [V_1.1, ..., V_m.1, V_1.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 [V_1.1, ..., V_1.(( dim) V_1), V_2.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 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 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 general procedure for constructing a base and strong generating set for the matrix group G. This version uses the default algorithm choices.
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 sufficient 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. 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 and, in the case of a matrix group, on its degree of transitivity. This parameter 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 BSGS for G.
Random: BoolElt Default: true
Construct a BSGS for G using the Todd-Coxeter Schreier algorithm. If the parameter Random is defined true, the random Schreier algorithm is first applied to create a probable BSGS.
Given a matrix group G for which a probable BSGS is stored, verify the correctness of the BSGS. If it is not complete, proceed to complete it. The Todd-Coxeter Schreier method is used.
Random: BoolElt Default: true
Max: RngIntElt Default: 100
Run: RngIntElt Default: 20
Construct a presentation for the matrix group G on a set of strong generators and return the presentation in the form of a finitely presented group F that is isomorphic to G. In Magma, the Todd-Coxeter Schreier algorithm is used to construct the presentation. If strong generators are not already known for G, they will be constructed. If strong generators have to be constructed, the parameter Random with its associated parameters Max and Run may be used to apply the Random Schreier algorithm to construct a probable BSGS before commencing the construction of the presentation. In the case in which strong generators are already known for G, the presentation will be on these strong generators. The group homomorphism f: F -> G, defining G as a matrix representation of F, is also returned.
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.
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.
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 Omega. 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 G.
A set of strong generators for the matrix group G. If they are not currently available, they will be computed.[Next] [Prev] [Right] [Left] [Up] [Index] [Root]