
\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

Let's recall the rank-nullity theorem.
\begin{thm}(Rank-Nullity)
  Let $A$ be an $m\times n$ matrix, and let $R$ be any row-echelon form of $A$.  Say $R$ has $k$ nonzero rows, $r_1,\ldots,r_k$, and the leading entry of $r_i$ appears in column $\ell_i$.  (Since $R$ is in row-echelon form, this means $\ell_1 < \ell_2 < \cdots < \ell_k$.)  Let $a_1,\ldots,a_n$ be the columns of $A$, in that order.  Then;
  \begin{enumerate}
    \item\label{row}  $\{r_1,\ldots,r_k\}$ is a basis for $\row(A)$.
    \item\label{col}  $\{a_{\ell_1},\ldots,a_{\ell_k}\}$ is a basis for $\col(A)$.
    \item\label{nul}  $\{s_1,\ldots,s_{n-k}\}$ is a basis for $\nul(A)$, where $s_i$ is the vector with a $1$ in the entry corresponding to the $i$th free variable, and a $0$ in every entry corresponding to the other free variables.  (Note that since $s_i$ must be in $\nul(A)$, this determines the rest of the entries in $s_i$.)
  \end{enumerate}
\end{thm}

\begin{proof}[Proof for row-echelon $A$]
  We assume in this proof that $A = R$.  Later we'll deal with the case where $A$ is not already in row-echelon form.

  Since the rows of $R$ span $\row(R)$, and only the nonzero ones matter, it follows that $\{r_1,\ldots,r_k\}$ spans $\row(R)$.  So it suffices to show that this set is linearly independent.  $R$ looks like this;
  \[
    \begin{pmatrix}
      0 & \cdots & R_{1\ell_1} & \cdots & R_{1\ell_2} & \cdots & R_{1\ell_k} & \cdots & R_{1n} \\
        &        &             &        & R_{2\ell_2} & \cdots & R_{2\ell_k} & \cdots & R_{2n} \\
        &        &             &        &             &        &             &                 \\
        &        &             &        &             &        & R_{k\ell_k} & \cdots & R_{kn} \\
        &        &             &        &             &        &             &                 \\
      0 &        &             &        &   \cdots    &        &             &        &   0    \\
    \end{pmatrix}
  \]
  Let $\lambda_1,\ldots,\lambda_k\in\RR$ be given.  Fix some $i \le k$.  Then the $\ell_i$th entry in the row vector
  \[
    \lambda_1 r_1 + \cdots + \lambda_k r_k
  \]
  is exactly
  \[
    \lambda_1 R_{1\ell_i} + \cdots + \lambda_i R_{i\ell_j} + 0 + \cdots + 0
  \]
  since the $\ell_i$th entry of $r_j$ is zero, whenever $j > i$.  Now suppose
  \[
    \lambda_1 r_1 + \cdots + \lambda_k r_k = 0
  \]
  Then since
  \[
    \lambda_1 R_{1\ell_1} + 0 + \cdots + 0 = 0
  \]
  and $R_{1\ell_1} \neq 0$, it must be that $\lambda_1 = 0$.  Then
  \[
    0 + \lambda_2 R_{2\ell_2} + 0 + \cdots + 0 = 0
  \]
  and similarly it follows that $\lambda_2 = 0$.  Continuing in this way we find that $\lambda_1 = \lambda_2 = \cdots = 0$, and so $r_1,\ldots,r_k$ are linearly independent.

  Similarly for $\col(R)$; if $c_1,\ldots,c_n$ are the columns of $R$, then the $i$th entry of the column vector
  \[
    \lambda_1 c_{\ell_1} + \cdots + \lambda_k c_{\ell_k}
  \]
  is
  \[
    0 + \cdots + 0 + \lambda_i R_{i\ell_i} + \lambda_{i+1} R_{i+1,\ell_{i+1}} + \cdots + \lambda_k R_{k\ell_k}
  \]
  If this column vector is the zero vector, then recursively we find that $\lambda_k = 0$, $\lambda_{k-1} = 0$, etc.  So $\{c_{\ell_1},c_{\ell_2},\ldots,c_{\ell_k}\}$ is linearly independent.

  Now for $\nul(R)$, let $f_i$ be the index of the $i$th free variable.  Then for any $\mu_1,\ldots,\mu_{n-k}\in\RR$, the $f_i$th entry of the linear combination
  \[
    \mu_1 s_1 + \cdots + \mu_{n-k} s_{n-k}
  \]
  is exactly $\mu_i$, since $s_i$ has a $1$ in the $f_i$th entry and $s_j$ has a $0$ in the $f_i$th entry for all $j\neq i$.  It follows that $\{s_1,\ldots,s_{n-k}\}$ is linearly independent.  It spans $\nul(R)$ by our back-substitution algorithm.
\end{proof}

\begin{lemma}
  If $A$ and $B$ are matrices such that $AB$ is defined then $\row(AB)\subseteq \row(B)$.
\end{lemma}

\begin{cor}
  If $A$ and $B$ are row-equivalent then $\row(A) = \row(B)$.
\end{cor}
\begin{proof}
  If $A$ and $B$ are row-equivalent then there is an invertible matrix $E$ (a product of elementary matrices) such that $B = EA$.  Then $\row(B)\subseteq\row(A)$.  But we also have $A = E^{-1}B$, so $\row(A)\subseteq\row(B)$.
\end{proof}

\begin{proof}[Proof of~\eqref{row} in Rank-Nullity]
  Since $A$ and $R$ are row-equivalent, $\row(A) = \row(R)$.  The nonzero rows of $R$ thus make up a basis of $\row(R) = \row(A)$.
\end{proof}

\begin{lemma}
  If $A$ and $B$ are row-equivalent then $\nul(A) = \nul(B)$.
\end{lemma}

\begin{proof}[Proof of~\eqref{nul} in Rank-Nullity]
  Since $A$ and $R$ are row-equivalent, $\nul(A) = \nul(R)$.  Then any basis for $\nul(R)$ is also a basis for $\nul(A)$.
\end{proof}

\begin{lemma}
  \label{roweq-cols}
  Suppose $A$ and $B$ are row-equivalent and $m\times n$.  Say their columns are $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ respectively.  If $1\le j_1 < \cdots < j_k \le n$ are any column indices, then the following are equivalent;
  \begin{enumerate}[(a)]
    \item  $\{a_{j_1},\ldots,a_{j_k}\}$ is linearly independent.
    \item  $\{b_{j_1},\ldots,b_{j_k}\}$ is linearly independent.
  \end{enumerate}
\end{lemma}
\begin{proof}
  Let $A'$ and $B'$ be the $m\times k$ \emph{submatrices} of $A$ and $B$, whose columns are $a_{j_1},\ldots,a_{j_k}$ and $b_{j_1},\ldots,b_{j_k}$ respectively.  Since $A$ and $B$ are row-equivalent, so are $A'$ and $B'$, by the same row operations.  So $\nul(A') = \nul(B')$.  The result follows.  (How? Work it out...)
\end{proof}

\begin{proof}[Proof of~\eqref{col} in Rank-Nullity]
  Since $A$ and $R$ are row-equivalent and the pivot columns of $R$ are a basis for $\col(R)$, by Lemma~\ref{roweq-cols} it follows that $X = \{a_{\ell_1},\ldots,a_{\ell_k}\}$ is linearly independent, and adding any other column of $A$ to $X$ would make it linearly dependent.  Hence $X$ is a basis for $\col(A)$.
\end{proof}

\begin{defn*}
  Let $A$ be a matrix.  The \emph{row rank} of $A$ is $\dim(\row(A))$.  The \emph{column rank} of $A$ is $\dim(\col(A))$.  The \emph{nullity} of $A$ is $\dim(\nul(A))$.
\end{defn*}

\begin{cor}
  The row rank of a matrix is the same as its column rank.  We call this common dimension the \emph{rank}.  If $A$ is $m\times n$, then $\rank(A) + \nullity(A) = n$.
\end{cor}

\begin{example*}
  Let $r$ be a row vector of length $n$ and $c$ a column vector of height $n$.  Let $A = rc$ and $B = cr$.  What is the rank of $A$? of $B$? What about the nullity?
\end{example*}

\begin{example*}
  If $A$ and $B$ are both $n\times n$, how are the rank of $AB$ and $BA$ related?  What about the nullity?  Look at a $2\times 2$ example.  
\end{example*}

\begin{example*}
  Consider the $n\times n$ \emph{shift} matrix;
  \[
    S = 
    \begin{pmatrix}
      0 & 0 & \cdots & 0 & 0 \\
      1 & 0 & \cdots & 0 & 0 \\
      0 & 1 & \cdots & 0 & 0 \\
        & & \ddots & & \\
      0 & 0 & \cdots & 1 & 0 \\
    \end{pmatrix}
  \]
  Calculate bases for $\nul(S^t)$ and $\ran(S^t)$, where $t \ge 1$.  
\end{example*}

\end{document}
