# Is there an algorithm to determine whether rational matrices generate a finite group?

This is inspired by this question. Given finitely many invertible rational $n\times n$ matrices $A_{1},\ldots, A_{k}\in\operatorname{GL}(n,\mathbb{Q})$, is there an algorithm (a practical one) to determine whether the group $\langle A_{1},\ldots, A_{k}\rangle$ that they generate is finite? One could, I suppose, use something like Dimino's algorithm to calculate the closure and stop when the size exceeds the maximum order possible (which is the order $2^{n}n!$ of the group of signed permutation matrices, except for some small exceptions, if I recall correctly) but that seems impractical. Is there something better?

-
How did you determine your maximal order? –  Phira May 28 '12 at 8:10
@Phira: Well, I did not determine it; I dragged it out of long-term memory. :-) Googling around a bit, I found this paper by Friedland attributing the result to Feit, which may be where I read about it. This paper has a table with the exceptions. –  James May 28 '12 at 14:45

## 1 Answer

There is such an algorithm, and it has allegedly been implemented in GAP and Magma. The only reference I have found is:

László Babai, Robert Beals, and Daniel Rockmore. Deciding finiteness of matrix groups in deterministic polynomial time. In Proc. ISSAC'93 (Internat. Symp. on Symbolic and Algebraic Computation), Kiev 1993, pages 117-126. ACM Press, 1993.

Unfortunately I could not find any open access version of this paper, and I have not seen it myself yet.

-
Thank you. I managed to get a copy of the paper, which looks to be very nice from a first read-through. –  James Jun 1 '12 at 10:54