Skip to content

4.4-final-2000

Final Exam, 2000 · Section 4.4: Orthonormal Bases and Gram-Schmidt Source: finalexam_1.pdf, p. 46

Problem

3. Gram-Schmidt is \(A = QR\) (start from rectangular \(A\) with independent columns, produce \(Q\) with orthonormal columns and upper triangular \(R\)). The problem is to produce the same \(Q\) and \(R\) from ordinary (symmetric) elimination on \(A^{T}A\) which gives

\[ A^{T}A = LDL^{T} = R^{T}R \quad (\text{with } R = \sqrt{D}L^{T}). \]

(a) (4 points) How do you know that the pivots are positive, so \(\sqrt{D}\) gives real numbers?

(b) (4 points) From \(A^{T}A = R^{T}R\) show that the matrix \(Q = AR^{-1}\) has orthonormal columns (what is the test?). Then we have \(A = QR\).

(c) (4 points) Apply Gram-Schmidt to these vectors \(a_1\) and \(a_2\), producing \(q_1\) and \(q_2\). Write your result as \(QR\):

\[ a_1 = \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix} \quad a_2 = \begin{bmatrix} \sin \theta \\ 0 \end{bmatrix}. \]
Solution (a) For \(x \neq 0\), \(x^T(A^TA)x = (Ax)^T(Ax) = \|Ax\|^2 > 0\), because \(A\) has independent columns, so \(Ax \neq 0\). Thus \(A^TA\) is positive definite, and positive definite matrices have positive pivots (elimination needs no row exchanges and every pivot is positive). (b) The test is \(Q^TQ = I\): \[ Q^TQ = (AR^{-1})^T(AR^{-1}) = R^{-T}A^TA R^{-1} = R^{-T}R^TR R^{-1} = I. \] (c) \(a_1\) is already a unit vector, so \(q_1 = \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix}\). Then \[ a_2 - (a_2^Tq_1)q_1 = \begin{bmatrix} \sin \theta \\ 0 \end{bmatrix} - \sin\theta\cos\theta \begin{bmatrix} \cos\theta \\ \sin\theta \end{bmatrix} = \sin^2\theta \begin{bmatrix} \sin\theta \\ -\cos\theta \end{bmatrix}, \] whose length is \(\sin^2\theta\). So \(q_2 = \begin{bmatrix} \sin\theta \\ -\cos\theta \end{bmatrix}\) and \[ A = QR = \begin{bmatrix} \cos\theta & \sin\theta \\ \sin\theta & -\cos\theta \end{bmatrix} \begin{bmatrix} 1 & \sin\theta\cos\theta \\ 0 & \sin^2\theta \end{bmatrix}. \]

Keywords: Gram-Schmidt, QR factorization, positive definite, pivots