\documentstyle[12pt]{article}
\input amssym.def
\input amssym

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{DEF}[theorem]{Definition}

\newtheorem{define}[theorem]{Definition}
%\newenvironment{define}{\begin{DEF}\bf}{\end{DEF}}

\newtheorem{exercise}[theorem]{Exercise}

\def\span{{\rm span}}
\def\col{{\rm col}}
\def\entry{{\rm entry}}
\def\proof{\par\noindent proof:\par }
\def\qed{\par\noindent QED\par}
\def\reals{{\Bbb R}}
\def\dim{{\rm dim}}
\def\range{{\rm range}}
\def\nullsp{{\rm null}}
\def\mat{{\rm MAT}}
\def\compose{\circ}


\begin{document}

\begin{flushright}
  A. Miller\\
  M340 \\
  May 97
\end{flushright}

\begin{center}
  Linear Transformations
\end{center}


\begin{define}
  A \underline{linear transformation} is a function $L:V\to W$
  from one vector space $V$ to another $W$ which satisfies:
  \begin{enumerate}
    \item $L(u+v)=L(u)+L(v)$
    \item $L(au)=aL(u)$
  \end{enumerate}
 for every $u,v\in V$ and scalar $a$.
\end{define}

\begin{exercise} \label{stran}
  Let $L:V\to W$ be a function from a vector space
  $V$ to a vector space $W$. Prove that $L$ is a linear transformation
  iff $$L(au+bv)=aL(u)+bL(v)$$ for any $u,v\in V$ and scalars $a$ and $b$.
\end{exercise}

\begin{theorem} \label{tranmat}
  Every linear transformation $L:\reals^n\to \reals^m$ is
  determined by a matrix $A\in\mat_{m,n}$:
  $$L(X)=AX$$
  for every $X\in\reals^n$
\end{theorem}
\proof
Given $A$ since
$$A(X+Y)=AX+AY \mbox{ and } A(aX)=a(AX)$$
it is clear that $L(X)=AX$ is a linear transformation.

For the converse, assume $L:\reals^n\to \reals^m$ is a
linear transformation.
The canonical basis for $\reals^n$ is the sequence of columns of the
$n\times n$ identity matrix, $I_{n\times n}$.  So
let $e_i=\col_i(I_{n\times n})$.  Note for any vector
$$\left[\begin{array}{c} x_1\\x_2\\ \vdots \\ x_n\end{array}\right]=
x_1e_1+x_2e_2+\cdots+x_ne_n.$$
Let $A$ be the matrix such that
$$L(e_i)=\col_i(A)$$
for every $i=1,\ldots,n$.  Then
$$
\begin{array}{lcl}
L\left[\begin{array}{c} x_1\\x_2\\ \vdots \\ x_n\end{array}\right]
& = & L(x_1e_1+x_2e_2+\cdots+x_ne_n)\\
& = & x_1L(e_1)+x_2L(e_2)+\cdots+x_nL(e_n)\\
& = & x_1\col_1(A)+x_2\col_2(A)+\cdots+x_n\col_n(A)\\
& = & A \left[\begin{array}{c} x_1\\x_2\\ \vdots \\ x_n\end{array}\right]\\
\end{array}
$$
\qed


\begin{define}
  For $L:V\to W$ a linear transformation, define
  the \underline{null space}
  of $L$, $\nullsp(L)$, and the \underline{range space} of $L$, $\range(L)$
  as follows:
  \begin{enumerate}
    \item $\nullsp(L)=\{v\in V: L(v)=z\}$
    \item $\range(L)=\{w\in W: \mbox{ there exists } v\in V
     \mbox{ such that }
           L(v)=w\}$
  \end{enumerate}
\end{define}

\begin{theorem}
  $\nullsp(L)$ and $\range(L)$ are subspaces of $V$ and $W$, respectively.
\end{theorem}
\proof

$\nullsp(L)$:  Suppose $u,v\in\nullsp(L)$ and $a,b$ scalars. Then
$L(u)=z$ and $L(v)=z$ and
$$L(au+bv)=aL(u)+bL(v)=az+bz=z+z=z.$$
Hence $au+bv\in\nullsp(L)$


$\range(L)$: Suppose $w_1,w_2\in\range(L)$ and $a_1,a_2$ are scalars. Then
there exists $v_1,v_2\in V$ such that $L(v_1)=w_1$ and
$L(v_2)=w_2$.  Then
$$L(a_1v_1+a_2v_2)=a_1L(v_1)+a_2L(v_2)=a_1w_1+a_2w_2$$
and so $a_1w_1+a_2w_2\in\range(L)$.

\qed

\begin{define}
  A function $L:V\to W$ is \underline{one-to-one} iff
  $L(u)=L(v)$ implies $u=v$ for every $u,v\in V$.
\end{define}

\begin{define}
A function $L:V\to W$ is \underline{onto} iff for every $w\in W$
  there exists $v\in V$ such that $L(v)=w$.
\end{define}

\begin{define}
  A function $L:V\to W$ is an \underline{isomorphism} iff
  $L$ is a one-to-one, onto, linear transformation.
\end{define}


\begin{theorem}
  A linear transformation $L:V\to W$ is an isomorphism iff
  $\nullsp(L)=\{z\}$ and $\range(L)=W$.
\end{theorem}
\proof

It is clear from the definitions that $L$ is onto
iff $\range(L)=W$.

\par\noindent Claim $L$ is one-to-one iff $\nullsp(L)=\{z\}$.
 \proof
  Assume $L$ is one-to-one. Then $L(u)=z$ and $L(z)=z$ implies
  $u=z$ and so $\nullsp(L)=\{z\}$.

  Conversely, assume $\nullsp(L)=\{z\}$.
  Then if $L(u)=L(v)$, then $L(u-v)=L(u)-L(v)=z$ and so
  $u-v\in\nullsp(L)$.  Hence $u-v\in \{z\}$ and so $u-v=z$ and
  therefore $u=v$.  So $L(u)=L(v)$ implies $u=v$ and therefore
  $L$ is one-to-one. This proves the Claim.
\qed

\begin{theorem}
  Suppose $A$ is an invertible $n\times n$ matrix.
  If $L:\reals^n\to\reals^n$ is defined by
  $L(X)=AX$, then $L$ is an isomorphism.
\end{theorem}
\proof
We already know from Theorem \ref{tranmat} that $L$ is a linear
transformation.  To see that it is one-to-one, assume
$L(X)=L(Y)$.  Then $AX=AY$ implies
$A^{-1}AX=A^{-1}AY$ implies $X=Y$.  To see that it is onto,
suppose $Y\in\reals^n$ and let $X=A^{-1}Y$, then
$L(X)=AX=AA^{-1}Y=Y$.\qed


\begin{theorem}
  A linear transformation $L:V\to W$ is an isomorphism iff
  there exists a linear transformation $L^{-1}:W\to V$ such
  that $L\compose L^{-1}=Id_{W}$ and
  $L^{-1}\compose L=Id_{V}$. ($Id_V$ is the identity map on $V$,
  i.e., $Id_V(u)=u$ all $u\in V$.)
\end{theorem}
\proof

First suppose that such an $L^{-1}$ exists.  To see that
$L$ is one-to-one, suppose $L(u)=L(v)$.  Then
$L^{-1}(L(u))= L^{-1}(L(v))$, but
$$u=L^{-1}(L(u))= L^{-1}(L(v))=v$$
and so $u=v$.  To see that
$L$ is onto, suppose $w\in W$.  Let $v=L^{-1}(w)$, then
$L(v)=L(L^{-1}(w))=w$.  Hence for every $w\in W$ there exists
$v\in V$ such that $L(v)=w$ and so $L$ is onto.

For the converse, suppose that $L$ is an isomorphism. This
means that $L$ is both one-to-one and onto.  It follows that
for every $w\in W$ there exists a unique $v\in V$ such that
$L(v)=w$.  Define $L^{-1}:W\to V$ by the rule
$L^{-1}(w)=v$ iff $L(v)=w$.  It follows that $v=L^{-1}(w)=v=L^{-1}(L(v))$
for every $v\in V$ and so $L^{-1}\compose L=Id_{V}$; and also
$w=L(v)=L(L^{-1}(w)$ for every $w\in W$ and so $L\compose L^{-1}=Id_{W}$.
Finally we prove the $L^{-1}$ is a linear transformation.
Suppose $w_1,w_2\in W$ and $a_1,a_2$ are scalars.  Let
$u=L^{-1}(a_1w_1+a_2w_2)$ and let $v=a_1L^{-1}w_1+a_2L^{-1}(w_2)$,
then
$$L(u)=L(L^{-1}(a_1w_1+a_2w_2))=a_1w_1+a_2w_2$$
and
$$L(v)=L(a_1L^{-1}w_1+a_2L^{-1}(w_2))=a_1L(L^{-1}(w_1)+a_2L(L^{-1}(w_2)=
                                               a_1w_1+a_2w_2$$
hence $L(u)=L(v)$ and since $L$ is one-to-one we know that
$u=v$ and so
$$L^{-1}(a_1w_1+a_2w_2)=u=v=a_1L^{-1}w_1+a_2L^{-1}(w_2)$$

\qed

\begin{exercise}\label{indx}
Suppose $L:V\to W$ is a is one-to-one linear transformation and
$v_1,\ldots,v_n$ are linearly independent vectors in $V$.
\par\noindent Prove that $L(v_1),\ldots,L(v_n)$ are
linearly independent vectors
in $W$.
\end{exercise}

\begin{exercise}\label{spanx}
Suppose $L:V\to W$ is a linear transformation and
$v_1,\ldots,v_n$ are vectors in $V$.
Prove that
$$L(\span(\{v_1,\ldots,v_n\}))=\span(\{L(v_1),\ldots,L(v_n)\})$$
\end{exercise}


\begin{define}
  $V$ and $W$ are isomorphic iff there exists an isomorphism
  $L:V\to W$.
\end{define}

\begin{theorem}
  $V$ is isomorphic to $W$ iff $\dim(V)=\dim(W)$.
\end{theorem}
\proof
This is true in general, but we only proof it in case the spaces have
finite dimension.

Suppose that $V$ is isomorphic to $W$.  Let $v_1,\ldots,v_n$ be
a basis for $V$ and define $w_1,\ldots,w_n$ by $L(v_i)=w_i$ for
$i=1,\ldots,n$.  By exercise \ref{indx} $w_1,\ldots,w_n$ are linearly
independent (since $L$ is one-to-one) and by exercise \ref{spanx}
they span $W$ since $L$ is onto.

For the converse suppose that $\dim(V)=\dim(W)$ and let
$v_1,\ldots,v_n$ be a basis for $V$ and $w_1,\ldots,w_n$ be a
basis for $W$.  Given any $v\in V$ there exists
a unique sequence of scalars $a_1,\ldots,a_n$ such that
$$v=a_1v_1+\cdots+a_nv_n$$
They exists because $v_1,\ldots,v_n$ span $V$ and they are unique
because
$$v=a_1v_1+\cdots+a_nv_n \mbox{ and } v=b_1v_1+\cdots+b_nv_n$$
implies
$$z=(a_1-b_1)v_1+\cdots+(a_n-b_n)v_n$$
and so by linear independence $a_1=b_1,\ldots,a_n=b_n$.  Now define
$L:V\to W$ by
$$L(a_1v_1+\cdots+a_nv_n)=a_1w_1+\cdots+a_nw_n$$

Now we check that $L$ is linear. Suppose
$v=a_1v_1+\cdots+a_nv_n$ and $w=b_1v_1+\cdots+b_nv_n$ and
$a,b$ are scalars. Then
$$
\begin{array}{lcl}
L(av+bw)&=& L((aa_1+bb_1)v_1+\cdots+(aa_n+bb_n)v_n)\\
        &=& (aa_1+bb_1)w_1+\cdots+(aa_n+bb_n)w_n \\
        &=& a(a_1w_1)+\cdots a_nw_n)+b(b_1w_1+\cdots+b_nw_n)\\
        &=& aL(v)+bL(w)
\end{array}$$
Next to see that $L$ is one-to-one and onto, note that for
any $w$ there exists unique $a_1,a_2,\ldots,a_n$ such
that $w=a_1w_1+\cdots+a_nw_n$ and so $v=a_1v_1+\cdots+a_nv_n$
is the unique element of $V$ such that $L(v)=w$.
\qed


\begin{theorem}\label{sum}
  Suppose $L:V\to W$ is a linear transformation.  Then
  $$\dim(V)=\dim(\nullsp(L))+\dim(\range(L)).$$
\end{theorem}
\proof

Let $u_1,\ldots,u_n$ be a basis for $\nullsp(L)$ and
$v_1,\ldots,v_m$ be a basis for $\range(L)$. Let
$w_1,\ldots,w_m$ be in $V$ such that $L(w_i)=v_i$.

\medskip
\noindent{\bf Claim.}
$u_1,\ldots,u_n,w_1,\ldots,w_m$ is a basis for $V$.

\proof

First we show they are linearly independent.
Suppose $$c_1u_1+\cdots+c_nu_n+d_1w_1+\cdots+d_mw_m=z$$ then
applying $L$ we get
$$z=L(z)=L(c_1u_1+\cdots+c_nu_n)+L(d_1w_1+\cdots+d_mw_m)
=z+d_1v_1+\cdots+d_mv_m$$
because $c_1u_1+\cdots+c_nu_n\in\nullsp(L)$.  Hence
$$d_1v_1+\cdots+d_mv_m=z$$
and since the $v's$ are linearly independent we get
$d_1=\cdots=d_m=0$.
Hence $c_1u_1+\cdots+c_nv_n=z$ and since the $u$'s
are linearly independent $c_1=\cdots=c_n=0$. So, our set
is linearly independent.

Now we must see that they span $V$. Suppose $v\in V$ is arbitrary
and let $L(v)=d_1v_1+\cdots+d_mv_m$, then
set $u=d_1w_1+\cdots+d_mw_m$ and notice that
$$L(u)=L(d_1w_1+\cdots+d_mw_m)=d_1L(w_1)+\cdots+d_mL(w_m)=
d_1v_1+\cdots+d_mv_m.$$
It follows that $L(u)=L(v)$ and so $L(u-v)=z$ since $L$ is linear
and therefore $v-u\in\nullsp(L)$.
Therefore (since the $u$'s are basis for $\nullsp(L)$)
there exists $c$'s
such that
$$v-u=c_1u_1+\cdots+c_nu_n$$
and therefore
$$v=u+c_1u_1+\cdots+c_nu_n=d_1w_1+\cdots+d_mw_m+c_1u_1+\cdots+c_nu_n.$$
Thus $v\in span(\{u_1,\ldots,u_n,w_1,\ldots,w_m\})$.
This proves the Claim.
\qed
From the Claim it follows that the dimension of $V$ is $n+m$ or
in otherwords $\dim(\nullsp(L))+\dim(\range(L))$.
This proves the Theorem. \qed

In the case that $L$ comes from an $m\times n$ matrix $A$, i.e.,
$L:\reals^n\to \reals^m$ is given by $L(X)=AX$ we have that
$$n=\dim(\reals^n)=\dim(\nullsp(A))+\dim(\range(A))$$

\begin{theorem}
  Suppose $PAQ=D$ where
  \begin{enumerate}
   \item $A$ and $D$ are $m\times n$
   \item $P$ is $m\times m$, $Q$ is   $n\times n$, both invertible, and
   \item all the
  entries of $D$ are zero except the lefthand corner which is
  the $k\times k$ identity matrix, i.e.,
  $$D=\left[
    \begin{array}{cc}
      I_{k\times k} & 0\\
      0             & 0\\
    \end{array}\right]_{m\times n} $$
  \end{enumerate}
  Then
  \begin{enumerate}
   \item $\col_{k+1}(Q),\col_{k+2}(Q),\ldots, \col_n(Q)$ is a basis for
    $\nullsp(A)$,
   \item $\col_{1}(P^{-1}),\col_{2}(P^{-1}),\ldots, \col_k(P^{-1})$ is
    a basis for $\range(A)$,
   \item $Y\in\range(A)$ iff $\entry_{j}(PY)=0$ for all $j$ with
    $k+1\leq j\leq m$, and
   \item if $Y\in\range(A)$ then $A(QX)=Y$ where $X$ is any
   $n\times 1$ vector such that $\entry_j(X)=\entry_j(PY)$ for
   $j=1,\ldots,k$.
 \end{enumerate}
\end{theorem}

\proof
Recall that for any $j$
$$\col_j(BC)=B\col_j(C)$$
and for the case $C$ is the identity matrix
$$\col_j(B)= \col_j(BI)=B\col_j(I)$$
Using $PAQ=D$ so $AQ=P^{-1}D$ we have
that
$$A\col_j(Q)=P^{-1}\col_j(D).$$
Now when $1\leq j\leq k$ we have that $\col_j(D)=\col_j(I_{m\times m})$
and so
$$ 1\leq j\leq k \mbox{ implies }
A\col_j(Q)=P^{-1}\col_j(D)=P^{-1}\col_j(I_{m\times m})=\col_j(P^{-1})$$
and thus  $\col_j(P^{-1})\in\range(A)$.

But when $k+1\leq j\leq n$ we have that $\col_j(D)=Z_{m\times 1}$
and so
$$ k+1\leq j \leq n \mbox{ implies }
A\col_j(Q)=P^{-1}\col_j(D)=P^{-1}Z_{m\times 1}=Z_{m\times 1}$$
and thus $\col_j(Q)\in\nullsp(A)$.

Since the columns of an invertible matrix are linearly independent we
get that
\begin{enumerate}
   \item $\col_{k+1}(Q),\col_{k+2}(Q),\ldots, \col_n(Q)$ are $n-k$
    linearly independent vectors in $\nullsp(A)$ and
   \item $\col_{1}(P^{-1}),\col_{2}(P^{-1}),\ldots, \col_k(P^{-1})$ are
   $k$ linearly independent vectors in $\range(A)$.
\end{enumerate}

Hence, $\dim(\nullsp(A))\geq n-k$.
and  $\dim(\range(A))\geq k$.
But Theorem \ref{sum} implies that
$$n=\dim(\reals^n)=\dim(\nullsp(A))+\dim(\range(A))$$
and therefore $\dim(\nullsp(A))=n-k$ and $\dim(\range(A))=k$.
(If either were larger they could not add to $n$.)
But any set of $m$ linearly independent vectors in a space of
dimension $m$ are a basis, so this proves (1) and (2).

To see (3):
$$\begin{array}{lcl}
 Y\in\range(A) & \mbox{ iff } & \mbox{ there exists } X \;\; AX=Y \\
        & \mbox{ iff } & \mbox{ there exists } X \;\; PAX=PY \\
        & \mbox{ iff } & \mbox{ there exists } X \;\; PAQQ^{-1}X=PY \\
        & \mbox{ iff } & \mbox{ there exists } U \;\; PAQU=PY \\
        & \mbox{ iff } & \mbox{ there exists } U \;\; DU=PY \\
        & \mbox{ iff } & PY \in\range(D)\\
\end{array}$$
But $\range(D)$ is exactly the set of all those vectors whose coordinates
$\geq k+1$ are zero, i.e.
$$D\left[\begin{array}{c} s_1\\s_2\\ \vdots \\ s_n\end{array}\right]=
\left[\begin{array}{c} t_1\\t_2\\ \vdots \\ t_m\end{array}\right]
\mbox{ iff }
s_1=t_1,\ldots,s_k=t_k \mbox{ and } t_{k+1}=0,\ldots,t_m=0$$
That is to say $Y\in\range(A)$ iff $PY\in\range(D)$ iff
$\entry_{j}(PY)=0$ for all $j$ with
    $k+1\leq j\leq m$.

To see (4).  Just note that $DX=PY$ implies $PAQX=PY$ implies
$AQX=Y$.
\qed


\end{document}