\(\newcommand{\bmu}{\boldsymbol{\mu}}\) \(\newcommand{\bSigma}{\boldsymbol{\Sigma}}\) \(\newcommand{\bfbeta}{\boldsymbol{\beta}}\) \(\newcommand{\bflambda}{\boldsymbol{\lambda}}\) \(\newcommand{\bgamma}{\boldsymbol{\gamma}}\) \(\newcommand{\bsigma}{{\boldsymbol{\sigma}}}\) \(\newcommand{\bpi}{\boldsymbol{\pi}}\) \(\newcommand{\btheta}{{\boldsymbol{\theta}}}\) \(\newcommand{\bphi}{\boldsymbol{\phi}}\) \(\newcommand{\balpha}{\boldsymbol{\alpha}}\) \(\newcommand{\blambda}{\boldsymbol{\lambda}}\) \(\renewcommand{\P}{\mathbb{P}}\) \(\newcommand{\E}{\mathbb{E}}\) \(\newcommand{\indep}{\perp\!\!\!\perp} \newcommand{\bx}{\mathbf{x}}\) \(\newcommand{\bp}{\mathbf{p}}\) \(\renewcommand{\bx}{\mathbf{x}}\) \(\newcommand{\bX}{\mathbf{X}}\) \(\newcommand{\by}{\mathbf{y}}\) \(\newcommand{\bY}{\mathbf{Y}}\) \(\newcommand{\bz}{\mathbf{z}}\) \(\newcommand{\bZ}{\mathbf{Z}}\) \(\newcommand{\bw}{\mathbf{w}}\) \(\newcommand{\bW}{\mathbf{W}}\) \(\newcommand{\bv}{\mathbf{v}}\) \(\newcommand{\bV}{\mathbf{V}}\) \(\newcommand{\bfg}{\mathbf{g}}\) \(\newcommand{\bfh}{\mathbf{h}}\) \(\newcommand{\horz}{\rule[.5ex]{2.5ex}{0.5pt}}\) \(\renewcommand{\S}{\mathcal{S}}\) \(\newcommand{\X}{\mathcal{X}}\) \(\newcommand{\var}{\mathrm{Var}}\) \(\newcommand{\pa}{\mathrm{pa}}\) \(\newcommand{\Z}{\mathcal{Z}}\) \(\newcommand{\bh}{\mathbf{h}}\) \(\newcommand{\bb}{\mathbf{b}}\) \(\newcommand{\bc}{\mathbf{c}}\) \(\newcommand{\cE}{\mathcal{E}}\) \(\newcommand{\cP}{\mathcal{P}}\) \(\newcommand{\bbeta}{\boldsymbol{\beta}}\) \(\newcommand{\bLambda}{\boldsymbol{\Lambda}}\) \(\newcommand{\cov}{\mathrm{Cov}}\) \(\newcommand{\bfk}{\mathbf{k}}\) \(\newcommand{\idx}[1]{}\) \(\newcommand{\xdi}{}\)
2.6. Exercises#
2.6.1. Warm-up worksheets#
(with help from Claude, Gemini, and ChatGPT)
Section 2.2
E2.2.1 Determine whether the set \(U = \{(x, y, z) \in \mathbb{R}^3 : x + 2y - z = 0\}\) is a linear subspace of \(\mathbb{R}^3\).
E2.2.2 Determine whether the vectors \(u_1 = (1, 1, 1)\), \(u_2 = (1, 0, -1)\), and \(u_3 = (2, 1, 0)\) are linearly independent.
E2.2.3 Find a basis for the subspace \(U = \{(x, y, z) \in \mathbb{R}^3 : x - y + z = 0\}\).
E2.2.4 Find the dimension of the subspace \(U = \{(x, y, z, w) \in \mathbb{R}^4 : x + y = 0, z = w\}\).
E2.2.5 Verify whether the vectors \(u_1 = (1/\sqrt{2}, 1/\sqrt{2})\), \(u_2 = (1/\sqrt{2}, -1/\sqrt{2})\) form an orthonormal list.
E2.2.6 Given the orthonormal basis \(q_1 = (1/\sqrt{2}, 1/\sqrt{2})\), \(q_2 = (1/\sqrt{2}, -1/\sqrt{2})\), find the orthonormal expansion of \(w = (1, 0)\).
E2.2.7 Determine if the matrix \(A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\) is nonsingular.
E2.2.8 Solve the system of equations \(Ax = b\), where \(A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\) and \(b = (5, 11)\).
E2.2.9 Given the vectors \(\mathbf{w}_1 = (1, 0, 1)\) and \(\mathbf{w}_2 = (0, 1, 1)\), express the vector \(\mathbf{v} = (2, 3, 5)\) as a linear combination of \(\mathbf{w}_1\) and \(\mathbf{w}_2\).
E2.2.10 Verify if the vectors \(\mathbf{u} = (1, 2, 3)\) and \(\mathbf{v} = (4, -2, 1)\) are orthogonal.
E2.2.11 Find the null space of the matrix \(B = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}\).
E2.2.12 Given the basis \(\{\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\}\) for \(\mathbb{R}^3\), express the vector \(\mathbf{v} = (4, 5, 6)\) as a linear combination of the basis vectors.
E2.2.13 Determine whether the vectors \(\mathbf{u}_1 = (1, 2, 3)\), \(\mathbf{u}_2 = (2, -1, 0)\), and \(\mathbf{u}_3 = (1, 8, 6)\) are linearly independent.
E2.2.14 Verify the Cauchy-Schwarz Inequality for the vectors \(\mathbf{u} = (2, 1)\) and \(\mathbf{v} = (1, -3)\).
E2.2.15 Solve the system of equations \(2x + y = 3\) and \(x - y = 1\) using matrix inversion.
Section 2.3
E2.3.1 Let \(Q = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{6}} \\ 0 & \frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \end{pmatrix}\). Is \(Q\) an orthogonal matrix?
E2.3.2 True or False: The orthogonal projection of a vector onto a subspace is always strictly shorter than the original vector.
E2.3.3 For the vector \(\mathbf{v} = (2, 3)\) and the linear subspace \(U\) made from the line spanned by \(\mathbf{u} = (1, 1)\), find the orthogonal projection \(\mathrm{proj}_{U} \mathbf{v}\).
E2.3.4 Let \(U = \mathrm{span}((1, 1, 0)^T)\) and \(v = (1, 2, 3)^T\). Compute \(\|v\|^2\) and \(\|\mathrm{proj}_Uv\|^2\).
E2.3.5 Find the orthogonal projection of \(\mathbf{v} = (1, 2, 1)\) onto the subspace spanned by \(\mathbf{u} = (1, 1, 0)\).
E2.3.6 Let \(U = \mathrm{span}((1, 0, 1), (0, 1, 1))\). Find a basis for \(U^\perp\).
E2.3.7 Let \(v = (1, 2, 3)\) and \(U = \mathrm{span}((1, 0, 1), (0, 1, 1))\). Compute \(\mathrm{proj}_U v\).
E2.3.8 Let \(v = (1, 2, 3)\) and \(U = \mathrm{span}((1, 0, 1), (0, 1, 1))\). Decompose \(v\) into its orthogonal projection onto \(U\) and a vector in \(U^\perp\).
E2.3.9 Let \(v = (1, 2, 3)^T\) and \(U = \mathrm{span}((1, 0, 1)^T, (0, 1, 1)^T)\). Verify Pythagoras’ Theorem: \(\|v\|^2 = \|\mathrm{proj}_U v\|^2 + \|v - \mathrm{proj}_U v\|^2\).
E2.3.10 Let \(A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix}\). Is \(P = AA^T\) an orthogonal projection matrix?
E2.3.11 Let \(\mathbf{u}_1 = \begin{pmatrix} 2 \\ 1 \\ -2 \end{pmatrix}\) and \(\mathbf{u}_2 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\). Compute \(\mathrm{proj}_{\mathbf{u}_1} \mathbf{u}_2\).
E2.3.12 Find the orthogonal complement of the subspace spanned by \(\mathbf{u} = (1, 1, 0)\) in \(\mathbb{R}^3\).
E2.3.13 Let \(W = \mathrm{span}\left((1, 1, 0)\right)\). Find a basis for \(W^\perp\).
E2.3.14 Let \(A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ 1 & 0 \end{pmatrix}\) and \(\mathbf{b} = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}\). Set up the normal equations to solve the linear least squares problem \(A\mathbf{x} \approx \mathbf{b}\).
E2.3.15 Solve the normal equation \(A^T A \mathbf{x} = A^T \mathbf{b}\) for \(A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\) and \(\mathbf{b} = \begin{pmatrix} 3 \\ 1 \end{pmatrix}\).
E2.3.16 Let \(\mathbf{a} = (1, 2, 1)\) and \(\mathbf{b} = (1, 0, -1)\). Find the orthogonal projection of \(\mathbf{a}\) onto \(\mathrm{span}(\mathbf{b})\).
Section 2.4
E2.4.1 Let \(\mathbf{a}_1 = (1, 0)\) and \(\mathbf{a}_2 = (1, 1)\). Apply the Gram-Schmidt algorithm to find an orthonormal basis for \(\mathrm{span}(\mathbf{a}_1, \mathbf{a}_2)\).
E2.4.2 Determine the QR decomposition of the matrix \(A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) using the Gram-Schmidt algorithm.
E2.4.3 Apply the Gram-Schmidt algorithm to transform the basis \(\{(1, 1), (1, 0)\}\) into an orthonormal basis.
E2.4.4 Given the vectors \(a_1 = (1, 1, 1)\), \(a_2 = (1, 0, -1)\), apply the Gram-Schmidt algorithm to obtain an orthonormal basis for \(\mathrm{span}(a_1, a_2)\).
E2.4.5 For the vectors \(a_1\) and \(a_2\) from E2.4.4, find the QR decomposition of the matrix \(A = [a_1\ a_2]\).
E2.4.6 Solve the system \(Rx = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix} x = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\) using back substitution.
E2.4.7 Let \(R = \begin{pmatrix} 2 & -1 \\ 0 & 3 \end{pmatrix}\) and \(\mathbf{b} = (4, 3)\). Solve the system of equations \(R\mathbf{x} = \mathbf{b}\) using back substitution.
E2.4.8 Given the matrix \(A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) and the vector \(b = (1, 2)\), solve the least squares problem \(\min_{x \in \mathbb{R}^2} \|Ax - b\|\) using the QR decomposition.
E2.4.9 Let \(\mathbf{z} = (1, -1, 0)\). Find the Householder reflection matrix \(H\) that reflects across the hyperplane orthogonal to \(\mathbf{z}\).
E2.4.10 Find the Householder reflection matrix that introduces zeros below the diagonal in the first column of the matrix \(A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\).
E2.4.11 Verify that the Householder reflection matrix \(H_1\) from E2.4.10 is orthogonal and symmetric.
E2.4.12 Apply the Householder reflection matrix \(H_1\) from E2.4.10 to the matrix \(A\) from E2.4.10 and verify that it introduces zeros below the diagonal in the first column.
E2.4.13 Using the Householder reflection matrix \(H_1\) from E2.4.10, find the QR decomposition of the matrix \(A\) from E2.4.10.
E2.4.14 Verify that the QR decomposition from E2.4.13 satisfies \(A = QR\) and that \(Q\) is orthogonal.
E2.4.15 Let \(A = \begin{pmatrix} 3 & 1 \\ 4 & 2 \end{pmatrix}\). Find a Householder reflection matrix \(H_1\) such that the first column of \(H_1 A\) has a zero in the second entry.
E2.4.16 Let \(A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ 0 & 1 \end{pmatrix}\) and \(\mathbf{b} = (2, 0, 1)^T\). Set up the normal equations \(A^TA\mathbf{x} = A^T\mathbf{b}\) for the linear least squares problem associated with \(A\) and \(\mathbf{b}\).
E2.4.17 Use the QR decomposition to solve the linear least squares problem \(Ax = \mathbf{b}\) for \(A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\) and \(\mathbf{b} = \begin{pmatrix} 2 \\ 0 \end{pmatrix}\).
Section 2.5
E2.5.1 Given the data points \((x_1, y_1) = (1, 2)\), \((x_2, y_2) = (2, 4)\), \((x_3, y_3) = (3, 5)\), and \((x_4, y_4) = (4, 7)\), find the coefficients \(\beta_0\) and \(\beta_1\) that minimize the least squares criterion \(\sum_{i=1}^4 (y_i - \beta_0 - \beta_1 x_i)^2\).
E2.5.2 For the data points in E2.5.1, compute the fitted values and residuals for the linear regression model.
E2.5.3 Given the data points \((x_1, y_1) = (1, 3)\), \((x_2, y_2) = (2, 5)\), and \((x_3, y_3) = (3, 8)\), set up the linear system \(A \boldsymbol{\beta} = \mathbf{y}\) for finding the least squares line.
E2.5.4 For the data in E2.5.3, compute the normal equations \(A^T A \boldsymbol{\beta} = A^T \mathbf{y}\).
E2.5.5 Solve the normal equations from E2.5.4 to find the coefficients \(\beta_0\) and \(\beta_1\) of the least squares line.
E2.5.6 Using the data from E2.5.3 and the fitted line from E2.5.5, calculate the residuals for each data point.
E2.5.7 Given the data points \((x_1, y_1) = (-1, 2)\), \((x_2, y_2) = (0, 1)\), and \((x_3, y_3) = (1, 3)\), construct the matrix \(A\) for fitting a quadratic polynomial (degree 2).
E2.5.8 Suppose we have a sample of \(n = 100\) observations and we perform bootstrapping by resampling with replacement. What is the probability that a specific observation is included in a given bootstrap sample?
E2.5.9 Given the matrix \(A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix}\) and the vector \(\mathbf{y} = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}\), solve for the coefficients \(\beta\) in the least squares problem \(A \beta = \mathbf{y}\).
E2.5.10 For the polynomial regression problem \(y = \beta_0 + \beta_1 x + \beta_2 x^2\) with points \((0, 1)\), \((1, 2)\), \((2, 5)\), form the matrix \(A\).
E2.5.11 What is the residual sum of squares (RSS) for the linear fit \(y = 2x + 1\) on the data points \((1, 3)\), \((2, 5)\), \((3, 7)\)?
E2.5.12 For the polynomial regression \(y = \beta_0 + \beta_1 x + \beta_2 x^2\) on points \((1, 1)\), \((2, 4)\), \((3, 9)\), find the normal equations.
2.6.2. Problems#
2.1 Show that \(\mathbf{0}\) is an element of any (non-empty) linear subspace. \(\lhd\)
2.2 Prove that \(\mathrm{null}(B)\) is a linear subspace. \(\lhd\)
2.3 Let \(\beta_j \neq 0\) for all \(j \in [m]\). Show that \(\mathrm{span}(\beta_1 \mathbf{w}_1, \ldots, \beta_m \mathbf{w}_m) = \mathrm{span}(\mathbf{w}_1, \ldots, \mathbf{w}_m).\) \(\lhd\)
2.4 (Adapted from [Sol]) Suppose that \(U_1\) and \(U_2\) are linear subspaces of vector space \(V\). Show that \(U_1 \cap U_2\) is a linear subspace of \(V\). Is \(U_1 \cup U_2\) always a linear subspace of \(V\)? \(\lhd\)
2.5 Let \(\mathcal{U}, \mathcal{V}\) be linear subspaces of \(V\) such that \(\mathcal{U} \subseteq \mathcal{V}\). Show that \(\mathrm{dim}(\mathcal{U}) \leq \mathrm{dim}(\mathcal{V})\). [Hint: Complete the basis.] \(\lhd\)
2.6 (Adapted from [Axl]) Prove that if \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) spans \(U\), then so does the list
obtained by subtracting from each vector (except the last one) the following vector. \(\lhd\)
2.7 (Adapted from [Axl]) Prove that if \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) is linearly independent, then so is the list
obtained by subtracting from each vector (except the last one) the following vector. \(\lhd\)
2.8 (Adapted from [Axl]) Suppose \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) are linearly independent in \(U\) and \(\mathbf{w} \in U\). Prove that if \(\{\mathbf{v}_1 + \mathbf{w},\ldots, \mathbf{v}_n + \mathbf{w}\}\) are linearly dependent, then \(\mathbf{w} \in \mathrm{span}(\mathbf{v}_1,\ldots,\mathbf{v}_n)\). \(\lhd\)
2.9 Establish that \(U^\perp\) is a linear subspace. \(\lhd\)
2.10 Let \(U \subseteq V\) be a linear subspace and let \(\mathbf{v} \in U\). Show that \(\mathrm{proj}_U \mathbf{v} = \mathbf{v}\). \(\lhd\)
2.11 Let \(A \in \mathbb{R}^{n \times n}\) be a square matrix. Show that, if for any \(\mathbf{b} \in \mathbb{R}^n\) there exists a unique \(\mathbf{x} \in \mathbb{R}^n\) such that \(A \mathbf{x} = \mathbf{b}\), then \(A\) is nonsingular. [Hint: Consider \(\mathbf{b} = \mathbf{0}\).] \(\lhd\)
2.12 Show that, if \(B \in \mathbb{R}^{n \times m}\) and \(C \in \mathbb{R}^{m \times p}\), then \((BC)^T = C^T B^T\). [Hint: Check that the entries match.] \(\lhd\)
2.13 Let \(A \in \mathbb{R}^{n\times m}\) be an \(n\times m\) matrix with linearly independent columns. Show that \(m\leq n\).\(\lhd\)
2.14 Is the vector \(\mathbf{v} = (0,0,1)\) in the span of
\(\lhd\)
2.15 Given a vector \(\mathbf{v} = (1, 2, 3)\) and a plane spanned by \(\mathbf{u}_1 = (1, 0, 0)\) and \(\mathbf{u}_2 = (0, 1, 0)\), find the orthogonal projection of \(v\) onto the plane.
2.16 Given the orthonormal basis \(\{(1/\sqrt{2}, 1/\sqrt{2}), (-1/\sqrt{2}, 1/\sqrt{2})\}\), find the projection of the vector \(\mathbf{v} = (3, 3)\) onto the subspace spanned by this basis.
2.17 Find the orthogonal projection of the vector \(\mathbf{v} = (4, 3, 0)\) onto the line spanned by \(\mathbf{u} = (1, 1, 1)\) in \(\mathbb{R}^3\). \(\lhd\)
2.18 Let \(Q, W \in \mathbb{R}^{n \times n}\) be invertible. Show that \((Q W)^{-1} = W^{-1} Q^{-1}\) and \((Q^T)^{-1} = (Q^{-1})^T\). \(\lhd\)
2.19 Prove the Reducing a Spanning List Lemma. \(\lhd\)
2.20 Show that for any \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3 \in \mathbb{R}^n\) and \(\beta \in \mathbb{R}\):
a) \(\langle \mathbf{x}_1, \mathbf{x}_2 \rangle = \langle \mathbf{x}_2, \mathbf{x}_1 \rangle\)
b) \(\langle \beta \,\mathbf{x}_1 + \mathbf{x}_2, \mathbf{x}_3 \rangle = \beta \,\langle \mathbf{x}_1,\mathbf{x}_3\rangle + \langle \mathbf{x}_2,\mathbf{x}_3\rangle\)
c) \(\|\mathbf{x}_1\|^2 = \langle \mathbf{x}_1, \mathbf{x}_1 \rangle\)
\(\lhd\)
2.21 Using the notation introduced for Householder reflections, define
a) Show that \(\tilde{H}_1 \mathbf{y}_1 = - \|\mathbf{y}_1\| \,\mathbf{e}_1^{(n)}\).
b) Compute the matrix \(\tilde{H}_1\) in the case \(\mathbf{y}_1 = \|\mathbf{y}_1\| \,\mathbf{e}_1^{(n)}\). \(\lhd\)
2.22 Show that the product of two orthogonal matrices \(Q_1\) and \(Q_2\) is also orthogonal. \(\lhd\)
2.23 Establish that \((U^\perp)^\perp = U\). \(\lhd\)
2.24 Compute \(U^\perp \cap U\) and justify your answer. \(\lhd\)
2.25 (Adapted from [Sol]) If \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^m\) with \(\|\mathbf{x}\| = \|\mathbf{y}\|\), write an algorithm for finding an orthogonal matrix \(Q\) such that \(Q\mathbf{x} = \mathbf{y}\). \(\lhd\)
2.26 (Adapted from [Sol]) Suppose \(A \in \mathbb{R}^{m \times n}\) has rank \(m\), with \(m \leq n\). Let
be the QR decomposition of \(A^T\) obtained by the Gram-Schmidt algorithm. Provide a solution \(\mathbf{x}\) to the underdetermined system \(A\mathbf{x} = \mathbf{b}\) in terms of \(Q\) and \(R\). [Hint: Try the square case first. Then guess and check the solution to the general case by adding \(0\)’s.] \(\lhd\)
2.27 (Adapted from [Sol]) Let \(A \in \mathbb{R}^{m \times m}\) have full column rank and suppose \(L \in \mathbb{R}^{m \times m}\) is a lower triangular matrix with positive diagonal entries such that \(A^T A = L L^T\) (this is called a Cholesky decomposition).
a) Prove that \(L^T\) is invertible by showing that its columns are linearly independent.
b) Define \(Q = A(L^T)^{-1}\). Show that the columns of \(Q\) form an orthonormal list.
c) Give a QR decomposition of \(A\) using the matrix \(Q\) in (b). Make sure to show that \(R\) has the desired structure.
\(\lhd\)
2.28 (Adapted from [Sol]) Suppose \(A\in\mathbb{R}^{m\times n}\) has full column rank and \(A = QR\) be a QR decomposition obtained by the Gram-Schmidt algorithm. Show that \(P_0 = I_{m\times m} - QQ^T\) is the projection matrix onto the null space of \(A^T\). [Hint: Check the geometric characterization in the Orthogonal Projection Theorem.] \(\lhd\)
2.29 Suppose we consider \(\mathbf{a} \in \mathbb{R}^n\) as an \(n \times 1\) matrix. Write out its QR decomposition explicitly. \(\lhd\)
2.30 (Adapted from [Sol]) Show that a matrix \(A \in \mathbb{R}^{m \times n}\) with linearly independent columns can be factored into \(A = QL\), where \(L\) is lower triangular. [Hint: Modify our procedure to obtain the QR decomposition.] \(\lhd\)
2.31 (Adapted from [Sol]) Suppose \(A \in \mathbb{R}^{n \times p}\), \(B \in \mathbb{R}^{m \times p}\), \(\mathbf{a} \in \mathbb{R}^n\), and \(\mathbf{b} \in \mathbb{R}^m\). Find a linear system of equations satisfied by any \(\mathbf{x}\) minimizing \(\|A\mathbf{x} - \mathbf{a}\|^2 + \|B\mathbf{x} - \mathbf{b}\|^2\). [Hint: Rewrite the problem as a linear least squares problem.] \(\lhd\)
2.32 Let \(P\) be a projection matrix. Show that:
a) \(P^2 = P\)
b) \(P^T = P\)
c) Check the above two claims for the projection onto the span of \(\mathbf{u} = (1, 0, 1)\) in \(\mathbb{R}^3\).
\(\lhd\)
2.33 Show that for any \(\mathbf{x}_1, \ldots, \mathbf{x}_m, \mathbf{y}_1, \ldots, \mathbf{y}_\ell, \in \mathbb{R}^n\),
\(\lhd\)
2.34 Let \(A \in \mathbb{R}^{n\times m}\) be an \(n\times m\) matrix with \(n \geq m\) and let \(\mathbf{b} \in \mathbb{R}^n\) be a vector. Let
and \(\mathbf{x}^*\) be such that \(\mathbf{p}^* = A \mathbf{x}^*\). Construct an \(A\) and a \(\mathbf{b}\) such that \(\mathbf{x}^*\) is not unique. \(\lhd\)
2.35 Let \(H_k \in \mathbb{R}^{n \times n}\) be a matrix of the form
where
for some unit vector \(\mathbf{z}_k \in \mathbb{R}^{n - k + 1}\). Show that \(H_k\) is an orthogonal matrix. \(\lhd\)
2.36 Using the notation for Householder reflections, let \(A\) have linearly independent columns.
a) Assuming that \(\mathbf{z}_1 \neq \mathbf{0}\), show that \(\mathbf{y}_2 \neq \mathbf{0}\).
b) Assuming that \(\mathbf{z}_1, \mathbf{z}_2 \neq \mathbf{0}\), show that \(\mathbf{y}_3 \neq \mathbf{0}\). \(\lhd\)
2.37 Let \(R \in \mathbb{R}^{n \times m}\), with \(n \geq m\), be upper triangular with non-zero entries on the diagonal. Show that the columns of \(R\) are linearly independent. \(\lhd\)
2.38 Consider the linear regression problem on input data \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\).
a) Show that the problem has a unique solution if there are \(d+1\) vectors of the form
that form an independent list.
b) Simplify the previous condition in the case \(d=1\), i.e., when the \(x_i\)s are real-valued.
\(\lhd\)
2.39 Let \(U\) be a linear subspace of \(\mathbb{R}^n\) and assume that \(\mathbf{q}_1, \ldots, \mathbf{q}_k\) is an orthonormal basis of \(U\). Let \(\mathbf{v} \in \mathbb{R}^n\).
a) Show that the orthogonal projection of \(\mathbf{v}\) onto the subspace \(U^\perp\) (i.e., the orthogonal complement of \(U\)) is \(\mathbf{v} - \mathrm{proj}_U \mathbf{v}\). [Hint: Use the geometric characterization of the projection.]
b) Let \(Q\) be the matrix with columns \(\mathbf{q}_1, \ldots, \mathbf{q}_k\). Write the projection matrix onto the subspace \(U^\perp\) in terms of \(Q\). [Hint: Use a).]
\(\lhd\)
2.40 Prove the following claim, which is known as the Subspace Intersection Lemma. Let \(\mathcal{S}_1\) and \(\mathcal{S}_2\) be linear subspaces of \(\mathbb{R}^d\) and let
Then it holds that
[Hint: Consider a basis of \(\mathcal{S}_1 \cap \mathcal{S}_2\) and complete into bases of \(\mathcal{S}_1\) and \(\mathcal{S}_2\). Show that the resulting list of vectors is linearly independent.] \(\lhd\)
2.41 Let \(\mathcal{U}, \mathcal{V} \subseteq \mathbb{R}^d\) be subspaces such that \(\mathrm{dim}(\mathcal{U}) + \mathrm{dim}(\mathcal{V}) > d\). Use Problem 2.40 to show there exists a non-zero vector in the intersection \(\mathcal{U} \cap \mathcal{V}\). \(\lhd\)
2.42 Show that, for any linear subspaces \(\mathcal{S}_1, \ldots, \mathcal{S}_m\) of \(\mathcal{V} = \mathbb{R}^d\), it holds that
[Hint: Use the Subspace Intersection Lemma in Problem 2.40 and induction.] \(\lhd\)
2.43 Let \(\mathcal{W}\) be a linear subspace of \(\mathbb{R}^d\) and let \(\mathbf{w}_1,\ldots,\mathbf{w}_k\) be an orthonormal basis of \(\mathcal{W}\). Show that there exists an orthonormal basis of \(\mathbb{R}^d\) that includes the \(\mathbf{w}_i\)’s. \(\lhd\)
2.44 Let \(\mathcal{U}, \mathcal{V}\) be linear subspaces of \(V\) such that \(\mathcal{U} \subseteq \mathcal{V}\). Show that if \(\mathrm{dim}(\mathcal{U}) = \mathrm{dim}(\mathcal{V})\) then \(\mathcal{U} = \mathcal{V}\). [Hint: Complete the basis.] \(\lhd\)
2.45 Let \(\mathcal{U}, \mathcal{V}\) be linear subspaces of \(V\) such that \(\mathcal{U} \subseteq \mathcal{V}\). Show that if \(\mathrm{dim}(\mathcal{U}) < \mathrm{dim}(\mathcal{V})\) then there is a \(\mathbf{u} \in \mathcal{V}\) such that \(\mathbf{u} \notin \mathcal{U}\). [Hint: Complete the basis.] \(\lhd\)
2.46 Let \(\mathcal{Z} \subseteq \mathcal{W}\) be linear subspaces such that \(\mathrm{dim}(\mathcal{Z}) < \mathrm{dim}(\mathcal{W})\). Show that there exists a unit vector \(\mathbf{w} \in \mathcal{W}\) that is orthogonal to \(\mathcal{Z}\). \(\lhd\)
2.47 Let \(\mathcal{W} = \mathrm{span}(\mathbf{w}_1,\ldots,\mathbf{w}_\ell)\) and \(\mathbf{z} \in \mathcal{W}\) of unit norm. Show that there exists an orthonormal basis of \(\mathcal{W}\) that includes \(\mathbf{z}\). \(\lhd\)
2.48 Let \(\{\mathbf{u_1},\ldots,\mathbf{u}_m\}\) be an independent list. Show that for any nonzero \(\beta_1,\ldots,\beta_m \in \mathbb{R}\), the list \(\{\beta_1\mathbf{u_1},\ldots,\beta_m\mathbf{u}_m\}\) is also independent. \(\lhd\)
2.49 Let \(\mathcal{Z}\) be a linear subspace of \(\mathbb{R}^n\) and let \(\mathbf{v} \in \mathbb{R}^n\). Show that \(\|\mathrm{proj}_{\mathcal{Z}}\mathbf{v}\|_2 \leq \|\mathbf{v}\|_2\). \(\lhd\)