QR decomposition for rank-deficient matrix 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?

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.
