DIMACS TR: 95-33

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

Author: Gretchen Ostheimer


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