5
$\begingroup$

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?

  • 0
    @Phira: Well, *I* did not determine it; I dragged it out of long-term memory. :-) Googling around a bit, I found [this](http://www.ams.org/journals/proc/1997-125-12/S0002-9939-97-04283-4/S0002-9939-97-04283-4.pdf) paper by Friedland attributing the result to Feit, which may be where I read about it. [This](http://www-math.mit.edu/~poonen/papers/conjdim.pdf) paper has a table with the exceptions.2012-05-28

1 Answers 1

4

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.

  • 0
    Thank you. I managed to get a copy of the paper, which looks to be very nice from a first read-through.2012-06-01