isometries-householder-qr · Matrix Theory

Exercise.standardBeyond 21-242 Let

𝐴 = (\begin{matrix} 2 & 15 \\ 1 & 0 \\ 2 & - 6 \end{matrix})

. Using two Householder reflections, find an orthogonal

𝑄 \in ℝ^{3 \times 3}

and an upper triangular

𝑅_{0} \in ℝ^{3 \times 2}

with

𝐴 = 𝑄 𝑅_{0}

, and read off the QR factorization of Theorem 6.4.38.

Solution.

Uses. Proposition 8.4.21 (A reflection exchanging two vectors), Example 8.4.20 (Householder reflections), Theorem 6.4.38 (QR factorization)

Hint 1. First map the first column

(2, 1, 2)

(3, 0, 0)

(Exercise 8.4.22).

Hint 2. Then apply a

2 \times 2

reflection to the lower part of the second column, inside

diag (1, 𝐻^{'})

Sketch.

𝐻_{1} =

\frac{1}{3} (\begin{matrix} 2 & 1 & 2 \\ 1 & 2 & - 2 \\ 2 & - 2 & - 1 \end{matrix})

gives

𝐻_{1} 𝐴 = (\begin{matrix} 3 & 6 \\ 0 & 9 \\ 0 & 12 \end{matrix})

𝐻^{'} = \frac{1}{5} (\begin{matrix} 3 & 4 \\ 4 & - 3 \end{matrix})

maps

(9, 12)

(15, 0)

, so

𝐻_{2} = diag (1, 𝐻^{'})

gives

𝐻_{2} 𝐻_{1} 𝐴 =

(\begin{matrix} 3 & 6 \\ 0 & 15 \\ 0 & 0 \end{matrix})

𝑄 = 𝐻_{1} 𝐻_{2}

, and

𝐴 = 𝑄_{1} 𝑅

with

𝑅 = (\begin{matrix} 3 & 6 \\ 0 & 15 \end{matrix})

and

𝑄_{1}

the first two columns of

𝑄

The first column $(2, 1, 2)$ has length $3$ . By Exercise 8.4.22, $𝐻_{1} =$ $\frac{1}{3} (\begin{matrix} 2 & 1 & 2 \\ 1 & 2 & - 2 \\ 2 & - 2 & - 1 \end{matrix})$ maps it to $(3, 0, 0)$ , and

𝐻_{1} (\begin{matrix} 15 \\ 0 \\ - 6 \end{matrix}) = \frac{1}{3} (\begin{matrix} 30 - 12 \\ 15 + 12 \\ 30 + 6 \end{matrix}) = (\begin{matrix} 6 \\ 9 \\ 12 \end{matrix}), so 𝐻_{1} 𝐴 = (\begin{matrix} 3 & 6 \\ 0 & 9 \\ 0 & 12 \end{matrix}) .

The vector $(9, 12)$ has length $15$ ; Proposition 8.4.21 with $𝐝 =$ $(9, 12) -$ $(15, 0) =$ $(- 6, 12)$ , parallel to $(- 1, 2)$ , gives $𝐻^{'} =$ $𝐼_{2} -$ $\frac{2}{5} (\begin{matrix} 1 & - 2 \\ - 2 & 4 \end{matrix}) =$ $\frac{1}{5} (\begin{matrix} 3 & 4 \\ 4 & - 3 \end{matrix})$ with $𝐻^{'} (9, 12) = (15, 0)$ . Let $𝐻_{2} = diag (1, 𝐻^{'})$ , also a Householder reflection (with $𝐮 = (0, - 1, 2) / \sqrt{5}$ ). Then

𝐻_{2} 𝐻_{1} 𝐴 = (\begin{matrix} 3 & 6 \\ 0 & 15 \\ 0 & 0 \end{matrix}) = 𝑅_{0} .

Since $𝐻_{1}, 𝐻_{2}$ are orthogonal and their own inverses, $𝐴 = 𝑄 𝑅_{0}$ with $𝑄 = 𝐻_{1} 𝐻_{2}$ . Only the first two columns $𝑄_{1}$ of $𝑄$ meet the nonzero rows of $𝑅_{0}$ , so $𝐴 = 𝑄_{1} 𝑅$ with $𝑅 = (\begin{matrix} 3 & 6 \\ 0 & 15 \end{matrix})$ and

𝑄_{1} = 𝐻_{1} (\begin{matrix} 1 & 0 \\ 0 & 3 / 5 \\ 0 & 4 / 5 \end{matrix}) = \frac{1}{15} (\begin{matrix} 10 & 11 \\ 5 & - 2 \\ 10 & - 10 \end{matrix}) .

$𝑅$ has positive diagonal, so by uniqueness this is the factorization of Theorem 6.4.38. Check: $𝑄_{1} 𝑅$ has second column $\frac{1}{15} (60 + 165, 30 - 30, 60 - 150) =$ $(15, 0, - 6)$ .