QR decomposition for rank-deficient matrix

Question

Say $A = Q\begin{bmatrix} R\\ 0\\ \end{bmatrix}$ where $A$ is $m \times n, m>n$ and $\operatorname{rank}(A) = k, k<n$ and $Q$ is $m \times m$ and $R$ is $n \times n$. Can we say $\operatorname{span} \lbrace a_1,\ldots,a_k \rbrace = \operatorname{span} \lbrace q_1,\ldots, q_k \rbrace$ where $a_j$ and $q_j$ are the $j$th columns of $A$ and $Q$ respectively?

Answer 1

I came across your question while trying to answer my own question of how one extends QR decompositions to rank deficient matrices. I spent a little while looking at how QR decomposition is arrived at in the case of rank deficient matrices and it seems to me like it can be naturally extended. Having looked at that, I think I can answer your question.

I think the answer is no to what you explicitly asked. This follows simply by supposing A is such that the first k columns are not linearly independent (I assume your question was for any general rank deficient A?). By definition for Q to be orthogonal span{$q_1, \ldots , q_k$} must be equivalent to $\mathbb{R}^k$, however by assumption of {$a_i$}, $i=1, \ldots k$ not being linearly independent, they cannot span something equivalent to $\mathbb{R}^k$

However, if you assumed A was ordered such that the first columns are the linearly independent columns than I believe the answer to your question would be yes.

Answer 2

Yes. If we take a QR factorization with pivoting, the diagonal elements of R are in decreasing order. That allows us to look at the diagonal elements to figure out when to cut things off. There's probably a better way to do this with a rank revealing QR, but the following will work in a pinch. Here's some MATLAB/Octave code that demonstrates it:

% Finds a QR factorization of a rank deficient matrix
function [Q R p] = qrrd(A,tol)
    % Find the QR factorization with pivoting
    [Q R p] = qr(A,0);

    % Since the diagonal of Q has elements decreasing in magnitude, find the
    % first element that's near zero
    rrank = find(abs(diag(R))<tol);
    rrank = rrank(1)-1;

    % If we have zero rank, throw an error
    if rrank==0
        error('Attempted to take a QR factorization of a rank-0 matrix')
    end

    % Reduce the size of Q and R accordingly
    Q = Q(:,1:rrank);
    R = R(1:rrank,:);
end

Then, we can test this with

% Create a tall and skinny, rank deficient matrix
m = 10;
n = 5;
r = 3;
A = randn(m,r)*randn(r,n);

% Find the rank deficient QR factorization with pivoting
[Q R p] = qrrd(A,1e-12);

% Find the residual
fprintf('(tall) || A(:,p) - QR ||: %e\n',norm(A(:,p)-Q*R,'fro'));

% Make A short and fat by taking the transpose
A = A';

% Repeat the exercise
[Q R p] = qrrd(A,1e-12);
fprintf('(short) || A(:,p) - QR ||: %e\n',norm(A(:,p)-Q*R,'fro'));

I haven't really checked the code all that closely, so use at your own risk. Since StackExchange has a new funny policy with code, consider it public domain.