Deciding finiteness of matrix groups in deterministic polynomial time

László Babai, Robert Beals, Daniel Rockmore

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

Let G be a group of matrices with entries over an algebraic number field F (given symbolically). The group G is given by a list of generators. In this paper we give several algorithms, both deterministic and randomized, which can decide in polynomial time whether or not G is finite. It is easy to reduce the problem to the case F = Q. As a next step, we present a polynomial time algorithm which transforms G into a group of integral matrices whenever possible. Having done so, the main results of the paper are several polynomial time algorithms to handle the case of integral matrices. We give both randomized and deterministic algorithms to decide finiteness for finitely generated integral matrix groups. Although we are able to prove much better upper bounds for the complexity of the deterministic algorithms, in practice, the randomized algorithms support a much more efficient implementation. Thus, both kinds of algorithms are presented here but only the implementation of the randomized algorithm is explored. All algorithms in some way depend on a characterization (effectively due to Burnside) of finite integral matrix groups as those subgroups G ≤ GL(n,Z) which preserve some positive definite quadratic form. The randomized (Monte Carlo) algorithms use recent random walk techniques to obtain nearly uniformly distributed random elements in G (in a precise sense, whether G is finite or not). The subsequent analysis rests on a new estimate of the norm of the matrices in finite groups of integral matrices in terms of the norms of the generators. If G is infinite, one of our Monte Carlo algorithms is likely to produce an element with larger norm, thus certifying infiniteness. If G is finite, our other Monte Carlo algorithm is likely to produce a positive definite G-invariant quadratic form, thus certifying finiteness. Consequently, the combination of these two give an efficient and very simple Las Vegas algorithm (randomized algorithm that never errs) which we have successfully implemented. The deterministic algorithms are of two kinds. One algorithm uses some basic facts from the representation theory of finite groups to construct a G-invariant quadratic form (if it exists), by efficiently averaging the matrices ATA. The other deterministic algorithm uses the ellipsoid method to search for a positive definite quadratic form in a linear space U of quadratic forms. The new estimate on the norm of elements of G is used to ensure that if G is finite, then U contains a sizable ball of positive definite forms, as required for the ellipsoid method to be applicable.

Original languageEnglish (US)
Title of host publicationProceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993
EditorsManuel Bronstein
PublisherAssociation for Computing Machinery
Pages117-126
Number of pages10
ISBN (Electronic)0897916042
DOIs
StatePublished - Aug 1 1993
Externally publishedYes
Event1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 - Kiev, Ukraine
Duration: Jul 6 1993Jul 8 1993

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993
CountryUkraine
CityKiev
Period7/6/937/8/93

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Deciding finiteness of matrix groups in deterministic polynomial time'. Together they form a unique fingerprint.

  • Cite this

    Babai, L., Beals, R., & Rockmore, D. (1993). Deciding finiteness of matrix groups in deterministic polynomial time. In M. Bronstein (Ed.), Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 (pp. 117-126). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/164081.164104