Return to Question

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.

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.

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra generated by a subgroup of $\mbox{GL}_n(\mathbf{F})$.

Equivalently, let $G$ be a subgroup of $\mbox{GL}_n(\mathbf{F})$, and let $A:=\mbox{span}_\mathbb{F}(G)$, the span as a vector space over the field $\mathbb{F}$.

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$?

I am interested in a bound that applies to all such $A$. Replacing "high probability" by "probability bounded away from zero" would also be fine.

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.

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.

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra generated by a subgroup of $\mbox{GL}_n(\mathbf{F})$.

Equivalently, let $G$ be a subgroup of $\mbox{GL}_n(\mathbf{F})$, and let $A:=\mbox{span}_\mathbb{F}(G)$, the span as a vector space over the field $\mathbb{F}$.

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$?

I am interested in a bound that applies to all such $A$. Replacing "high probability" by "probability bounded away from zero" would also be fine.

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

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra generated by a subgroup of $\mbox{GL}_n(\mathbf{F})$.

Equivalently, let $G$ be a subgroup of $\mbox{GL}_n(\mathbf{F})$, and let $A:=\mbox{span}_\mathbb{F}(G)$, the span as a vector space over the field $\mathbb{F}$.

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$?

I am interested in a bound that applies to all such $A$. Replacing "high probability" by "probability bounded away from zero" would also be fine.

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.