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$
  • $\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$ – Hagen von Eitzen Feb 3 at 13:40
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$
  • $\begingroup$ I am sorry for the late comment... But what do you mean by $AA$ please? $\endgroup$ – Hilder Vitor Lima Pereira Feb 3 at 11:28
  • $\begingroup$ @HilderVitorLimaPereira, $AA = \{ab| a, b \in A\}$. $\endgroup$ – Yanior Weg Feb 3 at 13:30

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.