11.8 QR, Householder and Hessenberg

Section 2 turned a basis into an orthonormal basis one vector at a time, and every step was bookkeeping: each new vector recorded in terms of those already produced. Collect that bookkeeping into a matrix and the Gram–Schmidt process becomes a factorization $\mathbf{A} = \mathbf{Q}\mathbf{R}$ — an orthogonal counterpart of the $\mathbf{L}\mathbf{U}$ factorization of Definition 3.6.1. This section proves it and its uniqueness, then builds it a second time out of reflections, a route that survives dependent columns. The same reflections, applied on both sides, bring any square matrix to an almost-triangular form by a unitary similarity. Throughout, $F$ is $\mathbb{R}$ or $\mathbb{C}$ , and $F^m$ carries the standard inner product, linear in the first slot.

11.8.1. Gram–Schmidt in matrix form

Let $\mathbf{A} \in M_{m \times n}(F)$ have columns $\mathbf{a}_1, \dots, \mathbf{a}_n$ , and suppose they are linearly independent. Apply Theorem 11.2.2 to the list $(\mathbf{a}_1, \dots, \mathbf{a}_n)$ . It returns an orthonormal list $(\mathbf{q}_1, \dots, \mathbf{q}_n)$ in $F^m$ with $\operatorname{span}(\mathbf{q}_1, \dots, \mathbf{q}_k) = \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_k)$ for every $k$ . In particular $\mathbf{a}_k$ lies in $\operatorname{span}(\mathbf{q}_1, \dots, \mathbf{q}_k)$ , and Theorem 11.2.1 (a), applied inside that subspace, expands it: $\mathbf{a}_k = \sum_{i=1}^{k} \langle \mathbf{a}_k, \mathbf{q}_i \rangle\,\mathbf{q}_i \qquad (k = 1, \dots, n). \tag{$\ast$}$

Now read $(\ast)$ as a matrix product. Put $\mathbf{Q} = (\mathbf{q}_1 \mid \dots \mid \mathbf{q}_n) \in M_{m \times n}(F)$ and let $\mathbf{R} \in M_n(F)$ have entries $r_{ik} = \begin{cases} \langle \mathbf{a}_k, \mathbf{q}_i \rangle, & i \le k, \\ 0, & i > k. \end{cases}$ Then $\mathbf{R}$ is upper triangular (Definition 0.9.5), and $(\ast)$ says that the $k$ -th column of $\mathbf{A}$ equals $\mathbf{Q}$ times the $k$ -th column of $\mathbf{R}$ . That is exactly $\mathbf{A} = \mathbf{Q}\mathbf{R}$ . Nothing has been computed; the factorization is the Gram–Schmidt output, rewritten.

Two features of the rewriting matter later. First the diagonal: in the notation of Theorem 11.2.2, $\mathbf{q}_k = \mathbf{w}_k/\left\| \mathbf{w}_k \right\|$ with $\mathbf{w}_k = \mathbf{a}_k - \sum_{i<k}\langle \mathbf{a}_k, \mathbf{q}_i \rangle\mathbf{q}_i$ , so comparing with $(\ast)$ gives $r_{kk} = \langle \mathbf{a}_k, \mathbf{q}_k \rangle = \left\| \mathbf{w}_k \right\| > 0 ,$ strictly positive because $\mathbf{w}_k \neq \mathbf{0}$ . Second, $\mathbf{R}$ is recoverable from $\mathbf{Q}$ and $\mathbf{A}$ : since the columns of $\mathbf{Q}$ are orthonormal, $(\mathbf{Q}^{*}\mathbf{Q})_{ij} = \sum_{p=1}^{m} \overline{q_{pi}}\,q_{pj} = \langle \mathbf{q}_j, \mathbf{q}_i \rangle = \delta_{ij},$ by Definition 11.1.2, so $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ and $\mathbf{R} = \mathbf{Q}^{*}\mathbf{A}$ .

Theorem 11.8.1 (QR Factorization)

Let $\mathbf{A} \in M_{m \times n}(F)$ have linearly independent columns. Then there are matrices $\mathbf{Q} \in M_{m \times n}(F)$ and $\mathbf{R} \in M_n(F)$ with

(a) the columns of $\mathbf{Q}$ orthonormal, equivalently $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ ;
(b) $\mathbf{R}$ upper triangular with positive real diagonal entries;
(c) $\mathbf{A} = \mathbf{Q}\mathbf{R}$ .

Moreover $\mathbf{Q}$ and $\mathbf{R}$ are unique: any pair satisfying (a), (b), (c) is this one. The pair $(\mathbf{Q}, \mathbf{R})$ is the QR factorization of $\mathbf{A}$ .

Idea. Existence is the paragraph above: run Gram–Schmidt and read off the coefficients. For uniqueness, suppose $\mathbf{Q}_1\mathbf{R}_1 = \mathbf{Q}_2\mathbf{R}_2$ . We cannot cancel $\mathbf{Q}$ , which is not square, but $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}$ turns $\mathbf{A}^{*}\mathbf{A}$ into $\mathbf{R}^{*}\mathbf{R}$ and makes the $\mathbf{Q}$ ’s vanish. That leaves $\mathbf{R}_1^{*}\mathbf{R}_1 = \mathbf{R}_2^{*}\mathbf{R}_2$ , so the matrix $\mathbf{S}$ carrying $\mathbf{R}_1$ to $\mathbf{R}_2$ is upper triangular with positive diagonal and satisfies $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}$ . Such a matrix has no room to be anything but $\mathbf{I}$ : column by column, orthogonality to the earlier columns kills every entry above the diagonal.

Proof. Existence. Apply Theorem 11.2.2 to the columns of $\mathbf{A}$ , which is legitimate because they are independent, and define $\mathbf{Q}$ and $\mathbf{R}$ as above. Then (a) holds by orthonormality of the output, (b) holds because $r_{kk} = \left\| \mathbf{w}_k \right\| > 0$ , and (c) is $(\ast)$ .

Uniqueness. Suppose $\mathbf{A} = \mathbf{Q}_1\mathbf{R}_1 = \mathbf{Q}_2\mathbf{R}_2$ with both pairs satisfying (a) and (b). Each $\mathbf{R}_t$ has non-zero diagonal entries, hence is invertible by Lemma 3.6.2. Using $\mathbf{Q}_t^{*}\mathbf{Q}_t = \mathbf{I}_n$ twice, $\mathbf{R}_1^{*}\mathbf{R}_1 = \mathbf{R}_1^{*}\mathbf{Q}_1^{*}\mathbf{Q}_1\mathbf{R}_1 = \mathbf{A}^{*}\mathbf{A} = \mathbf{R}_2^{*}\mathbf{Q}_2^{*}\mathbf{Q}_2\mathbf{R}_2 = \mathbf{R}_2^{*}\mathbf{R}_2 .$ Put $\mathbf{S} = \mathbf{R}_2\mathbf{R}_1^{-1}$ , so that $\mathbf{R}_2 = \mathbf{S}\mathbf{R}_1$ . The matrix $\mathbf{R}_1^{-1}$ is upper triangular: its $j$ -th column is the solution $\mathbf{x}$ of $\mathbf{R}_1\mathbf{x} = \mathbf{e}_j$ , and solving from the bottom row upward gives $x_i = 0$ for every $i > j$ , exactly as in the proof of Lemma 3.6.2. Hence $\mathbf{S}$ is upper triangular, being a product of upper triangular matrices: in $(\mathbf{S})_{ij} = \sum_k (\mathbf{R}_2)_{ik}(\mathbf{R}_1^{-1})_{kj}$ a term can be non-zero only when $i \le k$ and $k \le j$ , which is impossible for $i > j$ , and for $i = j$ only the term $k = i$ survives. So its diagonal entries are $(\mathbf{S})_{kk} = (\mathbf{R}_2)_{kk}(\mathbf{R}_1)_{kk}^{-1} > 0$ , a quotient of positive reals. Substituting $\mathbf{R}_2 = \mathbf{S}\mathbf{R}_1$ into the display gives $\mathbf{R}_1^{*}\mathbf{R}_1 = \mathbf{R}_1^{*}\mathbf{S}^{*}\mathbf{S}\mathbf{R}_1$ , and multiplying by $(\mathbf{R}_1^{*})^{-1} = (\mathbf{R}_1^{-1})^{*}$ on the left and $\mathbf{R}_1^{-1}$ on the right leaves $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n .$

Claim. An upper triangular $\mathbf{S} \in M_n(F)$ with $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n$ and positive real diagonal entries is $\mathbf{I}_n$ .

Proof. Write $\mathbf{s}_1, \dots, \mathbf{s}_n$ for the columns of $\mathbf{S}$ . As computed before the theorem, $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n$ says $\langle \mathbf{s}_j, \mathbf{s}_i \rangle = \delta_{ij}$ . We show $\mathbf{s}_j = \mathbf{e}_j$ by induction on $j$ . Let $1 \le j \le n$ and suppose $\mathbf{s}_i = \mathbf{e}_i$ for every $i < j$ (no assumption when $j = 1$ ). For $i < j$ , $0 = \langle \mathbf{s}_j, \mathbf{s}_i \rangle = \langle \mathbf{s}_j, \mathbf{e}_i \rangle = s_{ij},$ so every entry of $\mathbf{s}_j$ above the diagonal vanishes; and $s_{ij} = 0$ for $i > j$ because $\mathbf{S}$ is upper triangular. Hence $\mathbf{s}_j = s_{jj}\mathbf{e}_j$ , and $1 = \langle \mathbf{s}_j, \mathbf{s}_j \rangle = \lvert s_{jj}\rvert^2$ forces $\lvert s_{jj}\rvert = 1$ . Since $s_{jj} > 0$ , this gives $s_{jj} = 1$ and $\mathbf{s}_j = \mathbf{e}_j$ .

By the Claim, $\mathbf{S} = \mathbf{I}_n$ , so $\mathbf{R}_2 = \mathbf{R}_1$ and therefore $\mathbf{Q}_2 = \mathbf{A}\mathbf{R}_2^{-1} = \mathbf{A}\mathbf{R}_1^{-1} = \mathbf{Q}_1$ . This proves uniqueness.

The positivity in (b) is a normalization and nothing deeper: without it, scaling $\mathbf{q}_k$ by any $c$ of modulus $1$ and row $k$ of $\mathbf{R}$ by $\overline{c}$ gives another factorization. Exercise (C1: All the QR factorizations of a matrix) describes all of them.

Warning. In $\mathbf{A} = \mathbf{Q}\mathbf{R}$ the matrix $\mathbf{Q}$ is usually not square, and $\mathbf{Q}\mathbf{Q}^{*} \neq \mathbf{I}$ . Only $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ holds. For the $3 \times 2$ matrix of Example (A $3 \times 2$ QR, and a least-squares problem) below, $\mathbf{Q}\mathbf{Q}^{*} = \tfrac{1}{18}\begin{pmatrix} 2 & 4 & 4 \\ 4 & 17 & -1 \\ 4 & -1 & 17 \end{pmatrix},$ whose trace is $2$ , not $3$ . This is the “identity on what?” trap of Theorem 11.7.3: the columns of $\mathbf{Q}$ are an orthonormal basis of a plane, and $\mathbf{Q}\mathbf{Q}^{*}$ is the orthogonal projection onto it (Theorem 11.3.3).

Quick check. Each factor of a QR factorization is recoverable from the other: $\mathbf{R} = \mathbf{Q}^{*}\mathbf{A}$ and $\mathbf{Q} = \mathbf{A}\mathbf{R}^{-1}$ . One of the two recoveries needs an invertibility hypothesis and the other does not. Which, and why?

Solution. The second. Multiplying $\mathbf{A} = \mathbf{Q}\mathbf{R}$ on the left by $\mathbf{Q}^{*}$ gives $\mathbf{Q}^{*}\mathbf{Q}\mathbf{R} = \mathbf{R}$ , which uses only $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ : nothing is inverted, and $\mathbf{Q}$ is not even square. Multiplying on the right by $\mathbf{R}^{-1}$ presupposes that $\mathbf{R}$ is invertible — true by Lemma 3.6.2, but only because clause (b) makes the diagonal positive.

11.8.2. Least squares through QR

An inconsistent system $\mathbf{A}\mathbf{x} = \mathbf{b}$ was handled in Section 4 by the normal equations $\mathbf{A}^{*}\mathbf{A}\mathbf{x} = \mathbf{A}^{*}\mathbf{b}$ (Theorem 11.4.2). When the columns of $\mathbf{A}$ are independent, the QR factorization simplifies those equations to a triangular system.

Substituting $\mathbf{A} = \mathbf{Q}\mathbf{R}$ and using $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ , $\mathbf{A}^{*}\mathbf{A} = \mathbf{R}^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{R} = \mathbf{R}^{*}\mathbf{R}, \qquad \mathbf{A}^{*}\mathbf{b} = \mathbf{R}^{*}\mathbf{Q}^{*}\mathbf{b} ,$ so the normal equations read $\mathbf{R}^{*}\mathbf{R}\mathbf{x} = \mathbf{R}^{*}\mathbf{Q}^{*}\mathbf{b}$ . Now $\mathbf{R}$ is invertible by Lemma 3.6.2, hence so is $\mathbf{R}^{*}$ , with $(\mathbf{R}^{*})^{-1} = (\mathbf{R}^{-1})^{*}$ — conjugate-transpose $\mathbf{R}\mathbf{R}^{-1} = \mathbf{I}_n$ . So $\mathbf{R}^{*}$ cancels: $\mathbf{R}\mathbf{x} = \mathbf{Q}^{*}\mathbf{b} . \tag{$\dagger$}$ By Corollary 11.4.4 the least-squares solution is unique here, and $(\dagger)$ is a triangular system, solved by back substitution. The deeper reason to prefer it is not the operation count: forming $\mathbf{A}^{*}\mathbf{A}$ squares the sensitivity of the problem to rounding, while $(\dagger)$ never forms that product at all. Chapter 24 makes “sensitivity” precise and proves the comparison; here we record only the practice.

Example (A

3 \times 2

QR, and a least-squares problem)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 2 & 3 \end{pmatrix}, \qquad \mathbf{b} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} .$

(a) Find the QR factorization of $\mathbf{A}$ .
(b) Find the $\mathbf{x} \in \mathbb{R}^2$ minimizing $\left\| \mathbf{A}\mathbf{x} - \mathbf{b} \right\|$ , using (a).

Solution.

(a) Write $\mathbf{a}_1 = (1,2,2)$ and $\mathbf{a}_2 = (1,1,3)$ . They are independent, since neither is a multiple of the other.
Step 1. $\left\| \mathbf{a}_1 \right\|^2 = 1 + 4 + 4 = 9$ , so $r_{11} = 3$ and $\mathbf{q}_1 = \tfrac13(1,2,2)$ .

Step 2. $r_{12} = \langle \mathbf{a}_2, \mathbf{q}_1 \rangle = \tfrac13(1 + 2 + 6) = 3$ , so $\mathbf{w}_2 = (1,1,3) - 3 \cdot \tfrac13(1,2,2) = (0,-1,1),$ with $\left\| \mathbf{w}_2 \right\| = \sqrt2 = r_{22}$ and $\mathbf{q}_2 = \tfrac{1}{\sqrt2}(0,-1,1)$ . Hence $\mathbf{Q} = \begin{pmatrix} \tfrac13 & 0 \\[2pt] \tfrac23 & -\tfrac{1}{\sqrt2} \\[2pt] \tfrac23 & \tfrac{1}{\sqrt2} \end{pmatrix}, \qquad \mathbf{R} = \begin{pmatrix} 3 & 3 \\ 0 & \sqrt2 \end{pmatrix}.$ Check. $\mathbf{Q}\mathbf{R}$ has first column $3\mathbf{q}_1 = (1,2,2)$ and second column $3\mathbf{q}_1 + \sqrt2\,\mathbf{q}_2 = (1,2,2) + (0,-1,1) = (1,1,3)$ , which is $\mathbf{A}$ .
(b) By $(\dagger)$ we need $\mathbf{Q}^{*}\mathbf{b}$ . Here $\langle \mathbf{b}, \mathbf{q}_1 \rangle = \tfrac13(1+2+2) = \tfrac53$ and $\langle \mathbf{b}, \mathbf{q}_2 \rangle = \tfrac{1}{\sqrt2}(0 - 1 + 1) = 0$ , so the system is $\begin{pmatrix} 3 & 3 \\ 0 & \sqrt2 \end{pmatrix}\mathbf{x} = \begin{pmatrix} \tfrac53 \\ 0 \end{pmatrix}.$ Back substitution gives $\sqrt2\,x_2 = 0$ , so $x_2 = 0$ , and then $3x_1 = \tfrac53$ , so $x_1 = \tfrac59$ . The minimizer is $\mathbf{x} = (\tfrac59, 0)$ .

Check against the normal equations. $\mathbf{A}^{\top}\mathbf{A} = \begin{pmatrix} 9 & 9 \\ 9 & 11\end{pmatrix}$ and $\mathbf{A}^{\top}\mathbf{b} = (5, 5)$ . Subtracting the first equation from the second gives $2x_2 = 0$ , and then $9x_1 = 5$ . The same answer, with the same arithmetic done in a worse order.

11.8.3. Reflections

Gram–Schmidt builds $\mathbf{Q}$ out of the columns of $\mathbf{A}$ . There is an entirely different route to a triangular $\mathbf{R}$ , modeled on elimination: hit $\mathbf{A}$ on the left with simple matrices that create zeros, one column at a time, and collect the inverses. Chapter 3 used shears and got $\mathbf{A} = \mathbf{L}\mathbf{U}$ ; if every matrix we hit $\mathbf{A}$ with is unitary instead, the collected product is unitary and we get $\mathbf{A} = \mathbf{Q}\mathbf{R}$ . Which unitary matrices are simple enough? A rotation in the plane of two coordinates is one answer, taken up below. The more efficient answer is a reflection, because one reflection can flatten an entire column at once.

A reflection in a hyperplane sends a vector to its mirror image: keep the part perpendicular to $\mathbf{w}$ , and reverse the part along $\mathbf{w}$ .

Definition 11.8.1 (Householder Reflection)

Let $\mathbf{w} \in F^m$ be non-zero. The Householder reflection determined by $\mathbf{w}$ is $\mathbf{H}_{\mathbf{w}} = \mathbf{I}_m - \frac{2\,\mathbf{w}\mathbf{w}^{*}}{\left\| \mathbf{w} \right\|^2} \in M_m(F) .$

In words: $\mathbf{w}\mathbf{w}^{*}$ is an $m \times m$ matrix (a column times a row), and for any $\mathbf{v} \in F^m$ the product $\mathbf{w}^{*}\mathbf{v}$ is the scalar $\sum_p \overline{w_p}v_p = \langle \mathbf{v}, \mathbf{w} \rangle$ . So the definition says $\mathbf{H}_{\mathbf{w}}\mathbf{v} = \mathbf{v} - 2\,\frac{\langle \mathbf{v}, \mathbf{w} \rangle}{\left\| \mathbf{w} \right\|^2}\,\mathbf{w} = \mathbf{v} - 2P_{\operatorname{span}(\mathbf{w})}\mathbf{v} , \tag{$\ddagger$}$ where the last equality is Theorem 11.3.3 with the orthonormal basis $(\mathbf{w}/\left\| \mathbf{w} \right\|)$ of the line $\operatorname{span}(\mathbf{w})$ . Writing $\mathbf{v} = P_{\operatorname{span}(\mathbf{w})}\mathbf{v} + (\mathbf{v} - P_{\operatorname{span}(\mathbf{w})}\mathbf{v})$ as in Theorem 11.3.2, we see that $\mathbf{H}_{\mathbf{w}}$ keeps the component of $\mathbf{v}$ in $\operatorname{span}(\mathbf{w})^{\perp}$ and reverses the component along $\mathbf{w}$ . That is a mirror reflection in the hyperplane $\operatorname{span}(\mathbf{w})^{\perp}$ .

Note at once that $\mathbf{H}_{c\mathbf{w}} = \mathbf{H}_{\mathbf{w}}$ for every non-zero scalar $c$ , since $(c\mathbf{w})(c\mathbf{w})^{*} = \lvert c\rvert^2\mathbf{w}\mathbf{w}^{*}$ and $\left\| c\mathbf{w} \right\|^2 = \lvert c\rvert^2\left\| \mathbf{w} \right\|^2$ . Only the line through $\mathbf{w}$ matters.

Examples.

The smallest case. In $F^1$ take $\mathbf{w} = 1$ : then $\mathbf{H}_{\mathbf{w}} = -1$ , the map $x \mapsto -x$ . The “hyperplane” is $\{0\}$ , and this is the only non-trivial isometry of the line.
A coordinate reflection. In $\mathbb{R}^2$ take $\mathbf{w} = \mathbf{e}_2$ , so $\mathbf{w}\mathbf{w}^{\top} = \begin{pmatrix} 0&0\\mathbf{0}&1\end{pmatrix}$ and $\mathbf{H}_{\mathbf{w}} = \operatorname{diag}(1, -1)$ : the reflection in the $x$ -axis.
A diagonal reflection. In $\mathbb{R}^2$ take $\mathbf{w} = (1, -1)$ , so $\left\| \mathbf{w} \right\|^2 = 2$ and $\mathbf{H}_{\mathbf{w}} = \mathbf{I}_2 - \begin{pmatrix} 1&-1\\-1&1\end{pmatrix} = \begin{pmatrix} 0&1\\mathbf{1}&0\end{pmatrix}$ , which swaps the coordinates. It is the reflection in the line $y = x$ , and $\operatorname{span}(\mathbf{w})^{\perp}$ is that line.
A complex one. In $\mathbb{C}^m$ take $\mathbf{w} = \mathbf{e}_1$ : then $\mathbf{H}_{\mathbf{w}} = \operatorname{diag}(-1, 1, \dots, 1)$ , over either field.

Non-example by minimal change. Drop the factor $2$ : the matrix $\mathbf{I}_m - \mathbf{w}\mathbf{w}^{*}/\left\| \mathbf{w} \right\|^2$ is $\mathbf{I}_m - P_{\operatorname{span}(\mathbf{w})}$ , the orthogonal projection onto $\operatorname{span}(\mathbf{w})^{\perp}$ . It is Hermitian, as $\mathbf{H}_{\mathbf{w}}$ is, but not unitary and not invertible: it sends $\mathbf{w}$ to $\mathbf{0}$ . Halving the coefficient turns “reverse the component along $\mathbf{w}$ ” into “delete it”, an isometry into a shadow.

Proposition 11.8.2 (Properties of a Householder Reflection)

Let $\mathbf{w} \in F^m$ be non-zero and $\mathbf{H} = \mathbf{H}_{\mathbf{w}}$ . Then

(a) $\mathbf{H}^{*} = \mathbf{H}$ ( $\mathbf{H}$ is Hermitian);
(b) $\mathbf{H}^2 = \mathbf{I}_m$ , so $\mathbf{H}^{-1} = \mathbf{H}$ ;
(c) $\mathbf{H}$ is unitary;
(d) $\mathbf{H}\mathbf{w} = -\mathbf{w}$ , and $\mathbf{H}\mathbf{v} = \mathbf{v}$ for every $\mathbf{v} \perp \mathbf{w}$ ;
(e) $\det \mathbf{H} = -1$ .

Proof.

(a) By Definition 11.1.2, $(\mathbf{w}\mathbf{w}^{*})^{*} = \mathbf{w}^{**}\mathbf{w}^{*} = \mathbf{w}\mathbf{w}^{*}$ , and $\left\| \mathbf{w} \right\|^2$ is a real number (Theorem 11.1.1 (a)), so $\mathbf{H}^{*} = \mathbf{I}_m - 2\mathbf{w}\mathbf{w}^{*}/\left\| \mathbf{w} \right\|^2 = \mathbf{H}$ .
(b) Since $\mathbf{w}^{*}\mathbf{w} = \langle \mathbf{w}, \mathbf{w} \rangle = \left\| \mathbf{w} \right\|^2$ , $\mathbf{H}^2 = \mathbf{I}_m - \frac{4\mathbf{w}\mathbf{w}^{*}}{\left\| \mathbf{w} \right\|^2} + \frac{4\,\mathbf{w}(\mathbf{w}^{*}\mathbf{w})\mathbf{w}^{*}}{\left\| \mathbf{w} \right\|^4} = \mathbf{I}_m ,$ because the last two terms cancel.
(c) By (a) and (b), $\mathbf{H}^{*}\mathbf{H} = \mathbf{H}^2 = \mathbf{I}_m$ , which is the criterion of Definition 11.7.2.
(d) Both statements are read off $(\ddagger)$ : $P_{\operatorname{span}(\mathbf{w})}\mathbf{w} = \mathbf{w}$ gives $\mathbf{H}\mathbf{w} = \mathbf{w} - 2\mathbf{w} = -\mathbf{w}$ , and $\langle \mathbf{v}, \mathbf{w} \rangle = 0$ gives $\mathbf{H}\mathbf{v} = \mathbf{v}$ .
(e) Extend the unit vector $\mathbf{w}/\left\| \mathbf{w} \right\|$ to an orthonormal basis $(\mathbf{f}_1, \dots, \mathbf{f}_m)$ of $F^m$ with $\mathbf{f}_1 = \mathbf{w}/\left\| \mathbf{w} \right\|$ , which is possible by Corollary 11.2.3, and let $\mathbf{P} = (\mathbf{f}_1 \mid \dots \mid \mathbf{f}_m)$ . By (d), $\mathbf{H}\mathbf{f}_1 = -\mathbf{f}_1$ and $\mathbf{H}\mathbf{f}_i = \mathbf{f}_i$ for $i \ge 2$ , that is, $\mathbf{H}\mathbf{P} = \mathbf{P}\mathbf{D}$ with $\mathbf{D} = \operatorname{diag}(-1, 1, \dots, 1)$ . The matrix $\mathbf{P}$ is unitary, hence invertible, so $\mathbf{H} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}$ . Taking determinants, $\det \mathbf{H} = \det\mathbf{D}$ by Theorem 7.5.4 and Corollary 7.5.6, and $\det \mathbf{D} = -1$ by Theorem 7.4.6.

So a Householder reflection is a unitary involution of determinant $-1$ : cheap to store (one vector) and cheap to apply, by $(\ddagger)$ . What makes it useful is the following choice of $\mathbf{w}$ .

Theorem 11.8.3 (A Reflection Flattening a Vector)

Let $\mathbf{x} \in F^m$ be non-zero, and let $\alpha = \begin{cases} x_1/\lvert x_1\rvert, & x_1 \neq 0, \\ 1, & x_1 = 0, \end{cases} \qquad \mathbf{w} = \mathbf{x} + \alpha\left\| \mathbf{x} \right\|\,\mathbf{e}_1 .$ Then $\mathbf{w} \neq \mathbf{0}$ and $\mathbf{H}_{\mathbf{w}}\,\mathbf{x} = -\alpha\left\| \mathbf{x} \right\|\,\mathbf{e}_1 .$ In particular $\mathbf{H}_{\mathbf{w}}\mathbf{x}$ is a multiple of $\mathbf{e}_1$ of length $\left\| \mathbf{x} \right\|$ . Over $\mathbb{R}$ , $\alpha$ is the sign of $x_1$ (or $1$ if $x_1 = 0$ ), and $\mathbf{H}_{\mathbf{w}}\mathbf{x} = \mp\left\| \mathbf{x} \right\|\mathbf{e}_1$ according to that sign.

Idea. Picture the real plane. We want a mirror line taking $\mathbf{x}$ to a point on the first axis at the same distance from the origin. There are two such points, $\pm\left\| \mathbf{x} \right\|\mathbf{e}_1$ , and for each the mirror is the perpendicular bisector of the segment joining $\mathbf{x}$ to it — whose normal direction is the difference $\mathbf{x} \mp \left\| \mathbf{x} \right\|\mathbf{e}_1$ . So the vector $\mathbf{w}$ is forced, up to which of the two targets we aim at, and all that remains is to check that the coefficient $2\langle \mathbf{x}, \mathbf{w} \rangle/\left\| \mathbf{w} \right\|^2$ in $(\ddagger)$ comes out exactly $1$ , so that $\mathbf{H}_{\mathbf{w}}\mathbf{x} = \mathbf{x} - \mathbf{w}$ . The role of $\alpha$ is to choose the target on the far side from $\mathbf{x}$ .

Proof. Note first that $\overline{\alpha}x_1 = \lvert x_1\rvert$ in both cases, and $\lvert \alpha\rvert = 1$ . Expanding with (IP1) and Theorem 11.1.1 (b), $\begin{aligned} \left\| \mathbf{w} \right\|^2 &= \left\| \mathbf{x} \right\|^2 + \overline{\alpha}\left\| \mathbf{x} \right\|\langle \mathbf{x}, \mathbf{e}_1 \rangle + \alpha\left\| \mathbf{x} \right\|\langle \mathbf{e}_1, \mathbf{x} \rangle + \lvert\alpha\rvert^2\left\| \mathbf{x} \right\|^2 \\ &= 2\left\| \mathbf{x} \right\|^2 + 2\left\| \mathbf{x} \right\|\,\lvert x_1\rvert , \end{aligned}$ where the second line uses $\langle \mathbf{x}, \mathbf{e}_1 \rangle = x_1$ , $\langle \mathbf{e}_1, \mathbf{x} \rangle = \overline{x_1}$ and $\overline{\alpha}x_1 + \alpha\overline{x_1} = 2\lvert x_1\rvert$ . Since $\mathbf{x} \neq \mathbf{0}$ we have $\left\| \mathbf{x} \right\| > 0$ , so $\left\| \mathbf{w} \right\|^2 > 0$ and $\mathbf{w} \neq \mathbf{0}$ . Likewise $\langle \mathbf{x}, \mathbf{w} \rangle = \left\| \mathbf{x} \right\|^2 + \overline{\alpha}\left\| \mathbf{x} \right\|\,x_1 = \left\| \mathbf{x} \right\|^2 + \left\| \mathbf{x} \right\|\lvert x_1\rvert ,$ so that $2\langle \mathbf{x}, \mathbf{w} \rangle = \left\| \mathbf{w} \right\|^2$ . Hence by $(\ddagger)$ , $\mathbf{H}_{\mathbf{w}}\mathbf{x} = \mathbf{x} - \frac{2\langle \mathbf{x}, \mathbf{w} \rangle}{\left\| \mathbf{w} \right\|^2}\,\mathbf{w} = \mathbf{x} - \mathbf{w} = -\alpha\left\| \mathbf{x} \right\|\,\mathbf{e}_1 .$ Finally $\left\| -\alpha\left\| \mathbf{x} \right\|\mathbf{e}_1 \right\| = \lvert\alpha\rvert\left\| \mathbf{x} \right\| = \left\| \mathbf{x} \right\|$ by Theorem 11.1.2 (b), as it must be, since $\mathbf{H}_{\mathbf{w}}$ is unitary. This proves the theorem.

Why that sign. The opposite choice $\mathbf{w}' = \mathbf{x} - \alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ also works whenever $\mathbf{w}' \neq \mathbf{0}$ , giving $\mathbf{H}_{\mathbf{w}'}\mathbf{x} = +\alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ ; in exact arithmetic the two are equally good, and in floating point they are not. The first entry of $\mathbf{w}'$ is $x_1 - \alpha\left\| \mathbf{x} \right\|$ , a difference of two numbers of modulus $\lvert x_1\rvert$ and $\left\| \mathbf{x} \right\|$ — and when $\mathbf{x}$ is close to a multiple of $\mathbf{e}_1$ those two are nearly equal, so the leading digits cancel and the computed first entry keeps only the few digits they did not share. The other entries of $\mathbf{w}'$ are copied from $\mathbf{x}$ and stay exact, so the computed $\mathbf{w}'$ points in a noticeably wrong direction, and so does the reflection built from it. With $\mathbf{w} = \mathbf{x} + \alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ the first entry has modulus $\lvert x_1\rvert + \left\| \mathbf{x} \right\|$ : like-signed quantities, nothing to cancel. (The same computation shows $\mathbf{w} \ne \mathbf{0}$ always, whereas $\mathbf{w}' = \mathbf{0}$ exactly when $\mathbf{x} = \alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ , the extreme case of that cancellation.) Chapter 24 quantifies the loss; the summary here is that both signs are correct mathematics and only one is correct arithmetic.

Warning. Do not build the matrix $\mathbf{H}_{\mathbf{w}}$ in order to use it. Forming it and multiplying costs $m^2$ operations per column, while $(\ddagger)$ applies the same reflection with one inner product and one scaled subtraction, about $4m$ . Every “multiply by $\mathbf{H}$ ” below is really an instance of $(\ddagger)$ ; the matrix is a proof device.

Quick check. Let $\mathbf{x} = (0, 3, 4) \in \mathbb{R}^3$ . Find $\mathbf{w}$ and $\mathbf{H}_{\mathbf{w}}\mathbf{x}$ as in Theorem 11.8.3, and say why the sign question does not arise here.

Solution. $\left\| \mathbf{x} \right\| = 5$ and $x_1 = 0$ , so $\alpha = 1$ and $\mathbf{w} = (0,3,4) + 5(1,0,0) = (5,3,4)$ . Then $\mathbf{H}_{\mathbf{w}}\mathbf{x} = -5\mathbf{e}_1 = (-5,0,0)$ . With $x_1 = 0$ there is no cancellation to avoid: the first entry of $\mathbf{w}$ is $0 \pm 5$ either way, and both choices are equally accurate. The convention $\alpha = 1$ is only a convention.

11.8.4. QR by reflections

One reflection makes the first column a multiple of $\mathbf{e}_1$ — exactly the zeros an upper triangular matrix needs in column $1$ . Repeating on the trailing submatrix triangularizes everything.

Theorem 11.8.4 (QR by Householder Reflections)

Let $\mathbf{A} \in M_{m \times n}(F)$ . Then there are a unitary $\mathbf{Q} \in M_m(F)$ and an $\mathbf{R} \in M_{m \times n}(F)$ with $r_{ij} = 0$ whenever $i > j$ , such that $\mathbf{A} = \mathbf{Q}\mathbf{R} .$ Moreover $\mathbf{Q}$ can be taken to be a product of at most $\min(n, m-1)$ Householder reflections. No hypothesis on the columns of $\mathbf{A}$ is needed.

Idea. Induction on the number of columns. Step one is Theorem 11.8.3 applied to the first column: after it, the first column is $\rho\mathbf{e}_1$ and what is left to triangularize is the trailing $(m-1) \times (n-1)$ block. Feed that block to the induction hypothesis, and lift the unitary matrix it returns to $F^m$ by putting a $1$ in the top-left corner — a block matrix of that shape does not touch the first row or the first column, so it cannot spoil the zeros just created.

Proof. We induct on $n$ , the statement being asserted for every $m \ge 1$ at once.

If $m = 1$ , then $\mathbf{A}$ has no entries below its diagonal, so $\mathbf{Q} = \mathbf{I}_1$ and $\mathbf{R} = \mathbf{A}$ work. Assume from now on that $m \ge 2$ .

Let $\mathbf{a}$ be the first column of $\mathbf{A}$ . If $\mathbf{a} = \mathbf{0}$ , put $\mathbf{H} = \mathbf{I}_m$ and $\rho = 0$ ; otherwise let $\mathbf{H} = \mathbf{H}_{\mathbf{w}}$ be the reflection of Theorem 11.8.3 for $\mathbf{x} = \mathbf{a}$ , and $\rho = -\alpha\left\| \mathbf{a} \right\|$ . In both cases $\mathbf{H}$ is unitary and Hermitian with $\mathbf{H}^{-1} = \mathbf{H}$ — by Proposition 11.8.2 (a)–(c) for a reflection, and because $\mathbf{I}_m^{*} = \mathbf{I}_m = \mathbf{I}_m^{-1}$ in the degenerate case — and $\mathbf{H}\mathbf{a} = \rho\mathbf{e}_1$ . Hence, by Theorem 8.1.1, $\mathbf{H}\mathbf{A} = \begin{pmatrix} \rho & \mathbf{b}^{*} \\ \mathbf{0} & \mathbf{A}' \end{pmatrix}$ for some $\mathbf{b} \in F^{n-1}$ and $\mathbf{A}' \in M_{(m-1)\times(n-1)}(F)$ , where the $\mathbf{0}$ is a column of $m - 1$ zeros.

Base case $n = 1$ . There is no block $\mathbf{A}'$ , and $\mathbf{H}\mathbf{A} = \rho\mathbf{e}_1$ already has $r_{i1} = 0$ for $i > 1$ . So $\mathbf{A} = \mathbf{H}(\mathbf{H}\mathbf{A})$ is of the required form with $\mathbf{Q} = \mathbf{H}$ .

Induction step. Let $n \ge 2$ and assume the statement for $n - 1$ columns. Applied to $\mathbf{A}'$ , which has $m - 1 \ge 1$ rows, it gives a unitary $\mathbf{Q}' \in M_{m-1}(F)$ and an $\mathbf{R}'$ with zeros below the diagonal and $\mathbf{A}' = \mathbf{Q}'\mathbf{R}'$ . Put $\mathbf{U} = \begin{pmatrix} 1 & \mathbf{0}^{*} \\ \mathbf{0} & \mathbf{Q}' \end{pmatrix}, \qquad \mathbf{R} = \begin{pmatrix} \rho & \mathbf{b}^{*} \\ \mathbf{0} & \mathbf{R}' \end{pmatrix} .$ Then $\mathbf{U}^{*}\mathbf{U} = \mathbf{I}_m$ by Theorem 8.1.1, so $\mathbf{U}$ is unitary, and $\mathbf{U}\mathbf{R} = \mathbf{H}\mathbf{A}$ by the same computation. Also $\mathbf{R}$ has zeros below its diagonal: in column $1$ this is the block $\mathbf{0}$ ; and for $j \ge 2$ and $i > j$ , the $(i, j)$ -entry of $\mathbf{R}$ is the $(i-1, j-1)$ -entry of $\mathbf{R}'$ , which vanishes because $i - 1 > j - 1$ .

Therefore $\mathbf{A} = \mathbf{H}\mathbf{U}\mathbf{R}$ , and $\mathbf{Q} = \mathbf{H}\mathbf{U}$ is unitary as a product of unitary matrices (Proposition 11.7.4). Unwinding the induction, $\mathbf{Q}$ is a product of one reflection (or $\mathbf{I}_m$ ) for each of the columns $1, \dots, \min(n, m-1)$ , since the recursion stops once one row is left. This proves the theorem.

Example (A

3 \times 3

QR by reflections)

Triangularize $\mathbf{A} = \begin{pmatrix} 2 & 0 & 1 \\ 1 & 5 & 2 \\ 2 & 5 & 4 \end{pmatrix}$ by Householder reflections, and read off $\mathbf{Q}$ and $\mathbf{R}$ .

Solution. Step 1. The first column is $\mathbf{a} = (2,1,2)$ with $\left\| \mathbf{a} \right\| = 3$ and $a_1 = 2 > 0$ , so $\alpha = 1$ and $\mathbf{w}_1 = (2,1,2) + 3(1,0,0) = (5,1,2), \qquad \left\| \mathbf{w}_1 \right\|^2 = 30 .$ Apply $(\ddagger)$ to each column: $\mathbf{H}_1\mathbf{v} = \mathbf{v} - \tfrac{1}{15}\langle \mathbf{v}, \mathbf{w}_1 \rangle\mathbf{w}_1$ . All three columns pair with $\mathbf{w}_1$ to give $15$ , so each loses exactly one copy of $\mathbf{w}_1$ : $\mathbf{H}_1\mathbf{A} = \begin{pmatrix} -3 & -5 & -4 \\ 0 & 4 & 1 \\ 0 & 3 & 2 \end{pmatrix}.$ (As predicted, the first column is $-\left\| \mathbf{a} \right\|\mathbf{e}_1$ .)

Step 2. Work now in the trailing $2 \times 2$ block, whose first column is $\mathbf{y} = (4,3)$ with $\left\| \mathbf{y} \right\| = 5$ and $y_1 > 0$ . So $\mathbf{w}_2 = (9,3)$ , and inside $\mathbb{R}^3$ we reflect in $\widetilde{\mathbf{w}}_2 = (0,9,3)$ , which fixes $\mathbf{e}_1$ and so leaves column $1$ alone; here $\mathbf{H}_2\mathbf{v} = \mathbf{v} - \tfrac{1}{45}\langle \mathbf{v}, \widetilde{\mathbf{w}}_2 \rangle\,\widetilde{\mathbf{w}}_2$ . The second and third columns of $\mathbf{H}_1\mathbf{A}$ pair with $\widetilde{\mathbf{w}}_2$ to give $36 + 9 = 45$ and $9 + 6 = 15$ , so they lose one copy and a third of a copy respectively: $\mathbf{R} = \mathbf{H}_2\mathbf{H}_1\mathbf{A} = \begin{pmatrix} -3 & -5 & -4 \\ 0 & -5 & -2 \\ 0 & 0 & 1 \end{pmatrix}.$

The unitary factor. By Proposition 11.8.2 (b), $\mathbf{A} = \mathbf{H}_1\mathbf{H}_2\mathbf{R}$ , so $\mathbf{Q} = \mathbf{H}_1\mathbf{H}_2$ . Computing the product, $\mathbf{Q} = \tfrac13\begin{pmatrix} -2 & 2 & -1 \\ -1 & -2 & -2 \\ -2 & -1 & 2 \end{pmatrix},$ whose columns have length $1$ and are pairwise orthogonal, as one checks from the integer entries: for instance $(-2)(2) + (-1)(-2) + (-2)(-1) = 0$ .

Check. $\det \mathbf{A} = 15$ by expansion along the first row, and $\det \mathbf{R} = (-3)(-5)(1) = 15$ by Theorem 7.4.6, consistent with $\det \mathbf{Q} = (-1)(-1) = 1$ from Proposition 11.8.2 (e).

The diagonal of $\mathbf{R}$ here is $(-3, -5, 1)$ , not positive: the reflection route produces a factorization, not the one of Theorem 11.8.1. The two are related by flipping the sign of each row of $\mathbf{R}$ with a negative diagonal entry, and of the matching column of $\mathbf{Q}$ ; Exercise (B2: The same matrix by reflections) carries this out on the matrix of Example (A $3 \times 2$ QR, and a least-squares problem).

Warning. “The QR factorization” is definite only with the positivity normalization. Theorem 11.8.1 pins the pair down by demanding $r_{kk} > 0$ ; the reflection algorithm ignores that demand and chooses signs for stability instead. So two correct computations of “the QR factorization of $\mathbf{A}$ ” can differ by signs. Compare $\lvert r_{kk}\rvert$ , and the lines spanned by the columns of $\mathbf{Q}$ .

Where Gram–Schmidt cannot follow. Theorem 11.8.4 assumed nothing about the columns, and that is a genuine gain. Let the columns of $\mathbf{A}$ be dependent, and let $k$ be the first index with $\mathbf{a}_k \in \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{k-1})$ . The Gram–Schmidt recursion then produces $\mathbf{w}_k = \mathbf{0}$ and stops, because the next step divides by $\left\| \mathbf{w}_k \right\|$ ; Exercise (C2: Gram–Schmidt on a dependent list) works this out. Nor is the failure an artifact of the method: if $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_n$ and $\mathbf{R}$ upper triangular with positive diagonal, then $\mathbf{R}$ is invertible by Lemma 3.6.2, so $\operatorname{rank} \mathbf{A} = \operatorname{rank} \mathbf{Q} = n$ and the columns were independent after all. A QR factorization in the sense of Theorem 11.8.1 exists exactly for matrices of full column rank. The reflection route is untroubled: a dependent column simply puts a zero on the diagonal of $\mathbf{R}$ where the dependence appears, and the algorithm continues (Exercise (C2: Reflections do not mind dependence)).

11.8.5. Givens rotations

A reflection zeroes a whole column at once. Sometimes that is too much: if $\mathbf{A}$ is nearly triangular already, we would rather kill the few offending entries one at a time and leave the rest alone.

Definition 11.8.2 (Givens Rotation)

Let $1 \le i < j \le m$ and let $c, s \in \mathbb{R}$ with $c^2 + s^2 = 1$ . The Givens rotation $\mathbf{G}(i, j; c, s) \in M_m(\mathbb{R})$ is the identity matrix with the four entries in rows and columns $i, j$ replaced by $\begin{pmatrix} g_{ii} & g_{ij} \\ g_{ji} & g_{jj} \end{pmatrix} = \begin{pmatrix} c & s \\ -s & c \end{pmatrix} .$

The two columns involved are orthonormal, since $c^2 + s^2 = 1$ and $cs - sc = 0$ , and every other column of $\mathbf{G}$ is a standard basis vector, orthogonal to both; so $\mathbf{G}^{\top}\mathbf{G} = \mathbf{I}_m$ and $\mathbf{G}$ is orthogonal, with $\det\mathbf{G} = c^2 + s^2 = 1$ by expansion along those other columns (Theorem 7.6.1). Moreover $\mathbf{G}$ acts as the identity on every coordinate other than $i$ and $j$ . Given a vector $\mathbf{v}$ with $(v_i, v_j) \neq (0,0)$ , set $r = \sqrt{v_i^2 + v_j^2}, \qquad c = \frac{v_i}{r}, \qquad s = \frac{v_j}{r} .$ Then the $i$ -th entry of $\mathbf{G}\mathbf{v}$ is $(v_i^2 + v_j^2)/r = r$ and the $j$ -th is $(-v_jv_i + v_iv_j)/r = 0$ , while every other entry is unchanged. One rotation, one new zero.

Here is one rotation at work. To clear the $(3,1)$ -entry of the matrix $\mathbf{A}$ below, take $i = 1$ , $j = 3$ and for $\mathbf{v}$ its first column, so that $(v_1, v_3) = (3, 4)$ and $r = 5$ , $c = \tfrac35$ , $s = \tfrac45$ . Then $\mathbf{G} = \mathbf{G}(1, 3; \tfrac35, \tfrac45)$ replaces row $1$ by $\tfrac35(\text{row } 1) + \tfrac45(\text{row } 3)$ and row $3$ by $-\tfrac45(\text{row } 1) + \tfrac35(\text{row } 3)$ , and leaves row $2$ alone: $\mathbf{A} = \begin{pmatrix} 3 & 5 & 0 \\ 0 & 2 & 1 \\ 4 & 0 & 5 \end{pmatrix}, \qquad \mathbf{G}\mathbf{A} = \begin{pmatrix} 5 & 3 & 4 \\ 0 & 2 & 1 \\ 0 & -4 & 3 \end{pmatrix} .$ The new $(1,1)$ -entry is $\tfrac15(3 \cdot 3 + 4 \cdot 4) = 5 = r$ and the new $(3,1)$ -entry is $\tfrac15(-4 \cdot 3 + 3 \cdot 4) = 0$ , as designed; the zero already sitting in position $(2,1)$ survives because row $2$ was never touched. A reflection would have flattened the whole first column in one step, at the price of rewriting row $2$ as well.

Applied in a suitable order, rotations triangularize any real matrix, which is a second proof of Theorem 11.8.4 over $\mathbb{R}$ at the cost of more steps: a full $m \times n$ matrix needs about $mn$ rotations where reflections need $n$ . For a nearly triangular matrix the count reverses, which is why the Hessenberg matrices below are handled with rotations in practice. Over $\mathbb{C}$ one takes $c \in \mathbb{R}$ , $s \in \mathbb{C}$ with $c^2 + \lvert s\rvert^2 = 1$ , and $-\overline{s}$ in place of $-s$ ; to zero the $j$ -th entry of $\mathbf{v}$ one puts $r = \sqrt{\lvert v_i\rvert^2 + \lvert v_j\rvert^2}$ and takes $c = \lvert v_i\rvert/r$ and $s = (v_i/\lvert v_i\rvert)\overline{v_j}/r$ when $v_i \neq 0$ , and $c = 0$ , $s = 1$ when $v_i = 0$ .

11.8.6. Hessenberg form

So far the unitary matrices acted on one side. A similarity needs both: to preserve eigenvalues we must pass from $\mathbf{A}$ to $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ , not to $\mathbf{Q}^{*}\mathbf{A}$ . What can reflections achieve under that constraint?

Not triangularity, and the reason is worth seeing before the theorem. Suppose we reflect so that the first column becomes $\rho\mathbf{e}_1$ . Multiplying on the right must not disturb column $1$ , so the right factor must fix $\mathbf{e}_1$ — and so must the left factor, since they are the same matrix. But a reflection fixing $\mathbf{e}_1$ acts only on the coordinates $2, \dots, n$ , so in column $1$ the best it can do is compress rows $2, \dots, n$ into row $2$ . The entry just below the diagonal survives, by necessity. That is exactly the pattern we can reach.

Theorem 11.8.5 (Reduction to Hessenberg Form)

Let $\mathbf{A} \in M_n(F)$ , $n \ge 1$ . Then there is a unitary $\mathbf{Q} \in M_n(F)$ such that $\mathbf{Z} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ is upper Hessenberg, that is, $z_{ij} = 0 \qquad \text{whenever } i > j + 1 .$ The matrix $\mathbf{Q}$ can be taken to be a product of $n - 2$ factors, each a Householder reflection or an identity matrix (and $\mathbf{Q} = \mathbf{I}_n$ when $n \le 2$ ). For $n = 4$ the pattern is $\mathbf{Z} = \begin{pmatrix} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ 0 & \ast & \ast & \ast \\ 0 & 0 & \ast & \ast \end{pmatrix}.$

Idea. Work column by column, as in Theorem 11.8.4, but apply each reflection on both sides. At step $k$ it is chosen to fix $\mathbf{e}_1, \dots, \mathbf{e}_k$ and to flatten the part of column $k$ in rows $k+1, \dots, n$ . Two observations do the bookkeeping. On the left it only recombines rows $k+1, \dots, n$ , and in the earlier columns those rows are already zero, so a combination of them is still zero. On the right it only recombines columns $k+1, \dots, n$ , so the columns already in shape are untouched.

Proof. For $0 \le k \le n-2$ say that $\mathbf{B} \in M_n(F)$ satisfies $(\ast_k)$ if $b_{ij} = 0$ whenever $j \le k$ and $i \ge j + 2$ . Every matrix satisfies $(\ast_0)$ vacuously, and $(\ast_{n-2})$ says precisely that $\mathbf{B}$ is upper Hessenberg, since the conditions with $j = n-1$ and $j = n$ are empty.

Put $\mathbf{A}_0 = \mathbf{A}$ . Let $1 \le k \le n - 2$ and suppose $\mathbf{A}_{k-1}$ satisfies $(\ast_{k-1})$ . Let $\mathbf{a} \in F^{n-k}$ be the vector of entries in rows $k+1, \dots, n$ of column $k$ of $\mathbf{A}_{k-1}$ . If $\mathbf{a} = \mathbf{0}$ , put $\mathbf{H}_k = \mathbf{I}_{n-k}$ ; otherwise let $\mathbf{H}_k \in M_{n-k}(F)$ be the reflection of Theorem 11.8.3 with $\mathbf{H}_k\mathbf{a} = \rho\mathbf{e}_1$ , where $\rho = -\alpha\left\| \mathbf{a} \right\|$ . Set $\mathbf{Q}_k = \begin{pmatrix} \mathbf{I}_k & \mathbf{0} \\ \mathbf{0} & \mathbf{H}_k\end{pmatrix} \in M_n(F), \qquad \mathbf{A}_k = \mathbf{Q}_k\mathbf{A}_{k-1}\mathbf{Q}_k .$ The block $\mathbf{H}_k$ is unitary and Hermitian with $\mathbf{H}_k^{-1} = \mathbf{H}_k$ — by Proposition 11.8.2 (a)–(c) for a reflection, and because $\mathbf{I}_{n-k}^{*} = \mathbf{I}_{n-k} = \mathbf{I}_{n-k}^{-1}$ otherwise — so by Theorem 8.1.1 $\mathbf{Q}_k$ is unitary and Hermitian with $\mathbf{Q}_k^{-1} = \mathbf{Q}_k$ , and $\mathbf{Q}_k\mathbf{e}_j = \mathbf{e}_j$ for every $j \le k$ .

Claim 1. $\mathbf{Q}_k\mathbf{A}_{k-1}$ satisfies $(\ast_{k-1})$ , and its entries in rows $i \ge k+2$ of column $k$ are $0$ .

Proof. By Theorem 8.1.1, the rows $1, \dots, k$ of $\mathbf{Q}_k\mathbf{A}_{k-1}$ are those of $\mathbf{A}_{k-1}$ , and each of the rows $k+1, \dots, n$ is a linear combination of the rows $k+1, \dots, n$ of $\mathbf{A}_{k-1}$ . Fix a column $j \le k - 1$ . By $(\ast_{k-1})$ , the entries of that column in rows $i \ge j+2$ vanish, and $k + 1 \ge j + 2$ , so all the entries being combined are $0$ and the combination is $0$ . Hence $(\ast_{k-1})$ survives. In column $k$ , the entries in rows $k+1, \dots, n$ form the vector $\mathbf{H}_k\mathbf{a} = \rho\mathbf{e}_1$ , whose entries after the first are $0$ ; these sit in rows $k+2, \dots, n$ .

Claim 2. $\mathbf{A}_k = (\mathbf{Q}_k\mathbf{A}_{k-1})\mathbf{Q}_k$ has the same first $k$ columns as $\mathbf{Q}_k\mathbf{A}_{k-1}$ .

Proof. For $j \le k$ , the $j$ -th column of $\mathbf{B}\mathbf{Q}_k$ is $\mathbf{B}(\mathbf{Q}_k\mathbf{e}_j) = \mathbf{B}\mathbf{e}_j$ , the $j$ -th column of $\mathbf{B}$ .

Combining the two claims, $\mathbf{A}_k$ satisfies $(\ast_k)$ : columns $1, \dots, k-1$ keep the zeros guaranteed by Claim 1, and column $k$ has zeros in rows $k+2, \dots, n$ , also by Claim 1, and both survive the right multiplication by Claim 2.

Running $k = 1, \dots, n-2$ produces $\mathbf{A}_{n-2}$ satisfying $(\ast_{n-2})$ , that is, upper Hessenberg. Put $\mathbf{Q} = \mathbf{Q}_1\mathbf{Q}_2\cdots\mathbf{Q}_{n-2}$ , unitary as a product of unitary matrices (Proposition 11.7.4). Since each $\mathbf{Q}_k^{*} = \mathbf{Q}_k$ , $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q} = \mathbf{Q}_{n-2}\cdots\mathbf{Q}_1\,\mathbf{A}\,\mathbf{Q}_1\cdots\mathbf{Q}_{n-2} = \mathbf{A}_{n-2},$ which proves the theorem. (For $n \le 2$ there are no steps and every matrix is already Hessenberg.)

Because $\mathbf{Q}^{-1} = \mathbf{Q}^{*}$ , the matrices $\mathbf{A}$ and $\mathbf{Z}$ are similar (Definition 4.2.2), so they share their characteristic polynomial, their eigenvalues and their trace. The reduction is not merely tidying: it removes $\binom{n-1}{2}$ entries and keeps the whole spectrum.

Example (Hessenberg form of a

3 \times 3

matrix)

Reduce $\mathbf{A} = \begin{pmatrix} 2 & 1 & 0 \\ 0 & 3 & 1 \\ 1 & 0 & 4 \end{pmatrix}$ to upper Hessenberg form by a unitary similarity.

Solution. Only $k = 1$ occurs, and only the entry $a_{31}$ has to be killed. The relevant vector is $\mathbf{a} = (a_{21}, a_{31}) = (0, 1) \in \mathbb{R}^2$ , with $\left\| \mathbf{a} \right\| = 1$ and $a_1 = 0$ , so $\alpha = 1$ and $\mathbf{w} = (0,1) + (1,0) = (1,1), \qquad \left\| \mathbf{w} \right\|^2 = 2 .$ Hence $\mathbf{H}_1 = \mathbf{I}_2 - \mathbf{w}\mathbf{w}^{\top} = \begin{pmatrix} 0 & -1 \\ -1 & 0\end{pmatrix}$ , and $\mathbf{Q}_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & -1 & 0\end{pmatrix}.$ Left multiplication by $\mathbf{Q}_1$ exchanges rows $2$ and $3$ and negates them, and right multiplication does the same to columns $2$ and $3$ : $\mathbf{Q}_1\mathbf{A} = \begin{pmatrix} 2 & 1 & 0 \\ -1 & 0 & -4 \\ 0 & -3 & -1\end{pmatrix}, \qquad \mathbf{Q}_1\mathbf{A}\mathbf{Q}_1 = \begin{pmatrix} 2 & 0 & -1 \\ -1 & 4 & 0 \\ 0 & 1 & 3\end{pmatrix} .$ Entry $(3,1)$ is $0$ and entry $(2,1)$ is $-1 = -\left\| \mathbf{a} \right\|$ , as Theorem 11.8.3 predicts. Watch column $1$ through the second multiplication: it is untouched, because $\mathbf{Q}_1\mathbf{e}_1 = \mathbf{e}_1$ . Both matrices have trace $9$ , as similarity requires.

Warning. Hessenberg form is not one small step from triangular form. A few more reflections will not clear the subdiagonal, and not merely because the argument above breaks. The diagonal of a triangular matrix similar to $\mathbf{A}$ lists the eigenvalues of $\mathbf{A}$ (Theorem 9.7.4), so a finite procedure using only arithmetic and square roots that always produced one would extract the roots of an arbitrary polynomial from its coefficients by those operations alone. No such procedure exists: from degree five on, the roots of a general polynomial cannot be written with arithmetic and radicals at all. That is a theorem of Abel and Ruffini, which this book does not prove and which nothing later depends on; we quote it only to explain why the algorithms of Chapter 24 iterate instead of terminating. Over $\mathbb{C}$ a triangularizing unitary does exist (Theorem 9.7.2); what does not exist is a finite algorithm of this kind producing it. Over $\mathbb{R}$ even the existence fails: a rotation in $\operatorname{O}(2)$ with no real eigenvalue is already Hessenberg and is orthogonally similar to no real triangular matrix.

Hessenberg form is where the practical computation of eigenvalues begins. One applies the reduction once, then iterates a cheap step that preserves the pattern: factor $\mathbf{Z} = \mathbf{Q}\mathbf{R}$ and replace $\mathbf{Z}$ by $\mathbf{R}\mathbf{Q} = \mathbf{Q}^{*}\mathbf{Z}\mathbf{Q}$ , again a unitary similarity. Chapter 24 develops that iteration and explains why every implementation starts with the reduction proved here.

Quick check. In the reduction of a $5 \times 5$ matrix, how many reflections are used, and how many entries does the second one set to zero?

Solution. Three, namely $k = 1, 2, 3$ . The step $k = 2$ chooses a reflection acting on the coordinates $3, 4, 5$ and sets the entries in rows $4$ and $5$ of column $2$ to zero: two entries. (Step $1$ sets three, step $3$ sets one, for $\binom{4}{2} = 6$ in total.)

11.8.7. Exercises

A. Check your understanding

Exercise (A1)

(a) State Theorem 11.8.1 in full, including the two normalizations that make $\mathbf{Q}$ and $\mathbf{R}$ unique.
(b) Which hypothesis on $\mathbf{A}$ does Theorem 11.8.1 need, and which does Theorem 11.8.4 need? Explain the difference in one sentence.
(c) Write down the Householder reflection determined by $\mathbf{w}$ , and list three of its properties.
(d) In Theorem 11.8.3, which of the two possible targets $\pm\left\| \mathbf{x} \right\|\mathbf{e}_1$ is chosen, and why?
(e) True or false: applying reflections on both sides, as in Theorem 11.8.5, can be pushed to make every complex matrix unitarily similar to an upper triangular one. Justify your answer.
(f) Why must the reflection used at step $k$ of Theorem 11.8.5 fix $\mathbf{e}_1, \dots, \mathbf{e}_k$ ?

Solution.

(a) If the columns of $\mathbf{A} \in M_{m\times n}(F)$ are independent, then $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{R}$ upper triangular; the normalizations are that the columns of $\mathbf{Q}$ are orthonormal and that the diagonal of $\mathbf{R}$ is positive real. With both, the pair is unique.
(b) Theorem 11.8.1 needs independent columns; Theorem 11.8.4 needs nothing. A positive diagonal forces $\mathbf{R}$ to be invertible and hence $\operatorname{rank}\mathbf{A} = n$ , while the reflection route is content to put a zero on the diagonal where a dependence occurs.
(c) $\mathbf{H}_{\mathbf{w}} = \mathbf{I}_m - 2\mathbf{w}\mathbf{w}^{*}/\left\| \mathbf{w} \right\|^2$ (Definition 11.8.1); it is Hermitian, unitary, equal to its own inverse, and has determinant $-1$ (Proposition 11.8.2).
(d) The target $-\alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ , where $\alpha$ is the phase (over $\mathbb{R}$ , the sign) of $x_1$ — that is, the target on the opposite side from $x_1$ . The reason is arithmetic: this makes the first entry of $\mathbf{w} = \mathbf{x} + \alpha\left\| \mathbf{x} \right\|\mathbf{e}_1$ a sum of like-signed quantities, with no cancellation of leading digits.
(e) False. A reflection preserving the zeros already created must fix $\mathbf{e}_1, \dots, \mathbf{e}_k$ , and then it cannot touch the entry in row $k+1$ of column $k$ . More decisively, such a finite procedure would compute the roots of an arbitrary polynomial by arithmetic and square roots alone, which the theorem of Abel and Ruffini quoted in the warning rules out.
(f) Because the same matrix multiplies on the right, and right multiplication by $\mathbf{Q}_k$ changes column $j$ only if $\mathbf{Q}_k\mathbf{e}_j \neq \mathbf{e}_j$ . Fixing $\mathbf{e}_1, \dots, \mathbf{e}_k$ is exactly what leaves columns $1, \dots, k$ , and the zeros in them, alone.

B. Practice

Exercise (B1: QR by Gram–Schmidt)

Find the QR factorization of $\mathbf{A} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ in the sense of Theorem 11.8.1, and verify that $\mathbf{R} = \mathbf{Q}^{\top}\mathbf{A}$ for the top-left $2 \times 2$ entries.

Solution. Step 1. $\mathbf{a}_1 = (1,1,1)$ has $\left\| \mathbf{a}_1 \right\| = \sqrt3$ , so $r_{11} = \sqrt3$ and $\mathbf{q}_1 = \tfrac{1}{\sqrt3}(1,1,1)$ .

Step 2. $r_{12} = \langle \mathbf{a}_2, \mathbf{q}_1 \rangle = \tfrac{2}{\sqrt3}$ , so $\mathbf{w}_2 = (1,1,0) - \tfrac23(1,1,1) = \tfrac13(1,1,-2),$ with $\left\| \mathbf{w}_2 \right\|^2 = \tfrac19 \cdot 6 = \tfrac23$ . Hence $r_{22} = \sqrt{2/3}$ and $\mathbf{q}_2 = \tfrac{1}{\sqrt6}(1,1,-2)$ .

Step 3. $r_{13} = \langle \mathbf{a}_3, \mathbf{q}_1 \rangle = \tfrac{1}{\sqrt3}$ and $r_{23} = \langle \mathbf{a}_3, \mathbf{q}_2 \rangle = \tfrac{1}{\sqrt6}$ , so $\mathbf{w}_3 = (1,0,0) - \tfrac13(1,1,1) - \tfrac16(1,1,-2) = \big(\tfrac12, -\tfrac12, 0\big),$ with $\left\| \mathbf{w}_3 \right\| = \tfrac{1}{\sqrt2} = r_{33}$ and $\mathbf{q}_3 = \tfrac{1}{\sqrt2}(1,-1,0)$ . Therefore $\mathbf{Q} = \begin{pmatrix} \tfrac{1}{\sqrt3} & \tfrac{1}{\sqrt6} & \tfrac{1}{\sqrt2} \\[2pt] \tfrac{1}{\sqrt3} & \tfrac{1}{\sqrt6} & -\tfrac{1}{\sqrt2} \\[2pt] \tfrac{1}{\sqrt3} & -\tfrac{2}{\sqrt6} & 0 \end{pmatrix}, \qquad \mathbf{R} = \begin{pmatrix} \sqrt3 & \tfrac{2}{\sqrt3} & \tfrac{1}{\sqrt3} \\[2pt] 0 & \tfrac{2}{\sqrt6} & \tfrac{1}{\sqrt6} \\[2pt] 0 & 0 & \tfrac{1}{\sqrt2} \end{pmatrix},$ where $r_{22} = \sqrt{2/3} = 2/\sqrt6$ . All three diagonal entries are positive, as required.

For the verification, $(\mathbf{Q}^{\top}\mathbf{A})_{11} = \langle \mathbf{a}_1, \mathbf{q}_1 \rangle = 3/\sqrt3 = \sqrt3 = r_{11}$ and $(\mathbf{Q}^{\top}\mathbf{A})_{12} = \langle \mathbf{a}_2, \mathbf{q}_1 \rangle = 2/\sqrt3 = r_{12}$ ; also $(\mathbf{Q}^{\top}\mathbf{A})_{21} = \langle \mathbf{a}_1, \mathbf{q}_2 \rangle = (1 + 1 - 2)/\sqrt6 = 0 = r_{21}$ and $(\mathbf{Q}^{\top}\mathbf{A})_{22} = \langle \mathbf{a}_2, \mathbf{q}_2 \rangle = 2/\sqrt6 = r_{22}$ .

Exercise (B2: The same matrix by reflections)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 2 & 3\end{pmatrix}$ , the matrix of Example (A $3 \times 2$ QR, and a least-squares problem).

(a) Find $\mathbf{w}_1$ and the reflection $\mathbf{H}_1$ of Theorem 11.8.3 for the first column of $\mathbf{A}$ , and compute $\mathbf{H}_1\mathbf{A}$ .
(b) Find the second reflection and hence a factorization $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{Q} \in M_3(\mathbb{R})$ orthogonal and $\mathbf{R} \in M_{3\times2}(\mathbb{R})$ upper triangular.
(c) Compare the $\mathbf{R}$ of (b) with the $\mathbf{R}$ of Example (A $3 \times 2$ QR, and a least-squares problem), and say exactly how the two factorizations differ.

Solution.

(a) The first column is $\mathbf{a} = (1,2,2)$ with $\left\| \mathbf{a} \right\| = 3$ and $a_1 = 1 > 0$ , so $\alpha = 1$ and $\mathbf{w}_1 = (1,2,2) + 3\mathbf{e}_1 = (4,2,2)$ , with $\left\| \mathbf{w}_1 \right\|^2 = 24$ . By $(\ddagger)$ , $\mathbf{H}_1\mathbf{v} = \mathbf{v} - \tfrac{1}{12}\langle \mathbf{v}, \mathbf{w}_1 \rangle\mathbf{w}_1$ . Since $\langle \mathbf{a}, \mathbf{w}_1 \rangle = 4 + 4 + 4 = 12$ and $\langle (1,1,3), \mathbf{w}_1 \rangle = 4 + 2 + 6 = 12$ , each column loses one copy of $\mathbf{w}_1$ : $\mathbf{H}_1\mathbf{A} = \begin{pmatrix} -3 & -3 \\ 0 & -1 \\ 0 & 1 \end{pmatrix}.$
(b) The trailing vector is $\mathbf{y} = (-1, 1)$ , with $\left\| \mathbf{y} \right\| = \sqrt2$ and $y_1 = -1 < 0$ , so $\alpha = -1$ and $\mathbf{w}_2 = (-1,1) - \sqrt2(1,0) = (-1-\sqrt2,\,1)$ . By Theorem 11.8.3, the reflection sends $\mathbf{y}$ to $+\sqrt2\,\mathbf{e}_1$ . Embedding it as $\mathbf{H}_2 = \mathbf{I}_1 \oplus \mathbf{H}_{\mathbf{w}_2}$ , we get $\mathbf{R} = \mathbf{H}_2\mathbf{H}_1\mathbf{A} = \begin{pmatrix} -3 & -3 \\ 0 & \sqrt2 \\ 0 & 0\end{pmatrix}, \qquad \mathbf{Q} = \mathbf{H}_1\mathbf{H}_2 ,$ and $\mathbf{A} = \mathbf{Q}\mathbf{R}$ because each $\mathbf{H}_i$ is its own inverse (Proposition 11.8.2 (b)).
(c) In Example (A $3 \times 2$ QR, and a least-squares problem), $\mathbf{R}_0 = \begin{pmatrix} 3 & 3 \\ 0 & \sqrt2\end{pmatrix}$ . Deleting the zero row of $\mathbf{R}$ leaves $\mathbf{R}_0$ with its first row negated, and correspondingly the first column of $\mathbf{Q}$ is $-\mathbf{q}_1$ while the second is $\mathbf{q}_2$ . The reflection route did not aim for a positive diagonal, and by the uniqueness in Theorem 11.8.1 signs are the only discrepancy possible.

Exercise (B3: A least-squares fit through QR)

Fit a line $y = c_0 + c_1t$ to the data $(t, y) = (0,1), (1,3), (2,2)$ in the least-squares sense, by finding the QR factorization of the design matrix and solving $\mathbf{R}\mathbf{x} = \mathbf{Q}^{\top}\mathbf{b}$ . Compute the residual and check the answer against the normal equations.

Solution. The system is $\mathbf{A}\mathbf{x} = \mathbf{b}$ with $\mathbf{A} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2\end{pmatrix}, \qquad \mathbf{b} = \begin{pmatrix} 1 \\ 3 \\ 2 \end{pmatrix}, \qquad \mathbf{x} = (c_0, c_1).$ Gram–Schmidt: $\left\| \mathbf{a}_1 \right\| = \sqrt3$ , so $r_{11} = \sqrt3$ and $\mathbf{q}_1 = \tfrac{1}{\sqrt3}(1,1,1)$ . Then $r_{12} = \langle \mathbf{a}_2, \mathbf{q}_1 \rangle = 3/\sqrt3 = \sqrt3$ and $\mathbf{w}_2 = (0,1,2) - (1,1,1) = (-1,0,1),$ so $r_{22} = \sqrt2$ and $\mathbf{q}_2 = \tfrac{1}{\sqrt2}(-1,0,1)$ . Now $\langle \mathbf{b}, \mathbf{q}_1 \rangle = 6/\sqrt3 = 2\sqrt3$ and $\langle \mathbf{b}, \mathbf{q}_2 \rangle = (-1 + 0 + 2)/\sqrt2 = 1/\sqrt2$ , so $(\dagger)$ reads $\begin{pmatrix} \sqrt3 & \sqrt3 \\ 0 & \sqrt2 \end{pmatrix}\mathbf{x} = \begin{pmatrix} 2\sqrt3 \\ 1/\sqrt2\end{pmatrix}.$ Back substitution gives $c_1 = \tfrac12$ and then $\sqrt3(c_0 + \tfrac12) = 2\sqrt3$ , so $c_0 = \tfrac32$ . The fitted line is $y = \tfrac32 + \tfrac12 t$ , with residual $\mathbf{A}\mathbf{x} - \mathbf{b} = (\tfrac12, -1, \tfrac12)$ and $\left\| \mathbf{A}\mathbf{x} - \mathbf{b} \right\|^2 = \tfrac32$ .

Check. $\mathbf{A}^{\top}\mathbf{A} = \begin{pmatrix} 3 & 3 \\ 3 & 5\end{pmatrix}$ and $\mathbf{A}^{\top}\mathbf{b} = (6, 7)$ . Subtracting the first normal equation from the second gives $2c_1 = 1$ , and then $3c_0 + \tfrac32 = 6$ , so $c_0 = \tfrac32$ . The residual is orthogonal to both columns of $\mathbf{A}$ : $\tfrac12 - 1 + \tfrac12 = 0$ and $0 \cdot \tfrac12 - 1 \cdot 1 + 2 \cdot \tfrac12 = 0$ , which is what the normal equations of Theorem 11.4.2 say.

Exercise (B4: Determine which are QR factorizations)

Determine which of the following are QR factorizations of the matrix on the left in the sense of Theorem 11.8.1. Justify your answer; for those that are not, name the clause that fails and repair it if possible.

(a) $\begin{pmatrix} 3 & 1 \\ 4 & 7\end{pmatrix} = \tfrac15\begin{pmatrix} 3 & -4 \\ 4 & 3\end{pmatrix}\begin{pmatrix} 5 & \tfrac{31}{5} \\ 0 & \tfrac{17}{5}\end{pmatrix}$ .
(b) $\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} = \begin{pmatrix} 1 & -1 \\ 1 & 1\end{pmatrix}\begin{pmatrix} 1 & \tfrac12 \\ 0 & \tfrac12\end{pmatrix}$ .
(c) $\begin{pmatrix} -1 & 0 \\ 0 & 1\end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}\begin{pmatrix} -1 & 0 \\ 0 & 1\end{pmatrix}$ .

Solution.

(a) Yes. The product is $\tfrac15\begin{pmatrix} 15 & \tfrac{93}{5} - \tfrac{68}{5} \\ 20 & \tfrac{124}{5} + \tfrac{51}{5}\end{pmatrix} = \tfrac15\begin{pmatrix} 15 & 5 \\ 20 & 35\end{pmatrix} = \begin{pmatrix} 3 & 1 \\ 4 & 7\end{pmatrix},$ the columns of the left factor are $\tfrac15(3,4)$ and $\tfrac15(-4,3)$ , both of length $1$ and orthogonal, and the diagonal entries $5$ and $\tfrac{17}{5}$ are positive. All three clauses hold, so by the uniqueness in Theorem 11.8.1 this is the QR factorization.
(b) No. The identity is correct, and $\mathbf{R}$ is upper triangular with positive diagonal, but the columns of the left factor have length $\sqrt2$ , not $1$ , so clause (a) of Theorem 11.8.1 fails. Repair it by dividing each column of $\mathbf{Q}$ by $\sqrt2$ and multiplying the matching row of $\mathbf{R}$ by $\sqrt2$ : $\mathbf{Q} = \tfrac{1}{\sqrt2}\begin{pmatrix} 1 & -1 \\ 1 & 1\end{pmatrix}, \qquad \mathbf{R} = \begin{pmatrix} \sqrt2 & \tfrac{1}{\sqrt2} \\ 0 & \tfrac{1}{\sqrt2}\end{pmatrix}.$
(c) No. The identity is correct and the columns of $\mathbf{Q} = \mathbf{I}_2$ are orthonormal, but $r_{11} = -1 < 0$ , so clause (b) fails. Repair it by moving the sign across: $\mathbf{Q} = \operatorname{diag}(-1, 1)$ , whose columns are still orthonormal, and $\mathbf{R} = \mathbf{I}_2$ , whose diagonal is positive. This is the move described in Exercise (C1: All the QR factorizations of a matrix) with $\mathbf{D} = \operatorname{diag}(-1,1)$ .

C. Going deeper

Exercise (C1: All the QR factorizations of a matrix)

Let $\mathbf{A} \in M_{m\times n}(F)$ have independent columns, with QR factorization $\mathbf{A} = \mathbf{Q}\mathbf{R}$ as in Theorem 11.8.1.

(a) Prove that an upper triangular $\mathbf{S} \in M_n(F)$ with $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n$ is diagonal, with diagonal entries of modulus $1$ .
(b) Deduce that the pairs $(\mathbf{Q}_1, \mathbf{R}_1)$ with $\mathbf{Q}_1^{*}\mathbf{Q}_1 = \mathbf{I}_n$ , $\mathbf{R}_1$ upper triangular and invertible, and $\mathbf{A} = \mathbf{Q}_1\mathbf{R}_1$ , are exactly the pairs $(\mathbf{Q}\mathbf{D}^{-1}, \mathbf{D}\mathbf{R})$ for $\mathbf{D} = \operatorname{diag}(d_1, \dots, d_n)$ with $\lvert d_k\rvert = 1$ .
(c) Hence give a second proof of the uniqueness statement of Theorem 11.8.1.

Solution.

(a) Let $\mathbf{s}_1, \dots, \mathbf{s}_n$ be the columns of $\mathbf{S}$ ; as in the proof of Theorem 11.8.1, $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n$ says $\langle \mathbf{s}_j, \mathbf{s}_i \rangle = \delta_{ij}$ . We show $\mathbf{s}_j = s_{jj}\mathbf{e}_j$ with $\lvert s_{jj}\rvert = 1$ , by induction on $j$ . Suppose this holds for every $i < j$ . For such $i$ , $0 = \langle \mathbf{s}_j, \mathbf{s}_i \rangle = \overline{s_{ii}}\langle \mathbf{s}_j, \mathbf{e}_i \rangle = \overline{s_{ii}}\,s_{ij},$ and $s_{ii} \ne 0$ , so $s_{ij} = 0$ . Together with upper triangularity this gives $\mathbf{s}_j = s_{jj}\mathbf{e}_j$ , and $\left\| \mathbf{s}_j \right\| = 1$ gives $\lvert s_{jj}\rvert = 1$ .
(b) $(\Leftarrow)$ If $\lvert d_k\rvert = 1$ for all $k$ , then $\mathbf{D}^{*}\mathbf{D} = \mathbf{I}_n$ , so $(\mathbf{Q}\mathbf{D}^{-1})^{*}(\mathbf{Q}\mathbf{D}^{-1}) = (\mathbf{D}^{-1})^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{D}^{-1} = (\mathbf{D}\mathbf{D}^{*})^{-1} = \mathbf{I}_n$ ; the matrix $\mathbf{D}\mathbf{R}$ is upper triangular and invertible; and $(\mathbf{Q}\mathbf{D}^{-1})(\mathbf{D}\mathbf{R}) = \mathbf{Q}\mathbf{R} = \mathbf{A}$ .

$(\Rightarrow)$ Suppose $\mathbf{A} = \mathbf{Q}_1\mathbf{R}_1$ as stated. Exactly as in the proof of Theorem 11.8.1, $\mathbf{R}_1^{*}\mathbf{R}_1 = \mathbf{A}^{*}\mathbf{A} = \mathbf{R}^{*}\mathbf{R}$ , and $\mathbf{S} = \mathbf{R}_1\mathbf{R}^{-1}$ is upper triangular with $\mathbf{S}^{*}\mathbf{S} = \mathbf{I}_n$ . By (a), $\mathbf{S} = \mathbf{D}$ is diagonal with $\lvert d_k\rvert = 1$ . Then $\mathbf{R}_1 = \mathbf{D}\mathbf{R}$ and $\mathbf{Q}_1 = \mathbf{A}\mathbf{R}_1^{-1} = \mathbf{Q}\mathbf{R}\mathbf{R}^{-1}\mathbf{D}^{-1} = \mathbf{Q}\mathbf{D}^{-1}$ .
(c) If in addition both $\mathbf{R}$ and $\mathbf{R}_1 = \mathbf{D}\mathbf{R}$ have positive real diagonal entries, then $d_k = (\mathbf{R}_1)_{kk}/(\mathbf{R})_{kk}$ is a positive real number of modulus $1$ , so $d_k = 1$ for every $k$ . Hence $\mathbf{D} = \mathbf{I}_n$ , $\mathbf{R}_1 = \mathbf{R}$ and $\mathbf{Q}_1 = \mathbf{Q}$ .

Exercise (C2: Reflections do not mind dependence)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 & 2 \\ 2 & 1 & 3 \\ 2 & 3 & 5 \end{pmatrix},$ whose third column is the sum of the first two.

(a) Run the Gram–Schmidt process of Theorem 11.2.2 on the columns of $\mathbf{A}$ and say precisely which step fails.
(b) Carry out the Householder reduction of Theorem 11.8.4 on $\mathbf{A}$ and exhibit $\mathbf{R}$ .
(c) Explain, using Theorem 11.8.1, why no factorization $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_3$ and $\mathbf{R}$ upper triangular with positive diagonal can exist.

Solution.

(a) Steps $1$ and $2$ go through: $\mathbf{q}_1 = \tfrac13(1,2,2)$ and, since $\langle \mathbf{a}_2, \mathbf{q}_1 \rangle = \tfrac13(1 + 2 + 6) = 3$ , $\mathbf{w}_2 = (1,1,3) - (1,2,2) = (0,-1,1)$ and $\mathbf{q}_2 = \tfrac{1}{\sqrt2}(0,-1,1)$ . At step $3$ , $\mathbf{a}_3 = \mathbf{a}_1 + \mathbf{a}_2$ lies in $\operatorname{span}(\mathbf{a}_1,\mathbf{a}_2) = \operatorname{span}(\mathbf{q}_1,\mathbf{q}_2)$ , so by Theorem 11.2.1 (a) the vector subtracted from $\mathbf{a}_3$ is $\mathbf{a}_3$ itself and $\mathbf{w}_3 = \mathbf{0}$ . The normalization $\mathbf{q}_3 = \mathbf{w}_3/\left\| \mathbf{w}_3 \right\|$ divides by $0$ and fails. This is the situation of Exercise (C2: Gram–Schmidt on a dependent list).
(b) The first column is $(1,2,2)$ , so as in Exercise (B2: The same matrix by reflections) we take $\mathbf{w}_1 = (4,2,2)$ with $\left\| \mathbf{w}_1 \right\|^2 = 24$ , and $\mathbf{H}_1\mathbf{v} = \mathbf{v} - \tfrac{1}{12}\langle \mathbf{v}, \mathbf{w}_1 \rangle\mathbf{w}_1$ . The inner products of the three columns with $\mathbf{w}_1$ are $12$ , $12$ and $24$ , so $\mathbf{H}_1\mathbf{A} = \begin{pmatrix} -3 & -3 & -6 \\ 0 & -1 & -1 \\ 0 & 1 & 1\end{pmatrix}.$ The trailing vector of column $2$ is $(-1,1)$ , which by Exercise (B2: The same matrix by reflections) (b) the second reflection sends to $\sqrt2\,\mathbf{e}_1$ ; it sends the trailing vector of column $3$ , which is the same vector $(-1,1)$ , to the same place. Hence $\mathbf{R} = \begin{pmatrix} -3 & -3 & -6 \\ 0 & \sqrt2 & \sqrt2 \\ 0 & 0 & 0 \end{pmatrix},$ upper triangular, with a zero in position $(3,3)$ exactly where the dependence sits. No step of the algorithm divided by zero.
(c) Such an $\mathbf{R}$ would be invertible by Lemma 3.6.2, so $\operatorname{rank}\mathbf{A} = \operatorname{rank}(\mathbf{Q}\mathbf{R}) = \operatorname{rank}\mathbf{Q} = 3$ . But $\mathbf{a}_3 = \mathbf{a}_1 + \mathbf{a}_2$ , so the columns are dependent and $\operatorname{rank}\mathbf{A} \le 2$ , a contradiction. The positive-diagonal factorization exists precisely for matrices of full column rank.

Exercise (C3: Triangularizing with rotations)

(a) Let $(a, b) \in \mathbb{R}^2$ be non-zero and $r = \sqrt{a^2+b^2}$ . Verify that the Givens rotation $\mathbf{G}$ of Definition 11.8.2 with $c = a/r$ and $s = b/r$ satisfies $\mathbf{G}(a,b) = (r, 0)$ , and that $\mathbf{G} \in \operatorname{SO}(2)$ .
(b) Use (a) to write $\mathbf{A} = \begin{pmatrix} 3 & 1 \\ 4 & 2\end{pmatrix}$ as $\mathbf{Q}\mathbf{R}$ with $\mathbf{Q} \in \operatorname{SO}(2)$ and $\mathbf{R}$ upper triangular with positive diagonal.
(c) How many Givens rotations does it take to triangularize a general $3\times3$ real matrix, and which entries does each one kill? Compare with the number of Householder reflections.

Solution.

(a) $\mathbf{G}(a,b) = (ca + sb,\ -sa + cb) = \big((a^2+b^2)/r,\ (-ab+ab)/r\big) = (r, 0)$ . Also $c^2 + s^2 = 1$ , so the columns of $\mathbf{G}$ are orthonormal and $\det\mathbf{G} = c^2 + s^2 = 1$ ; hence $\mathbf{G} \in \operatorname{SO}(2)$ .
(b) The first column is $(3,4)$ , so $r = 5$ , $c = \tfrac35$ , $s = \tfrac45$ and $\mathbf{G} = \tfrac15\begin{pmatrix} 3 & 4 \\ -4 & 3\end{pmatrix}$ . Then $\mathbf{G}\mathbf{A} = \tfrac15\begin{pmatrix} 9 + 16 & 3 + 8 \\ -12 + 12 & -4 + 6 \end{pmatrix} = \begin{pmatrix} 5 & \tfrac{11}{5} \\ 0 & \tfrac25 \end{pmatrix} =: \mathbf{R} ,$ whose diagonal entries $5$ and $\tfrac25$ are positive. Since $\mathbf{G}^{-1} = \mathbf{G}^{\top} \in \operatorname{SO}(2)$ , we get $\mathbf{A} = \mathbf{Q}\mathbf{R}$ with $\mathbf{Q} = \mathbf{G}^{\top} = \tfrac15\begin{pmatrix} 3 & -4 \\ 4 & 3\end{pmatrix}$ . As a check, $\det\mathbf{A} = 2 = 5 \cdot \tfrac25 = \det\mathbf{R}$ .
(c) Three: one for $a_{21}$ (rows $1, 2$ ), one for $a_{31}$ (rows $1, 3$ ), and one for the new $(3,2)$ -entry (rows $2, 3$ ). The last acts on rows $2$ and $3$ , which by then have zeros in column $1$ , so it does not undo the earlier work. Householder needs two reflections, one per column, since each clears a whole column at once.