## DIMACS TR: 95-33

## Algorithms for Polycyclic-by-finite Matrix Groups: Preliminary Report

### Author: Gretchen Ostheimer

**
ABSTRACT
**

Let R be the ring of integers or a number field. We present several
algorithms for working with polycyclic-by-finite subgroups of GL(n,R).
Let G be a subgroup of GL(n,R) given by a finite generating set of
matrices. We describe an algorithm for deciding whether or not G is
polycyclic-by-finite. For polycyclic-by-finite G, we describe an
algorithm for deciding whether or not a given matrix is an element of
G. We also describe an algorithm for deciding whether or not G is
solvable-by-finite, providing an alternative to the algorithm proposed
by Beals ([Be1]) for this problem.
Baumslag, Cannonito, Robinson and Segal prove that the problem of
determining whether or not a finitely generated subgroup of GL(n,Z) is
polycyclic-by-finite is decidable and that the problem of testing
membership in a polycyclic-by-finite subgroup of GL(n,Z) is also
decidable ([BCRS]). In this report we extend these results by
describing algorithms which appear to be suitable for computer
implementation. Experimentation is needed to determine the range of
input for which they are practical.

Our method is to first reduce each problem to the corresponding
problem for triangularizable matrix groups. The reduction is an easy
consequence of the result of Dixon ([Di1]) that subgroups of the
p-congruence subgroup of GL(n,Z_p) are connected in the Zariski
topology, where Z_p is the ring of p-adic integers for a prime p.

We then prove a structure theorem for triangularizable matrix groups
that allows us to decide whether or not a matrix group is
triangularizable and to reduce the problem of testing membership in a
polycyclic, triangularizable matrix group to the corresponding
problems for finitely generated abelian matrix groups and for finitely
generated unitriangular matrix groups. In the case of an abelian
matrix group we can find a presentation for the group, and our
membership test can be made constructive. For these results we rely
heavily on the work of Ge ([Ge]) concerning algorithms for
multiplicative subgroups of a number field. We also rely on an
algorithm of Beals ([Be2]) to decide whether or not a triangularizable
matrix group is polycyclic.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-33.ps.gz

DIMACS Home Page