% Hill3.tex

\section{Vector spaces}
\setcounter{subsection}{3}
We assume that, from an earlier course introducing linear algebra,
you know the definition of a {\bf vector space over a field}.
In all the applications in Hill, the field is usually the real numbers \DoubleR
(although the complex numbers \DoubleC are used in \S 5.2 and \S 5.4
when looking at eigenvalues, and the field $\DoubleZ_2$ of integers mod 2
is used in \S 3.9 when looking at error-correcting codes).

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 Hill \S 3.3 (pages 155-157).
\begin{enumerate}
\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. An example is given below.
\begin{verbatim}
# Hill Section 3.3 Example 9 p156.
# Sums and scalar multiples of continuous real-valued functions
#
> f:= x->x:              # This is the function whose rule is  f(x) = x
> twosin:= 2*sin:                                     SUM:= f + sin:
#
# If your computer terminal has graphics capabilities, you should plot these:
> plot( {f(x),sin(x),twosin(x),SUM(x)},-Pi..Pi ):
# If your computer terminal does not have graphics capabilities,
#  the following may help you visualise them:
> f(0),sin(0),twosin(0),SUM(0);
                                   0, 0, 0, 0

> f(Pi/2),sin(Pi/2),twosin(Pi/2),SUM(Pi/2);
                         1/2 Pi,  1,  2,  1/2 Pi + 1

> f(Pi/3),sin(Pi/3),twosin(Pi/3),SUM(Pi/3);
                              1/2    1/2                 1/2
                1/3 Pi,  1/2 3   ,  3   ,  1/3 Pi + 1/2 3

# Hill Section 3.3 Example 10 p157 will be done in chapter 4.
\end{verbatim}
\medskip

\subsection{Subspaces, Span, Null spaces}
\setcounter{theorem}{26}
\begin{theorem} 
  A nonempty subset $S$ of a vector space is a 
  {\bf subspace} if it satisfies both:
  \begin{enumerate} \item[]
    \begin{enumerate}
    \item  If \b u and \b v are in $S$, 
      their sum $\b u+\b v$ is in $S$.  
    \item If \b u is in $S$, the scalar multiple $r\b u$ is still
      in $S$ for any number $r$.
    \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$ is given by\par
\headq{Definition 3.28} Let $A$ be an $m\times n$ matrix $A$. The set
$\{\b x\mid A\b x=0\}$ is called the {\bf null space},
or {\bf kernel}, of $A$ and is denoted by $NS(A)$, or $\ker(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 of a {\bf linear combination} and {\bf span}
of a set of vectors (See Hill 3.30 and 3.39 respectively).
These are illustrated by the following.

\begin{verbatim}
# Hill Section 3.4 Example 6 p167.
> with(linalg):
> v1:= vector( [2,1] ):                         v2:= vector( [-4,-2] ):
> b:= vector( [b1,b2] ):
#
# b is a linear combination of v1,v2 if there are scalars a1, a2 such that
> evalm(a1*v1 + a2*v2) = b;
                         [ 2 a1 - 4 a2, a1 - 2 a2 ] = b

# As in    Example 9 of Hill Section 1.3,    this can be done as follows
> A:= augment(v1,v2):                       x:= vector( [a1,a2] ):
> evalm(A&*x);
                           [ 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  -4       b1     ]
                          U := [                    ]
                               [ 0   0  b2 - 1/2 b1 ]

# (a)  b:= vector( [6,3] ):
> subs (b1=6, b2=3, evalm(U) );
                                  [ 2  -4  6 ]
                                  [          ]
                                  [ 0   0  0 ]

# Since these equations are consistent, [6,3] is in span {v1,v2}.
# i.e. [6,3] = a1*v1 + a2*v2, where [a1,a2] is given by (for any value of t2):
> backsub(");
                                [ 2 t2 + 3, t2 ]

# (b)  b:= vector( [3,5] ):
> subs (b1=3, b2=5, evalm(U) );
                                 [ 2  -4   3  ]
                                 [            ]
                                 [ 0   0  7/2 ]

# The last row shows the equations are inconsistent.     So [3,5] is not
#  in span {v1,v2}.     i.e. [3,5] is not a linear combination of v1,v2.
\end{verbatim}
This not only shows that the combination in a given linear combination need
not be unique, but also illustrates theorem 3.32 (see also theorem 1.32 of
Hill \S 1.3).
\setcounter{theorem}{31}
\begin{theorem} If $A$ is a matrix whose columns are $\rowi{\b v}{n}$
  and \b x is an $n\times 1$ matrix, then the product $A\b x$ is a
  linear combination of $\{\rowi{\b v}{n}\}$.
\end{theorem}
Since the converse of this is also true,\qquad
   span \{$\rowi{\b v}{n}\}=\{A\b x: \b x\in \DoubleR^n\}$.
\smallskip

\noindent Note also that in the above Maple example, the span of $\b v_1$ and
$\b v_2$ is

\smallskip\centerline{
  ${\rm span}\{\b v_1,\b v_2\}=\{[b_1, b_2]\mid b_1 = 2*b_2\}$.}

\smallskip\noindent Thus (since, for example,
$[3,5]\not\in {\rm span}\{v_1,v_2\}$\/) $v_1$ and $v_2$ do not span $\DoubleR^2$.
\medskip

\subsection{Linear Independence}
Once again, it is assumed that, from an earlier course in linear algebra,
you are familiar with the terms {\bf linear dependence} and
{\bf linear independence} (See Hill Definition 3.41). For example
\setcounter{theorem}{41}
\begin{theorem} 
  A set of vectors $\{\rowi{\b v}{k}\}$ is linearly dependent if and only if
  there are numbers $\rowi{c}{k}$, not all zero, such that
    $$ \b 0 = c_1 \b v_1 + \cdots c_k \b v_k. $$
\end{theorem}

\begin{verbatim}
# Hill Section 3.5 Example 7 p178.
> with(linalg):
> v1:= vector([2,-3]):       v2:= vector([4,-2]):        v3:= vector([-4,3]):
# 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])) );
                                   [ 2  4  -4  0 ]
                              U := [             ]
                                   [ 0  4  -3  0 ]

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

# This shows that the  v1,v2,v3  above are linearly dependent. For example
> evalm( 2*v1 + 3*v2 + 4*v3 );
                                    [ 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{verbatim}
This illustrates the following.
\smallskip

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

\subsection{Basis and Dimension}
Here again is another definition with which you should be familiar.
\medskip

\headq{Definition 3.50.} A {\bf 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{verbatim}
# Hill Section 3.6 Example 2 p182.
> with(linalg):
# Show that the vectors v1,v2,v3 form a basis for R^3, where
> v1:=vector([2,1,0]):      v2:=vector([-3,-3,1]):      v3:=vector([-2,1,-1]):
#
# 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
> x:=vector([x1,x2,x2]):
# and solve the equation    Ac = x  where
> A:= augment( v1,v2,v3 );
                                    [ 2  -3  -2 ]
                                    [           ]
                               A := [ 1  -3   1 ]
                                    [           ]
                                    [ 0   1  -1 ]

> gausselim( augment(A,x) );
                        [ 2  -3   -2         x1       ]
                        [                             ]
                        [ 0   1   -1         x2       ]
                        [                             ]
                        [ 0   0  1/2  5/2 x2 - 1/2 x1 ]

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

\setcounter{theorem}{61}
\begin{theorem} 
  Suppose that $\rowi{v}{n}$ and
  $\rowi{w}{m}$ are both bases for the same vector space $V$.  Then $m=n$.
\end{theorem}

\noindent This leads to the following:

\smallskip
\headq{Definition 3.63(a).} The dimension of the vector space $V$  is $n$
  if $V$ has a basis of $n$ elements.
\medskip

\setcounter{theorem}{63}
\begin{theorem} 
  Let $V$ be a vector space of dimension $n$ and $S=\{\rowi{v}{k}\}\subset V$.
  \begin{enumerate}\item[]
  \begin{enumerate}
  \item If $S$ is linearly independent, then we can extend $S$ to a basis
    $S=\{\rowi{v}{k},v_{k+1},\ldots v_m\}$ for $V$.
  \item If $S$ spans $V$ and $V$ is not the zero vector space, then some
    subset of $S$ is a basis.
  \item If $S$ is linearly independent and $k=n$, then $S$ must be a basis
    for $V$,
  \item If $S$ spans $V$ and $k=n$, then $S$ must be a basis for $V$.
  \end{enumerate} \end{enumerate}
\end{theorem}

\goodbreak
\begin{verbatim}
# Hill Section 3.6 Example 13 p188.
> with(linalg):
> c1:= vector([-2,4]):        c2:= vector([1,-2]):        c3:= vector([3,5]):
> A:= augment( c1,c2,c3 );
                                    [ -2   1  3 ]
                               A := [           ]
                                    [  4  -2  5 ]

# The three columns c1,c2,c3 of A are in R^2 and are linearly dependent (WHY?)
#
> gausselim(A);
                                 [ -2  1   3 ]
                                 [           ]
                                 [  0  0  11 ]

# The pivots in columns 1 and 3 of this Echelon form show that
#  c1,c3  are linearly independent and so form a basis for R^2.
#
# The two rows  r1,r2  of A are in R^3 but do not span R^3 (WHY?).  However,
#   if {e1,e2,e3} is the standard basis for R^3, then 
#      {r1,r2,e1,e2,e3} must span R^3.  They are the columns of the matrix
> augment( transpose(A),diag(1,1,1) );
                              [ -2   4  1  0  0 ]
                              [                 ]
                              [  1  -2  0  1  0 ]
                              [                 ]
                              [  3   5  0  0  1 ]

> gausselim(");
                             [ -2   4   1   0  0 ]
                             [                   ]
                             [  0  11  3/2  0  1 ]
                             [                   ]
                             [  0   0  1/2  1  0 ]

# Since the first three columns are pivots,  {r1,r2,e1} is a basis for R^3.
#    Note that  {r1,r2,e3} is NOT a basis for R^3    (CHECK this).
\end{verbatim}

\goodbreak
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 null space or kernel of a matrix.
\begin{verbatim}
> with(linalg):
> I3:= diag(1,1,1):                                  nullspace(I3);
                                       {}

# Output like  {}  indicates that the answer is the zero subspace.
#
# Hill Section 3.6 Example 15 p189.
# Find the null space of the matrix
\end{verbatim}
\goodbreak
\begin{verbatim}
> A:= matrix( [[0, 0, 1, -4],  
>              [2,-4,-1, -2],  
>              [4,-8, 0,-12]] ):

> nullspace(A);
                        {[ 2, 1, 0, 0 ], [ 3, 0, 4, 1 ]}

# The displayed vectors are a basis for the null space NS(A), or kernel, of A.
#
# Alternatively, solve the equation  Ax = 0  by reducing A to Echelon form
> U:= gausselim(A):                                        nullspace(U);
                        {[ 2, 1, 0, 0 ], [ 3, 0, 4, 1 ]}

# Thus  NS(U) = NS(A),  illustrating equation 3.65 of Hill (p 190).
\end{verbatim}
    $$ NS(A) = NS(U).\eqno{(3.65)} $$

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

\headq{Definition 3.67.} Let $A$ be an $m\times n$ matrix. Then
  \begin{enumerate}\item[]
  \begin{enumerate}
  \item the {\bf row space} $RS(A)$ of $A$ is the set of all linear combinations
    of the rows of $A$;
  \item the {\bf column space} $CS(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{verbatim}
> 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{verbatim}
(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{verbatim}
# Hill Section 3.7 Examples 3-8 pp 196-201
> with(linalg):
# Examples 3 and 4:    Find a basis for the vector space spanned by
> v1:= vector( [2,-3,  4, 1, 2] ):       v2:= vector( [  4,-6,  5, 3,-4] ):
> v3:= vector( [-10,15,-14, 3, 7] ):     v4:= vector( [ -8,12,-10, 4, 9] ):
#
# This can be done by finding a basis for the row space of the matrix
> A:= matrix( [v1, v2, v3, v4] );
                               [  2   -3   4   1   2 ]
                               [                     ]
                               [  4   -6   5   3  -4 ]
                          A := [                     ]
                               [ -10  15  -14  3   7 ]
                               [                     ]
                               [  -8  12  -10  4   9 ]

> rowspace(A);
                         89                    27
    {[ 1, -3/2, 0, 0, - ---- ], [ 0, 0, 1, 0, ---- ], [ 0, 0, 0, 1, 1/10 ]}
                         20                    10

# Note that this is different from the answer in Hill, who gives
> u1:= v1:    u2:= vector( [0,0,-3,1,-8] ):    u3:= vector( [0,0,0,10,1] ):
#
# This illustrates the fact that a basis for a vector space is not unique.
# In fact, Maple's answers are linear combinations of  u1, u2, u3:
> evalm( u1/2 + 2*u2/3 - 7*u3/60 ),  evalm( u3/30 - u2/3 ),  evalm( u3/10 );
                         89                    27
     [ 1, -3/2, 0, 0, - ---- ], [ 0, 0, 1, 0, ---- ], [ 0, 0, 0, 1, 1/10 ]
                         20                    10

#    (Exercise: express u1, u2, u3 as linear combinations of Hill's basis)
#
# Now consider the rowspace of the Echelon form U of A.
> U:= gausselim(A);
                                [ 2  -3   4   1   2 ]
                                [                   ]
                                [ 0   0  -3   1  -8 ]
                           U := [                   ]
                                [ 0   0   0  10   1 ]
                                [                   ]
                                [ 0   0   0   0   0 ]

> rowspace(U);
                         89                    27
    {[ 1, -3/2, 0, 0, - ---- ], [ 0, 0, 1, 0, ---- ], [ 0, 0, 0, 1, 1/10 ]}
                         20                    10

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

# These are just the pivot columns of U (i.e. the columns of U with pivots)
# An alternative basis for CS(U) may be found by
> colspace(U); 
                {[ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ]}

> colspace(A);                                     # A basis for CS(A)
                {[ 0, 1, 0, 0 ], [ 1, 0, 0, 1 ], [ 0, 0, 1, 1 ]}

# Because of the 1 in the last place of some of these vectors, CS(A) <> CS(U)
#
# Examples 7 and 8:
# These two bases have the same number of vectors as the number of pivots of U.
#            Thus  dim CS(A)  =  dim CS(U)  =  dim RS(U)  =  dim RS(A).
\end{verbatim}

\noindent This illustrates Hill \S3.7 Theorem 3.78

\setcounter{theorem}{77}
\begin{theorem} 
  Let $A$ be an $m\times n$ matrix.  Then 
    $$ \dim CS(A) = \dim RS(A).$$
  {\em This dimension is called the {\bf rank} of $A$.}
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The following is not in Hill, but is important in Linear Algebra:
%
% \setcounter{theorem}{??}
% \begin{theorem} Suppose elimination reduces $Ax=b$ to $Ux=c$ and
% there are $r$ pivots (i.e. the last $m-r$ rows of $U$ are zero).  Then
% \begin{enumerate}\begin{enumerate}
% \item there is a solution only if the last $m-r$ components of $c$
%   are also zero: in particular, if $r=m$, there is always a solution;
% \item 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):
%   in particular, if $r=n$, there are no free variables and the
%   null space contains only $x=0$.
% \end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\goodbreak
\smallskip 
Thus the rank of a matrix is the number of linearly independent rows
(or columns). Alternatively -- see 3.71 of Hill \S3.7 (p. 197) -- the rank
of a matrix is the number of pivots in its echelon form.
\smallskip

The Maple function to determine this number is {\tt rank}\index{rank}.
\begin{verbatim}
> with(linalg):
> A:= matrix( [[a11,a12,a12],  
>              [a21,a22,a22]] ):
> rank(A);
                                       2
\end{verbatim}
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}
  \quad dim($NS(A)$)\quad\==\quad dim($RS(A)$)\quad
                            = \quad number of leading variables\= in \kill
  \quad $NS(A)$\> =\quad $NS(U)$\> $RS(A)$\quad =\quad $RS(U)$\\
  \quad dim($NS(A)$)\> =\quad number of free variables in the equation
                                  $Ux = \b 0$ \\
  \quad rank ($A$)\> =\quad dim($RS(A)$)\quad
              =\quad number of leading variables in the equation $Ux = \b 0$.
\end{tabbing}
\setcounter{theorem}{81}
\begin{theorem}[Rank-Nullity Theorem] Let $A$ be an $m\times n$ matrix. 
  \begin{enumerate} \item[]
    \begin{enumerate}
    \item dim $RS(A$) + dim $NS(A$) = $n$.
    \item dim $CS(A$) + dim $NS(A$) = $n$.
    \item   rank($A$) + dim $NS(A$) = $n$.
    \end{enumerate}
  \end{enumerate}
\end{theorem}
\goodbreak

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

\noindent Combining this result with theorem 1.50 of Hill \S 1.4, we get
\begin{theorem} Let $A$ be an $n\times n$ matrix. Then the following
  are equivalent
  \begin{enumerate} \item[]
    \begin{enumerate}
    \item $A$ is invertible.
    \item dim $NS(A$) = 0.
    \item   rank($A$) = dim $CS(A$) = dim $RS(A$) = $n$.
    \end{enumerate}
  \end{enumerate}
\end{theorem}

\goodbreak
\subsection{Coordinates and Change of Basis}
\setcounter{theorem}{86}
\begin{theorem} 
  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 {\bf 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}

\begin{verbatim}
# Hill Section 3.8 Example 7 p215.  (cf. Example 6, p213.)
> with(linalg):
# Find the coordinates of the vector x  relative to the basis  u1,u2,u3  where
> x:= vector([x1,x2,x3]):
> u1:=vector([2,3,-1]):        u2:=vector([2,1,2]):        u3:=vector([4,3,1]):
> B:= augment( u1,u2,u3 );
                                    [  2  2  4 ]
                                    [          ]
                               B := [  3  1  3 ]
                                    [          ]
                                    [ -1  2  1 ]

# First check that this is a basis for R^3 using the  rank  function:
> rank(B);
                                       3

# Thus  dim( CS(B) ) = 3  and so the columns are a basis for  R^3.
#
# The coordinates of  x  relative to  {u1,u2,u3}  are given by
> xB:= linsolve(B,x);
      xB := [ 1/3 x3 - 5/6 x1 + x2, x3 - x1 + x2, - 2/3 x3 + 7/6 x1 - x2 ]
\end{verbatim}

Note that the columns of the matrix $B$ form a basis for $\DoubleR^3$.
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,\b v_3\}$ is another basis for $\DoubleR^3$, 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,\b v_3]$.\quad Thus
(see Hill p.214)
  $$[\b x]_C = P [\b x]_B\quad {\rm where}\quad P = C^{-1}B.$$
Continuing the above example,
\begin{verbatim}
# Find the coordinates of  x  relative to the basis  v1,v2,v3  where
> v1:=vector([1,1,1]):         v2:=vector([0,1,1]):        v3:=vector([0,0,1]):
> C:= augment( v1,v2,v3 ):                                xC:= linsolve(C,x);
                       xC := [ x1, - x1 + x2, - x2 + x3 ]

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

> equal( evalm(P&*xB), xC );
                                      true
\end{verbatim}

\headq{Definition 3.89.} Let $V$ be a finite-dimensional vector space with
  bases $B$ and $C$. Then the {\bf 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 As mentioned in Hill (see theorem 3.91 on p.214), if $\DoubleR^n$
has two bases which are the columns of the matrices $B,C$, then this transition
matrix $P$ can be found by row-reducing the matrix $(C\mid B)$ --{\em not}
the matrix $(B\mid C)$-- to $(I\mid P)$. In Maple, this can be done using
the function {\tt gaussjord}\index{gaussjord}.
\begin{verbatim}
# P can also be found by reducing  (C:B)  to row reduced form:
> gaussjord( augment(C,B) );
                            [ 1  0  0   2   2   4 ]
                            [                     ]
                            [ 0  1  0   1  -1  -1 ]
                            [                     ]
                            [ 0  0  1  -4   1  -2 ]

> equal( submatrix(",1..3,4..6), P );
                                      true
\end{verbatim}
\setcounter{theorem}{93}
\begin{theorem} 
  If $P$ is the transition matrix from $B$ to $C$, then
  $P^{-1}$ is the transition matrix from $C$ to $B$.
\end{theorem}

\subsection{Error-Correcting Codes}
This deals with the field $\DoubleZ_2$, which is accessed in Maple using
the {\tt modp}\index{modp} function.
\begin{verbatim}
# Z2 looks like  {0,1}  except that
> modp( 1+1,2 );
                                       0
\end{verbatim}

\goodbreak
\headq{Definition 3.101} The {\bf (7,4) Hamming code} $C_{(7,4)}$ is\quad
span $\{\b u_1,\b u_2,\b u_3,\b u_4\}$,\quad where
  $$ \b u_1 = (1,0,0,0,0,1,1),\quad \b u_2 = (0,1,0,0,1,0,1),\quad 
                     \b u_3 = (0,0,1,0,1,1,0),\quad \b u_4 = (0,0,0,1,1,1,1) $$
\setcounter{theorem}{101}
\begin{theorem} $C_{(7,4)} = NS(H)$, where
  $$ H = \pmatrix{ 0&0&0&1&1&1&1 \cr
                   0&1&1&0&0&1&1 \cr
                   1&0&1&0&1&0&1 } $$
\end{theorem}
Thus, suppose that person A wishes to send a message $[x_1,x_2,x_3,x_4]$
to person B. If there is a good chance that one of the digits may be altered
along the way (but no more than one), then the error can be detected if A sends
the septuple $x_1\b u_1 + x_2\b u_2 + x_3\b u_3 + x_4\b u_4$ and B checks that
the received message is in $NS(H)$. In fact, this error can even be corrected:
\setcounter{theorem}{104}
\begin{theorem} Suppose that $\b w\in \DoubleZ_2^7$ and $H\b w$ is the $k$th
  column of $H$. If the $k$th entry of \b w is changed, then the corrected
  \b w will be in $NS(H)$.
\end{theorem}
\begin{verbatim}
# Hill Section 3.9 Examples 3 and 4, pp 225,226.
> with(linalg):
> u1:= vector( [1,0,0,0,0,1,1] ):              u2:= vector( [0,1,0,0,1,0,1] ):
> u3:= vector( [0,0,1,0,1,1,0] ):              u4:= vector( [0,0,0,1,1,1,1] ):
#
> H:= matrix([ [0,0,0,1,1,1,1],
>              [0,1,1,0,0,1,1],
>              [1,0,1,0,1,0,1] ]):
#
> map( modp, evalm(H&*u1), 2 );              # Checking that  u1  is in  NS(H)
                                  [ 0, 0, 0 ]

# Exercise:  Check that  u2, u3, u4  are also in  NS(H)
#
# Example 4 (p226): Correct (if necessary) the following messages,
#   given that there is at most one error in each.
> x:= vector( [0,1,1,0,0,1,1] ):
> y:= vector( [0,1,1,1,0,0,1] ):
#
> map( modp, evalm(H&*x), 2 );
                                  [ 0, 0, 0 ]

# So  x  is correct
#
> map( modp, evalm(H&*y), 2 );
                                  [ 0, 1, 0 ]

# Since this is the second column of H, change the second entry in  y:
> y[2]:= 0:                                    map( modp, evalm(H&*y), 2 );
                                  [ 0, 0, 0 ]
\end{verbatim}

\vfill
\eject

