math - 查找所有线性相关的向量子集

Question

我有这种形式的向量

(1 1 1 0 1 0)
(0 0 1 0 0 0)
(1 0 0 0 0 0) 
(0 0 0 1 0 0) 
(1 1 0 0 1 0) 
(0 0 1 1 0 0) 
(1 0 1 1 0 0) 

我需要找到 Z2 上的所有线性相关子集。

例如 1,2,5 和 3,6,7。

Answer 1

好的，我的 5 美分蛮力 IINM 正在迭代向量集的所有子集。所以，相反，你从底部开始，每个向量的单例集显然是线性独立的。

在下一步中，对于每个单例集合，您通过尝试添加集合中的每个剩余向量来创建一个列表，并查看这些对中的哪些是独立的，记下您已经测试过的那些对，以防止重复的努力。

在第 3 步中，对于每个独立的对，您将尝试将剩余的每个向量相加以形成三元组，测试新向量的独立性，并标记您已经测试过的三元组。

这应该比蛮力节省很多，最坏的情况是一组所有独立的向量。