|
[Next][Prev] [Right] [____] [Up] [Index] [Root]
In this chapter we provide algorithms for computing with a group
G given by a finite set S = { g1, ..., gr } of
invertible n x n matrices over an infinite field K. The
algorithms are based on special techniques developed for computing
in this class of groups ([DF08], [DF09], [DFO], [DEF09]),
which rely on properties of finitely generated
linear groups.
The group G is defined over the subring R of K generated by
the entries of the matrices gi, (gi) - 1 , 1 ≤i ≤r.
If ρis an ideal of R, then it induces a congruence
homomorphism from GL(n, R) onto GL(n, R/ρ), which replaces
every entry of an element in S by its image in R/ρ. Our
techniques depend on the construction of a congruence homomorphism
with the property that all torsion elements of its kernel
Gρ (called a congruence subgroup) are unipotent. The
existence of a normal subgroup of finite index in G with such a
property was proved by Selberg. One advantage of the congruence
homomorphism techniques is that they replace the ground domain by
a domain that is more convenient for computing. In particular, if
the ideal ρis maximal, then we get a reduction to a finite
field R/ρ. For more details on the method see [DF08, Section
3].
In this chapter we provide two sets of functions based on the
above techniques.
(a) Functions which test finiteness of matrix groups over a wide
range of infinite domains. These functions are an implementation
of algorithms developed in [DF09], [DFO]. Together with
other currently available algorithms for deciding finiteness, they
enable testing finiteness of a finitely generated linear group
over an arbitrary field (subject to special representation of
input data). Additionally, if a group is found to be finite, then
we can construct an isomorphic copy over a finite field, and use
that for further investigation of the group; in particular, to
compute its order.
(b) Functions for testing nilpotency and computing with nilpotent
matrix groups. These functions are an implementation of algorithms
developed in [DF08], which in turn are based on an
implementation of algorithms in [DF06] for computing with
nilpotent matrix groups over finite fields. As well as testing
nilpotency, the functions may be used for investigating the
structure of nilpotent matrix groups. In particular, special
algorithms have been developed for deciding finiteness, computing
orders of finite nilpotent matrix groups, and testing complete
reducibility of nilpotent matrix groups. The first implementation
of these functions, over a smaller range of domains, was carried
out by Bettina Eick.
Since G is finitely generated, it is defined over a finitely
generated subfield of K. Hence, the main fields to be considered
are F(x1, ..., xm), where the x1, ..., xm are
algebraically independent indeterminates, m ≥0, and the
coefficient field F is an algebraic number field or a finite
field. Notice that a finitely generated field is a finite degree
extension of some F(x1, ..., xm), so that a reduction to
the case of F(x1, ..., xm) can be obtained, for example, by
'blowing up' the size of matrix entries.
For a recent survey of work in the area of computing with matrix
groups over infinite fields, we refer to [DEF09].
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|
