6.6. Matrix decomposition exercises#
Exercise 6.1
Solve the following system of linear equations using LU decomposition.
\[\begin{split}\begin{align*}
2 x_1 + 3 x_2 - x_3 &= 4,\\
4 x_1 + 9 x_2 - x_3 &= 18,\\
3 x_2 + 2 x_3 &= 11.
\end{align*} \end{split}\]
Solution
The coefficient matrix is
\[\begin{split} A = \begin{pmatrix} 2 & 3 & -1 \\ 4 & 9 & -1 \\ 0 & 3 & 2 \end{pmatrix}. \end{split}\]
Compute the LU decomposition of \(A\)
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 2, \\
&& \ell_{21} &= \frac{1}{u_{11}}a_{21} = \frac{1}{2}(4) = 2, \\
&& \ell_{31} &= \frac{1}{u_{11}}a_{31} = \frac{1}{2}(0) = 0, \\
j &= 2: & u_{12} &= a_{12} = 3, \\
&& u_{22} &= a_{22} - \ell_{21}u_{12} = 9 - 2(3) = 3, \\
&& \ell_{32} &= \frac{1}{u_{22}}(a_{32} - \ell_{31}u_{12}) = \frac{1}{3}(3 - 0(3)) = 1, \\
j &= 3: & u_{13} &= a_{13} = -1, \\
&& u_{23} &= a_{23} - \ell_{21}u_{13} = -1 - 2(-1) = 1, \\
&& u_{33} &= a_{33} - \ell_{31}u_{13} - \ell_{32}u_{23} = 2 - 0(-1) - 1(1) = 1,
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
L &= \begin{pmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix}, &
U &= \begin{pmatrix}
2 & 3 & -1 \\
0 & 3 & 1 \\
0 & 0 & 1
\end{pmatrix}.
\end{align*} \end{split}\]
Solving \(L \mathbf{y} = \mathbf{b}\) using forward substitution
\[\begin{split} \begin{align*}
\begin{pmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix}
\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}
=
\begin{pmatrix} 4 \\ 18 \\ 11 \end{pmatrix}
\quad \implies \quad
\begin{aligned}
y_1 &= 4, \\
y_2 &= 18 - 2(4) = 10, \\
y_3 &= 11 - 10 = 1.
\end{aligned}
\end{align*} \end{split}\]
Solving \(U \mathbf{x} = \mathbf{y}\) using back substitution
\[\begin{split} \begin{align*}
\begin{pmatrix}
2 & 3 & -1 \\
0 & 3 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}
=
\begin{pmatrix} 4 \\ 10 \\ 1 \end{pmatrix}
\quad \implies \quad
\begin{aligned}
x_3 &= 1, \\
x_2 &= \frac{1}{3}(10 - 1) = 3, \\
x_1 &= \frac{1}{2}(4 - 3(3) + 1) = -2.
\end{aligned}
\end{align*} \end{split}\]
Exercise 6.2
Solve the following system of linear equations using LU decomposition with partial pivoting.
\[\begin{split} \begin{align*}
x_1 + 3x_2 + 2x_3 &= 16, \\
2x_1 + x_2 &= 0, \\
3x_1 + x_2 - x_3 &= -5.
\end{align*} \end{split}\]
Solution
The coefficient matrix is
\[\begin{split} A = \begin{pmatrix} 1 & 3 & 2 \\ 2 & 1 & 0 \\ 3 & 1 & -1 \end{pmatrix}.\end{split}\]
Performing partial pivoting on \(A\)
\[\begin{split} \begin{align*}
& \begin{pmatrix}
1 & 3 & 2 \\
2 & 1 & 0 \\
3 & 1 & -1
\end{pmatrix}
\begin{matrix} R_1 \leftrightarrow R_3 \\ \phantom{x} \\ \phantom{x} \end{matrix} &
\longrightarrow
& \begin{pmatrix}
3 & 1 & -1 \\
2 & 1 & 0 \\
1 & 3 & 2
\end{pmatrix}
\begin{matrix} \\ R_2 \leftrightarrow R_3 \\ \phantom{x} \end{matrix} \\ \\
\longrightarrow
& \begin{pmatrix}
3 & 1 & -1 \\
1 & 3 & 2 \\
2 & 1 & 0
\end{pmatrix} = PA.
\end{align*} \end{split}\]
So the permutation matrix is
\[\begin{split} \begin{align*}
& \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
\begin{matrix} R_1 \leftrightarrow R_3 \\ \phantom{x} \\ \phantom{x} \end{matrix} &
\longrightarrow
& \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}
\begin{matrix} \\ R_2 \leftrightarrow R_3 \\ \phantom{x} \end{matrix} \\ \\
\longrightarrow
& \begin{pmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix} = P.
\end{align*} \end{split}\]
Computing the LU decomposition of \(PA\)
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 3, \\
&& \ell_{21} &= \frac{1}{u_{11}}a_{21} = \frac{1}{3}(1) = \frac{1}{3}, \\
&& \ell_{31} &= \frac{1}{u_{11}}a_{31} = \frac{1}{3}(2) = \frac{2}{3}, \\
j &= 2: & u_{12} &= a_{12} = 1, \\
&& u_{22} &= a_{22} - \ell_{21}u_{12} = 3 - \frac{1}{3}(1) = \frac{8}{3}, \\
&& \ell_{32} &= \frac{1}{u_{22}}(a_{32} - \ell_{31}u_{12}) = \frac{3}{8}\left(1 - \frac{2}{3}(1)\right) = \frac{1}{8}, \\
j &= 3: & u_{13} &= a_{13} = -1, \\
&& u_{23} &= a_{23} - \ell_{21}u_{13} = 2 - \frac{1}{3}(-1) = \frac{7}{3}, \\
&& u_{33} &= a_{33} - \ell_{31}u_{13} - \ell_{32}u_{23} = 0 - \frac{2}{3}(-1) - \frac{1}{8}\left( \frac{7}{3} \right) = \frac{3}{8},
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
L &=
\begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{3} & 1 & 0 \\
\frac{2}{3} & \frac{1}{8} & 1
\end{pmatrix},
\qquad
U &=
\begin{pmatrix}
3 & 1 & -1 \\
0 & \frac{8}{3} & \frac{7}{3} \\
0 & 0 & \frac{3}{8}
\end{pmatrix},
\qquad
P &= \begin{pmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}.
\end{align*} \end{split}\]
Solving \(L \mathbf{y} = P\mathbf{b}\) using forward substitution
\[\begin{split}
\begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{3} & 1 & 0 \\
\frac{2}{3} & \frac{1}{8} & 1
\end{pmatrix}
\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}
=
\begin{pmatrix} -5 \\ 16 \\ 0 \end{pmatrix}
\quad \implies \quad
\begin{aligned}
y_1 &= -5 \\
y_2 &= 16 - \frac{1}{3}(-5) = \frac{53}{3}, \\
y_3 &= 0 - \frac{2}{3}(-5) - \frac{1}{8}\left( \frac{53}{3} \right) = \frac{9}{8}.
\end{aligned}
\end{split}\]
Solving \(U \mathbf{x} = \mathbf{y}\) using back substitution
\[\begin{split}
\begin{pmatrix}
3 & 1 & -1 \\
0 & \frac{8}{3} & \frac{7}{3} \\
0 & 0 & \frac{3}{8}
\end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}
=
\begin{pmatrix} -5 \\ \frac{53}{3} \\ \frac{9}{8} \end{pmatrix}
\quad \implies \quad
\begin{aligned}
x_3 &= \frac{8}{3}\left( \frac{9}{8} \right) = 3, \\
x_2 &= \frac{3}{8}\left( \frac{53}{3} - \frac{7}{3}(3)\right)= 4, \\
x_1 &= \frac{1}{3}(-5 - 4 + 3) = -2.
\end{aligned}
\end{split}\]
Exercise 6.3
Use LU decomposition to solve the systems of linear equations \(A \mathbf{x}_1 = \mathbf{b}_1\) and \(A \mathbf{x}_2 = \mathbf{b}_2\) where
\[\begin{split} \begin{align*}
A &= \begin{pmatrix}
2 & -3 & 1 \\
8 & -7 & 10 \\
-4 & 21 & 19
\end{pmatrix}, &
\mathbf{b}_1 &= \begin{pmatrix} -1 \\ 24 \\ 95 \end{pmatrix}, &
\mathbf{b}_2 &= \begin{pmatrix} 14 \\ 81 \\ 62 \end{pmatrix}.
\end{align*} \end{split}\]
Solution
Compute the LU decomposition of \(A\)
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 2, \\
&& \ell_{21} &= \frac{1}{u_{11}}a_{21} = \frac{1}{2}(8) = 4, \\
&& \ell_{31} &= \frac{1}{u_{11}}a_{31} = \frac{1}{2}(-4) = -2, \\
j &= 2: & u_{12} &= a_{12} = -3, \\
&& u_{22} &= a_{22} - \ell_{21}u_{12} = -7 - 4(-3) = 5, \\
&& \ell_{32} &= \frac{1}{u_{22}}(a_{32} - \ell_{31}u_{12}) = \frac{1}{5}(21 - (-2)(-3)) = 3, \\
j &= 3: & u_{13} & a_{13} = 1, \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 10 - 4(1) = 6, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 19 - (-2)(1) - 3(6) = 3,
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
L &= \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ -2 & 3 & 1 \end{pmatrix}, &
U &= \begin{pmatrix} 2 & -3 & 1 \\ 0 & 5 & 6 \\ 0 & 0 & 3 \end{pmatrix}.
\end{align*} \end{split}\]
Solving \(A \mathbf{x}_1 = \mathbf{b}_1\)
\[\begin{split} \begin{align*}
\begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ -2 & 3 & 1 \end{pmatrix}
\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} =
\begin{pmatrix} -1 \\ 24 \\ 95 \end{pmatrix}
&\quad \implies \quad
\begin{aligned}
y_1 &= -1, \\
y_2 &= 24 - 4(-1) = 28, \\
y_3 &= 95 + 2(-1) - 3(28) = 9,
\end{aligned} \\
\begin{pmatrix} 2 & -3 & 1 \\ 0 & 5 & 6 \\ 0 & 0 & 3 \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} =
\begin{pmatrix} -1 \\ 28 \\ 9 \end{pmatrix}
&\quad \implies \quad
\begin{aligned}
x_3 &= \frac{9}{3} = 3, \\
x_2 &= \frac{1}{5}(28 - 6(3)) = 2, \\
x_1 &= \frac{1}{2}(-1 - (-3)(2) - 3) = 1,
\end{aligned}
\end{align*} \end{split}\]
therefore \(\mathbf{x}_1 = (1, 2, 3)^\mathsf{T}\).
Solving \(A \mathbf{x}_2 = \mathbf{b}_2\)
\[\begin{split} \begin{align*}
\begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ -2 & 3 & 1 \end{pmatrix}
\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} =
\begin{pmatrix} 14 \\ 81 \\ 62\end{pmatrix}
&\quad \implies \quad
\begin{aligned}
y_1 &= 14, \\
y_2 &= 81 - 4(14) = 25, \\
y_3 &= 62 + 2(14) - 3(25) = 15,
\end{aligned} \\
\begin{pmatrix} 2 & -3 & 1 \\ 0 & 5 & 6 \\ 0 & 0 & 3 \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} =
\begin{pmatrix} 14 \\ 25 \\ 15 \end{pmatrix}
&\quad \implies \quad
\begin{aligned}
x_3 &= \frac{15}{3} = 5, \\
x_2 &= \frac{1}{5}(25 - 6(5)) = -1, \\
x_1 &= \frac{1}{2}(15 - (-3)(-1) - 5) = 3,
\end{aligned}
\end{align*} \end{split}\]
therefore \(\mathbf{x}_2 = (3, -1, 5)^\mathsf{T}\).
Exercise 6.4
Solve the following systems of linear equations using Cholesky decomposition.
\[\begin{split} \begin{align*}
16x_1 +16x_2 +4x_3 &=-8,\\
16x_1 +25x_2 +10x_3 &=-47,\\
4x_1 +10x_2 +6x_3 &=-30.
\end{align*} \end{split}\]
Solution
The coefficient matrix is
\[\begin{split} A = \begin{pmatrix}
16 & 16 & 4 \\
16 & 25 & 10 \\
4 & 10 & 6
\end{pmatrix}. \end{split}\]
Checking whether \(A\) is a positive definite matrix
\[\begin{split} \begin{align*}
\det(16) &= 16, \\
\det \begin{pmatrix} 16 & 16 \\ 16 & 25 \end{pmatrix} &= 144, \\
\det \begin{pmatrix}
16 & 16 & 4 \\
16 & 25 & 10 \\
4 & 10 & 6
\end{pmatrix}
&= 16 \begin{vmatrix} 25 & 10 \\ 10 & 6 \end{vmatrix}
- 16 \begin{vmatrix} 16 & 10 \\ 4 & 6 \end{vmatrix}
+ 4 \begin{vmatrix} 16 & 25 \\ 4 & 10 \end{vmatrix} \\
&= 16(50) - 16(56) + 4(60) = 144,
\end{align*} \end{split}\]
therefore \(A\) is positive definite. Computing the Cholesky decomposition of \(A\)
\[\begin{split} \begin{align*}
j &= 1: & \ell_{11} &= \sqrt{a_{11}} = \sqrt{16} = 4, \\
&& \ell_{21} &= \frac{1}{\ell_{11}}a_{21} = \frac{1}{4}(16) = 4, \\
&& \ell_{31} &= \frac{1}{\ell_{11}}a_{31} = \frac{1}{4}(4) = 1, \\
j &= 2: & \ell_{22} &= \sqrt{a_{22} - \ell_{21}^2} = \sqrt{25 - 4^2} = 3, \\
&& \ell_{32} &= \frac{1}{\ell_{22}}(a_{32} - \ell_{31}\ell_{21}) = \frac{1}{3}(10 - 1(4)) = 2, \\
j &= 3: & \ell_{33} &+ \sqrt{a_{33} - \ell_{31}^2 - \ell_{32}^2} = \sqrt{6 - 1^2 - 2^2} = 1,
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
L =
\begin{pmatrix}
4 & 0 & 0 \\
4 & 3 & 0 \\
1 & 2 & 1
\end{pmatrix}.
\end{align*} \end{split}\]
Solving \(L \mathbf{y} = \mathbf{b}\) using forward substitution
\[\begin{split}
\begin{pmatrix}
4 & 0 & 0 \\
4 & 3 & 0 \\
1 & 2 & 1
\end{pmatrix}
\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}
=
\begin{pmatrix} -8 \\ -47 \\ -30 \end{pmatrix}
\quad \implies \quad
\begin{aligned}
y_1 &= \frac{1}{4}(-8) = -2, \\
y_2 &= \frac{1}{3}(-47 - 4(-2)) = - 13, \\
y_3 &= -30 - (-2) - 2(-13) = -2.
\end{aligned}
\end{split}\]
Solving \(L^\mathsf{T} \mathbf{x} = \mathbf{y}\) using back substitution
\[\begin{split}
\begin{pmatrix}
4 & 4 & 1 \\
0 & 3 & 2 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}
=
\begin{pmatrix} -2 \\ -13 \\ -2 \end{pmatrix}
\quad \implies \quad
\begin{aligned}
x_3 &= -2, \\
x_2 &= \frac{1}{3}(-13 - 2(-2)) = -3, \\
x_1 &= \frac{1}{4}(-2 -4(3) - (-2)) = 3.
\end{aligned}
\end{split}\]
Exercise 6.5
Calculate the QR decomposition using the Gram-Schmidt process of the following matrices:
(a) \(\begin{pmatrix} 6 & 6 & 1 \\ 3 & 6 & 1 \\ 2 & 1 & 1 \end{pmatrix}\);
Solution
\[\begin{split} \begin{align*}
j &= 1: & \mathbf{u}_1 &= \mathbf{a}_1 = \begin{pmatrix} 6 \\ 3 \\ 2 \end{pmatrix}, \\
&& r_{11} &= \| \mathbf{u}_1 \| = 7, \\
&& \mathbf{q}_1 &= \frac{\mathbf{u}_1}{r_{11}} = \frac{1}{7}
\begin{pmatrix} 6 \\ 3 \\ 2 \end{pmatrix} =
\begin{pmatrix} \frac67 \\ \frac37 \\ \frac27 \end{pmatrix}, \\
j &=2 : & r_{12} &= \mathbf{q}_1 \cdot \mathbf{a}_2 =
\begin{pmatrix} \frac67 \\ \frac37 \\ \frac27 \end{pmatrix} \cdot
\begin{pmatrix} 6 \\ 6 \\ 1 \end{pmatrix} = 8, \\
&& \mathbf{u}_2 &= \mathbf{a}_2 - r_{12}\mathbf{q}_1 =
\begin{pmatrix} 6 \\ 6 \\ 1 \end{pmatrix} - 8
\begin{pmatrix} \frac67 \\ \frac37 \\ \frac27 \end{pmatrix} =
\begin{pmatrix} -\frac67 \\ \frac{18}{7} \\ -\frac{9}{7} \end{pmatrix}, \\
&& r_{22} &= \| \mathbf{u}_2 \| = 3, \\
&& \mathbf{q}_2 &= \frac{\mathbf{u}_2}{r_{22}} = \frac{1}{3}\begin{pmatrix} -\frac67 \\ \frac{18}{7} \\ -\frac{9}{7} \end{pmatrix} =
\begin{pmatrix} -\frac27 \\ \frac67 \\ -\frac37 \end{pmatrix}, \\
j &= 3: & r_{13} &= \mathbf{q}_1 \cdot \mathbf{a}_3 =
\begin{pmatrix} \frac67 \\ \frac37 \\ \frac27 \end{pmatrix} \cdot
\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = \frac{11}{7}, \\
&& r_{23} &= \mathbf{q}_2 \cdot \mathbf{a}_3 =
\begin{pmatrix} -\frac27 \\ \frac67 \\ -\frac37 \end{pmatrix} \cdot
\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = \frac17, \\
&& \mathbf{u}_3 &= \mathbf{a}_3 - r_{13}\mathbf{q}_1 - r_{23}\mathbf{q}_2 =
\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} - \frac{11}{7}
\begin{pmatrix} \frac67 \\ \frac37 \\ \frac27 \end{pmatrix} - \frac17
\begin{pmatrix} -\frac27 \\ \frac67 \\ -\frac37 \end{pmatrix} =
\begin{pmatrix} -\frac{15}{49} \\ \frac{10}{49} \\ \frac{30}{49} \end{pmatrix}, \\
&& r_{33} &= \| \mathbf{u}_3 \| = \frac57, \\
&& \mathbf{q}_3 &= \frac{\mathbf{u}_3}{r_{33}} = \frac75
\begin{pmatrix} -\frac{15}{49} \\ \frac{10}{49} \\ \frac{30}{49}\end{pmatrix} =
\begin{pmatrix} -\frac37 \\ \frac27 \\ \frac67 \end{pmatrix},
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
Q &= \begin{pmatrix} \frac{6}{7} & -\frac{2}{7} & -\frac{3}{7} \\ \frac{3}{7} & \frac{6}{7} & \frac{2}{7} \\ \frac{2}{7} & -\frac{3}{7} & \frac{6}{7} \end{pmatrix}, &
R &= \begin{pmatrix} 7 & 8 & \frac{11}{7} \\ 0 & 3 & \frac{1}{7} \\ 0 & 0 & \frac{5}{7} \end{pmatrix}
\end{align*} \end{split}\]
(c) \(\begin{pmatrix} 1 & 2 & 1 \\ 1 & 4 & 3 \\ 1 & -4 & 6 \\ 1 & 2 & 1 \end{pmatrix}\).
Solution
\[\begin{split} \begin{align*}
j &= 1: & \mathbf{u}_1 &= \mathbf{a}_1 =
\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \\
&& r_{11} &= \| \mathbf{u}_1 \| = 2, \\
&& \mathbf{q}_1 &= \frac{\mathbf{u}_1}{r_{11}} = \frac{1}{2}
\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} =
\begin{pmatrix} \frac12 \\ \frac12 \\ \frac12 \\ \frac12 \end{pmatrix}, \\
j &= 2: & r_{12} &= \mathbf{q}_1 \cdot \mathbf{a}_2 =
\begin{pmatrix} \frac12 \\ \frac12 \\ \frac12 \\ \frac12 \end{pmatrix} \cdot
\begin{pmatrix} 2 \\ 4 \\ -4 \\ 2 \end{pmatrix} = 2, \\
&& \mathbf{u}_2 &= \mathbf{a}_2 - r_{12} \mathbf{q}_1 =
\begin{pmatrix} 2 \\ 4 \\ -4 \\ 2 \end{pmatrix} - 2
\begin{pmatrix} \frac12 \\ \frac12 \\ \frac12 \\ \frac12 \end{pmatrix} =
\begin{pmatrix} 1 \\ 3 \\ -5 \\ 1 \end{pmatrix}, \\
&& r_{22} &= \| \mathbf{u}_2 \| = 6, \\
&& \mathbf{q}_2 &= \frac{\mathbf{u}_2}{r_{22}} = \frac{1}{6}
\begin{pmatrix} 1 \\ 3 \\ -5 \\ 1 \end{pmatrix} =
\begin{pmatrix} \frac16 \\ \frac12 \\ -\frac56 \\ \frac16 \end{pmatrix}, \\
j &= 3: & r_{13} &= \mathbf{q}_1 \cdot \mathbf{a}_3 =
\begin{pmatrix} \frac12 \\ \frac12 \\ \frac12 \\ \frac12 \end{pmatrix} \cdot
\begin{pmatrix} 1 \\ 3 \\ 6 \\ 1 \end{pmatrix} = \frac{11}{2}, \\
&& r_{23} &= \mathbf{q}_2 \cdot \mathbf{a}_3 =
\begin{pmatrix} \frac16 \\ \frac12 \\ -\frac56 \\ \frac16 \end{pmatrix} \cdot
\begin{pmatrix} 1 \\ 3 \\ 6 \\ 1 \end{pmatrix} = -\frac{19}{6}, \\
&& \mathbf{u}_3 &= \mathbf{a}_3 - r_{13} \mathbf{q}_1 - r_{23} \mathbf{q}_2 =
\begin{pmatrix} 1 \\ 3 \\ 6 \\ 1 \end{pmatrix} - \frac{11}{2}
\begin{pmatrix} \frac12 \\ \frac12 \\ \frac12 \\ \frac12 \end{pmatrix} - \left(-\frac{19}{6}\right)
\begin{pmatrix} \frac16 \\ \frac12 \\ -\frac56 \\ \frac16 \end{pmatrix} =
\begin{pmatrix} -\frac{11}{9} \\ \frac{11}{6} \\ \frac{11}{18} \\ -\frac{11}{9} \end{pmatrix} \\
&& r_{33} &= \| \mathbf{u}_3 \| = \frac{11\sqrt{18}}{18}, \\
&& \mathbf{q}_3 &= \frac{\mathbf{u}_3}{r_{33}} = \frac{18}{11\sqrt{18}}
\begin{pmatrix} -\frac{11}{9} \\ \frac{11}{6} \\ \frac{11}{18} \\ -\frac{11}{9} \end{pmatrix} =
\begin{pmatrix} -\frac{\sqrt{18}}{9} \\ \frac{\sqrt{18}}{6} \\ \frac{\sqrt{18}}{18} \\ -\frac{\sqrt{18}}{9} \end{pmatrix},
\end{align*} \end{split}\]
therefore
\[\begin{split} \begin{align*}
Q &= \begin{pmatrix} \frac{1}{2} & \frac{1}{6} & -\frac{\sqrt{18}}{9} \\ \frac{1}{2} & \frac{1}{2} & \frac{\sqrt{18}}{6} \\ \frac{1}{2} & -\frac{5}{6} & \frac{\sqrt{18}}{18} \\ \frac{1}{2} & \frac{1}{6} & -\frac{\sqrt{18}}{9} \end{pmatrix}, &
R &= \begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 6 & -\frac{19}{6} \\ 0 & 0 & \frac{11\sqrt{18}}{18} \end{pmatrix}.
\end{align*} \end{split}\]
Exercise 6.6
Calculate the QR decomposition of the matrices from Exercise 6.5 using the Householder reflections.
Solution
(a) \(A = \begin{pmatrix} 6 & 6 & 1 \\ 3 & 6 & 1 \\ 2 & 1 & 1 \end{pmatrix}\)
\[\begin{split} \begin{align*}
j &= 1: & \mathbf{x} &= \begin{pmatrix} 6 \\ 3 \\ 2 \end{pmatrix}, \\
&& \mathbf{v} &= \mathbf{x} - \operatorname{sign}(x_1)\|\mathbf{x}\|\mathbf{e}_1 =
\mathbf{x} = \begin{pmatrix} 6 \\ 3 \\ 2 \end{pmatrix} - 7
\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} =
\begin{pmatrix} -1 \\ 3 \\ 2\end{pmatrix}, \\
&& H &= I_3 - 2\frac{\mathbf{vv}^\mathsf{T}}{\mathbf{v}^\mathsf{T}\mathbf{v}} =
\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} - \frac{2}{14}
\begin{pmatrix} 1 & -3 & -2 \\ -3 & 9 & 6 \\ -2 & 6 & 4 \end{pmatrix} =
\begin{pmatrix}
\frac67 & \frac37 & \frac27 \\
\frac37 & -\frac27 & -\frac67 \\
\frac27 & -\frac67 & \frac37
\end{pmatrix}, \\
&& R &= HR =
\begin{pmatrix}
\frac67 & \frac37 & \frac27 \\
\frac27 & -\frac27 & -\frac67 \\
\frac27 & -\frac67 & \frac37
\end{pmatrix}
\begin{pmatrix} 6 & 6 & 1 \\ 3 & 6 & 1 \\ 2 & 1 & 1 \end{pmatrix} =
\begin{pmatrix}
7 & 8 & \frac{11}{7} \\
0 & 0 & -\frac{5}{7} \\
0 & -3 & -\frac{1}{7}
\end{pmatrix}, \\
&& Q &= QH = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}
\begin{pmatrix}
\frac67 & \frac37 & \frac27 \\
\frac27 & -\frac27 & -\frac67 \\
\frac27 & -\frac67 & \frac37
\end{pmatrix} =
\begin{pmatrix}
\frac67 & \frac37 & \frac27 \\
\frac37 & -\frac27 & -\frac67 \\
\frac27 & -\frac67 & \frac37
\end{pmatrix}. \\
j &= 2: & \mathbf{x} &= \begin{pmatrix} 0 \\ -3 \end{pmatrix}, \\
&& \mathbf{v} &= \mathbf{x} - \operatorname{x_1}\|\mathbf{x}\|\mathbf{e}_1 =
\begin{pmatrix} 0 \\ -3 \end{pmatrix} - 3
\begin{pmatrix} 1 \\ 0 \end{pmatrix} =
\begin{pmatrix} -3 \\ -3 \end{pmatrix}, \\
&& H' &= I_2 - 2 \frac{\mathbf{vv}^\mathsf{T}}{\mathbf{v}^\mathsf{T}\mathbf{v}} =
\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} - \frac{2}{18}
\begin{pmatrix} 9 & 9 \\ 9 & 9 \end{pmatrix} =
\begin{pmatrix} 0 & -1 \\ -1 & 0\end{pmatrix}, \\
&& H &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}, \\
&& R &= HR =
\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}
\begin{pmatrix}
7 & 8 & \frac{11}{7} \\
0 & 0 & -\frac{5}{7} \\
0 & -3 & -\frac{1}{7}
\end{pmatrix} =
\begin{pmatrix} 7 & 8 & \frac{11}{7} \\ 0 & 3 & \frac17 \\ 0 & 0 & \frac57 \end{pmatrix}, \\
&& Q &= QH =
\begin{pmatrix}
\frac67 & \frac37 & \frac27 \\
\frac27 & -\frac27 & -\frac67 \\
\frac27 & -\frac67 & \frac37
\end{pmatrix}
\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix} =
\begin{pmatrix}
\frac67 & -\frac27 & -\frac37 \\
\frac37 & \frac67 & \frac27 \\
\frac27 & -\frac37 & \frac67
\end{pmatrix}.
\end{align*} \end{split}\]
Checking the QR decomposition is correct
\[\begin{split} \begin{align*}
QR &= \begin{pmatrix}
\frac67 & -\frac27 & -\frac37 \\
\frac37 & \frac67 & \frac27 \\
\frac27 & -\frac37 & \frac67
\end{pmatrix}
\begin{pmatrix} 7 & 8 & \frac{11}{7} \\ 0 & 3 & \frac17 \\ 0 & 0 & \frac57 \end{pmatrix} =
\begin{pmatrix} 6 & 6 & 1 \\ 3 & 6 & 1 \\ 2 & 1 & 1 \end{pmatrix}, \quad \checkmark \\
Q^\mathsf{T}Q &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}. \quad \checkmark
\end{align*} \end{split}\]
(b) \(A = \begin{pmatrix} 1 & 2 & 1 \\ 1 & 4 & 3 \\ 1 & -4 & 6 \\ 1 & 2 & 1 \end{pmatrix}\)
Set \(Q = I_4\) and \(R = A\)
\[\begin{split} \begin{align*}
j &= 1: & \mathbf{x} &= \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \\
&& \mathbf{v} &= \mathbf{x} - \operatorname{sign}(x_1)\| \mathbf{x} \| \mathbf{e} =
\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} - 2
\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} =
\begin{pmatrix} -1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \\
&& H &= I_4 - 2 \frac{\mathbf{vv}^\mathsf{T}}{\mathbf{v}^\mathsf{T}\mathbf{v}} =
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} - \frac{2}{4}
\begin{pmatrix} 1 & -1 & -1 & -1 \\ -1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 \end{pmatrix} =
\begin{pmatrix} \frac12 & \frac12 & \frac12 & \frac12 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac12 & \frac12 & - \frac12 \\ \frac12 & -\frac12 & -\frac12 & \frac12 \end{pmatrix}, \\
&& R &= HR =
\begin{pmatrix} \frac12 & \frac12 & \frac12 & \frac12 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac12 & \frac12 & - \frac12 \\ \frac12 & -\frac12 & -\frac12 & \frac12 \end{pmatrix}
\begin{pmatrix} 1 & 2 & 1 \\ 1 & 4 & 3 \\ 1 & -4 & 6 \\ 1 & 2 & 1 \end{pmatrix} =
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 4 & -\frac32 \\ 0 & -4 & \frac32 \\ 0 & 2 & -\frac72 \end{pmatrix}, \\
&& Q &= QH =
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}
\begin{pmatrix} \frac12 & \frac12 & \frac12 & \frac12 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac12 & \frac12 & - \frac12 \\ \frac12 & -\frac12 & -\frac12 & \frac12 \end{pmatrix} =
\begin{pmatrix} \frac12 & \frac12 & \frac12 & \frac12 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac12 & \frac12 & - \frac12 \\ \frac12 & -\frac12 & -\frac12 & \frac12 \end{pmatrix}, \\
j &= 2: & \mathbf{x} &= \begin{pmatrix} 4 \\ -4 \\ 2 \end{pmatrix}, \\
&& \mathbf{v} &= \mathbf{x} - \operatorname{sign}(x_1)\| \mathbf{x} \| \mathbf{e} =
\begin{pmatrix} 4 \\ -4 \\ 2 \end{pmatrix} - 6 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} =
\begin{pmatrix} -2 \\ -4 \\ 2 \end{pmatrix}, \\
&& H' &= I_3 - 2 \frac{\mathbf{vv}^\mathsf{T}}{\mathbf{v}^\mathsf{T}\mathbf{v}} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} - \frac{2}{24}
\begin{pmatrix} 4 & 8 & -4 \\ 8 & 16 & -8 \\ -4 & -8 & 4 \end{pmatrix} =
\begin{pmatrix} \frac23 & -\frac23 & \frac13 \\ -\frac23 & -\frac13 & \frac23 \\ \frac13 & \frac23 & \frac23 \end{pmatrix}, \\
&& H &=
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac23 & -\frac23 & \frac13 \\ 0 & -\frac23 & -\frac13 & \frac23 \\ 0 & \frac13 & \frac23 & \frac23 \end{pmatrix}, \\
&& R &= HR =
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac23 & -\frac23 & \frac13 \\ 0 & -\frac23 & -\frac13 & \frac23 \\ 0 & \frac13 & \frac23 & \frac23 \end{pmatrix}
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 4 & -\frac32 \\ 0 & -4 & \frac32 \\ 0 & 2 & -\frac72 \end{pmatrix} =
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 6 & -\frac{19}{6} \\ 0 & 0 & -\frac{11}{6} \\ 0 & 0 & -\frac{11}{6} \end{pmatrix}, \\
&& Q &= QH =
\begin{pmatrix} \frac12 & \frac12 & \frac12 & \frac12 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac12 & \frac12 & - \frac12 \\ \frac12 & -\frac12 & -\frac12 & \frac12 \end{pmatrix}
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac23 & -\frac23 & \frac13 \\ 0 & -\frac23 & -\frac13 & \frac23 \\ 0 & \frac13 & \frac23 & \frac23 \end{pmatrix} =
\begin{pmatrix} \frac12 & \frac16 & -\frac16 & \frac56 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac56 & -\frac16 & -\frac16 \\ \frac12 & \frac16 & \frac56 & -\frac16 \end{pmatrix}, \\
j &= 3: & \mathbf{x} &= \begin{pmatrix} -\frac{11}{6} \\ -\frac{11}{6} \end{pmatrix}, \\
&& \mathbf{v} &= \mathbf{x} - \operatorname{sign}(x_1) \| \mathbf{x} \| \mathbf{e}_1 =
\begin{pmatrix} -\frac{11}{6} \\ -\frac{11}{6} \end{pmatrix} - (-1) \left( \frac{11\sqrt{2}}{6}\right)
\begin{pmatrix} 1 \\ 0 \end{pmatrix} =
\begin{pmatrix}-\frac{11}{6} + \frac{11\sqrt{2}}{6} \\ -\frac{11}{6} \end{pmatrix}, \\
&& H' &= I_2 - 2 \frac{\mathbf{vv}^\mathsf{T}}{\mathbf{v}^\mathsf{T}\mathbf{v}} =
\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} - \frac{2}{\frac{121}{9} - \frac{121\sqrt{2}}{18}}
\begin{pmatrix} \frac{121}{12} - \frac{121\sqrt{2}}{18} & \frac{121}{36} - \frac{121\sqrt{2}}{36} \\ \frac{121}{36} - \frac{121\sqrt{2}}{36} & \frac{121}{36} \end{pmatrix} =
\begin{pmatrix} -\frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix}, \\
&& H &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ 0 & 0 & -\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix}, \\
&& R &= HR =
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ 0 & 0 & -\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix}
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 6 & -\frac{19}{6} \\ 0 & 0 & -\frac{11}{6} \\ 0 & 0 & -\frac{11}{6} \end{pmatrix} =
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 6 & -\frac{19}{6} \\ 0 & 0 & \frac{11\sqrt{2}}{6} \\ 0 & 0 & 0 \end{pmatrix}, \\
&& Q &= QH =
\begin{pmatrix} \frac12 & \frac16 & -\frac16 & \frac56 \\ \frac12 & \frac12 & -\frac12 & -\frac12 \\ \frac12 & -\frac56 & -\frac16 & -\frac16 \\ \frac12 & \frac16 & \frac56 & -\frac16 \end{pmatrix}
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ 0 & 0 & -\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix} =
\begin{pmatrix} \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & \frac{\sqrt{2}}{2} \\ \frac12 & \frac12 & \frac{\sqrt{2}}{2} & 0 \\ \frac12 & -\frac56 & \frac{\sqrt{2}}{6} & 0 \\ \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & -\frac{\sqrt{2}}{2} \end{pmatrix}.
\end{align*} \end{split}\]
Checking that the QR decomposition is correct
\[\begin{split} \begin{align*}
QR &=
\begin{pmatrix} \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & \frac{\sqrt{2}}{2} \\ \frac12 & \frac12 & \frac{\sqrt{2}}{2} & 0 \\ \frac12 & -\frac56 & \frac{\sqrt{2}}{6} & 0 \\ \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & -\frac{\sqrt{2}}{2} \end{pmatrix}
\begin{pmatrix} 2 & 2 & \frac{11}{2} \\ 0 & 6 & -\frac{19}{6} \\ 0 & 0 & \frac{11\sqrt{2}}{6} \\ 0 & 0 & 0 \end{pmatrix} =
\begin{pmatrix} 1 & 2 & 1 \\ 1 & 4 & 3 \\ 1 & -4 & 6 \\ 1 & 2 & 1 \end{pmatrix}, \quad \checkmark \\
Q^\mathsf{T} Q &=
\begin{pmatrix}
\frac12 & \frac12 & \frac12 & \frac12 \\
\frac16 & \frac12 & -\frac16 & \frac16 \\
-\frac16 & -\frac12 & -\frac16 & \frac56 \\
\frac56 & -\frac12 & -\frac16 & -\frac16
\end{pmatrix}
\begin{pmatrix} \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & \frac{\sqrt{2}}{2} \\ \frac12 & \frac12 & \frac{\sqrt{2}}{2} & 0 \\ \frac12 & -\frac56 & \frac{\sqrt{2}}{6} & 0 \\ \frac12 & \frac16 & -\frac{\sqrt{2}}{3} & -\frac{\sqrt{2}}{2} \end{pmatrix}
=
\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \quad \checkmark
\end{align*} \end{split}\]