通过添加标准基础上的向量来构建满秩矩阵 [英] Construct a full rank matrix by adding vectors from the standard basis

问题描述

我有一个nxn的奇异矩阵.我想向此矩阵添加k行(必须来自标准基础e1，e2，...，en)，以使新的(n + k)xn矩阵具有完整的列级.添加的行数k必须最小，并且只要k最小即可以任意顺序添加它们(不仅是e1，e2，...，也可以是e4，e10，e1，...).

有人知道这样做的简单方法吗?感谢您的帮助.

解决方案

您可以通过执行使用列旋转进行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

其中Q是正交矩阵(如果A是实数)或an矩阵(如果A是实数)复杂的; R是上三角矩阵，而E是 netlib QR因式分解页面上找到更详细的描述.

由于Q和E都是正交(或unit)矩阵，所以R的秩与A的秩相同.要调高A的秩，我们只需要找到增加R的秩的方法即可；并且由于R的枢转结果以及R的上三角关系，这更加直接了.

现在，对旋转过程有要求，如果R的任何对角元素为0，则整行必须为0.如果R导致无效，则底部的n-rank(A)行为0s.如果我们将右下角替换为一个单位矩阵，则该新矩阵将是完整等级.好吧，我们不能真正进行替换，但是我们可以将行矩阵附加到R的底部，并形成一个具有相同等级的新矩阵:

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

此处I的维数是A的无效性，R的无效性. 很容易看到rank(newR)=n.然后，我们还可以通过简单地扩展其维度来定义新的unit 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)列中的第一个，因此是一组基于标准的行，这正是您想要的！

I have a nxn singular matrix. I want to add k rows (which must be from the standard basis e1, e2, ..., en) to this matrix such that the new (n+k)xn matrix is full column rank. The number of added rows k must be minimum and they can be added in any order (not just e1, e2 ,..., it can be e4, e10, e1, ...) as long as k is minimum.

Does anybody know a simple way to do this? Any help is appreciated.

解决方案

You can achieve this by doing a QR decomposition with column pivoting, then taking the transpose of the last n-rank(A) columns of the permutation matrix. In matlab, this is achieved by the qr function(See the matlab documentation here):

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

Each row of transpose(E(:,end-r+1:end)) will be a member of standard basis, rank of newA will be n, and this is also the minimal number of standard basis you will need to do so.

Here is how this works:

QR decomposition with column pivoting is a standard procedure to decompose a matrix A into products:

A*E==Q*R

where Q is an orthogonal matrix if A is real, or an unitary matrix if A is complex; R is upper triangular matrix, and E is a permutation matrix.

In short, the permutations are chosen so that the diagonal elements are larger than the off-diagonals in the same row, and that size of the diagonal elements are non-increasing. More detailed description can be found on the netlib QR factorization page.

Since Q and E are both orthogonal (or unitary) matrices, the rank of R is the same as the rank of A. To bring up the rank of A, we just need to find ways to increase the rank of R; and this is much more straight forward thanks to the structure of R as the result of pivoting and the fact that it is upper-triangular.

Now, with the requirement placed on pivoting procedure, if any diagonal element of R is 0, the entire row has to be 0. The n-rank(A) rows of 0s in the bottom if R is responsible for the nullity. If we replace the lower right corner with an identity matrix, the that new matrix would be full rank. Well, we cannot really do the replacement, but we can append the rows matrix to the bottom of R and form a new matrix that has the same rank:

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

Here the dimensionality of I is the nullity of A and that of R. It is readily seen that rank(newR)=n. Then we can also define a new unitary Q matrix by expanding its dimensionality in a trivial manner:

newQ=[Q 0 ; 0 I]

With that, our new rank n matrix can be obtained as

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

Note that B is [0 I] and E is a permutation matrix, so B*transpose(E) is simply the transpose of the last n-rank(A) columns of E, and thus a set of rows made of standard basis, and that's just what you wanted!

这篇关于通过添加标准基础上的向量来构建满秩矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！