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.

  • $\begingroup$ Sorry, misread your question; please ignore my previous comment [now deleted] $\endgroup$ – Yemon Choi May 11 '15 at 19:26
  • $\begingroup$ 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).$ $\endgroup$ – Igor Rivin May 11 '15 at 19:48
  • $\begingroup$ The initial question dealt with arbitrary subalgebras $A$ of $\mbox{Mat}_n(\mathbb{F})$, and was answered below by Will Sawin. $\endgroup$ – Boaz Tsaban May 11 '15 at 21:02
  • $\begingroup$ Why not post a new, refined question, rather than making a substantial change to the question that invalidates the answers? $\endgroup$ – user13113 May 12 '15 at 0:19
  • $\begingroup$ @Hurkyl: I agree. Thus, I edited the question accordingly. Notice that the refined version is also solved below, so no problem this time. $\endgroup$ – 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.

  • 1
    $\begingroup$ And, if "algebra" means "containing the identity" for the OP, then just take the span of Will's example together with the identity matrix. $\endgroup$ – David E Speyer May 11 '15 at 20:20
  • 1
    $\begingroup$ @BoazTsaban My algebra, with David Speyer's modification, is spanned by a group. Indeed the set of matrices that are equal to the identity plus one of the elements of my original algebra are a group. $\endgroup$ – Will Sawin May 11 '15 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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