Using QR decomposition to solve a system of equations with a singular matrix

Question

If $A\in\mathbb{R}^{n\times n}$ is singular and $x,b\in\mathbb{R}^{n}$ are such that $Ax=b$, am I right in thinking that the upper triangular matrix $R$ of $A$'s $QR$ decomposition must have at least one diagonal entry because otherwise saying $Rx=Q^{T}b$ and using backward substitution would give one definite answer for $x$. But, because $A$ is singular, there cannot be just one solution to the system?

Answer 1

If your matrix $A$ is singular, then you can use the pivoted QR factorisation: $$ A\Pi=QR, $$ where $\Pi$ is a permutation matrix, $Q$ is square orthogonal and the triangular $R$ has the block form $$ R=\begin{bmatrix} R_{11} & R_{12} \\ 0 & 0 \end{bmatrix}, $$ where $R_{11}\in\mathbb{R}^{r\times r}$ ($r$ is the rank of $A$) is nonsingular and upper triangular. Then $Ax=b$ is equivalent to $$ R\tilde{x}=\tilde{b}, \qquad \tilde{x}=\Pi^Tx, \quad \tilde{b}=Q^Tb. $$ Using the partitioning $\tilde{x}=[\tilde{x}_1^T,\tilde{x}_2^T]^T$ and $\tilde{b}=[\tilde{b}_1^T,\tilde{b}_2^T]^T$ leads to $$ R_{11}\tilde{x}_1+R_{12}\tilde{x}_2=\tilde{b}_1, \quad 0 = \tilde{b}_2. $$ So, the system is solvable iff $\tilde{b}_2=0$ and any solution $x$ can be obtained by choosing an arbitrary vector $\tilde{x}_2$, solving $R_{11}\tilde{x}_1=\tilde{b}_1-R_{12}\tilde{x}_2$, and performing the permutation $x=\Pi\tilde{x}$. You might want to obtain, e.g., the minimum 2-norm solution, which can be done simply by choosing $\tilde{x}_2=0$.

Note that the QR decomposition can be less numerically reliable for solving rank-deficient problems than the SVD, or, more precisely, the truncated SVD approach.