# SubsectionThe assignment

• Read section 4.4 of Strang.
• Read the following and complete the exercises below.

# SubsectionLearning Goals

Before class, a student should be able to:

• Correctly decide if a matrix is orthogonal or not.
• Use the Gram-Schmidt algorithm to turn a basis into an orthonormal basis.

Some time after class, a student should be able to:

• Find the QR decomposition of a matrix.
• Describe the Gram-Schmidt process geometrically using orthogonal projections.

# SubsectionDiscussion: Gram-Schmidt

There are four main points to take away from this section:

• The idea of an orthonormal basis.
• The idea of an orthogonal matrix. The special property that $Q^T = Q^{-1}$ for an orthogonal matrix $Q$.
• The Gram-Schimdt algorithm for constructing an orthonormal basis.
• The $QR$ decomposition of a matrix $A$.

# SubsectionSage and the QR decomposition

Sage has a built-in command to find the QR decomposistion of a matrix. Essentially, it does the Gram-Schmidt algorithm under the hood.

If you check the documentation, you will see that the matrix has to be defined over a special type of ring, so use QQbar.

This matrix should be an orthogonal matrix. Let's check that.

That is machine language for “I am pretty sure that's the identity.” Those question marks are for machine precision representation of exact numbers.

# SubsectionExercises

(Strang ex. 4.4.12) If $a_1$, $a_2$, $a_3$ is a basis for $\mathbb{R}^3$, then any vector $b$ can be written as \begin{equation*} b = x_1 a_1 + x_2 a_2 + x_3 a_3 \end{equation*} or \begin{equation*} \begin{pmatrix} | & | & | \\ a_1 & a_2 & a_3 \\ | & | & | \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = b. \end{equation*}
1. Suppose the $a_i$'s are orthonormal. Show that $x_1 = a_1^T b$.
2. Suppose the $a_i$'s are orthogonal. Show that $x_1 = a_1^T b / a_1^T a_1$.
3. If the $a_i$'s are independent, $x_1$ is the first component of something times b. What is the something?
(Strang ex. 4.4.18) Find orthogonal vectors $A$, $B$, $C$ by Gram-Schmidt from $a$, $b$, $c$: \begin{equation*} a = (1,-1,0,0), \quad b = (0,1,-1,0), \quad c = (0,0,1,-1). \end{equation*} Note that both of these collections are bases for the hyperplane perpendicular to $(1,1,1,1)$.
(Strang ex. 4.4.19) If $A = QR$, then check that $A^TA$ is the same thing as $R^TR$. What can we say about the shape of the matrix $R$? Note that this means that Gram-Schmidt on $A$ corresponds to elimination on $A^TA$! The pivots for $A^TA$ must be the squares of the diagonal entries of $R$. Find $Q$ and $R$ by Gram-Schmidt for this $A$: \begin{equation*} A = \begin{pmatrix} -1 & 1 \\ 2 & 1 \\ 2 & 4 \end{pmatrix}. \end{equation*} Compare with the structure of this matrix: \begin{equation*} A^TA = \begin{pmatrix} 9 & 9 \\ 9 & 18 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 9 & 0 \\ 0 & 9 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. \end{equation*}
(Strang ex. 4.4.21) Find an orthonormal basis for the column space of $A$, and then compute the projection of $b$ onto that column space. \begin{equation*} A = \begin{pmatrix} 1 & -2 \\ 1 & 0 \\ 1 & 1 \\ 1 & 3\end{pmatrix} \qquad \text{ and } \qquad b = \begin{pmatrix} -4 \\ -3 \\ 3 \\ 0 \end{pmatrix}. \end{equation*}
(Strang ex. 4.4.23) Let $a$, $b$, $c$ be the columns of the matrix \begin{equation*} A = \begin{pmatrix} 1 & 2 & 4 \\ 0 & 0 & 5 \\ 0 & 3 & 6 \end{pmatrix} \end{equation*} Note that these vectors are linearly independent, so make a basis for $\mathbb{R}^3$. Find an orthonormal basis $q_1$, $q_2$, $q_3$ and express the vectors as linear combinations of $a$, $b$, $c$. Finally, write $A$ as $QR$.
1. Find a basis for the subspace $S$ in $\mathbb{R}^4$ spanned by all solutions of \begin{equation*} x_1 + x_2 + x_3 - x_4 = 0. \end{equation*}
2. Find a basis for the orthogonal complement $S^{\perp}$.
3. Find $b_1$ in $S$ and $b_2$ in $S^{\perp}$ so that $b_1 + b_2 = b = (1,1,1,1)$.