# How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.

Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$ that one needs to take such that, with high probability, the algebra generated by $a_1,\dots,a_k$ is $A$? What if $A$ is generated by a group of matrices?

I am interested in a bound that applies to all such $A$.

Taking $k=O(n^2)$ will provide a set that spans $A$ as a vector space. Would less than that suffice?

Comment: This is related to this question.

• Sorry, misread your question; please ignore my previous comment [now deleted] – Yemon Choi May 11 '15 at 19:26
• Presumably, for a simple algebra, the answer is $O(1),$ whereas for a direct sum of $M_2$s you need at least $O(n)$ (probably $O(n \log n).$ – Igor Rivin May 11 '15 at 19:48
• The initial question dealt with arbitrary subalgebras $A$ of $\mbox{Mat}_n(\mathbb{F})$, and was answered below by Will Sawin. – Boaz Tsaban May 11 '15 at 21:02
• Why not post a new, refined question, rather than making a substantial change to the question that invalidates the answers? – user13113 May 12 '15 at 0:19
• @Hurkyl: I agree. Thus, I edited the question accordingly. Notice that the refined version is also solved below, so no problem this time. – Boaz Tsaban May 12 '15 at 1:34

At least $n^2/4$. Divide $n \times n$ matrices into four $n/2 \times n/2$ blocks, and consider the subalgebra of matrices that are zero outside the upper right block. Then because the product of any two elements is zero, your elements generate as an algebra if and only if they generate as a vector space. So you need at least $n^2/4$.
On the other hand, clearly $n^2+ c$ elements suffice for any algebra for a small constant $c$.
Your use of big $O$ notation suggests that the constant doesn't matter. If it does, then I'd guess $n^2/4$ is optimal, as this algebra is a worst-case algebra in many respects - e.g. it is the abelian subalgebra of the largest dimension.