5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Boaz Tsaban Apr 4 '14 at 10:11
  • $\begingroup$ It would still be useful to have, if possible, a method working in the general case. $\endgroup$ – Boaz Tsaban Apr 28 '14 at 11:53
2
$\begingroup$

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.

In the case of non absolutely irreducible representations, it is not difficult to rewrite the representation over the larger field, which would make it possible to write down a basis of the space spanned by the original matrices.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.