How to generate algebraic span of a set of matrices (how many multiplications?)

Question

I've got a question about matrices and matrix algebras that offhand seems difficult, I'm wondering there is any sharp solution? Or perhaps it's known to not have any solution at all?

Suppose you have some set of n complex DxD matrices {M1,...,Mn}, and consider the algebra which they generate (under finite multiplications and additions with coefficients over the complex numbers), in particular, consider the case where that algebra is NOT the full matrix algebra M_D(C).

EDIT: First question, I suppose, is to ask, given the generators (and supposing that they're linearly independent), what's the best way to figure out the sub-algebra (or even just its dimension) of the full matrix algebra that you can generate?

Second, It seems clear that you should be able to generate any "basis" element (in the vector space sense, a matrix with a one in exactly one entry and zero everywhere else) which exists in your algebra after some finite number of multiplications. My question is, is there a good way to figure out exactly what the "maximum" number of multiplications you'd need to generate any of the basis elements is? Certainly it should be bounded, but has anyone figured out bounds on this, perhaps different bounds given different conditions on your set of generators?

If anyone recognizes this as something other people have thought about/figured out and could point me in the right direction I would be very grateful!

Answer 1

I believe that you could determine such a bound by repeated application of the Cayley-Hamilton Theorem. You might want to trace down some of the references given in the following paper,

Cohen, Ajeh M., Gábor Ivanyos, and David B. Wales. "Finding the radical of an algebra of linear transformations." Journal of Pure and Applied Algebra 117 (1997): 177-193.

Edit:

The specific quote I was thinking of comes from the following paper

Rónyai, Lajos. "Computing the structure of finite algebras." Journal of Symbolic Computation 9.3 (1990): 355-373.

Author states

We remark that algebras may be given as matrix algebras. In this case it suffices to specify a set of matrices which generates the algebra. Our results are applicable in this setting as well, since from this representation one can efficiently find a basis of the algebra and then the structure constants with respect to this basis. In the case of associative algebras the regular representation gives an efficient method to obtain a matrix representation from structure constants. We mention here that the methods do not seem to be directly applicable when the algebras are given by generators and relations.

The trick I think will just be to find some algorithmic statement.