通过添加来自标准基的向量构建一个满秩矩阵

Question

我有一个n×n的奇异矩阵。我希望添加k行（这些行必须来自标准基向量e1，e2，...，en），使得新的（n+k）×n矩阵是满列秩的。 添加的行数k必须最小化，并且它们可以以任何顺序添加（不仅限于e1，e2，...，可以是e4，e10，e1，...），只要k是最小的。

有人知道简单的方法吗？ 任何帮助都将不胜感激。

- Alexandru Popa

---

你正在使用什么方法来测试排名？ - Bitwise

在Matlab中，我检查rank(A)是否等于n，其中A是我的矩阵。 - Alexandru Popa

Answer 1

您可以通过进行 列主元QR分解，然后取置换矩阵的最后 n-rank(A) 列的转置来实现此操作。 在matlab中，这可以通过 qr 函数实现（请参见 matlab 文档 此处）：

r=rank(A);
[Q,R,E]=qr(A);
newA=[A;transpose(E(:,end-r+1:end))];

每行transpose(E(:,end-r+1:end))都将成为标准基的一个成员，newA的秩将为n，并且这也是您所需的最小标准基数。

以下是它的工作原理：

QR分解和列交换是一种常见的过程，可以将矩阵A分解为以下乘积：

A*E==Q*R

其中如果A是实数，则Q是正交矩阵，如果A是复数，则Q是酉矩阵；R是上三角矩阵，E是置换矩阵。

简而言之，置换是选择使对角线元素大于相同行中的非对角线元素，并且对角线元素的大小不断减小。更详细的描述可以在netlib QR factorization page找到。

由于Q和E都是正交（或幺模）矩阵，因此R的秩与A的秩相同。为了提高A的秩，我们只需要找到增加R秩的方法；而这要归功于R作为枢轴点结果的结构以及它是上三角形的事实，这更加直接。

现在，在枢轴过程中放置要求时，如果R的任何对角线元素为0，则整行必须为0。 R底部的n-rank（A）个0行负责零空间。如果我们用一个单位矩阵替换右下角，那么新矩阵将是满秩的。好吧，我们实际上不能进行替换，但是我们可以将行矩阵附加到R底部并形成具有相同秩的新矩阵：

B==[ 0 I ]     =>   newR=[ R ; B ]

这里，I的维数是A的零空间和R的维数。很容易看出rank(newR)=n。然后，我们也可以通过以一种琐碎的方式扩展其维数来定义一个新的酉Q矩阵：

newQ=[Q 0 ; 0 I]

有了这个，我们可以得到新的n阶矩阵

newA=newQ*newR.transpose(E)=[Q*R ; B ]*transpose(E) =[A ; B*transpose(E)]

请注意，B是[0 I]，E是一个置换矩阵，因此B*transpose(E)只是E的最后n-rank(A)列的转置，因此是由标准基向量组成的一组行，这正是您想要的！

- Xiaolei Zhu

Answer 2

这个问题和n是否很大有关。最简单的解决方法是不使用任何算法，尝试添加e_i并查看排名是否增加。如果排名增加了，则保留e_i并继续进行下一个操作，直到完成。

- Bitwise

---

谢谢。如果 e_i 和 e_j（i<j）都增加了排名，我们能确定两者都提供了获得相同最小 k 的可能性吗？难道在添加 e_i 后，我们需要再添加 4 行才能获得完整的排名，而在添加 e_j 后，我们只需要再添加 3 行就能获得完整的排名，这种情况不可能发生吗？ - Alexandru Popa

@user3071889说：“不可能。添加的向量要么是现有列向量的线性相关，要么不是。如果是线性相关的，它就不能添加任何东西；如果不是，它将增加矩阵的秩1。标准基向量彼此线性独立，使用它们中的任何一个来增加秩都没有关系。无论选择哪个向量，你始终需要额外添加n-rank A个向量，其中A是原始矩阵。” - A. Donda

Answer 3

我喜欢@Xiaolei Zhu的解决方案，因为它很优雅，但另一种更高效的方法是：

1. 确定矩阵A的任何行（索引为i）是否全部为零。如果是，则必须连接相应的e_i。
2. 在此过程之后，您可以简单地连接未在步骤1中添加的身份矩阵的n-rank(A)列的任何子集。

- Chris A.

---

非常感谢大家，这对我帮助很大。 - Alexandru Popa

Answer 4

单位矩阵的行/列可以以任意顺序相加。一般情况下，不需要按照通常的顺序如e1，e2，...来使矩阵满秩。

- zara

---

@m7913d 要使矩阵满秩，您可以按任意顺序添加 e1、e2 等，但新添加的矩阵的维数应为 n - rank。如果我错了，请告诉我。 - zara