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?

  • 1
    $\begingroup$ Did you consider a cycle of length $d$ and a transposition? $\endgroup$ – Andreas Thom Feb 2 '17 at 10:42
  • $\begingroup$ I didn't. In dimension three this requires two steps to generate a five-dimensional algebra, but I don't have much intuition for how quickly it would generate in higher dimensions. In general this would seem to generate the $((d-1)^2+1)$-dimensional algebra of matrices with all row and column sums equal. $\endgroup$ – Ian Morris Feb 2 '17 at 11:05

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.)


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.


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.