% FILE anton3IPS.tex

% AR Chapter 3. 
\section{Vectors in 2-space and 3-space}

The following functions from {\tt linalg} have meanings appropriate
to their names. Use Maple's online help if necessary.
\index{dotprod}\index{crossprod}
\begin{verbatim}
dotprod(nVec1,nVec2);
crossprod(threeVec1,threeVec2);
\end{verbatim}

Material related to this chapter is also in Maple's
{\tt geometry} and {\tt geom3d} packages.

% AR Chapter 4-in-6th ed., 4,5-in-7th ed..

\addtocounter{section}{1}
\section*{\ChEGVS\quad Euclidean and General Vector Spaces}
\ifodd\ARed\addtocounter{section}{1}\fi

We assume that, from an earlier course introducing linear algebra,
you know the definition of a {\it vector space over a field},
and the idea of {\em inner products} in $\DoubleR^n$.
(There will be more on inner products in the Chapter \ChIPS.)
In the applications in \cite{AR}, 
the field is usually the real numbers $\DoubleR$
or the rationals $\DoubleQ$.
(However,
the complex numbers $\DoubleC$ are useful, 
e.g. when looking at eigenvalues, 
and the field $\DoubleZ_2$ of integers mod 2 is
used when looking at error-correcting codes.
Slightly away from the conventional set-up,
Anton uses the {\it ring} $Z_n$ when looking at Hill ciphers in
the final Applications chapter.)

Maple prefers, for {\tt linsolve}, fields more like
the rationals $\DoubleQ$, but we won't digress any more on this here.
\smallskip

\headq{Some Examples of vector spaces} from 
[AR6] \S4.2, [AR7] \S5.1:
\begin{enumerate}
\item The set $ \DoubleR^n$ of real $n$ vectors;
\item The set $M_{mn} = \DoubleR^{m\times n}$ of $m\times n$ matrices;
\item The set $P_n$ of real polynomials of degree at most $n$;
\item The set $C[a,b]$ of continuous real-valued functions defined on the
  interval $[a,b]$.
\end{enumerate}
Because these are vector spaces, Maple allows you to add $m\times n$ matrices,
real polynomials or continuous real-valued functions,
or multiply any of them by a scalar. 
\medskip

\ifodd\ARed\setcounter{subsection}{1}\else\setcounter{subsection}{2}\fi
% AR6 \setcounter{subsection}{2}
\subsection{Subspaces} % Span, Null spaces

\headq{Definition.} A subset $W$ of a vector space $V$ is called a
{\it subspace} of $V$ if $W$ is itself a vector space under the
addition and scalar multiplication defined on $V$.

\setcounter{theorem}{0}
\begin{theorem} 
%\par\noindent{\bf Theorem AR 4.3.1.}{\it
  If $W$ is a nonempty subset of a vector space $V$,
  then $W$ is a {\it subspace} if and only if the following conditions
hold.
  \begin{enumerate} \item[]
    \begin{enumerate}
    \item  If \b u and \b v are in $W$, 
      their sum $\b u+\b v$ is in $W$.  
    \item If \b u is in $W$, the scalar multiple $k\b u$ is still
      in $W$ for any number $k$.
    \end{enumerate}
  \end{enumerate}
\end{theorem}

\headq{EXERCISE.} Show that the set of all lower triangular
$n\times n$ matrices and the set of all symmetric $n\times n$ matrices
are subpaces of $M_{nn}$,
but the set of all unit lower triangular $n\times n$ matrices is not.
\medskip

\noindent Another example of a subspace of $\DoubleR^n$,
which we will study later, is given by\par
\headq{Definition.} Let $A$ be an $m\times n$ matrix $A$. The set
$\{\b x\mid A\b x=0\}$ is called the {\it null space},
or {\it kernel}, of $A$ and is denoted by ${\rm nullSpace}(A)$, or 
%$\ker(A)$.
${\rm kernel}(A)$.

\smallskip
The Maple function 
{\tt nullspace}\index{nullspace}, or 
{\tt kernel}\index{kernel}
calculates this.

\medskip
We again assume that, from an earlier course introducing linear algebra,
you know the definitions,
given in this section of \cite{AR},
of a {\it linear combination} and {\it span}
of a set of vectors 
These are illustrated by the following.

\begin{maple}
# AR6 Section 4.3 Example 8 p168; AR7 Section 5.2 Example 9
> with(linalg,vector,augment,gausselim,backsub):
> v1:= vector( [1,2,-1] ):                    v2:= vector( [6,4,2] ):
> b:= vector( [b1,b2,b3] ):
# b is a linear combination of v1,v2 if there are scalars a1, a2 with b equal to
> evalm(a1*v1 + a2*v2); 
                    [ a1 + 6 a2, 2 a1 + 4 a2, - a1 + 2 a2 ]

# This can be done as follows
> A:= augment(v1,v2):                         x:= vector( [a1,a2] ):
> evalm(A&*x);
                    [ a1 + 6 a2, 2 a1 + 4 a2, - a1 + 2 a2 ]

# Since this is the same as  a1*v1 + a2*v2,  solve the equation    A*x = b
> U:= gausselim( augment(A,b),2 );
                             [ 1   6       b1      ]
                             [                     ]
                        U := [ 0  -8    b2 - 2 b1  ]
                             [                     ]
                             [ 0   0  b3 - b1 + b2 ]

# where  (a)  b:= vector( [9,2,7] ):
> subs (b1=9, b2=2, b3=7, evalm(U) );
                               [ 1   6   9  ]
                               [            ]
                               [ 0  -8  -16 ]
                               [            ]
                               [ 0   0   0  ]

# The row of zeroes shows that [9,2,7] is in span {v1,v2}.
# i.e. [9,2,7] = a1*v1+a2*v2, where a1, a2 are given by 
> with(linalg,col): x:= backsub(");
                             x := [ - 3, 2 ]

#        (b)  b:= vector( [4,-1,8] ):
> subs (b1=4, b2=-1, b3=8, evalm(U) );
                                [ 1   6   4 ]
                                [           ]
                                [ 0  -8  -9 ]
                                [           ]
                                [ 0   0   3 ]

# The last row shows that [4,-1,8] is not in span {v1,v2}.
# i.e. [4,-1,8] is not a linear combination of v1,v2.
\end{maple}

This not only shows that the combination in a given linear combination need
not be unique, but also illustrates 
the following:

%\headq{THEOREM } 
\theoremNN{\it If $A$ is a matrix whose columns are $\rowi{\b a}{n}$,
  then}\par
   \smallskip\centerline{ {\rm span}\{$\rowi{\b a}{n}\}=\{A\b x: \b x\in \DoubleR\}$. }
\theoremNNEnd

Note also that in the above Maple example, the span of $\b v1$ and $\b v2$ is

\smallskip\centerline{ ${\rm span}\{\b v1,\b v2\}=\{[b1, b2,b3]\mid 
b1 = b2+b3\}$.}
\goodbreak

%\smallskip\noindent Thus (since, for example,
%$[4,-1,8]\not\in {\rm span}\{v1,v2\}$\/) 
%$v1$ and $v2$ do not span $\DoubleR^3$.

\subsection{Linear Independence ([J] \S2.2)}
Once again, it is assumed that, from an earlier course in linear algebra,
you are familiar with the terms {\it linear dependence} and
{\it linear independence}, defined as follows in this section of 
\cite{AR}.
\headq{Definition.} 
  If $S=\{\rowi{\b v}{r}\}$ is a nonempty set of vectors, 
  then the vector equation
    $$  k_1 \b v_1 + \ldots k_r \b v_r = \b 0 . $$
  has at least one solution, namely
    $$ k_1 = 0, \ldots , k_r = 0 .$$
  If this is the only solution, then $S$ 
  is called a {\it linearly independent} set.
  If there are other solutions, then $S$ is called a
  {\it linearly dependent} set.

\begin{maple}
# Example 4 - AR6 Section 4.4 p174; AR7 Section 5.3 p223
> with(linalg):
> v1:= vector([1,-2,3]):    v2:= vector([5,6,-1]):    v3:= vector([3,2,1]):
# These are linearly dependent if there are numbers c1, c2, c3, not all zero,
# such that                      0 = c1*v1 + c2*v2 + c3*v3
# These can be found as follows
> A:= augment( v1,v2,v3 ):
> U:= gausselim( augment(A,vector([0,0,0])) );
                                 [ 1   5  3  0 ]
                                 [             ]
                            U := [ 0  16  8  0 ]
                                 [             ]
                                 [ 0   0  0  0 ]

> x:=backsub(");
                       x := [ - 1/2 t3, - 1/2 t3, t3 ]

# This shows that the  v1,v2,v3  above are linearly dependent. For example
> evalm( v1 + v2 - 2*v3 );
                                    [ 0, 0, 0 ]

# In particular    number of pivot columns in U  <=  rowdim(U)  =  rowdim(A)
# So the equations must always have a solution for any vectors  v1, v2, v3
\end{maple}

Reworking the above example with three vectors in $\DoubleR^2$ would
illustrate the following.
This is 
[AR6] Theorem 1.3.1 and 4.4.3;
[AR7] Theorem 1.2.1 and 5.3.3.
\smallskip

% AR6 \headq{THEOREM 1.3.1 and 4.4.3 } 
\theoremNN{\it Suppose 
$r$ and $n$ are integers with $r>n>0$. Then
\begin{enumerate} \item[]
  \begin{enumerate}
  \item a homogeneous system of $n$ linear equations in $r$ unknowns has a
    non-trivial solution;\quad and so
  \item any set of $r$ vectors in $\DoubleR^n$ is linearly dependent.
  \end{enumerate}
\end{enumerate}}
\theoremNNEnd

\subsection{Basis and Dimension ([J] \S2.3)}
Here again is another definition with which you should be familiar.
\medskip

\headq{Definition.} A {\it basis} for a vector space $V$ is
  a set $S$ of vectors such that
  \begin{enumerate} \item[]
  \begin{enumerate}
  \item $S$ is linearly independent,\quad and
  \item $S$ spans $V$.
  \end{enumerate}
  \end{enumerate}
 
\begin{maple}
# Example 3 - AR6 Section 4.5 p184; AR7 Section 5.4 p246
> with(linalg):
\end{maple}
\goodbreak
\begin{maple}
# Show that the vectors v1,v2,v3 form a basis for R^3, where
> v1:=vector([1,2,1]):      v2:=vector([2,9,0]):      v3:=vector([3,3,4]):
#
# We need to show that v1, v2, v3 span R^3 and are linearly independent.
# To show they span R^3, consider an arbitrary vector in R^3
> b:=vector([b1,b2,b2]):
# and solve the equation    Ac = b  where
> A:= augment( v1,v2,v3 );
                                   [ 1  2  3 ]
                                   [         ]
                              A := [ 2  9  3 ]
                                   [         ]
                                   [ 1  0  4 ]

> gausselim( augment(A,b) );
                       [ 1  2    3          b1       ]
                       [                             ]
                       [ 0  5   -3      b2 - 2 b1    ]
                       [                             ]
                       [ 0  0  -1/5  7/5 b2 - 9/5 b1 ]


# Since the pivots on the diagonal of this matrix are all non-zero, the
#    equation    Ac = b  has a solution for any b1,b2,b2, and so they span R^3.
# In fact the solutions are unique and so, setting b1 = b2 = b3 = 0,
#    we can see that the equation    Ac = 0  has only one solution.
# Thus v1, v2, v3 are linearly independent.
\end{maple}
\medskip

\setcounter{theorem}{2}
\begin{theorem} 
%\headq{THEOREM AR 4.5.3.} {\it
Any two bases for a finite dimensional vector space have the same
number of vectors.
\end{theorem}
%  Suppose that $\rowi{v}{n}$ and
%  $\rowi{w}{m}$ are both bases for the same vector space $V$.  Then $m=n$.

\noindent This leads to the following:

\smallskip
\headq{Definition.} The {\it dimension} of 
a finite dimensional vector space $V$  is  defined to be the
number of vectors in a basis for $V$.
In addition, we define the zero vector space to have dimension 0.
\medskip

\ifodd\ARed\addtocounter{theorem}{1}\fi
\begin{theorem} 
%\headq{THEOREM 4.5.4.} {\it \\
\begin{enumerate}\item[]
\begin{enumerate}
\item If $S=\{\rowi{\b v}{n}\}\subset V$ is a set of $n$ linearly
 independent vectors in an $n$-dimensional vector space $V$,
 then $S$ is a basis for $V$.
\item If $S=\{\rowi{\b v}{n}\}\subset V$ is a set of $n$ 
 vectors that spans an $n$-dimensional vector space $V$,
 then $S$ is a basis for $V$.
\end{enumerate}\end{enumerate}
\end{theorem}

% 4.5.5
\begin{theorem} 
 Let $V$ be an $n$-dimensional vector space.
\begin{enumerate}\item[]
\begin{enumerate} 
\item If $S=\{\rowi{\b v}{r}\}\subset V$ is a linearly
 independent set of vectors in $V$, and if $r<n$, 
 then $S$ can be enlarged to a basis for $V$;
 that is, there are vectors ${\b v}_{r+1},\ldots,{\b v}_n$ such that
 $\{\rowi{\b v}{n}\}$ is a basis for $V$.
\item If $W$ is a subspace of $V$, then
$\dim(W)\leq\dim(V)$; moreover, $\dim(W)=\dim(V)$
if and only if $W=V$.
\end{enumerate}\end{enumerate}
\end{theorem}

\headq{Definition.} If $S$ and $T$ are subsets of vector space $V$,
define the {\it sum} of $S$ and $T$ by
$$S+T = \{s+t\mid \ s\in S, t\in T\} .$$

%\headq{THEOREM} 
\theoremNN{\it 
Let $U$ and $V$ be vector subspaces of vector space $W$.
Then
$$\dim(U+V) + \dim(U\cap V) = \dim(U) + \dim(V) .$$
}
\theoremNNEnd

\smallskip

For uses of Maple's 
{\tt basis}\index{basis}
command, see \cite{J}.

\goodbreak
\subsection{Row Space, Column Space and Nullspace ([J] \S2.4)}

Maple has some commands concerning bases of subspaces of $\DoubleR^n$
and similar finite-dimensional vector spaces.  Here are some examples
of finding a basis for the 
{\tt nullspace}\index{nullspace} or 
{\tt kernel}\index{kernel} of a matrix.
\begin{maple}
> with(linalg):
> I3:= diag(1,1,1):                                  nullspace(I3);
                                       {}

# Output like  {}  indicates that the answer is the zero subspace.
#
# AR6 Section 4.6 Example 3 p195; AR7 Section 5.5 Example 4 p263
# Find the null space of the matrix
> A:= matrix( [[ 2, 2,-1, 0, 1],  
               [-1,-1, 2,-3, 1],  
               [ 1, 1,-2, 0,-1],
               [ 0, 0, 1, 1, 1]] ):
> nA:=nullspace(A);
                  nA:= {[ 1, -1, 0, 0, 0 ], [ 0, -1, -1, 0, 1 ]}

# The displayed vectors are a basis for nullSpace(A), or kernel, of A.
#
# Alternatively, solve the equation  Ax = 0  by reducing A to Echelon form
> U:= gausselim(A):                                   nU:= nullspace(U);
                  nU:= {[ 1, -1, 0, 0, 0 ], [ 0, -1, -1, 0, 1 ]}
> basis([op(nA),op(nU)]);   # has 2 elements like nA or nU
# Thus nullSpace(U) = nullSpace(A), illustrating the theorem in [AR]
\end{maple}
    $$ {\rm nullSpace}(A) = {\rm nullSpace}(U). $$

\medskip
%\subsection{The Fundamental Subspaces of a Matrix; Rank}

\headq{Definition.} Let $A$ be an $m\times n$ matrix. Then
  \begin{enumerate}\item[]
  \begin{enumerate}
  \item the {\it row space}, ${\rm rowSpace}(A)$, of $A$ is the set of all linear combinations
    of the rows of $A$;
  \item the {\it column space}, ${\rm colSpace}(A)$, of $A$ is the set of all
    linear combinations of the columns of $A$.
  \end{enumerate} \end{enumerate}

The linalg package of Maple has commands for finding bases for the three
fundamental subspaces of matrix $A$ (an example of the use of these commands
is given below).
\medskip

\index{nullspace}\index{kernel}\index{rowspace}\index{colspace}
\begin{center}
  \begin{tabular}{ || l | l ||}        \hline
    Subspace	&Maple function \\ \hline
    null space, or kernel & {\tt nullspace}, or {\tt kernel}\\
    row space             & {\tt rowspace}\\
    column space          & {\tt colspace}\\  \hline
  \end{tabular}
\end{center}
\medskip

\label{nullity}
\begin{maple}
> with(linalg):
> A:= matrix( [[a11,a12,a12],  
>              [a21,a22,a22]] ):
> nullspace(A);
                                 {[ 0, -1, 1 ]}

> rowspace(A);
                           {[ 1, 0, 0 ], [ 0, 1, 1 ]}

> colspace(A);
                              {[ 0, 1 ], [ 1, 0 ]}
\end{maple}
\goodbreak
(Maple is a bit cavalier in assuming that the entries of $A$
are not zero).  There are two vectors in the basis for the row space,
and so the dimension of the row space is 2.
Also note that the number of vectors for the basis of the column space
is the same as  for the row space, but the basis vectors are different. 
Unfortunately, Maple notation does not distinguish between row and column
vectors. Thus, the basis vectors for the column space appear to be row vectors,
although they are actually column vectors. This affects the next example.

\begin{maple}
# AR6 Section 4.6 Example 4 p196- ; AR7 Section 5.5 Example 7 p267-
> with(linalg):
# Example 4:    Find a basis for the vector space spanned by
> v1:= vector( [ 1,-2, 0, 0, 3] ):     v2:= vector( [ 2,-5,-3,-2, 6] ):
  v3:= vector( [ 0, 5,15,10, 0] ):     v4:= vector( [ 2, 6,18, 8, 6] ):
#
# To do this, find a basis for the row space of the matrix A
> A:= matrix( [v1, v2, v3, v4] ):                         rowspace(A);
         {[ 0, 0, 1, 1, 0 ], [ 0, 1, 0, -1, 0 ], [ 1, 0, 0, -2, 3 ]}


# Now consider the rowspace of the Echelon form U of A.
> U:= gausselim(A);
                              [ 1  -2   0    0   3 ]
                              [                    ]
                              [ 0  -1   -3   -2  0 ]
                         U := [                    ]
                              [ 0   0  -12  -12  0 ]
                              [                    ]
                              [ 0   0   0    0   0 ]

> rowspace(U);
         {[ 0, 0, 1, 1, 0 ], [ 0, 1, 0, -1, 0 ], [ 1, 0, 0, -2, 3 ]}

#    which iluustrates that rowSpace(A) = rowSpace(U).
\end{maple}
In fact, if $U$ is the Echelon form of {\em any} matrix $A$,
\quad ${\rm rowSpace}(A)={\rm rowSpace}(U)$
\quad and so
  $$\dim({\rm rowSpace}(A))
   = \dim({\rm rowSpace}(U))
   = \mbox{number of non-zero rows of}~U
   = \mbox{number of pivots of}~U$$
\begin{maple}
# Find bases for the column spaces colSpace(U) and colSpace(A):
> basis([ col(U,1..5) ]); 
             [[ 1, 0, 0, 0 ], [ -2, -1, 0, 0 ], [ 0, -3, -12, 0 ]]

# These are just the pivot columns of U (i.e. the columns of U with pivots)
> colspace(A);
             {[ 0, 1, -5, 0 ], [ 1, 0, 10, 0 ], [ 0, 0, 0, 1 ]}

# Because of the 1's in the last places in some of the last set of vectors,
#                       colSpace(A) <> colSpace(U)
#
# These two bases have the same number of vectors as the number of pivots of U.
# Thus  dim colSpace(A) = dim colSpace(U) = dim rowSpace(U) = dim rowSpace(A).
\end{maple}


\subsection{Rank and Nullity}

\setcounter{theorem}{0}
\begin{theorem} 
%\headq{THEOREM AR 4.7.1.} {\it
If $A$ is any matrix, then the row space and column space of $A$
have the same dimension.
\end{theorem}
%  Let $A$ be an $m\times n$ matrix.  Then 
%    $$ \dim {\rm colSpace}(A) = \dim {\rm rowSpace}(A).$$
%  This dimension is called the {\em rank} of $A$.

% \setcounter{theorem}{??}
% \begin{theorem} 
% \noindent{\bf THEOREM 2D.} {\it Suppose elimination reduces $Ax=b$ to $Ux=c$.
% Let there be $r$ pivots; the last $m-r$ rows of $U$ are zero.
% Then there is a solution only if the last $m-r$ components of $c$ are also zero.
% If $r=m$, there is always a solution.
% \end{theorem}

% The general solution is the sum of a particular solution
% (with all free variables zero) and a homogeneous solution
% (with the $n-r$ free variables as independent parameters).
% If $r=n$, there are no free variables and the null space contains only $x=0$.}

\smallskip 
Thus the rank of a matrix is the number of linearly independent rows
(or columns). 
%From what we know of the effects of row-operations,
%alternatively ,
%the rank of a matrix is the number of its pivots.
\smallskip

The Maple function to determine the rank of a matrix is 
{\tt rank}\index{rank}.
\begin{maple}
> with(linalg):
> A:= matrix( [[a11,a12,a12],  
>              [a21,a22,a22]] ):
> rank(A);
                                       2
\end{maple}
This checks with your previous results on the {\tt colspace} and
{\tt rowspace} of $A$:\quad ${\rm rank}(A)=2$.
\medskip

We have now seen above that, when $A$ is reduced to the Echelon form $U$,
\begin{tabbing}
dim(${\rm nullSpace}(A)$)\quad\==\quad dim(${\rm rowSpace}(A)$)\quad
  = \quad number of %leading variables
   \= in blah blah blah blah \kill
${\rm nullSpace}(A)$\> =\quad ${\rm nullSpace}(U)$
   \> ${\rm rowSpace}(A)$\quad =\quad ${\rm rowSpace}(U)$\\
  \\
dim(${\rm nullSpace}(A)$)\> =\quad number of free variables in the equation
                                  $Ux = \b 0$ \\
  \\
  \quad rank ($A$)\> =\quad dim(${\rm rowSpace}(A)$)\quad
              =\quad number of leading variables in the equation $Ux = \b 0$.
\end{tabbing}

In a like manner, one defines ${\rm nullity}(A)=\dim({\rm nullSpace}(A))$.

The  discussion above proves the following

\ifodd\ARed\addtocounter{theorem}{1}\fi
%\headq{THEOREM 4.7.2. Rank-Nullity Theorem.} {\it 
\begin{theorem}[Rank-Nullity Theorem.]
If $A$ is a matrix with $n$ columns, then
$${\rm rank}(A) + {\rm nullity}(A) = n.$$
\end{theorem}
%Let $A$ be an $m\times n$ matrix. 
%  \begin{enumerate} \item[]
%    \begin{enumerate}
%    \item dim ${\rm rowSpace}(A$) + dim ${\rm nullSpace}(A$) = $n$.
%    \item dim ${\rm colSpace}(A$) + dim ${\rm nullSpace}(A$) = $n$.
%    \item   rank($A$) + dim ${\rm nullSpace}(A$) = $n$.
%    \end{enumerate}
%  \end{enumerate}
\medskip

\noindent Thus, in the example on page~\pageref{nullity} of these notes,
we see that
  $$ \dim({\rm nullSpace}(A)) = 3 - {\rm rank}(A) = 3 - 2 = 1.$$


\subsection*{Coordinates and Change of Basis}

We chose to depart slightly from the ordering in \cite{AR}.
This material, on transition matrices, is given in 
\cite{AR} at the end of Chapter \ChIPS,
but it does not depend on inner-products, so we chose to present it
earlier, so that all items in Chapter \ChIPS\ will relate to inner-products.
This material can be read with the treatment of matrices of linear
transformations from Chapter \ChLT.

%\headq{THEOREM } 
\theoremNN{\it 
  Suppose that $S = [\rowi{\b v}{n}]$ is a basis for the vector space $V$. 
  Then any vector in $V$ can be expressed
  in one and only one way as a linear combination of $\rowi{\b v}{n}$.
  Thus if $\b x\in V$, there are unique scalars $\rowi{a}{n}$ such that
    $$ \b x = a_1 \b v_1 + \cdots + a_n \b v_n. $$
  {\em The numbers $\rowi{a}{n}$ are called the {\em co-ordinates} of \b x
  relative to the (ordered) basis $S$.
  They are usually stored as the co-ordinate vector $[\b x]_S=[\rowi{a}{n}]$}.
} %\end{theorem}
\theoremNNEnd

\begin{maple}
# Adapted from 
# AR6 Section 5.4 Example 2 p251; AR7 Section 6.5 Example 4 p343
> with(linalg):
# Find the coordinates of the vector x  relative to the basis  u1,u2  where
> x:= vector([x1,x2]):
  u1:=vector([1,1]):        u2:=vector([2,1]):
#
# First check that it is a basis for R^2 using the  rank  function:
\end{maple}
\goodbreak
\begin{maple}
> B:= augment( u1,u2 ): rank(B);
                                       2

# Thus  dim( colSpace(B) ) = 2 and so the columns are a basis for R^2.
#
# To find the coordinates of  x  relative to  {u1,u2}, solve  as follows
> xB:= linsolve(B,x);
                         xB := [ 2 x2 - x1, - x2 + x1 ]
\end{maple}

Note that the columns of the matrix $B$ form a basis for $\DoubleR^2$.
Thus $B$ is invertible and so the system $B [\b x]_B = \b x$ can be solved
(in theory) by inverting $B$, giving\quad $[\b x]_B = B^{-1}\b x$.

Similarly, if $\{\b v_1,\b v_2,\}$ is another basis for $\DoubleR^2$, then
the coordinates of \b x relative to this basis are given by\quad
$[\b x]_C = C^{-1}\b x$\quad where $C=(\b v_1,\b v_2,)$.\quad Thus
  $$[\b x]_C = P [\b x]_B\quad {\rm where}\quad P = C^{-1}B.$$
Continuing the above example,
\begin{maple}
# Find the coordinates of  x  relative to the basis  v1,v2  where
> v1:=vector([2,1]):         v2:=vector([1,1]):
> C:= augment( v1,v2 ):                                xC:= linsolve(C,x);
                            xC := [ - x2 + x1, 2 x2 - x1 ]

# Alternatively:
> P:= evalm( inverse(C)&*B );
                                     [ 0  1 ]
                                P := [      ]
                                     [ 1  0 ]

> evalm( P&*xB );
                          [ - x2 + x1, 2 x2 - x1 ]
\end{maple}

\headq{Definition.} Let $V$ be a finite-dimensional vector space with bases
  $B$ and $C$. Then the {\em transition matrix} from $B$ to $C$ is the
  (invertible) matrix $P$ such that
    $$ P [x]_B = [x]_C\qquad \mbox{for all \b x}\in V. $$

\noindent If $V=\DoubleR^n$, then the transition matrix 
can be found by row-reducing the matrix $(C\mid B)$ to $(I\mid P)$, where $B,C$
are the matrices whose columns are the given bases.

%\subsection{Error-Correcting Codes} 
%Notes on this are available separately.

\vfill 
\eject

%
%
% AR Chapter \ChIPS   (5 in 6ed., 6 in 7ed.)

\setcounter{section}{\ChIPSm}
\section{Inner Product Spaces}


\subsection{Inner Products}
We again assume that, from an earlier course in linear algebra,
you have seen the properties of 
dotproducts, inner products, in $\DoubleR^n$.
Here is another example of an inner product:
$$ \langle f , g\rangle = \int_a^b f(x) g(x) dx . $$

\begin{maple}
# Show that the following is an inner product:
> a:='a': b:='b': r:='r':
> dot:= proc(fx,gx,lims)        int( expand(fx*gx),x=lims )        end:
> combine( dot(f(x),h(x),a..b) +dot(g(x),h(x),a..b) -dot((f+g)(x),h(x),a..b) );
                                       0

> combine( dot(f(x),g(x),a..b) - dot(g(x),f(x),a..b) );
                                       0

> combine( dot(r*f(x),g(x),a..b) - r*dot(f(x),g(x),a..b) );
                                       0
\end{maple}
Note that {\tt combine} was needed to force the linearity of integration
(use {\tt help} for more details).

\medskip
\headq{Definition.} A (real) {\em inner product space} is a vector space 
equipped 
with an inner product, ${\langle\cdot,\cdot\rangle}$,
 which has the properties of symmetry, additivity,
homogeneity and positivity as given in 
[AR6] p215, [AR7] p287.

\headq{Definition.} If $\b u$ is a vector in an inner product space, 
the {\em norm}
of $\b u$ is $\Vert\b u\Vert = \sqrt{\langle\b u,\b u\rangle}$.
%\sqrt{\b u\cdot \b u}$.

Maple's {\tt linalg} package has functions 
{\tt dotprod}\index{dotprod} and 
{\tt norm}\index{norm} which
calculate dot products and find norms respectively of vectors in $\DoubleR^n$
(get {\tt help} on these functions). Note that this {\tt norm} is
different from the function {\tt norm} not in the {\tt linalg} package.\quad
To find the norm of the vector $\b v$, use
\begin{verbatim}
  norm(v,2);    # This is the standard norm  -  there are others.
\end{verbatim}

\subsection{Angle and Orthogonality in Inner Product Spaces}

% AR 5.2.1
\setcounter{theorem}{0}
\begin{theorem}[Cauchy-Schwarz inequality.]
If $\b u$ abd $\b v$ are vectors in an
  inner product space $V$, then
    $$ \vert\langle\b u,\b v\rangle\vert^2 \leq
     \vert\langle\b u,\b u\rangle\vert 
     \vert\langle\b v,\b v\rangle\vert . $$
\end{theorem}

% AR 5.2.2
\begin{theorem}[Triangle inequality.]
 If $\b u$ and $\b v$ are vectors in an
  inner product space $V$, then
    $$ \Vert\b u + \b v\Vert  \leq \Vert\b u\Vert + \Vert\b v\Vert. $$
\end{theorem}

\medskip\noindent
The following theorem gives a convenient representation of dot products in
$\DoubleR^n$.

%\setcounter{theorem}{15}
%\begin{theorem} 
%\headq{THEOREM }
\theoremNN{\it
Suppose we identify a $1\times 1$ matrix with its (single)
   entry.  If $\b u,\b v\in \DoubleR^n$ are represented as column vectors, then
    $$ \langle\b u , \b v\rangle  = \b u^T \b v $$
defines an inner-product on $\DoubleR^n$. Henceforth we denote
this inner-product  by
    $$ \b u\cdot \b v = \b u^T \b v $$
} %\end{theorem}
\theoremNNEnd

\begin{maple}
# Here is an example for this theorem:
> with(linalg):
> u:= vector( [u1,u2] ):                             v:= vector( [v1,v2] ):
> dotprod(u,v) - evalm( transpose(u)&*v );
                                       0

# Note that Maple treats vectors as COLUMN vectors (i.e. m by 1 matrices). So
> evalm( u&*transpose(v) );
                                [ u1 v1    u1 v2 ]
                                [                ]
                                [ u2 v1    u2 v2 ]
\end{maple}

%\setcounter{theorem}{17}
%\begin{theorem} 
%\headq{THEOREM }
\theoremNN{\it
Let $A$ be an $m\times n$ matrix. Then\par
  \qquad {\em(a)}\quad ${\rm nullSpace}(A^TA) = {\rm nullSpace}(A);$
  \qquad\qquad {\em(b)}\quad $rank(A^TA) = rank(A).$
} %\end{theorem}
\theoremNNEnd
\headq{COROLLARY } {\em If the matrix $A$ has linearly independent columns,
  then $A^T A$ is invertible.}

\smallskip
\headq{EXERCISE.} Show that $A^T A$ is symmetric and\quad
  $\langle \b x,\b y\rangle = \b x^TA^T A\b y$\quad is an inner product
  if the columns of $A$ are linearly independent.

\medskip
\subsection*{The general least squares problem}

From before we have

%\setcounter{theorem}{20}
%\begin{theorem}
%\headq{THEOREM } 
\theoremNN{\it
 If $A$ is a matrix, then the system\quad $A\b x=\b y$\quad is
  consistent if and only if \b y is in the column space ${\rm colSpace}(A)$ of $A$.
} %\end{theorem}
\theoremNNEnd

In a Chapter \ChMO\ of \cite{AR}, we
consider the situation where\quad $A\b x=\b y$\quad is
inconsistent (i.e. has no solution). 
The notation we use there will be \quad $M\b x=\b y$\quad
but here we use $A$ rather than $M$. In this case, it is natural to
look for an \b x which makes $A\b x$ as close as possible to \b y.
[AR7] p329 gives the definition.

\smallskip
\headq{Definition.} The {\em least squares problem} for the inconsistent
  system\quad $A\b x=\b y$\quad is to find a vector ${\b x}_*$
  (called the {\em least squares solution} to the system) such that
  $\Vert\b y - A{\b x}_*\Vert$ is a minimum.

\smallskip
Maple has a function 
{\tt leastsqrs}\index{leastsqrs}
in the {\tt linalg} package.
(Get {\tt help} on it.) 
If $A$ is a matrix and \b y is a vector, then {\tt leastsqrs(A,y)}
finds the least squares solution of the system $A\b x=\b y$.
In Chapter \ChMO\ we will also
see the {\tt regression} function in the {\tt stats}
packages used in applications of least squares {\it approximation}.
(The simplest, and possibly the most widely used application 
of the material in this part of Chapter \ChMO\ is the fitting of
a straight line to data points.)

For a least squares problem 
  \quad $A\b x=\b y$\quad , we define the associated
{\tt normal equations}
$$ A^T A{\b x} = A^T{\b y} .$$
\smallskip

\theoremNN{{\bf AR7 6.4.2} \it  For any linear system
  \quad $A\b x=\b y$\quad , the associated normal system
$$ A^T A{\b x} = A^T{\b y} ,$$
is consistent, and all solutions of the normal system
are least squares solutions of 
  \quad $A\b x=\b y$.
} %\end{theorem}
\theoremNNEnd


Most of the rest of this chapter has uses in theory associated
with least squares.

\subsection*{Orthogonal projections}

\smallskip
\headq{Definition.} Suppose $W$ is a subspace of $\DoubleR^m$ and
  $\b y\in \DoubleR^m$.
  Then the {\em perpendicular projection} of $\b y$ into $W$ is the unique
  vector $\b p\in W$ such that $\b y - \b p\perp W$ and the function which
  maps each $\b y$ onto its perpendicular projection is called the
  {\em perpendicular projection function}.

\smallskip
\headq{EXERCISE.} Show that the perpendicular projection function is a linear
  transformation.

%\begin{theorem}
%\headq{THEOREM }
\theoremNN{{\bf AR7 6.4.2.} \it 
 Let $A$ be an $m$ by $n$ matrix, and let $W$ be the column space of
 $A$. Let $\b x$ be any least squares solution of
  \quad $A\b x=\b y$\quad , then the orthogonal projection of
 $\b b$ on $W$ is
$$ {\rm proj}_W {\b b} = A{\b x} .$$
} %\end{theorem}
\theoremNNEnd

%\begin{theorem}
%\headq{THEOREM }
\theoremNN{{\bf AR7 6.4.4.} \it 
 Assume $A$ has linearly independent columns.
  Then the matrix of the perpendicular projection function into 
  ${\rm colSpace}(A)$ is\quad
  $P=A (A^T A)^{-1} A^T$.
} %\end{theorem}
\theoremNNEnd

\headq{EXERCISE.} Show that $P$ satisfies the following properties:

  \smallskip
  \qquad(a) $P^2 = P$.\qquad\qquad\qquad(b) $P^T = P$.

 \smallskip
 Conversely, any symmetric matrix with $P^2=P$ represents a projection function.


\subsection{Orthonormal Bases; Gram-Schmidt Process ([J] \S2.5)}

This section shows how the idea of the perpendicular projection can be used to
find a special basis for a vector space.

\smallskip
\headq{Definitions.} The vectors $\rowi{\b v}{m}$ are

  \quad {\it orthogonal}\quad if $\langle\b v_i,\b v_j\rangle = 0$ 
    whenever $i\ne j$.

  \quad {\it orthonormal}\quad if they are orthogonal and each
  $\Vert\b v_i\Vert=1$.

% In particular, an orthogonal spanning set is an orthogonal basis.
\smallskip

\setcounter{theorem}{0}
\begin{theorem} 
If $S=\{\rowi{\b v}{n}\}$ is an orthonormal basis for an inner-product
space $V$, and $\b u$ is any vector in $V$, then 
$$\b u = \langle\b u\cdot\b v_1\rangle \b v_1 + \ldots
         \langle\b u\cdot\b v_n\rangle \b v_n . $$
\end{theorem}

% AR 5.3.3
\setcounter{theorem}{2}
\begin{theorem}
 Any set of nonzero orthogonal vectors is linearly independent.
\end{theorem}


\subsubsection*{The Gram-Schmidt process}
The Gram-Schmidt
process starts with linearly independent vectors $\rowi{\b v}{n}$
and ends with orthonormal vectors $\rowi{\b u}{n}$.  At step $k$
it subtracts from $\b v_k$ its projection onto span$\{\rowi{\b v}{k-1}\}$:
$$\b w_k = \b v_k  - \sum_{i=1}^{k-1} (\b u_i^T \b v_k) \b u_i ,$$
and then $\b u_k$ is defined to be the unit vector
$\b w_k/\Vert\b w_k \Vert$.\index{GramSchmidt}

\begin{maple}
# Example 7 - AR6 Section 5.3 p242; AR7 Section 6.3 p320
> with(linalg,vector,GramSchmidt,dotprod,norm):
# Use GramSchmidt to find an orthonormal basis for the spaces
# spanned by the list of vectors [v1,v2,v3] where
> v1:= vector([1,1,1]):    v2:= vector([0,1,1]):    v3:= vector([0,0,1]):
# This can be done using the function  GramSchmidt  in the  linalg  package:
\end{maple}
\goodbreak
\begin{maple}
> GramSchmidt( [v1,v2,v3] );
             [[ 1, 1, 1 ], [ -2/3, 1/3, 1/3 ], [ 0, -1/2, 1/2 ]]

# Each of these should be divided by its norm to give an orthonormal basis
#
# To help understand the process, we also do it as follows:
> w1:= v1:                                    u1:= evalm( w1/norm(w1,2) ):
  w2:= evalm( v2 - dotprod(v2,u1)*u1 ):       u2:= evalm( w2/norm(w2,2) ):
  w3:= evalm( v3 - dotprod(v3,u1)*u1 - dotprod(v3,u2)*u2 ):
  u3:= evalm( w3/norm(w3,2) ):
  print (u1,u2,u3);
                      1/2       1/2       1/2
               [ 1/3 3    , 1/3 3   , 1/3 3    ],

                  1/2  1/2       1/2  1/2       1/2  1/2
         [ - 1/3 2    3   , 1/6 2    3   , 1/6 2    3    ],

                                   1/2       1/2
               [ 0        , - 1/2 2   , 1/2 2    ]

# Apart from the norms of the vectors, this agrees with the above.
\end{maple}

\ifodd\ARed\addtocounter{subsection}{1}\fi
\subsection{Changes of orthonormal bases; Orthogonal matrices} 

\headq{Definition.} A square matrix $Q$ such that $Q^T Q=I$
is said to be an {\it orthogonal} matrix.

The function 
{\tt orthog}\index{orthog}
(in Maple's {\tt linalg} package) which returns the
value {\tt true} if the given matrix is orthogonal.

\medskip
\headq{Examples.} In 
[AR7] Example 2 \S6.5 p338
it is shown that the rotation
$$ Q(\theta) = \pmatrix{\cos (\theta)&-\sin (\theta)\cr
                        \sin (\theta)&\cos (\theta)\cr} ,$$
is orthogonal. Also any permutation matrix is an orthogonal matrix.

%\setcounter{theorem}{59}
%\begin{theorem}
%\headq{THEOREM } 
\theoremNN{\it 
 If $A$ is an $m\times n$ matrix with orthonormal columns, then
    $$ A^T A = I$$
} %\end{theorem}
\theoremNNEnd

% AR 5.4.3
\ifodd\ARed\setcounter{theorem}{0}\else\setcounter{theorem}{2}\fi
% AR6 \setcounter{theorem}{2}
\begin{theorem}
The following are equivalent for an $n\times n$ real matrix $Q$:
  \begin{enumerate}
  \item[]
    \begin{enumerate}
    \item $Q$ is orthogonal.
    \item the row vectors of $Q$ form an orthonormal set in
          $\DoubleR^n$ with the usual Euclidean inner product.
    \item the column vectors of $Q$ form an orthonormal set in
          $\DoubleR^n$ with the usual Euclidean inner product.
    \end{enumerate}
  \end{enumerate}
\end{theorem}

\smallskip
\headq{Warning} A square matrix with orthogonal columns is not called
  orthogonal unless its columns also have norm 1.
\smallskip

%\begin{theorem}
%\headq{THEOREM } 
\theoremNN{{\bf AR7 6.5.3} \it 
The following are equivalent for an $n\times n$ real matrix $Q$:
  \begin{enumerate}
  \item[]
    \begin{enumerate}
    \item $Q$ is orthogonal.
    \item $Q^T=Q^{-1}$;
    \item $Q$ preserves inner products:\qquad
      $(Q \b x)^T (Q \b y) = \b x^T Q^T Q \b y = \b x^T \b y$;
    \item $Q$ preserves norms:\qquad
      $\Vert Q \b x\Vert = \Vert\b x\Vert$\quad for every vector \b x.
    \end{enumerate}
  \end{enumerate}
} %\end{theorem}
\theoremNNEnd

%\setcounter{theorem}{62}
%\begin{theorem}
%\headq{THEOREM } 
\theoremNN{\it 
  The product (and inverses) of orthogonal matrices is orthogonal.
} %\end{theorem}
\theoremNNEnd

\medskip

% Chpt IPS continues in anton3QR.tex
