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

QR分解为A 的列空间提供正交基础:

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

如果等级A为n,则第一n列q形成列空间的基础A.

Answer 2

尝试使用这个

scipy.linalg.orth(A)

这产生矩阵 A 的正交基