
\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

\section{More on projections and orthogonal subspaces}

Here's a question.  How do you find (a basis for) the orthogonal subspace of a subspace?
\begin{fact}
  Let $A$ be a size $m\times n$ matrix.  Then $\col(A)^\perp = \nul(A^H)$.
\end{fact}
\begin{proof}
  Suppose $x\in \col(A)^\perp$.  Let $a_1,\ldots,a_n\in\CC^m$ be the columns of $A$.  Then, $a_1^H,\ldots,a_n^H$ are the rows of $A^H$.  Hence $a_1^H x,\ldots,a_n^H x$ are the entries of $A^H x$.  But for each $i$ we have
  \[
    a_i^H x = \brak{x}{a_i} = 0
  \]
  Hence $x\in\nul(A^H)$.  The opposite direction follows from the same translation; if $x\in\nul(A^H)$, then $x$ is orthogonal to each of the column vectors of $A$.  But then $x$ is orthogonal to anything in their span.
\end{proof}

\begin{cor}
  If $V$ is a subspace of $\CC^n$, then $\dim(V) + \dim(V^\perp) = n$.
\end{cor}
\begin{proof}
  Let $v_1,\ldots,v_m$ be a basis for $V$, and let $A$ be the $n\times m$ matrix with columns $v_1,\ldots,v_m$.  Then $V = \col(A)$, and $V^\perp = \col(A) = \nul(A^H)$.  But the column rank of $A$ and the row rank of $A^H$ are the same (why?); so by the rank-nullity theorem,
  \[
    \dim(V) + \dim(V^\perp) = \rank(A^H) + \nullity(A^H) = n
  \]
\end{proof}

\begin{example*}
  Find a basis for the orthogonal subspace of
  \[
    \lspan\left\{
      \begin{pmatrix}
        1 \\ 0 \\ 2 \\ 2 \\
      \end{pmatrix},
      \begin{pmatrix}
        0 \\ 2 \\ 1 \\ 5 \\
      \end{pmatrix}
    \right\}
  \]
\end{example*}

\pagebreak

\begin{thm}
  Let $V$ be a subspace of $\CC^n$.  Then,
  \begin{enumerate}
    \item\label{def}  $\PP_V : \CC^n\to \CC^n$ is a well-defined linear transformation.
    \item\label{idem}  If $v\in V$ then $\PP_V(v) = v$.
    \item\label{perp}  If $w\in V^\perp$ then $\PP_V(w) = 0$.
    \item\label{proj}  If $P_V$ is the matrix which implements $\PP_V$, then $P_V$ is a projection matrix.
  \end{enumerate}
\end{thm}
\begin{proof}
  What we mean in~\eqref{def} is, if we used two different orthonormal bases $\{u_1,\ldots,u_k\}$ and $\{\hat{u}_1,\ldots,\hat{u}_k\}$ for $V$, would we get the same output always?  That is, do we have
  \[
    \sum_{i=1}^k \brak{x}{u_i} u_i = \sum_{i=1}^k \brak{x}{\hat{u}_i}\hat{u}_i
  \]
  for all $x\in\CC^n$?  The proof is not really significant so long as you understand the problem.

  For~\eqref{idem}, recall that for any $v\in V$,
  \[
    v = \sum_{i=1}^k \brak{v}{u_i} u_i
  \]
  where $u_1,\ldots,u_k$ is any orthonormal basis for $V$.  The right-hand-side is our definition of $\PP_V(v)$ (now that we know it makes sense).

  For~\eqref{perp}, let $w\in V^\perp$.  Then
  \[
    \PP_V(w) = \sum_{i=1}^k \brak{w}{u_i} u_i = 0\cdot u_1 + \cdots + 0\cdot u_k = 0
  \]
\end{proof}

\begin{thm}
  Let $V$ be a subspace of $\CC^n$.  Then for every $x\in\CC^n$, $x = \PP_V(x) + (x - \PP_V(x))$ is the unique decomposition of $x$ into vectors in $V$ and $V^\perp$.
\end{thm}

\begin{proof}
  To see that this pair is the only one that works, say $v\in V$ and $w\in V^\perp$ is another pair of vectors, such that $x = v + w$.  Then we have
  \[
    \PP_V(x) = \PP_V(v + w) = \PP_V(v) + \PP_V(w) = v + 0 = v
  \]
  But then $w = x - v = x - \PP_V(x)$ as well.
\end{proof}

\begin{proof}[Proof of~\eqref{proj}]
  Let $x\in\CC^n$, and write $P = P_V$.  Let $x = v + w$ be the unique decomposition of $x$ into vectors from $V$ and $V^\perp$ respectively.  Then,
  \[
    Px = P(v + w) = Pv + Pw = v + 0 = v
  \]
  On the other hand,
  \[
    P^2 x = P(Px) = Pv = v = Px
  \]
  So $Px = P^2x$ for all $x\in\CC^n$, and as we've seen this implies $P = P^2$.

  Now let $x,y\in\CC^n$ be given.  Say $x = v + w$ and $y = s + t$, where $v,s\in V$ and $w,t\in V^\perp$.  Then,
  \[
    \brak{Px}{y} = \brak{P(v + w)}{s + t} = \brak{v + 0}{s + t} = \brak{v}{s} + \brak{v}{t} = \brak{v}{s}
  \]
  Similarly,
  \[
    \brak{P^H x}{y} = \brak{x}{Py} = \brak{v + w}{P(s + t)} = \brak{v + w}{s + 0} = \brak{v}{s} + \brak{w}{s} = \brak{v}{s}
  \]
  Hence $\brak{Px}{y} = \brak{P^H x}{y}$ for all $x,y\in\CC^n$.  This implies $P = P^H$.

\end{proof}

\section{Eigenvalues and Orthogonality}

\begin{defn*}
  A matrix $A\in M_n(\CC)$ is \emph{Hermitian} if $A^H = A$.  $A$ is \emph{symmetric} if $A^\top = A$.  Note that if $A$ is a real matrix then $A$ is symmetric if and only if $A$ is Hermitian.
\end{defn*}

\begin{thm}
  Suppose $A$ is Hermitian, and $\lambda,\mu\in\CC$ are distinct eigenvalues for $A$.  Then $V_\lambda \perp V_\mu$.
\end{thm}
\begin{proof}
  Let $v\in V_\lambda$ and $w\in V_\mu$ be given.  Then,
  \[
    \brak{Av}{w} = \brak{\lambda v}{w} = \lambda\brak{v}{w}
  \]
  and also,
  \[
    \brak{Av}{w} = \brak{v}{A^H w} = \brak{v}{Aw} = \brak{v}{\mu w} = \bar{\mu}\brak{v}{w}
  \]
  By a problem on HW5, $\lambda$ and $\mu$ are actually real numbers; so in particular, $\bar{\mu} = \mu$, and we have
  \[
    \lambda\brak{v}{w} = \mu\brak{v}{w}
  \]
  Since $\lambda \neq \mu$, $\brak{v}{w} = 0$.
\end{proof}

\begin{defn*}
  Let $A\in M_n(\CC)$, and let $\lambda$ be an eigenvalue of $A$.  The \emph{geometric multiplicity} of $\lambda$ (with respect to $A$) is $\dim(V_\lambda)$.  The \emph{algebraic multiplicity} of $\lambda$ (with respect to $A$) is the number of times $\lambda$ appears as a root in the characteristic polynomial of $A$.
\end{defn*}

\begin{example*}
  Let
  \[
    A = \begin{pmatrix}
      2 & 0 & 0 \\
      0 & 5 & 0 \\
      0 & 0 & 5 \\
    \end{pmatrix}
  \]
  Then $\spec(A) = \{2,5\}$.  The geometric multiplicity of $2$, with respect to $A$, is $1$; whereas the geometric multiplicity of $5$ with respect to $A$ is $2$.  ($\{e_1\}$ is a basis for the eigenspace of $2$, and $\{e_2,e_3\}$ is a basis for the eigenspace of $5$.)  The characteristic polynomial of $A$ is
  \[
    p_A(\lambda) = \det(\lambda I - A) = (\lambda - 2)(\lambda - 5)^2
  \]
  hence the algebraic multiplicities are $1$ (for $2$) and $2$ (for $5$).
\end{example*}

\begin{fact}
  The sum of the algebraic multiplicities of the eigenvalues of an $n\times n$ matrix $A$ is exactly $n$.
\end{fact}
\begin{proof}
  We've seen that the characteristic polynomial of $A$ has degree exactly $n$; since the eigenvalues of $A$ are the roots of $p_A$, it follows that their multiplicities must sum up to $n$.
\end{proof}

The same is not true for the geometric multiplicities.  The shift matrix provides the canonical example.  (As you should see on HW5.)
\begin{example*}
  Let
  \[
    A = \begin{pmatrix}
      0 & 0 \\
      1 & 0 \\
    \end{pmatrix}
  \]
  The characteristic polynomial of $A$ is $\lambda^2 - (-1)\cdot 0 = \lambda^2$, hence the only eigenvalue of $A$ is $0$, with algebraic multiplicity $2$.  The eigenspace is exactly $\nul(A)$, which has a basis of $\{e_1\}$.  Hence the geometric multiplicity of $0$ with respect to $A$ is $1$.
\end{example*}


\end{document}
