Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.