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
    Jun 22, 2021 at 2:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.