### Orthogonal basis

• Orthonormal vectors:
$q^T_iq_j= \begin{cases} 0 \text{ if } i \neq j \\ 1 \text{ if } i = j \\ \end{cases}$
• Each vector is a unit vector (i.e. has length one).

• A set of orthonormal vectors is also a set of independent vectors.

• Orthonormal vectors make calculations nice, a lot of linear algebra in practice is built around them.

### Matrix with orthonormal columns

• A matrix with an orthonormal columns (each column is independent and has length 1):
$Q= \begin{bmatrix} \begin{array}{rcr} & & \\ q_1 & ... & q_n \\ & & \\ \end{array} \end{bmatrix}$
• Note that $$Q^TQ=I$$.

• If a matrix with orthonormal columns is square, then we call it an orthogonal matrix:
• Then $$Q^TQ=I$$ tells us $$Q^T=Q^{-1}$$
• An example is a permutation matrix
• Adhemar (sp?) matrices are matrices of 1s and -1s that are orthogonal. We know they exist for some sizes (e.g. 2x2, 4x4, 16x16, 64x64) but we don’t know in general which sizes allow for this.

• “The punishing thing about Gram-Schmidt is that we always run into square roots”

• Why do we want orthonormal matrices? What calculation is made easier?

• Suppose $$Q$$ has orthonormal columns. Project onto its column space.
$P=Q(Q^TQ)^{-1}Q^T$ $P=Q(I)^{-1}Q^T$ $P=QQ^T$
• If you have a square $$Q$$, then because of the orthonormal columns, then the matrix is full rank and any $$b$$ will be in the column space and thus $$QQ^T = I$$

• Two properties of any projection matrix:
• It’s symmetric
• And $$(QQ^T)(QQ^T) = QQ^T$$
• Remember $$A^TA\hat{x}=A^Tb$$, with orthogonal $$Q$$:
$Q^TQ\hat{x}=Q^Tb$ $I\hat{x}=Q^Tb$ $\hat{x}=Q^Tb$ $\hat{x}_i=q_i^Tb$

### Gram-Schmidt

• Start with independent vectors and turn them into an orthonormal basis.

• Given independent vectors $$a$$, $$b$$, and $$c$$, what’s an orthonormal basis ($$q_1$$, $$q_2$$, $$q_3$$) for the space they span?
• First, get orthogonal vectors $$A$$, $$B$$, and $$C$$
• Second, get orthonormal vectors $$q_1=\frac{A}{\lvert \lvert A\rvert\rvert}$$, $$q_2=\frac{B}{\lvert \lvert B\rvert\rvert}$$, and $$q_2=\frac{C}{\lvert \lvert C\rvert\rvert}$$,
• Idea: keep $$a$$ and then project $$b$$ onto an orthogonal subspace and then do the same for $$c$$ with respect to $$a$$ and $$b$$. Essentially we’re interested in the error component of the projection of $$b$$ onto $$a$$.

• For $$B$$:
$p=b-e$ $e=b-p$ $B=b-p$ $B=b-\frac{A^Tb}{A^TA}A$
• For $$C$$:
$C = c - \frac{A^Tc}{A^TA}A - \frac{B^Tc}{B^TB}B$
• You can think of (for example) $$\frac{A^Tc}{A^TA}A$$ as the component of $$c$$ in the $$a$$ direction that we’re subtracting off.

• Works through a numerical example starting at 38:15.

$a= \begin{bmatrix} \begin{array}{r} 1 \\ 1 \\ 1 \\ \end{array} \end{bmatrix} b= \begin{bmatrix} \begin{array}{r} 1 \\ 0 \\ 2 \\ \end{array} \end{bmatrix}$ $A=a$ $B=b - \frac{A^Tb}{A^TA}A$ $B=b - \frac{3}{3}A$ $B=\begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$ $B= \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}$ $q_1= \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$ $q_2= \frac{1}{\sqrt{2}}\begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}$
• The column space of $$A$$ and its orthonormal $$Q$$ calculated via Gram-Schmidt is the same.

• $$A=QR$$ is the magic formula expressing Gram-Schmidt (similar to $$A=LU$$ we saw earlier).

• $$R$$ is upper triangular.
$A=QR$ $\begin{bmatrix} && \\ a_1 && a_2 \\ && \\ \end{bmatrix} = \begin{bmatrix} && \\ q_1 && q_2 \\ && \\ \end{bmatrix} * \begin{bmatrix} a_1^Tq_1 && ... \\ a_1^Tq_2 && ... \\ \end{bmatrix}$
• Note $$a_1^Tq_2=0$$ because the later $$q$$’s are perpendicular to all the earlier vectors.