In $A = QR$ factorization do we need basis vectors from the left null space?

I am looking at the factorization $$A = QR$$ where $$A \in \mathbb{R^{m\times n}}$$ and $$Q$$ is orthogonal.

Background

The presentation of QR factorization that I've seen goes as follows. To construct $$Q$$, first find an orthonormal basis for the column space of $$A$$. These vectors $$\{q_1,...,q_r\}$$ will comprise the first $$r = \text{rank}(A)$$ columns of Q. We then complete the columns of $$Q$$ by taking orthonormal basis vectors from the left null space $$N(A^T)$$, and since $$C(A)^\perp = N(A^T)$$, we know the columns of Q will be orthonormal.

Question

My question is, how do I know that there will be enough basis vectors in $$N(A^T)$$ to complete the columns of $$Q$$? Also, is it necessary to take basis vectors from $$N(A^T)$$, or just convenient since they are guaranteed orthogonal?

• you need to explain the dimensions of $Q$. The standard case is $A$ is tall and skinny, e.g. for least squares. This lends itself to 2 equivalent QR factorizations -- one with $Q$ tall and skinny, R square, the other with $Q$ square, but R is not. I tend to use the former but I suspect you learned the latter – user8675309 Oct 29 '20 at 17:46
• @user8675309 Yes, I learned the case where Q is square (and hence orthogonal) – EssentialAnonymity Oct 29 '20 at 19:55

First, we are working in reals. Note that $$QR$$ factorization is unique when $$A$$ is invertible (with the convention/requirement that $$r_{i,i}\gt 0$$), and not unique otherwise. There are 2 basic approaches for QR factorization in your case. You've indicated that you want $$Q$$ to be square.

1.) Run Gram Schmidt on the columns of $$A$$. This does not naturally result in $$Q$$ being square though you can extend to a basis to get there.
2.) Reduce $$A$$ to (not necessarily square) upper triangular form by repeated application of $$Q^{(j)}...Q^{(2)}Q^{(1)}$$ where $$Q^{(k)}$$ is some particularly simple kind of orthogonal matrix -- typically Householder or perhaps Givens. This naturally results in a case where $$Q$$ is square.

It sounds like you are doing (1) though its worth your while to learn (2).

Focus on the case where $$A$$ is tall and skinny. Run Gram Schmidt on the columns of $$A$$ and if the result is non-zero for $$\mathbf a_k$$ then append on the right to the matrix $$Q$$ you are creating. (If the result is zero ignore it). Suppose $$\text{rank}\big(A\big) = r$$. After completing this you have

$$A=QR =\bigg[\begin{array}{c|c|c|c} \mathbf q_1 & \mathbf q_2 &\cdots & \mathbf q_{r}\end{array}\bigg]R$$

Note that this is 'thin' QR factorization, and $$Q^TQ = I_r$$ but $$Q$$ is not square.

Since you want $$Q$$ to be square, there is a second step. Append $$m-r$$ orthonormal columns to $$Q$$ to get
$$A=Q'R' =\bigg[\begin{array}{c|c|c|c|c|c} \mathbf q_1 & \mathbf q_2 &\cdots & \mathbf q_{r}&\mathbf q_{r+1}&\cdots&\mathbf q_m\end{array}\bigg]\begin{bmatrix} R \\\mathbf 0\end{bmatrix}$$

where $$Q'$$ is augmented to include those extra orthonormal columns and $$R'$$ is $$R$$ with rows of zeros appended so that the dimensions line up for matrix multiplication. If you write this out in terms of the 'outer product' form of matrix multiplication you can confirm these two different factorizations are both equal to $$A$$.

these boil down to, where does $$\bigg[\begin{array}{c|c|c|c}\mathbf q_{r+1}&\cdots&\mathbf q_m\end{array}\bigg]$$
(which has rank $$m-r$$) come from?

if you want to use the left nullspace of $$A$$, then applying rank nullity and equivalence of row and column rank

$$m =\text{rank}\Big(A^T\Big) + \dim\ker \Big(A^T\Big) = \text{rank}\Big(A\Big) + \dim\ker \Big(A^T\Big) =r+ \dim\ker \Big(A^T\Big)$$
$$\implies \dim\ker \Big(A^T\Big) = m-r$$

so yes the left nullspace of $$A$$ has $$m-r$$ linearly independent vectors in it -- run gram schmidt on them. These vectors are already orthogonal to the columns of $$A$$ or anything generated solely by linear combinations of the columns of $$A$$ (in particular the columns of thin $$Q$$).

Is it necessary to use the left nullspace of $$A$$?
No. Another approach is to use a random number generator and generate $$m-r$$ column vectors each having $$m$$ components that are uniform in $$[-1,1]$$. With probability 1 these are linearly independent from the columns of $$A$$. So e.g. consider $$A'$$ to be $$A$$ with these randomly generated vectors appended on the right. Now run $$QR$$ factorization. Finally delete the last $$m-r$$ columns in $$R$$.

(in the real world randomized algorithms are quite useful though you'd use a pseudo random number generator and the set of randomly generated vectors would be linearly independent with probability extremely close to but not quite 1.)

Of course you can also bypass all of this by using approach (2).

• Wow, thanks for such a detailed answer! I'll definitely look into the Householder/Givens matrices – EssentialAnonymity Oct 30 '20 at 0:42