# Bound on number of multiplications required to generate a matrix algebra from generators?

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 $D\times D$ matrices $\{M_1,...,M_n\}$, 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(\mathbb{C})$. I've seen solutions to the following problem in the case that the generators eventually generate the full algebra, but the techniques used to get the bounds operate under the important assumption that the full algebra is indeed generated.

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

• Sounds like a mix of recognizing nilpotence and solving a Rubik's cube quickly. Aug 2 '13 at 0:45
• Cross-posted on MSE. Aug 2 '13 at 1:56
• The speed of generating a subgroup of, say, symmetric group correlates with the expanding properties of the set of generators. There is a similar notion in the case of matrices and linear transformations, see Lubotzky, Alexander, Zelmanov, Efim Dimension expanders. J. Algebra 319 (2008), no. 2, 730–738. What you are looking for may be related.
– user6976
Aug 2 '13 at 3:39
• Certainly $D^2$ multiplications always suffice. Let $\mathcal{A}_N$ be the vector space spanned by all products of length up to $N$. If $\mathcal{A}_N=\mathcal{A}_{N+1}$ for some $N$ then it is not hard to see that $\mathcal{A}_N=\mathcal{A}_{N+m}$ for all $m \geq 1$ and therefore $\mathcal{A}_N$ is the whole algebra generated by the matrices. We have $\mathcal{A}_1\subseteq \mathcal{A}_2 \subseteq \cdots \mathcal{A}_{D^2+1}$ and these are all vector spaces with dimension at most $D^2$, so there exists $N\leq D^2$ such that $\dim \mathcal{A}_N=\dim \mathcal{A}_{N+1}$ and the result follows. Feb 2 '17 at 10:25