# Minimal set of $n\times n$ matrices whose products generate all $n\times n$ matrices with a single $1$

Let $$n \in \mathbb{N}^*$$ be the dimension of the matrices.

Let $$M_{i,j}$$ be the $$n\times n$$ matrix with $$1$$ at position $$(i,j)$$ and 0 elsewhere.

Let $$S_n$$ be the set containing all the $$n^2$$ matrices $$M_{1,1}$$, ..., $$M_{n, n}$$.

For instance, $$S_2$$ is

$$\left\{ \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\right\}.$$

I am interested in the smallest number of matrices that I need to take such that I can generate all the others by multiplying them.

For example, If I take

$$A_1 := \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A_2 := \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A_3 := \begin{pmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A_4 := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}.$$

Then, I have

$$A_1 \cdot A_3 := \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A_3 \cdot A_1 := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A_3 \cdot A_2 := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$$

$$A_4 \cdot A_1 := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}, A_4 \cdot A_2 := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}.$$

Therefore, all the elements of $$S_3$$ are of the form $$A_k$$ or $$A_k \cdot A_p$$.

But maybe if I take matrices that are not in $$S_3$$ to be those $$A_k$$'s, I can use less matrices to generate $$S_3$$.

So, the question is

Given $$n$$, what is the minimal number of matrices $$A_1, ..., A_m$$ such that $$M_{i, j} \in S_n \Rightarrow (\exists k : M_{i,j} = A_k) \text{ or } (\exists k, p : M_{i,j} = A_k\cdot A_p)?$$

Partial result:

I already know that I can take $$2n - 2$$ matrices to generate $$S_n$$. Specifically, I can take $$M_{1, j}$$ for $$2\le j \le n$$ and $$M_{i, 1}$$ for $$2\le i \le n$$ as I did in the example above for $$S_3$$. But, again, maybe I need less matrices. In particular, if I use generators that are not elements of $$S_n$$ themselves, does it improve something?

• Remark: If you allowed arbitrarily many factors, two matrices suffice. If you allow up to three factors, approximately $3\sqrt n$ matrices suffice. – Hagen von Eitzen Feb 3 at 13:40

You have already constructed an example of such set of $$2n-1$$ elements. Let's prove now that they cannot be smaller.
Suppose $$A \subset S_n$$. Let's construct an oriented graph $$\Gamma_n(A)$$ with $$n$$ vertices with an edge going from the $$i$$-th vertex to the $$j$$-th one iff $$M_{ij} \in A$$. Then it is not hard to see, that $$S_n \subset AA$$ iff $$\Gamma_n(A)$$ is strongly $$2$$-connected. Now suppose $$d_i(v)$$ is in-degree of $$v$$ and $$d_o(v)$$ is out-degree of $$v$$. Then if $$\Gamma(V, E)$$ has $$\sum_{v \in V} d_i(v)d_o(v)$$ edges. Thus if $$\Gamma$$ is strongly $$2$$ connected we have $$(|E| - |V| + 1)^2 + |V| - 1 \geq \sum_{v \in V} d_i(v)d_o(v) \geq |V|^2$$. And from that it follows, that $$|E| \geq 2|V|-1$$. Thus, as there are exactly $$|A|$$ edges in $$\Gamma_n(A)$$ we can conclude, that $$|A| \geq 2n-1$$.
• I am sorry for the late comment... But what do you mean by $AA$ please? – Hilder Vitor Lima Pereira Feb 3 at 11:28
• @HilderVitorLimaPereira, $AA = \{ab| a, b \in A\}$. – Yanior Weg Feb 3 at 13:30