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?
Is there an algorithm to determine whether rational matrices generate a finite group?
5
$\begingroup$
group-theory
reference-request
finite-groups
-
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
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.
-
0Thank you. I managed to get a copy of the paper, which looks to be very nice from a first read-through. – 2012-06-01