找到一个可逆子矩阵

Question

给出一个m乘n满秩矩阵，n> m，从m矩阵中选择m行形成一个可逆（满秩）m的有效算法是什么？

Answer 1

试试这个：

让M是矩阵，M(j)的j列处和M(i,j)在i行和列j的条目。

为j从1到m：

1. 选择已在j列中的非零项M(i,j)的第一行。该行被命名为i。

2. 使用M(i,j)通过计算

   M(k) = M(k) - M(i,k)/M(i,j) * M(j) for 1 <= k <= n and k != j 
   

3. 更新与所述列中的矩阵在步骤2

计算由于矩阵是秩m的该行的所有其他条目设置为零，你会发现有m行有一个非零的条目。
该算法运行于O(n*m^2)。

Answer 2

你想选择m列，而不是m行。

行 - 减少转置并选择转置的枢轴行。它们对应于一个有效的列选择。