7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Remark: If you allowed arbitrarily many factors, two matrices suffice. If you allow up to three factors, approximately $3\sqrt n$ matrices suffice. $\endgroup$ Feb 3, 2020 at 13:40

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I am sorry for the late comment... But what do you mean by $AA$ please? $\endgroup$ Feb 3, 2020 at 11:28
  • $\begingroup$ @HilderVitorLimaPereira, $AA = \{ab| a, b \in A\}$. $\endgroup$ Feb 3, 2020 at 13:30

You must log in to answer this question.

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