This is a question about a search problem associated with user6976's question. Suppose we are given a finite set of elements $S \subset \mathrm{GL}_n(\mathbb{Q})$ containing inverses of all its elements, and an integer $L$, and are asked to find a list of primitive non-redundant relationships of the form $a_1 a_2 \cdots a_{L'} = 1$ with $L' \leq L$. Here $a_1 a_2 \cdots a_{L'} = 1$ is primitive if no subproduct $a_l a_{l+1} \cdots a_{l'}$ of the l.h.s. evaluates to identity, and redundant if a cyclic permutation of it or its inverse is already in the list.
Of course, to fully specify the problem we must agree on how many such relationships should be in the list. We might ask for all of them (let say there are $m_L$ such relationships) or for a positive fraction of them: $\left\lfloor \rho m_L \right\rfloor$ relationships for some fixed $\rho \in (0, 1)$.
What is known about the complexity of this problem? In particular, can it be solved in the time polynomial in $L$, the size of the input, and $m_L$? Or, at least, (for a fixed $S$ and $\rho$) is there an upper bound better than $o\!\left(Lm_{L} + \left(\left|S\right|-1\right)^{L/2}\right)$? Are there any practical algorithms for solving it (better than brute-force)?
Note: similarly to user6976's question, $\mathbb{Q}$ can be replaced with any field of characteristic 0 by, possibly, moving to larger matrix sizes: e.g. $\sqrt{q}$ can be represented as $\left(\begin{smallmatrix}0&1\\q&0\end{smallmatrix}\right)$ by doubling the matrix size; see also (Lipton, Zalcstein) for the proof of logspace complexity of the original word problem.
Note 2: By brute force, in this context, I mean an algorithm going the breadth-first-search on products of length up to $L/2$, discarding all non-primitive products and writing the rest into a hash table, with complexity scaling with $L$ roughly as $\left(\left|S\right|-1\right)^{L/2}$ (but could be slightly better if a lot of products are discarded as non-primitive).
