I have an algorithm whose bottleneck is the following task:
Let $\mathbb{F}$ be a finite field. Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let $G=\langle g_1,\dots,g_k \rangle\le GL_n(\mathbb{F})$ be the group they generate, and assume that the characteristic of $\mathbb{F}$ does not divide $|G|$. Let $\operatorname{span}G\subseteq M_n(\mathbb{F})$ be the vector space spanned by linear combinations of the elements of $G$, or equivalently, the matrix algebra genrated by $g_1,\dots,g_k$.
Problem: Find, efficiently, a basis for the vector space $\operatorname{span}G$.
The naive algorithm has running time $O(kn^6)$. I am looking for something that is at most $O(kn^{2\omega})$, with $\omega$ being the linear algebra constant ($\omega\approx\log_27\approx 2.81$).
One possible direction may be as follows:
(1) Find a basis (i.e., a conjugating matrix) such that the group decomposes into a direct sum of irreducible representations (irreps).
(2) If the irreps are absolutely irreducible, we can take the standard basis for each, and we are done.
Can (1) be achieved in time $O(kn^{2\omega})$ (or faster)?
Is (2) correct in general? That is, in the above setting, must irreps be absolutely irreducible? And if not, is there anything more efficient than $O(kn^6)$ for irreps?
(This question is related to this and that questions.)
(Note: The probability that random $n^2$ elements of $G$ span may be negligible in general. Perhaps $O(n^2\log n)$ would do but I do not know that, either.)
