What is the most efficient way to factor a matrix into a given set of generators? I am studying finite index subgroups of certain finitely presented groups. The particular conditions on my groups make this problem easier than I phrase it here, but I am curious about a more general answer. After the main question I will indicate a simplified case for which there is probably a simplified answer.
Suppose you have a group of matrices $G\subset\mathrm{GL}_n(R)$
over a ring $R$,
and suppose it is finitely generated so that
$G=\langle g_1,\dots,g_n\rangle$.
Next suppose you are given a matrix $m\in G$
and you want to know how to write it as a word in the generators,
as short as possible.
What is an efficient way of computing this?
An inefficient solution that will give you a word
(not necessarily the shortest)
is to systematically go through all possible words and check by multiplying them together until $m$
is a result,
which is possible since the set of words on $n$ letters is countable.
Perhaps a smarter approach is to compute the Jordan canonical form of $m$ and of each of the $g_i$, then find a basis for $G$
in which you can write each of the $g_i$
as well as $m$,
upon which the solution can be found just be piecing words together
rather than having to multiply matrices each time.
I'm uncertain if this would lead one to discover the shortest word.
Even if it did, perhaps there is a more efficient process.
The easier sub-case:
Suppose $G\subset\mathrm{PSL}_2(\mathbb{C})$
is discrete and arithmetic, i.e. is Kleinian and has a representation into $\mathrm{GL}_n(\mathbb{Q})$ for some $n$.
Moreover, suppose $m=\overline{g}^{\top}g$ (it is Hermitian)
for some $g\in G$.
Is there an especially nice choice of generators for $\mathrm{PSL}_2(\mathbb{C})$
into which $m$
and the $g_i$
can be factored?
Or, perhaps a better approach than that?
I'm feeling like the eigendecomposition could be useful,
perhaps by using $m$'s pair of orthogonal eigenvectors
and the limited ways of splitting their eigenvalues (which are real)
over the coefficient ring.
 A: For the general case (i.e. no restrictions on the set $\{ g_1,\ldots,g_n \}$), one cannot get a computable upper bound on the runtime of any algorithm for the dimension $m\geq 4$. 
It follows from the undecidability of the membership problem in $SL_4(\mathbb{Z})$ due to Mikhailova. If one had an algorithm with a computable upper bound for the running time, then we could run it on any matrix $g\in SL_m(\mathbb{Z})$ and stop if it takes longer than our bound. After that we could check if the output indeed gives a word such that $g=g_{i_1}g_{i_2}\ldots g_{i_s}$ and hence we would solve the membership problem.
A: As to your general question, there is a method which is better
than the inefficient solution you give. -- Namely, compute spheres of radii
$r = 1, 2, \dots$ with respect to the word metric about the identity and
about the element $m$ to be factored, until these spheres intersect 
nontrivially. This way you always get the shortest possible word as desired, 
and depending on the structure of your group, you save a significant amount 
of runtime and memory.
Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ 
about each of $1$ and $m$ at a time, which further reduces memory
requirements -- how much, depends again on the structure of your qroup.
That said, in general the runtime- and memory requirements of this method
are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you
can do much better in general, as the problem of finding a word of minimal 
length is already hard for finite permutation groups (popular example:
solving the Rubik's Cube with the smallest possible number of moves).
