

\section{ Kernel, Range, Nullity, Rank }

\edz{ Define all for functions; segue into linear transformations; merge footnote into text.  Fluffy text before hitting with definitions. }
The \emph{range}\index{Range} of a linear transformation $L:V\rightarrow W$ is the set of vectors the linear transformation maps to.  This set is also often called the \emph{image}\index{Image} of $L$, written
\[
\text{ran}(L)=\text{Im}(L)=L(V)=\{ L(v) | v\in V \}\subset W.
\]  
The \emph{domain}\index{Domain} $V$ of a linear transformation $L:V\rightarrow W$ is often called the \emph{pre-image}\index{Pre-image} of $L$.  We can also talk about the pre-image of any subset of vectors $U\in W$: 
\[
L^{-1}(U)=\{ v\in V | L(v)\in U \}\subset V.
\]

A linear transformation $L$ is \emph{one-to-one}\index{One-to-one} if for any $x\neq y\in V$, $L(x)\neq f(y)$.  In other words, different vectors in $V$ always map to different vectors in $W$.  One-to-one transformations are also known as \emph{injective}\index{Injective} transformations.  Notice that injectivity is a condition on the pre-image of $L$.

A linear transformation $L$ is \emph{onto}\index{Onto} if for every $w\in W$, there exists an $x\in V$ such that $L(x)=w$.  In other words, every vector in $W$ is the image of some vector in $V$.  An onto transformation is also known as an \emph{surjective}\index{Surjective} transformation.  Notice that surjectivity is a condition on the image of $L$.
\footnote{
The notions of one-to-one and onto can be generalized to arbitrary functions on sets.  For example if $g$ is a function from a set $S$ to a set $T$, then $g$ is one-to-one if different objects in $S$ always map to different objects in $T$.  For a linear transformation $f$, these sets $S$ and $T$ are then just vector spaces, and we require that $f$ is a linear map; \emph{i.e.} $f$ respects the linear structure of the vector spaces.

The linear structure of sets of vectors lets us say much more about one-to-one and onto functions than one can say about functions on general sets.  For example, we always know that a linear function sends $0_V$ to $0_W$.  Then we can show that a linear transformation is one-to-one if and only if $0_V$ is the only vector that is sent to $0_W$: by looking at just one (very special) vector, we can figure out whether $f$ is one-to-one.  For arbitrary functions between arbitrary sets, things aren't nearly so convenient!
}

Suppose $L:V\rightarrow W$ is \emph{not} injective.  Then we can find $v_1 \neq v_2$ such that $Lv_1=Lv_2$.  Then $v_1-v_2\neq 0$, but
\[
L(v_1-v_2)=0.
\]

\begin{definition}
Let $L:V\rightarrow W$ be a linear transformation.  The set of all vectors $v$ such that $Lv=0_W$ is called the \emph{kernel of $L$}\index{Kernel}:
\[
\ker L = \{v\in V | Lv=0_W \}.
\]
\end{definition}

\begin{theorem}
A linear transformation $L$ is injective if and only if $$\ker L=\{ 0_V \}\, .$$
\end{theorem}

\begin{proof}
The proof of this theorem is an exercise.
\end{proof}

Notice that if $L$ has matrix $M$ in some basis, then finding the kernel of $L$ is equivalent to solving the homogeneous system 
\[
MX=0.
\]

\begin{example}
Let $L(x,y)=(x+y,x+2y,y)$.  Is $L$ one-to-one?

To find out, we can solve the linear system:
\[\begin{amatrix}{2}
1 & 1 & 0 \\
1 & 2 & 0 \\
0 & 1 & 0 \\
\end{amatrix} \sim
\begin{amatrix}{2}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0 \\
\end{amatrix}.
\]
Then all solutions of $MX=0$ are of the form $x=y=0$.  In other words, $\ker L=0$, and so $L$ is injective.
\end{example}

\begin{theorem}
Let $L:V\rightarrow W$.  Then $\ker L$ is a subspace of $V$.
\end{theorem}

\begin{proof}
Notice that if $L(v)=0$ and $L(u)=0$, then for any constants $c,d$, $L(cu+dv)=0$.  Then by the subspace theorem, 
\edz{hyperlink to subspace theorem}
the kernel of $L$ is a subspace of $V$.
\end{proof}

This theorem has an interpretation in terms of the eigenspaces of $L:V\rightarrow V$.  Suppose $L$ has a zero eigenvalue.  Then the associated eigenspace consists of all vectors $v$ such that $Lv=0v=0$; in other words, the $0$-eigenspace of $L$ is exactly the kernel of $L$.  




Returning to the previous example, let $L(x,y)=(x+y,x+2y,y)$.  $L$ is clearly not surjective, since $L$ sends $\Re^2$ to a plane in $\Re^3$.

Notice that if $x=L(v)$ and $y=L(u)$, then for any constants $c,d$, $cx+dy = L(cv+du)$.  Now the subspace theorem strikes again, and we have the following theorem.

\begin{theorem}
Let $L:V\rightarrow W$.  Then the image $L(V)$ is a subspace of $W$.
\end{theorem}

To find a basis of the image of $L$, we can start with a basis $S=\{v_1, \ldots, v_n\} $ for $V$, and conclude (see the Review Exercises) that
\[
L(V)=\spa L(S) = \spa \{L(v_1), \ldots, L(v_n)\}.
\]
However, the set $\{L(v_1), \ldots, L(v_n)\}$ may not be linearly independent, so we solve 
\[
c^1L(v_1)+ \ldots + c^nL(v_n)=0.
\]
By finding relations amongst $L(S)$, we can discard vectors until a basis is arrived at.  The size of this basis is the dimension of the image of $L$, which is known as the \emph{rank}\index{Rank} of $L$.


\begin{definition}
The \emph{rank} of a linear transformation $L$ is the dimension of its image, written $\rank L=\dim L(V) = \dim \text{ ran } L$.  

The \emph{nullity}\index{Nullity} of a linear transformation is the dimension of the kernel, written $\nul L=\dim \ker L$. 
\end{definition}

\begin{theorem}[Dimension Formula]\index{Dimension formula}
Let $L:V\rightarrow W$ be a linear transformation, with $V$ a finite-dimensional vector space\footnote{The formula still makes sense for infinite dimensional vector spaces, such as the space of all polynomials, but the notion of a basis for an infinite dimensional space is more sticky than in the finite-dimensional case.  Furthermore, the dimension formula for infinite dimensional vector spaces isn't useful for computing the rank of a linear transformation, since an equation like $\infty=\infty+x$ cannot be solved for $x$. As such, the proof presented assumes a finite basis for $V$.}.  Then:
\begin{eqnarray*}
\dim V &=& \dim \ker V + \dim L(V)\\
 &=& \nul L + \rank L.
\end{eqnarray*}
\end{theorem}



\begin{proof}
Pick a basis for $V$:
\[
\{ v_1,\ldots,v_p,u_1,\ldots, u_q \},
\]
where $v_1,\ldots,v_p$ is also a basis for $\ker L$.  This can always be done, for example, by finding a basis for the kernel of $L$ and then extending to a basis for $V$.  Then $p=\nul L$ and $p+q=\dim V$.  Then we need to show that $q=\rank L$.  To accomplish this, we show that 
$\{L(u_1),\ldots,L(u_q)\}$ is a basis for $L(V)$.

To see that $\{L(u_1),\ldots,L(u_q)\}$ spans $L(V)$, consider any vector $w$ in $L(V)$.  Then we can find constants $c^i, d^j$ such that:
\begin{eqnarray*}
w &=& L(c^1v_1 + \ldots + c^pv_p+d^1u_1 + \ldots + d^qu_q)\\
  &=& c^1L(v_1) + \ldots + c^pL(v_p)+d^1L(u_1)+\ldots+d^qL(u_q)\\
  &=& d^1L(u_1)+\ldots+d^qL(u_q) \text{ since $L(v_i)=0$,}\\
\Rightarrow L(V) &=& \spa \{L(u_1), \ldots, L(u_q)  \}.
\end{eqnarray*}

Now we show that $\{L(u_1),\ldots,L(u_q)\}$ is linearly independent.  We argue by contradiction: Suppose there exist constants $d^j$ (not all zero) such that
\begin{eqnarray*}
0 &=& d^1L(u_1)+\ldots+d^qL(u_q)\\
  &=& L(d^1u_1+\ldots+d^qu_q).\\
\end{eqnarray*}
But since the $u^j$ are linearly independent, then $d^1u_1+\ldots+d^qu_q\neq 0$, and so $d^1u_1+\ldots+d^qu_q$ is in the kernel of $L$.  But then $d^1u_1+\ldots+d^qu_q$ must be in the span of $\{v_1,\ldots, v_p\}$, since this was a basis for the kernel.  This contradicts the assumption that $\{ v_1,\ldots,v_p,u_1,\ldots, u_q \}$ was a basis for $V$, so we are done.
\end{proof}





\section*{References}
\begin{itemize}
\item Hefferon, Chapter Three, Section II.2: Rangespace and Nullspace (Recall that ``homomorphism'' is is used instead of ``linear transformation'' in Hefferon.)
\end{itemize}

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Rank_(linear_algebra)}{Rank}
\item \href{http://en.wikipedia.org/wiki/Dimension_theorem}{Dimension Theorem}
\item \href{http://en.wikipedia.org/wiki/Kernel_(linear_operator)}{Kernel of a Linear Operator}
\end{itemize}


\section*{Review Questions}

\begin{enumerate}
\item Let $L:V\rightarrow W$ be a linear transformation.  Prove that $\ker L=\{0_V\}$ if and only if $L$ is one-to-one.

\item Let $\{v_1, \ldots, v_n  \}$ be a basis for $V$.  Explain why
\[
L(V)=\spa \{L(v_1), \ldots, L(v_n) \}.
\]

\item Suppose $L:\Re^4\rightarrow \Re^3$ whose matrix $M$ in the standard basis is row equivalent to the folowing matrix:
\[
\begin{pmatrix}
1&0&0&-1\\
0&1&0&1\\
0&0&1&1\\
\end{pmatrix}.
\]
\emph{Explain} why the first three columns of the original matrix $M$ form a basis for $L(V)$.\\
\emph{Find and describe} and algorithm (\textit{i.e.} a general procedure) for finding a basis for $L(V)$ when $L:\Re^n\rightarrow \Re^m$. \\
\edz{Hold hands on this a bit more!}
Finally, provide an example of the use of your algorithm.

\item Claim: If $\{v_1, \ldots, v_n  \}$ is a basis for $\ker L$, where $L:V\rightarrow W$, then it is always possible to extend this set to a basis for $V$.  

Choose a simple yet non-trivial linear transformation with a non-trivial kernel and verify the above claim for the transformation you choose.

\item Let $P_n(x)$ be the space of polynomials in $x$ of degree less than or equal to $n$, and consider the derivative operator $\frac{\partial}{\partial x}$.  Find the dimension of the kernel and image of $\frac{\partial}{\partial x}$.

Now, consider $P_2(x,y)$, the space of polynomials of degree two or less in $x$ and $y$.  (Recall that $xy$ is degree two, $y$ is degree one and $x^2y$ is degree three, for example.)  Let $L=\frac{\partial}{\partial x}+\frac{\partial}{\partial y}$.  (For example, $L(xy)=\frac{\partial}{\partial x}(xy)+\frac{\partial}{\partial y}(xy) = y+x$.)  Find a basis for the kernel of $L$.  Verify the dimension formula in this case.

\end{enumerate}

\newpage
