MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

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.

share|cite|improve this question

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.

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.