How many multiplications are needed to generate a matrix algebra?

Question

This is similar to an earlier question but I hope that it will be seen as being sufficiently distinct to merit separate consideration.

Let $M_d(\mathbb{C})$ denote the set of all $d \times d$ complex matrices and let $X \subset M_d(\mathbb{C})$ be nonempty. Then the set $$\mathcal{A}(X):=\mathrm{span}\bigcup_{n=1}^\infty \{A_1\cdots A_n \colon A_j \in X\}$$ is a subalgebra of $M_d(\mathbb{C})$, usually called the algebra generated by $X$. My question is:

What is the smallest number $N(d)$ such that
$$\mathcal{A}(X)=\mathrm{span}\bigcup_{n=1}^{N(d)} \{A_1\cdots A_n \colon A_j \in X\}$$ for every nonempty set $X\subseteq M_d(\mathbb{C})$?

Let me remark that $N(d)=d^2$ is such a number, although I do not know if it is the smallest such number. To see this let us define $$\mathcal{A}_N(X):=\mathrm{span}\bigcup_{n=1}^{N} \{A_1\cdots A_n \colon A_j \in X\}$$ for each $N \geq 1$. We note that if $\mathcal{A}_N(X)=\mathcal{A}_{N+1}(X)$ for some integer $N$ then clearly $\mathcal{A}_N(X)=\mathcal{A}_{N+m}(X)$ for all $m \geq 1$ and therefore $\mathcal{A}(X)=\mathcal{A}_N(X)$. Since $$\mathcal{A}_1(X) \subseteq \mathcal{A}_2(X) \subseteq \cdots \subseteq \mathcal{A}_{d^2}(X) \subseteq \mathcal{A}_{d^2+1}(X)$$ and all of these sets are nonzero vector subspaces of the $d^2$-dimensional space $M_d(\mathbb{C})$, by the pigeonhole principle there is $N \leq d^2$ such that $\dim \mathcal{A}_N(X)=\dim \mathcal{A}_{N+1}(X)$ and therefore $\mathcal{A}_N(X)=\mathcal{A}_{N+1}(X)=\mathcal{A}(X)$. In particular we may take $N(d)= d^2$.

If we take $X$ to be a singleton set containing a permutation matrix of order $d$ then it is clear that $\mathcal{A}_N(X)=\mathcal{A}(X)$ for $N=d$ but not for any smaller $N$, so we cannot in general take $N(d)<d$ for nonempty $X\subseteq M_d(\mathbb{C})$. However I cannot think of any examples which require products of length greater than $d$ in order to generate the algebra. I therefore ask:

Can we take $N(d)=d$ in the previous question?

Answer 1

My original answer missed the word "span" everywhere, sorry!

The answer to your second question is no. Take $$A=\begin{pmatrix}0 & 0 & 0\\ 1& 0 & 1\\ 0& 0 & 0\end{pmatrix}, B=\begin{pmatrix}0 & 0 & 1\\ 1 & 0 & 1\\ 1 & 1& 1\end{pmatrix}.$$

If I computed things correctly, the dimensions of the spans go $2,5,8,9$. Thus $N(3)\geq 4$. (This example was found by taking random $0,1$ matrices, and calculating dimensions, until an example was found.)

Answer 2

One can receive some lower bounds on $N(d)$ from the theory of groups of central type. Let then $G$ be a finite group of order $d^2$. Assume that there exists a non-degenerate two cocycle $[\alpha]\in H^2(G,\mathbb{C}^{\times})$. This means that the twisted group algebra $\mathbb{C}^{\alpha}G$ is isomorphic with $M_d(\mathbb{C})$. This also means that $M_d(\mathbb{C})$ will have a basis $\{U_g\}_{g\in G}$ such that $U_gU_h=\alpha(g,h)U_{gh}$. Take now $X$ to be $\{U_{g_1},\ldots U_{g_r}\}$ where $\{g_1,\ldots ,g_r\}$ is a generating set for $G$. Then $\mathcal{A}_n(X)=M_d(\mathbb{C})$, and $N(d)$ will be the maximal length of a geodesic in the (oriented) Cayley graph of $G$ with respect to this generating set (where we have an oriented edge from $g$ to $gs$, for $s$ in the generating set).

From this point on we do not really to take $\alpha$ into account, we just need to know that it exists. The group $\mathbb{Z}/d\times\mathbb{Z}/d$ is a group of central type. With respect to the standard basis $\{(0,1),(1,0)\}$ we have a Cayley graph with maximal length of geodesic $2d-2$. That shows already that $N(d)$ is at least $2d-2$.

I do not know if the question about the length of geodesics in Cayley graphs of finite groups of central type was studied. I believe, however, that you can get better lower bounds for $N(d)$ from this.