
\documentclass[12pt]{amsart}

\usepackage{241}

\title{21-241 Matrices and Linear Transformations \\
       Summer 1 2012 \\
       Course notes \\
       June 14}
\author{Paul McKenney}


\begin{document}

\maketitle

\begin{defn*}
  If $V$ is a subspace of $\CC^n$, then the \emph{orthogonal subspace} of $V$ is
  \[
    V^\perp = \set{w\in\CC^n}{\forall v\in V\; \brak{w}{v} = 0}
  \]
\end{defn*}

\begin{fact}
  Let $V$ be a subspace of $\CC^n$.
  \begin{enumerate}
    \item  $V^\perp$ is a subspace of $\CC^n$.
    \item  $V\perp V^\perp$.
    \item  $(V^\perp)^\perp = V$.
  \end{enumerate}
\end{fact}

\begin{thm}
  If $V$ is a subspace of $\CC^n$ and $x\in\CC^n$, then $x - \PP_V(x)\in V^\perp$.
\end{thm}
\begin{proof}
  Let $\{v_1,\ldots,v_k\}$ be an orthonormal basis for $V$.  Set $w = x - \PP_V(x)$.  We'll first show that $w$ is orthogonal to each $v_i$ in turn.  To see this, recall that
  \[
    \PP_V(x) = \sum_{j=1}^k \brak{x}{v_j} v_j
  \]
  Then,
  \begin{align*}
    \brak{w}{v_i} & = \brak{x - \PP_V(x)}{v_i} \\
      & = \brak{x}{v_i} - \brak{\sum_{j=1}^k \brak{x}{v_j} v_j}{v_i} \\
      & = \brak{x}{v_i} - \sum_{j=1}^k (\brak{x}{v_j})\brak{v_j}{v_i} \\
      & = \brak{x}{v_i} - (0 + \cdots + \brak{x}{v_i}\cdot 1 + \cdots + 0) \\
      & = 0 \\
  \end{align*}
  Now let $v\in V$ be given.  Since $\{v_1,\ldots,v_k\}$ is a basis for $V$, we may write
  \[
    v = \lambda_1 v_1 + \cdots + \lambda_k v_k
  \]
  for some sequence of coefficients, $\lambda_1,\ldots,\lambda_k\in\CC$.  Then,
  \[
    \brak{w}{v} = \brak{w}{\lambda_1 v_1 + \cdots + \lambda_k v_k} = \overline{\lambda_1}\brak{w}{v_1} + \cdots + \overline{\lambda_k}\brak{w}{v_k} = 0 + \cdots + 0 = 0
  \]
\end{proof}

Now we can describe the Gram-Schmidt process, which takes in a sequence of vectors $x_1,\ldots,x_k$, and produces vectors $v_1,\ldots,v_\ell$, and $u_1,\ldots,u_\ell$, such that
\begin{enumerate}[(a)]
  \item  $\{v_1,\ldots,v_\ell\}$ is an orthogonal basis for $\lspan\{x_1,\ldots,x_k\}$.
  \item  $\{u_1,\ldots,u_\ell\}$ is an orthonormal basis for $\lspan\{x_1,\ldots,x_k\}$.
\end{enumerate}
The vectors $v_i$ are computed recursively as follows;
\begin{enumerate}
  \item  $v_1 = x_1$.
  \item  $v_{i+1} = x_{i+1} - \PP_{\lspan\{v_1,\ldots,v_i\}}(x_{i+1})$.
\end{enumerate}
At each step we compute $u_i$ by the formula
\[
  u_i = \frac{1}{\norm{v_i}} v_i
\]
\emph{if} $v_i\neq 0$.  If $v_i = 0$ then we discard $x_i$ and compute $v_i$ again with $x_{i+1}$ in its place.

\begin{note}
  Notice that, by construction (and the preceding theorem), $v_{i+1}$ is in the orthogonal subspace of $\lspan\{v_1,\ldots,v_i\}$.  In particular, $v_{i+1}$ is orthogonal to each of $v_1,\ldots,v_i$.  Hence at the end we will have an orthogonal set of vectors.  Moreover, at each step we've ensured that $v_1,\ldots,v_i$ are pairwise orthogonal, so $u_1,\ldots,u_i$ make up an orthonormal basis for their span.  Hence by our definition of the projection operators $\PP_S$, we can expand on our recursive definition of $v_{i+1}$ above;
\[
  v_{i+1} = x_{i+1} - \PP_{\lspan\{v_1,\ldots,v_i\}}(x_{i+1}) = x_{i+1} - \left(\sum_{j=1}^i \brak{x_{i+1}}{u_j} u_j\right)
\]
\end{note}

\begin{note}
  If $x_1,\ldots,x_k$ are already linearly independent, then it follows that $\ell = k$.  Otherwise, it follows that $\ell < k$.  (Why?)
\end{note}
\begin{note}
  The case where one of the vectors $v_i$ is zero only occurs when $x_i\in\lspan\{x_1,\ldots,x_{i-1}\}$, which itself only occurs when $x_1,\ldots,x_k$ are linearly dependent.
\end{note}


\end{document}
