特殊方阵线性组合构造目标矩阵：文献与算法问询

这是我3年前提出的问题，至今仍希望得到解答，特此重提。核心疑问有两点：

1. 该问题是否已在计算机科学文献中被讨论或记载？
2. 有没有能构造出更少输入矩阵的高效算法思路？

问题示例（n=2） #

当方阵维度n=2时，我使用3个输入矩阵：
输入矩阵

X1           X2           X3     
1 0    和    0 1    和    0 1
1 0          0 1         -1 0

通过线性组合X1 + X3和X2 - X3，可得到2个符合要求的输出矩阵：
输出矩阵

M1           M2
1 1    和    0 0
0 0          1 1

目标与规则 #

• 目标：用尽可能少的输入矩阵，通过线性组合生成n个输出矩阵。每个输出矩阵的特点是：某一行全为1，其余所有元素为0（第一个输出矩阵第一行全1，第二个输出矩阵第二行全1，依此类推）。
• 规则：每个输入矩阵的每一行最多只能包含一个非零元素。

现有尝试 #

我目前实现了一个递归算法，递推公式为T(n) = 3*T(n) + O(n)，所需输入矩阵数量低于O(n²)，但我希望能将复杂度优化到接近O(n log n)的水平。

n=3的示例（2024年8月17日补充） #

输入矩阵1
   1   0   0
   1   0   0
   1   0   0

输入矩阵2
   0   1   0
   0   1   0
   0   1   0

输入矩阵3
   0   0   1
   0   0   1
   0   0   1

输入矩阵4
   0  -1   0
   0   0   1
   0   0   0

输入矩阵5
  -1   0   0
   0   0   0
   0   0   1

输入矩阵6
   0   0   0
  -1   0   0
   0   1   0

线性组合方式：
输出矩阵1 = 0*输入矩阵1 + 0*输入矩阵2 + 1*输入矩阵3 + (-1)*输入矩阵4 + (-1)*输入矩阵5 + 0*输入矩阵6
输出矩阵2 = 0*输入矩阵1 + 1*输入矩阵2 + 0*输入矩阵3 + 1*输入矩阵4 + 0*输入矩阵5 + (-1)*输入矩阵6
输出矩阵3 = 1*输入矩阵1 + 0*输入矩阵2 + 0*输入矩阵3 + 0*输入矩阵4 + 1*输入矩阵5 + 1*输入矩阵6

内容的提问来源于stack exchange，提问作者BenBar