Scipy - 寻找矩阵列空间的基

Question

我正在尝试编写一个简单的单纯形算法，第一步是找到一个基本可行解：

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}

等等。

- MikeRand

---

对于“以上所有”，请在足够新的SciPy中尝试使用scipy.optimize.linprog - 它实际上实现了单纯形算法。 - Fred Foo

Answer 1

一个QR分解为A的列空间提供了一个正交基:

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

如果 A 的秩为 n，那么 q 的前 n 列形成 A 的列空间的一组基础。

- jme

---

但是我认为A列的基础将是A列的子集，这些子集将是线性独立的。上面的“q”似乎是其他东西。 - MikeRand

q是一组正交向量，它们跨越了矩阵A的列空间。列空间可能有无限多个基，q是其中一个特别好的基。但是如果您需要基由A的列组成，则可以计算QR分解并丢弃线性相关的列。例如，请参见此处。 - jme

我刚刚进行了测试，并发现目前使用 np.linalg.qr(A) 寻找 A 的列空间的基是不正确的。这是因为我们可能需要通过 q 提供的所有正交向量来生成 A ——即使对于奇异矩阵也是如此。相反，我们应该使用 scipy.linalg.qr(A, pivoting=True)，这样 q 的前n列将为我们提供一个基础。scipy.linalg.qr - Shahrokh Bah

Answer 2

尝试使用这个

scipy.linalg.orth(A)

这将为矩阵A产生规范正交基。

- Jayanth Kumar