MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Sounds like a mix of recognizing nilpotence and solving a Rubik's cube quickly. – The Masked Avenger Aug 2 '13 at 0:45
Cross-posted on MSE. – 1015 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. – Mark Sapir Aug 2 '13 at 3:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.