= Solution
Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an <orthogonal matrix> $H_1$ for which $H_1A$ has zeros below its first diagonal entry. At stage $j$, apply a <Householder transformation> to rows $j,\ldots,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.
After at most $n-1$ stages,
$$
R=H_{n-1}\cdots H_1A
$$
is an <upper triangular matrix>. Each $H_j$ is symmetric and orthogonal, so with
$$
Q=H_1\cdots H_{n-1}
$$
we have $Q^TQ=I$ and
$$
\boxed{A=QR.}
$$
No invertibility assumption was used, so the <Householder QR decomposition> also exists for singular matrices.
Back to article page
