Orthogonal Matrices and Gram-Schmidt

In this lecture we finish introducing orthogonality. Using an orthonormal basis or a matrix with orthonormal columns makes calculations much easier. The Gram-Schmidt process starts with any basis and produces an orthonormal basis that spans the same space as the original basis.

Orthonormal Vectors

The vectors ${\mathbf{q}}_{\mathbf{1}},{\mathbf{q}}_{\mathbf{2}},\cdots ,{\mathbf{q}}_{\mathbf{n}}$ are orthonormal if:

$${{\mathbf{q}}_{\mathbf{i}}}^T{\mathbf{q}}_{\mathbf{j}}=\{\begin{array}{l}0,\text{ if }i\ne j\\ 1,\text{ if }i=j\end{array}$$

In other words, they all have (normal) length $1$ and are perpendicular(orthonormal) to each other. Orthonormal vectors are always independent.

Orthonormal Matrix

If the columns of $Q=[{\mathbf{q}}_{\mathbf{1}}\cdots {\mathbf{q}}_{\mathbf{n}}]$ are orthonormal, then $Q^{T}Q=I$ is the identity.

Matrices with orthonormal columns are a new class of important matrices to add to those on our list:

• triangular
• diagonal
• permutation
• symmetric
• reduced row echelon
• projection

We'll call them orthonormal matrices.

A square orthonormal matrix $Q$ is called an orthogonal matrix. If $Q$ is square, then $Q^{T}Q=I$ tells us that:

$$Q^T=Q^{-1}$$

For example, if $Q=\left[\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]$ then $Q^T=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]$. Both $Q$ and $Q^T$ are orthogonal matrices, and their product is the identity.

The matrix $Q=\left[\begin{array}{cc}cos\theta & -sin\theta \\ sin\theta & cos\theta \end{array}\right]$ is orthogonal. The matrix $\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$ is not, but we can adjust that matrix to get the orthogonal matrix $Q=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$. We can use the same tactic to find some larger orthogonal matrices called Hadamard matrices:

$$Q=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right]$$

An example of a rectangular matrix with orthonormal columns is:

$$Q=\frac{1}{3}\left[\begin{array}{cc}1& -2\\ 2& -1\\ 2& 2\end{array}\right]$$

We can extend this to a (square) orthogonal matrix:

$$\frac{1}{3}\left[\begin{array}{ccc}1& -2& 2\\ 2& -1& -2\\ 2& 2& 1\end{array}\right]$$

These examples are particularly nice because they don't include complicated square roots.

Orthonormal Columns are Good

Suppose $Q$ has orthonormal columns, The matrix that projects onto the column space of $Q$ is:

$$P=Q(Q^{T}Q{)}^{-1}{Q}^T$$

If the columns of $Q$ are orthonormal, then $Q^{T}Q=I$ and $P=Q{Q}^T$. If $Q$ is square, then $P=I$ because the columns of $Q$ span the entire space.

Many equations become trivial when using a matrix with orthonormal columns. If our basis is orthonormal, the projection component $\widehat{x_i}$ is just ${{\mathbf{q}}_{\mathbf{i}}}^T\mathbf{b}$ because $A^{T}A\hat{x}=A^T\mathbf{b}$ becomes $\hat{\mathbf{x}}=Q^T\mathbf{b}$.

Gram-Schmidt

With elimination, our goal was make the matrix triangular. Now our goal is make the matrix orthonormal.

We start with two independent vectors $\mathbf{a}$ and $\mathbf{b}$ and want to find orthonormal vectors ${\mathbf{q}}_{\mathbf{1}}$ and ${\mathbf{q}}_{\mathbf{2}}$ that span the same plane. We start by finding orthogonal vectors $\mathbf{A}$ and $\mathbf{B}$ that span the same space as $\mathbf{a}$ and $\mathbf{b}$. Then the unit vectors ${\mathbf{q}}_{\mathbf{1}}=\frac{\mathbf{A}}{||\mathbf{A}||}$ and ${\mathbf{q}}_{\mathbf{2}}=\frac{\mathbf{B}}{||\mathbf{B}||}$ from the desired orthonormal basis.

Let $\mathbf{A}=\mathbf{a}$. We get a vector orthogonal to $\mathbf{A}$ in the space spanned by $\mathbf{a}$ and $\mathbf{b}$ by projecting $\mathbf{b}$ onto $\mathbf{a}$ and letting $\mathbf{B}=\mathbf{b}-\mathbf{p}$. ($\mathbf{B}$ is what we previously called $\mathbf{e}$.)

$$\mathbf{B}=\mathbf{b}-\frac{{\mathbf{A}}^T\mathbf{b}}{{\mathbf{A}}^T\mathbf{A}}\mathbf{A}$$

If we multiply both sides of this equation by ${\mathbf{A}}^T$, we see that ${\mathbf{A}}^T\mathbf{B}=\mathbf{0}$

What if we had started with three independent vectors, $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{c}$? Then we'd find a vector $\mathbf{C}$ orthogonal to both $\mathbf{A}$ and $\mathbf{B}$ by subtracting from $\mathbf{c}$ its components in the $\mathbf{A}$ and $\mathbf{B}$ directions:

$$\mathbf{C}=\mathbf{c}-\frac{{\mathbf{A}}^T\mathbf{c}}{{\mathbf{A}}^T\mathbf{A}}\mathbf{A}-\frac{{\mathbf{B}}^T\mathbf{c}}{{\mathbf{B}}^T\mathbf{B}}\mathbf{B}$$

For example, suppose $\mathbf{a}=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$ and $\mathbf{b}=\left[\begin{array}{c}1\\ 0\\ 2\end{array}\right]$. Then $\mathbf{A}=\mathbf{a}$ and:

$$\begin{array}{rl}\mathbf{B}& =\left[\begin{array}{c}1\\ 0\\ 2\end{array}\right]-\frac{{\mathbf{A}}^T\mathbf{b}}{{\mathbf{A}}^T\mathbf{A}}\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\\ & =\left[\begin{array}{c}1\\ 0\\ 2\end{array}\right]-\frac{3}{3}\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\\ & =\left[\begin{array}{c}0\\ -1\\ 1\end{array}\right]\end{array}$$

Normalizing, we get:

$$Q=[{\mathbf{q}}_{\mathbf{1}}{\mathbf{q}}_{\mathbf{2}}]=\left[\begin{array}{cc}1/\sqrt{3}& 0\\ 1/\sqrt{3}& -1/\sqrt{2}\\ 1/\sqrt{3}& 1/\sqrt{2}\end{array}\right]$$

The column space of $Q$ is the plane spanned by $\mathbf{a}$ and $\mathbf{b}$.

When we studied elimination, we wrote the process in terms of matrices and found $A=LU$. A similar equation $A=QR$ relates our starting matrix $A$ to the result $Q$ of the Gram-Schmidt process. Where $L$ was lower triangular, $R$ is upper triangular.

Suppose $A=[{\mathbf{a}}_{\mathbf{1}}{\mathbf{a}}_{\mathbf{2}}]$, then:

$$A=QR$$

$$\left[\begin{array}{cc}{\mathbf{a}}_{\mathbf{1}}& {\mathbf{a}}_{\mathbf{2}}\end{array}\right]=\left[\begin{array}{cc}{\mathbf{q}}_{\mathbf{1}}& {\mathbf{q}}_{\mathbf{2}}\end{array}\right]\left[\begin{array}{cc}{{\mathbf{a}}_{\mathbf{1}}}^T{\mathbf{q}}_{\mathbf{1}}& {{\mathbf{a}}_{\mathbf{2}}}^T{\mathbf{q}}_{\mathbf{1}}\\ {{\mathbf{a}}_{\mathbf{1}}}^T{\mathbf{q}}_{\mathbf{2}}& {{\mathbf{a}}_{\mathbf{2}}}^T{\mathbf{q}}_{\mathbf{2}}\end{array}\right]$$

If $R$ is upper triangular, then it should be true that ${{\mathbf{a}}_{\mathbf{1}}}^T{\mathbf{q}}_{\mathbf{2}}=0$. This must be true because we chose ${\mathbf{q}}_{\mathbf{1}}$ to be a unit vector in the direction of ${\mathbf{a}}_{\mathbf{1}}$. All the latter ${\mathbf{q}}_{\mathbf{i}}$ were chosen to be perpendicular to the earlier ones.

Notice that $R=Q^{T}A$. This makes sense; $Q^{T}Q=I$.