5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Sorry, misread your question; please ignore my previous comment [now deleted] $\endgroup$
    – Yemon Choi
    May 11, 2015 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, 2015 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$ May 11, 2015 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, 2015 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$ May 12, 2015 at 1:34

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • 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$ May 11, 2015 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, 2015 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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