Expressing a element of a Matrix subgroup in terms of subgroup generators

Question

I'm no (computational) algebraist, and my searches have been pretty unyielding (probably due to the vast amounts written on the key words), but perhaps someone may know if this is possible, and if so, lead me to some solution.

Consider the subgroup $S$ of $GL(n,\mathbb{Z})$ which is generated by elements $s_1,...,s_k$. If $x\in S$, then $x$ has a representation as a word in the form $x=\Pi_{i}s_i$. Is it possible to find such a representation?

If this is possible, and computable, is there any efficient software out there? My current problem is a 10x10 matrix and I'm trying to fit this in to a subgroup generated by 9 10x10 matrices.

Answer 1

If you know in advance that $x$ can be expressed as a word in $s_1,\ldots,s_k$, then clearly it is possible to find such a word: just try all words until you find one that works!

But the generalized word problem is known to be unsolvable for finitely generated subgroups of ${\rm GL}(n,\mathbb{Z})$ for $n \ge 4$. This means that, there is no algorithm to decide whether an arbitrary element $x \in {\rm GL}(n,\mathbb{Z})$ can be written as a word over $s_1,\ldots,s_k$. To find references for that result, it is probably easiest just to do a search for "generalized word problem GL(n,Z)". There are good survey papers by C.F. Miller on decision problems in group theory.

So there cannot be an efficient algorithm to solve your problem that is guaranteed to work on all inputs, because if there were then we could use it to solve the generalized word problem: just run it for the prescribed time, and if it fails to solve the problem, then that must be because $x$ is not in the subgroup. Of course, for specific problems, then there might happen to be a special purpose method that works in that case.