### 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 A^{T}A. 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 |

Editors | Manuel Bronstein |

Publisher | Association for Computing Machinery |

Pages | 117-126 |

Number of pages | 10 |

ISBN (Electronic) | 0897916042 |

DOIs | |

State | Published - Aug 1 1993 |

Externally published | Yes |

Event | 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 - Kiev, Ukraine Duration: Jul 6 1993 → Jul 8 1993 |

### Publication series

Name | Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC |
---|

### Other

Other | 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 |
---|---|

Country | Ukraine |

City | Kiev |

Period | 7/6/93 → 7/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

*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