## DIMACS TR: 97-44

## Practical Algorithms for Polycyclic Matrix Groups

### Author: Gretchen Ostheimer

**
ABSTRACT
**

Many fundamental problems are undecidable for infinite matrix groups.
Polycyclic matrix groups represent a large class of groups for which these
same problems are known to be decidable. In this paper we describe a
suite of new algorithms for studying polycyclic matrix groups ---
algorithms for testing membership and for uncovering the polycyclic
structure of the group. We also describe an algorithm for deciding
whether or not a group is solvable, which, in the important context of
subgroups of GL(n,Z), is equivalent to deciding whether or not a group is
polycyclic. In contrast to previous algorithms, the algorithms in this
paper are practical: experiments show that they are efficient enough to
be useful in studying some reasonably complex examples using current
technology.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-44.ps.gz

DIMACS Home Page