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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – David E Speyer
    Commented 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
    Commented May 11, 2015 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .