algorithm - 通过删除行和列使奇异矩阵成为非奇异矩阵

Question

我有一个大的稀疏方阵 n × n，它的秩略低于 n，假设为 m。我想通过按一定规则删除行和列来使其非奇异。规则是，如果删除第 i 行，则必须也删除第 i 列，以便矩阵始终是方阵。这有效地删除了邻接图中的节点。

我的第一个问题是:是否总是存在这样的 n-m 行和列的组合，我可以删除这样的组合，使得剩余的 m × m 子矩阵在结构上是非奇异的。

我的第二个问题是:是否有一种有效的算法可以在不删除过多行和列的情况下获得 p by p 非奇异子矩阵

为了提供更多背景信息，我正在处理的矩阵约为 1000 x 1000，稀疏度接近 0.05

Answer 1

1 不正确。这是一个例子。

[1 0 0 0;
 0 1 0 0;
 0 0 0 1;
 0 0 0 0]

排名显然是 3，恰好是非零行/列的数量)。您无法删除第 1,2,3 行或第 1,2,4 列。所以涵盖了 1 到 4。