\documentclass[11pt]{article}

\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}

%\pagestyle{empty}
\topmargin -0.75in
\oddsidemargin -0.25in
\evensidemargin -0.25in
\textheight 9.25in
\textwidth 7.0in 

\definecolor{ignoreGray}{rgb}{0.75,0.75,0.75}
\newcommand{\ig}{\color{ignoreGray}}

\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\newcommand{\B}[1]{{\bf #1}}
\newcommand{\bdot}{\,{\bf\bullet}\,}

\newcommand{\E}[2]{\B e_{#1}\B e_{#2}^T}

\newcommand{\force}{{$\mbox{\;}$}}

\begin{document}

\noindent \hfill
\fbox{\fbox{\parbox{6.9in}{{\scshape{Linear Algebra \hfill Gram-Schmidt Orthogonalization}} }}} \hfill 

\vspace{0.15in}

\noindent {\bf\large Definition:} Let $V$ be an inner product space. We say $\B v, \B w \in V$ are {\bf orthogonal} if $\langle \B v, \B w \rangle=0$. If $S \subseteq V$ and for all $\B v, \B w \in S$ and $\B v \not= \B w$ we have $\langle \B v, \B w \rangle=0$, then we say $S$ is an {\bf orthogonal} set. If $\B u \in V$ and $\|\B u \|=1$, we say $\B u$ is a {\bf unit vector}. Notice that any non-zero vector $\B v \in V$ can be {\bf normalized} (i.e. $\B u = \B v / \|\B v\|$) and turned into a unit vector. If $S$ is an orthogonal set of unit vectors, $S$ is called an {\bf orthonormal} set. It is not hard to show that an orthogonal set is linearly independent if and only if the zero vector does not belong to the set. In particular, an orthonormal set is always linearly independent.

\vspace{0.05in}

Coordinates and norms work particularly well in the context of orthogonal or orthonormal bases. Suppose that $\beta = \{ \B v_1, \dots, \B v_n \}$ is an orthogonal basis.  Let $\B v \in V$ and write $\B v = \sum\limits_{i=1}^n c_i \B v_i$. Then we have that $\langle \B v, \B v_i \rangle = \left\langle \sum\limits_{j=1}^n c_j\B v_j, \B v_i \right\rangle = \sum\limits_{j=1}^n c_j \langle \B v_j, \B v_i \rangle = c_i \langle \B v_i, \B v_i \rangle = c_i \|\B v_i\|^2$ where the sum collapses out since the inner products for $i\not=j$ yield zeros. So this means that $\B v = \sum\limits_{i=1}^n \dfrac{\langle \B v, \B v_i \rangle}{\|\B v_i\|^2} \B v_i$. So coordinates can be computed just using inner products! When our basis $\beta$ is orthonormal (i.e. $\|\B v_i\|=1$) this is even nicer: $\B v = \sum\limits_{i=1}^n \langle \B v, \B v_i\rangle \B v_i$. In this case the {\it coordinates are the inner products with $\B v$}. 

Suppose that $S=\{\B w_1,\dots,\B w_n \}$ is orthogonal. Then $$\|\B w_1+\cdots+\B w_n \|^2 = \left\langle \sum\limits_{i=1}^n \B w_i, \sum\limits_{j=1}^n \B w_j \right\rangle = \sum\limits_{i=1}^n \sum\limits_{j=1}^n \langle \B v_i, \B v_j \rangle = \sum\limits_{i=1}^n \langle \B w_i,\B w_i \rangle = \|\B w_1\|^2+\cdots+\|\B w_n\|^2$$ where one of the sums drops out because $\langle \B w_i,\B w_j \rangle=0$ if $i \not= j$. This then implies that if $\beta = \{\B v_1,\dots,\B v_n \}$ is an orthonormal basis, then $\| \B v\|^2 = \sum_{i=1}^n \|\langle \B v, \B v_i \rangle \B v_i\|^2 = \sum\limits_{i=1}^n |\langle \B v, \B v_i \rangle|^2$ (i.e. the length of $\B v$ is the sum of the squares of the lengths of its coordinates.

\vspace{0.15in}

Let $\alpha = \{ \B w_1,\dots, \B w_n \}$ be a linearly independent set. Recursively define a set $\beta =\{ \B v_1,\dots, \B v_n \}$ as follows:
$$\B v_1 = \B w_1 \qquad \qquad \B v_{n+1} = \B w_{n+1} - \mathrm{proj}_{\B v_1}(\B w_{n+1}) - \cdots - - \mathrm{proj}_{\B v_n}(\B w_{n+1})$$
where $\mathrm{proj}_{\B v}(\B w) = \dfrac{\langle \B w, \B v \rangle}{\|\B v\|^2}\B v$ is the orthogonal projection of $\B w$ onto $\B v$.  These sets then have the property that $\mathrm{span}\{\B w_1,\dots, \B w_j \}= \mathrm{span}\{\B v_1,\dots,\B v_j \}$ for each $j=1,\dots,n$ and $\beta = \{\B v_1,\dots,\B v_n\}$ is orthogonal (and linearly independent). In particular, if $\alpha$ is a basis for $V$, then $\beta$ is an orthogonal basis for $V$. Computing the $\B v_i$'s is called the {\bf Gram-Schmidt} orthogonalization process. If we add in the additional step of normalizing the elements of $\beta$, then we will have an orthonormal basis for $V$. 

One consequence of the Gram-Schmidt algorithm is that {\it every finite dimensional inner product space has an orthonormal basis}. Let $\beta = \{ \B v_1,\dots, \B v_n\}$ be an orthonormal basis for $V$. Recall that $\B e_i = (0,\dots,0,1,0,\dots,0)$ with $1$ in the $i$-th position. Define a linear map $\varphi$ that sends $\B v_i$ to $\B e_i$ for $i=1,\dots,n$. This map is an isomorphism (since we send a basis to a basis) and $\varphi(\langle \B v, \B w \rangle) = \varphi(\B v) \bdot \varphi(\B w)$ (it preserves inner products). Thus $V \cong \mathbb{F}^n$ (isomorphic not only as vector spaces but also as inner product spaces). So in a sense, the only inner product one can have on a finite dimensional inner product space is the dot product (up to isomorphism).

It is worth mentioning that if you start with merely a spanning set, Gram-Schmidt will still produce an orthogonal basis -- if we toss out the zero vector anytime it appears (if a vector is linearly dependent on previous vectors, once we subtract out projections, nothing will be left).

\vspace{0.15in}

\noindent {\bf\large Example:} Consider $S = \{\B w_1, \B w_2, \B w_3, \B w_4 \} = \{ (1,0,0,i), (1+i,1,1,1+i),(3+i,1,1,1+3i),(0,1+2i,0,1) \}$. 

\vspace{0.1in}

\hspace*{-0.35in}\begin{minipage}{7.25in}
\begin{itemize}
\item $\B v_1 = \B w_1 = (1,0,0,i)$
\item $\B v_2 = \B w_2 - \dfrac{\B w_2 \bdot \B v_1}{\|\B v_1 \|^2}\B v_1 = (1+i,1,1,1+i) - \dfrac{2}{2}(1,0,0,i) = (i,1,1,1)$
\item Notice that $\B w_3 - \dfrac{\B w_3 \bdot \B v_1}{\|\B v_1\|^2}\B v_1 - \dfrac{\B w_3 \bdot \B v_2}{\|\B v_2\|^2}\B v_2 = (3+i,1,1,1+3i) - \dfrac{6}{2}(1,0,0,i) - \dfrac{4}{4}(i,1,1,1) = (0,0,0,0)$. 

This means that $\B w_3 \in \mathrm{span}\{\B v_1,\B v_2 \} = \mathrm{span}\{\B w_1,\B w_2 \}$. So we can toss out $\B w_3$ (and $\B 0$). 
\item $\B v_3 = \B w_4 - \dfrac{\B w_4 \bdot \B v_1}{\|\B v_1\|^2}\B v_1 - \dfrac{\B w_4 \bdot \B v_2}{\|\B v_2\|^2}\B v_2 = (0,1+2i,0,1) - \dfrac{-i}{2}(1,0,0,i)-\dfrac{2+2i}{4}(i,1,1,1) = \dfrac{1}{2}(1,1+3i,-1-i,-i)$ 
\end{itemize}
\end{minipage}

\vspace{0.1in}

\noindent
So $\mathrm{span}(S) = \mathrm{span} \beta$ where $\beta = \left\{ (1,0,0,i), (i,1,1,1), \dfrac{1}{2}(1,1+3i,-1-i,-i) \right\}$ is an orthogonal basis. We could also normalize the vectors in $\beta$ and get $\alpha = \left\{ \dfrac{1}{\sqrt{2}}(1,0,0,i), \dfrac{1}{2}(i,1,1,1), \dfrac{1}{\sqrt{14}}(1,1+3i,-1-i,-i) \right\}$. $\alpha$ is then an orthonormal basis for $\mathrm{span}(S)$.

\vspace{0.15in}

\noindent {\bf\large Example:}  Consider the inner product $\displaystyle \langle f,g \rangle = \int_{-1}^1 f(x)g(x)\,dx$ defined on $\mathbb{R}[x]$. If we run the Gram-Schmidt algorithm (unnormalized) on $\{1,x,x^2,\dots \}$ and then rescale them so that $\|P_n(x)\|^2=\dfrac{2}{2n+1}$, we will get a collection of polynomials known as {\it Legendre polynomials} (we will denote them $P_0(x),P_1(x),$ etc.). In particular\dots

\begin{itemize}
\item $f_0(x) = 1$. We then need $2(?)^2=(?)^2\int_{-1}^1 1^2\,dx = (?)^2\|f_0(x)\|^2=\dfrac{2}{2(0)+1}$, so $?=1$ and thus $P_0(x)=f_0(x)=1$.
\item $f_1(x) = x - \dfrac{\langle x,1 \rangle}{\|1\|^2}1 = x - \dfrac{\int_{-1}^1 x \cdot 1 \,dx}{\int_{-1}^1 1^2 \,dx}\,1 = x - \dfrac{0}{2}\,1 = x$. We then need $\dfrac{2}{3}(?)^2 = \|(?)^2f_1(x)\|^2 = \dfrac{2}{2(1)+1}$ so $?=1$ and thus $P_1(x)=f_1(x)=x$.
\item $f_2(x) = x^2 - \dfrac{\langle x^2,1 \rangle}{\|1\|^2}1 - \dfrac{\langle x^2,x \rangle}{\|x\|^2}x = x^2 - \dfrac{\int_{-1}^1 x^2 \cdot 1 \,dx}{\int_{-1}^1 1^2 \,dx}\,1 - \dfrac{\int_{-1}^1 x^2 \cdot x \,dx}{\int_{-1}^1 x^2 \,dx}\,x = x^2 -\dfrac{2/3}{2}\,1 - \dfrac{0}{2/3}x = x^2-\dfrac{1}{3}$. We then need $\dfrac{8}{45}(?)^2 = (?)^2\int_{-1}^1 (x^2-1/3)^2\,dx=\|?\,f_2(x)\|^2 = \dfrac{2}{2(2)+1}=\dfrac{2}{5}$ so $(?)^2=9/4$ and thus $?=3/2$. Thus $P_2(x) = (3/2)f_2(x) = \dfrac{3}{2}x^2-\dfrac{1}{2}$.
\end{itemize}



\end{document}
