在numpy中查找矩阵的线性相关列

Question

问题：我有一个 MxN 的矩阵，其中 M 大于等于 N。我想找出这个矩阵中线性相关的列向量组。

我希望能在 numpy 中找到一个快速简单的方法来实现这个。

>>> a = np.random.randn(7, 6)
>>> a[:, 3] = 2*a[:, 0]-a[:, 4]
>>> a[:, 5] = 3*a[:, 1]

我在寻找一个叫做 get_column_groups 的函数，它会返回

>>> get_column_groups(a)
array([0, 1, 2, 0, 0, 1])

如果这个函数还能返回每个组的秩，那就更好了，比如：

>>> groups, group_ranks = get_column_groups(a)
>>> groups    
array([0, 1, 2, 0, 0, 1])
>>> group_ranks
[2, 1, 1]

Answer 1

根据我对这个问题的理解，计算矩阵的Spark是你所请求的内容中的一个子问题，因此在大多数情况下，这个问题是NP完全的。

可能有一些算法能比简单地组合评估列（最多到rank(a)的大小）做得更好，但这可以作为一个起点。