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.*

8more comments