找到一個可逆子矩陣

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行。

行 - 減少轉置並選擇轉置的樞軸行。它們對應於一個有效的列選擇。