3
$\begingroup$

I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.

Given an integer n, we want to combine some square input-matrices of size n in a way that is possible to construct n output matrices. The goal is to minimize the number of input-matrices. I think O(n*log(n)) ist possible. But I've only found algorithm of size O(n^k) with k approx. 1,5.

Output matrices

The i-th output-matrix have to be full of 1's in the i-th row, the other cells have to be zero.

Input matrices

The input-matrices may have at most one nonzero element (-1 or +1) per row.

Example for n = 2.

Inputs

X1           X2           X3     
1 0    and   0 1    and   0 1
1 0          0 1         -1 0

Outputs

M1           M2
1 1    and   0 0
0 0          1 1

The output-matrices can all be constructed with linear combinations of the X's:

M1 = 1*X1 + 1*X3
M2 = 1*X2 - 1*X3

This algorithm can be used recursively. So for n = 4 it is possible to construct all 4 outputs using 9 inputs.

I've done some simulations and I've discovered than n = 4 can also be constructed using 8 inputs.

Is this problem known?

Is there an efficient algorithm?

Thank you for you help!

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Just for the record, for $n=3$ one would need at least 6 matrices. One particular solution is $$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 1 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & -1 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0 & -1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}.$$ $\endgroup$
    – Max Alekseyev
    Commented Jun 22, 2021 at 2:45

0

Reset to default

You must log in to answer this question.