5
$\begingroup$

Suppose that $A_{1},\ldots, A_{k}$ are rational $n\times n$ matrices that generate a finite group. It is a well-known fact that there is a matrix $T$ such that $T^{-1}A_{1}T,\ldots, T^{-1}A_{k}T$ are integer matrices (and so generate an isomorphic subgroup of $\operatorname{GL}_{n}(\mathbb{Z})$. Is there an algorithm which takes the given matrices $A_{i}$ and outputs a suitable matrix $T$?

1 Answers 1

6

Yes, I have programmed such an algorithm myself in a computer algebra system, and it generally works well!

Let $b_1,b_2,\ldots,b_n$ be the natural basis of the space of row vectors on which the group $G$ acts by multiplication on the right. (Of course you can do it by multiplication on the left by column vectors if you prefer!) Then the additive abelian group $M$ spanned by $\{b_ig : g \in G \}$ is invariant under $G$.

So we just have to find a free basis of $M$ as a free abelian group, or equivalently as a free ${\mathbb Z}$-module of rank $n$, make that basis into the rows of a matrix $T$, and then $TgT^{-1}$ will be have entries in ${\mathbb Z}$ for all $g \in G$.

To find a basis of $M$, it is probably easiest if you first multiply the generating vectors $b_ig$ by the least common denominator $d$ of their entries, to bring them into ${\mathbb Z}^n$ (so you will actually be finding a free basis of $dM$, but that's OK). Then make all of these vectors into the rows of a matrix, and put it into Hermite Normal Form. (There are good implementations of HNF around.) The remaining nonzero rows give you your matrix $T$.

In practice, you want to use this method on very large groups, so you do not really want to calculate $b_ig$ for all $g \in G$. It generally works well if you just do this for $g$ in a small subset of $G$. In my implementations I first try it with $g$ ranging over all words of length at most two in the generators $A_i$. You can tell whether it has worked by just checking whether all of the matrices $TA_iT^{-1}$ have integer entries. This usually works, but if not you can go up to words of length 3, or try a random sample of 20 words or something like that!