python - Scipy - 找到矩阵列空间的基础

Question

我正在尝试编写一个简单的 Simplex 算法，第一步是找到一个基本可行的解决方案:

1. 选择 A 的线性独立列的集合 B
2. 将与不在 B 中的列对应的 x 的所有分量设置为零。
3. 求解 m 个方程式以确定 x 的分量。这些是基本变量。

我知道解决方案将涉及使用 scipy.linalg.svd(或 scipy.linalg.lu)和一些 numpy.argwhere/numpy.where 魔法，但我不确定具体如何。

有没有人有纯 Numpy/Scipy 实现来寻找基础(第 1 步)，或者更好的是，以上所有的实现？

例子:

>>> A
array([[1, 1, 1, 1, 0, 0, 0],
       [1, 0, 0, 0, 1, 0, 0],
       [0, 0, 1, 0, 0, 1, 0],
       [0, 3, 1, 0, 0, 0, 1]])

>>> u, s, v = scipy.linalg.svd(A)
>>> non_zero, = numpy.where(s > 1e-7)
>>> rank = len(non_zero)
>>> rank
4
>>> for basis in some_unknown_function(A):
...     print(basis)
{3, 4, 5, 6}
{1, 4, 5, 6}

等等。

Answer 1

A QR decomposition为 A 的列空间提供正交基:

q,r = np.linalg.qr(A)

如果 A 的秩为 n，则 q 的前 n 列构成A 的列空间。