在numpy或matlab中由满秩非方矩阵求可逆方阵

Question

假设您有一个NxM矩阵A，其中M>N。如果我们用C_i（维数为Nx1）来表示列，那么我们可以将矩阵写成

A = [C_1, C_2, ..., C_M]

如何获得原始矩阵A的第一个线性独立列，从而构造一个新的NxN矩阵B，它是一个非零行列式的可逆矩阵。在

^{pr2}$

如何在matlab或pythonnumpy中找到索引{i1, i2, ..., iN}？这可以用奇异值分解来实现吗？代码片段将非常受欢迎。在

编辑： 为了使其更加具体，考虑下面的python代码

from numpy import *
from numpy.linalg.linalg import det

M = [[3, 0, 0, 0, 0],
     [0, 0, 1, 0, 0],
     [0, 0, 0, 0, 1], 
     [0, 2, 0, 0, 0]]
M = array(M)

I = [0,1,2,4]
assert(abs(det(M[:,I])) > 1e-8)

因此，给定一个矩阵M，我们需要找到一组N线性无关列向量的指数。在

Answer 1

简单，用MATLAB编程。使用QR，特别是旋转QR。在

M = [3 0 0 0 0;
     0 0 1 0 0;
     0 0 0 0 1; 
     0 2 0 0 0]

[Q,R,E] = qr(M)
Q =
     1     0     0     0
     0     0     1     0
     0     0     0     1
     0     1     0     0

R =
     3     0     0     0     0
     0     2     0     0     0
     0     0     1     0     0
     0     0     0     1     0

E =
     1     0     0     0     0
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     0     1
     0     0     0     1     0

E的前4列表示要使用的M列，即[1,2,3,5]列。如果你想要M的列，只需形成乘积M*E

^{pr2}$

顺便说一句，用det来判断矩阵是否是奇异的，绝对是最糟糕的方法。在

改用rank。在

从本质上讲，除非你理解为什么det是一件坏事，而且你选择使用它，尽管事实如此，否则你实际上永远不应该在MATLAB中使用det。在

Answer 2

我的第一个想法是尝试M列中N列的每个可能的组合。可以这样做（在Python中）：

import itertools
import numpy.linalg

# 'singular' returns whether a matrix is singular.
# You could use something more efficient than the determinant
# (I'm not sure what options there are in NumPy)
singular = lambda m: numpy.linalg.det(m) == 0

def independent_square(A):
    N,M = A.shape
    for colset in itertools.combinations(xrange(M), N):
        B = A[:,colset]
        if not singular(B):
            return B

如果需要列索引而不是结果的平方矩阵，只需将return B替换为return colset。或者你可以用return colset,B同时得到这两个。在

我不知道SVD能帮上什么忙。事实上，我想不出任何纯粹的数学运算可以把A转换成B（甚至任何可以计算出MxN列选择矩阵Q，从而B=A.Q）的运算，除了尝试和错误。但是如果你想知道是否有人存在，math.stackexchange.com网站是个好地方问问。在

如果您只需要一种计算方法，那么上面的代码就足够了。在