Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 6 down vote accepted

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!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.