# Finding a basis for the (linear combinations) span of a matrix group, efficiently?

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

• Update: It turns out that there is a simple way to do this, assuming that the field size is substantially larger than $n^2$ (and that the field characteristic does not divide the order of $G$). This is so because the double centralizer of the given group elements coincides with their span (this was pointed out to me by Rami Aizenbud). So, the algorithm is: Compute the centralizer in time $O(kn^{2\omega})$, pick few (two should suffice) random elements there, and compute their centralizer. I hope to add more details in the next version of the linked paper, that will be joint with Aizenbud. Apr 4, 2014 at 10:11
• It would still be useful to have, if possible, a method working in the general case. Apr 28, 2014 at 11:53

The MeatAxe algorithm (which is available in GAP and Magma) can be used to solve (1). It is very fast in practice and I think it computes a decompostion into irreducibles in time $O(n^4)$ in the coprime case.