\section{ Gram-Schmidt and Orthogonal Complements }


\edz{Put pictures here?}
Given a vector $u$ and some other vector $v$ not in the span of $u$, we can construct a new vector: 
\[
v^\perp=v-\frac{u\cdot v}{u\cdot u}u.
\]
This new vector $v^\perp$ is orthogonal to $u$ because 
\[
u\dotprod v^\perp = u\dotprod v - \frac{u\cdot v}{u\cdot u}u\dotprod u = 0.
\]
Hence, $\{u, v^\perp\}$ is an orthogonal basis for $\spa \{u,v\}$.  When $v$ is not parallel to $u$, $v^\perp \neq 0$, and normalizing these vectors we obtain $\{\frac{u}{|u|}, \frac{v^\perp}{|v^\perp|} \}$, an orthonormal basis.

Sometimes we write $v = v^\perp + v^\parallel$ where:
\begin{eqnarray*}
v^\perp &=& v-\frac{u\cdot v}{u\cdot u}u \\
v^\parallel &=& \phantom{v-}\frac{u\cdot v}{u\cdot u}u.
\end{eqnarray*}
This is called an \emph{orthogonal decomposition}\index{Orthogonal decomposition} because we have decomposed $v$ into a sum of orthogonal vectors.  It is significant that we wrote this decomposition with $u$ in mind; $v^\parallel$ is parallel to $u$.

If $u$, $v$ are linearly independent vectors in $\Re^3$, then the set $\{u, v^\perp, u\times v^\perp \}$ would be an orthogonal basis for $\Re^3$.  This set could then be normalized by dividing each vector by its length to obtain an orthonormal basis.

However, it often occurs that we are interested in vector spaces with dimension greater than $3$, and must resort to craftier means than cross products to obtain an orthogonal basis.
\footnote{Actually, given a set $T$ of $(n-1)$ independent vectors in $n$-space, one can define an analogue of the cross product that will produce a vector orthogonal to the span of $T$, using a method exactly analogous to the usual computation for calculating the cross product of two vectors in $\Re^3$.  This only gets us the \emph{last} orthogonal vector, though; the process in this Section gives a way to get a full orthogonal basis.}

Given a third vector $w$, we should first check that $w$ does not lie in the span of $u$ and $v$, \textit{i.e.} check that $u,v$ and $w$ are linearly independent.   We then can define:
\[
w^\perp = w - \frac{u\cdot w}{u\cdot u}\,u - \frac{v^\perp\cdot w}{v^\perp\cdot v^\perp}\,v^\perp.
\]

\edz{Put in the computation!}
One can check by directly computing $u\dotprod w^\perp$ and $v^\perp\dotprod w^\perp$ that $w^\perp$ is orthogonal to both $u$ and $v^\perp$; as such, $\{u,v^\perp,w^\perp \}$ is an orthogonal basis for $\spa \{u,v,w\}$.

In fact, given a collection $\{v_1, v_2, \ldots \}$ of linearly independent vectors, we can produce an orthogonal basis for $\spa \{v_1,v_2, \ldots \}$ consisting of the following vectors:
\begin{eqnarray*}
v_1^\perp&=&v_1 \\
v_2^\perp &=& v_2 - \frac{v_1\cdot v_2}{v_1\cdot v_1}\,v_1 \\
&\vdots& \\
v_3^\perp &=& v_3 - \frac{v_1^\perp\cdot v_3}{v_1^\perp\cdot v_1^\perp}\,v_1^\perp - \frac{v_2^\perp\cdot v_3}{v_2^\perp\cdot v_2^\perp}\,v_2^\perp\\
&\vdots& \\
v_i^\perp&=& v_i - \sum_{j<i} \frac{v_j^\perp\cdot v_i}{v_j^\perp\cdot v_j^\perp}\,v_j^\perp \\
 &=& v_i - \frac{v_1^\perp\cdot v_i}{v_1^\perp\cdot v_1^\perp}\,v_1^\perp - \ldots - \frac{v_{n-1}^\perp\cdot v_i}{v_{n-1}^\perp\cdot v_{n-1}^\perp}\,v_{n-1}^\perp\\
&\vdots& \\
\end{eqnarray*}
Notice that each $v_i^\perp$ here depends on the existence of $v_j^\perp$ for every $j<i$.  This allows us to inductively/algorithmically build up a linearly independent, orthogonal set of vectors whose span is $\spa \{v_1, v_2, \ldots \}$. This algorithm bears the name \emph{Gram--Schmidt orthogonalization procedure}\index{Gram--Schmidt orthogonalization procedure}.

\begin{example}
Let $u=\rowvec{1&1&0}, v=\rowvec{1&1&1},$ and $w=\rowvec{3&1&1}$.  We'll apply Gram-Schmidt to obtain an orthogonal basis for $\Re^3$.

First, we set $u^\perp=u$.  Then:
\begin{eqnarray*}
v^\perp&=& \rowvec{1&1&1} - \frac{2}{2}\rowvec{1&1&0} = \rowvec{0&0&1} \\
w^\perp&=& \rowvec{3&1&1} - \frac{4}{2}\rowvec{1&1&0} - \frac{1}{1}\rowvec{0&0&1} = \rowvec{1&-1&0}. 
\end{eqnarray*}
Then the set
\[
\{ \rowvec{1&1&0},\rowvec{0&0&1},\rowvec{1&-1&0}\}
\]
is an orthogonal basis for $\Re^3$.  To obtain an orthonormal basis, as always we simply divide each of these vectors by its length, yielding:
\[
\{ \rowvec{\frac{1}{\sqrt2}&\frac{1}{\sqrt2}&0},\rowvec{0&0&1},\rowvec{\frac{1}{\sqrt2}&\frac{-1}{\sqrt2}&0}\}.
\]
\end{example}

\subsection{Orthogonal Complements}

Let $U$ and $V$ be subspaces of a vector space $W$.  We saw as a review exercise that $U\cap V$ is a subspace of $W$, and that $U\cup V$ was not a subspace.  However, $\spa U\cup V$ is certainly a subspace, since the span of \emph{any} subset is a subspace.

Notice that all elements of $\spa U\cup V$ take the form $u+v$ with $u\in U$ and $v\in V$.  We call the subspace 
\[
\spa U\cup V = \{u+v | u\in U, v\in V \} = U+V
\] 
the \emph{sum}\index{Sum of vectors spaces} of $U$ and $V$.  Here, we are not adding vectors, but vector spaces to produce a new vector space!

\begin{definition}
Given two subspaces $U$ and $V$ of a space $W$ such that $U\cap V=\{0_W\}$, the \emph{direct sum}\index{Direct sum} of $U$ and $V$ is defined as:
\[
U \oplus V = \spa U \cup V = \{u+v | u\in U, v\in V \}.
\]
\end{definition}

The direct sum has a very nice property.

\begin{theorem}
Let $w=u+v\in U\oplus V$.  Then the expression $w=u+v$ is unique.  
\end{theorem}

\begin{proof}
Suppose that $u+v=u'+v'$, with $u,u'\in U$, and $v,v' \in V$.  Then we could express $0=(u-u')+(v-v')$.  Then $(u-u')=-(v-v')$.  Since $U$ and $V$ are subspaces, we have $(u-u')\in U$ and $-(v-v')\in V$.  But since these elements are equal, we also have $(u-u')\in V$.  Since $U\cap V=\{0\}$, then $(u-u')=0$.  Similarly, $(v-v')=0$, proving the theorem. 
\end{proof}

Given a subspace $U$ in $W$, we would like to write $W$ as the direct sum of $U$ and \emph{something}.  Using the inner product, there is a natural candidate for this second subspace.

\begin{definition}
Given a subspace $U$ of a vector space $W$, define:
\[
U^\perp = \{w\in W | w\dotprod u=0 \text{ for all } u\in U\}.
\]
\end{definition}

The set $U^\perp$ (pronounced ``$U$-perp'') is the set of all vectors in $W$ orthogonal to \emph{every} vector in $U$.  This is also often called the \emph{orthogonal complement}\index{Orthogonal complement} of $U$.

\begin{theorem}
Let $U$ be a subspace of a finite-dimensional vector space $W$.  Then the set $U^\perp$ is a subspace of $W$, and $W=U\oplus U^\perp$\index{``Perp''}.
\end{theorem}

\begin{proof}
To see that $U^\perp$ is a subspace, we only need to check closure, which requires a simple check.

We have $U\cap U^\perp=\{0\}$, since if $u\in U$ and $u\in U^\perp$, we have:
\[
u\dotprod u = 0 \Leftrightarrow u=0.
\]

Finally, we show that any vector $w\in W$ is in $U\oplus U^\perp$.  (This is where we use the assumption that $W$ is finite-dimensional.)  Let $e_1, \ldots, e_n$ be an orthonormal basis for $W$.  Set: 
\begin{eqnarray*}
u&=&(w\dotprod e_1)e_1 + \ldots + (w\dotprod e_n)e_n \in U\\
u^\perp&=& w-u
\end{eqnarray*}
It is easy to check that $u^\perp \in U^\perp$ (see the Gram-Schmidt procedure).  Then $w=u+u^\perp$, so $w\in U\oplus U^\perp$, and we are done.
\end{proof}

\begin{example}
Consider any plane $P$ through the origin in $\Re^3$.  Then $P$ is a subspace, and $P^\perp$ is the line through the origin orthogonal to $P$.  For example, if $P$ is the $xy$-plane, then
\[
\Re^3=P\oplus P^\perp=\{(x,y,0)| x,y\in \Re \} \oplus \{(0,0,z)| z\in \Re \}.
\]
\end{example}

Notice that for any subspace $U$, the subspace $(U^\perp)^\perp$ is just $U$ again.  As such, $\perp$ is an involution on the set of subspaces of a vector space.



\section*{References}
\begin{itemize}
\item Hefferon, Chapter Three, Section VI.2: Gram-Schmidt Orthogonalization
\end{itemize}

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Gram_schmidt}{Gram-Schmidt Process}
\item \href{http://en.wikipedia.org/wiki/Orthonormal_basis}{Orthonormal Basis}
\item \href{http://en.wikipedia.org/wiki/Direct_sum}{Direct Sum}
\end{itemize}


\section*{Review Questions}

\begin{enumerate}
\item Suppose $u$ and $v$ are linearly independent.  Show that $u$ and $v^\perp$ are also linearly independent.  Explain why $\{u, v^\perp\}$ are a basis for $\spa \{u,v\}$.

\item Repeat the previous problem, but with three independent vectors $u,v,w$, and $v^\perp$ and $w^\perp$ as defined in the lecture.  

\item Given any three vectors $u,v,w$, when do $v^\perp$ or $w^\perp$ vanish?

\item This question will answer the question, ``If I choose a vector \emph{at random}\index{Random}, what is the probability that it lies in the span of some other vectors?''

\item For $U$ a subspace of $W$, use the subspace theorem to check that $U^\perp$ is a subspace of $W$.

\begin{itemize}
\item[$i.$] Given a collection $S$ of $k$ vectors in $\Re^n$, consider the matrix $M$ whose columns are the vectors in $S$.  Show that $S$ is linearly independent if and only if the kernel of $M$ is trivial.

\item[$ii.$] Give some method for choosing a random vector $v$.  Suppose $S$ is a collection of $k$ linearly independent vectors in $\Re^n$.  How can we tell whether $S\cup \{v\}$ is linearly independent?  Do you think it is likely or unlikely that $S\cup \{v\}$ is linearly independent?  Explain your reasoning.

\item[$iii.$]  Let $M$ be an $n\times n$ diagonalizable matrix whose eigenvalues are chosen uniformly at random.  (\textit{i.e.} every real number has equal chance of being an eigenvalue.)  What is the probability that the columns of $M$ form a basis for $\Re^n$?  (Hint: What is the relationship between the kernel of $M$ and its eigenvalues?)
\end{itemize}


\end{enumerate}

\newpage
