\documentclass[11pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[pdftex]{color}

%\pagestyle{empty}
\topmargin -1in
\oddsidemargin -0.25in
\evensidemargin -0.25in
\textheight 9.5in
\textwidth 7.0in 

\definecolor{ignoreGray}{rgb}{0.75,0.75,0.75}
\newcommand{\ig}{\color{ignoreGray}}

\begin{document}

\noindent \hfill
\fbox{\fbox{\parbox{6.9in}{{\scshape{Math 2240 \hfill Computing with Bases}} }}} \hfill 

This is an extended example of computing with bases. Let us begin with a subspace $W$ of $\mathbb{R}^5$.

\vspace{-0.1in}

\[ W = \left\{ \begin{array}{c|c} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \end{bmatrix} \in \mathbb{R}^5 \; &  \begin{array}{rc} v_1+2v_2-v_3+v_4+5v_5=0, & \\ v_3+v_4-2v_5=0, & \\ & \mbox{ and } \\ -v_1-2v_2+2v_3-7v_5=0, & \end{array} \end{array} \right\} \]

%\vspace{-0.05in}

We might immediately notice that the elements of $W$ satisfy a system of homogeneous equations. In particular, for any ${\bf v} \in W$ we have...

\vspace{-0.25in}

\[ A{\bf v} = \begin{bmatrix} 1 & 2 & -1 & 1 & 5 \\ 0 & 0 & 1 & 1 & -2 \\ -1 & -2 & 2 & 0 & -7 \end{bmatrix} {\bf v} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

\noindent
Therefore, $W = N(A)$ ($W$ is the null space of $A$). So $W$ is indeed a subspace of $\mathbb{R}^5$.

To find a basis for $W$, we should find the RREF of $A$ and solve the system $A{\bf x}={\bf 0}$. 

\vspace{-0.25in}

\[ \begin{bmatrix} 1 & 2 & -1 & 1 & 5 \\ 0 & 0 & 1 & 1 & -2 \\ -1 & -2 & 2 & 0 & -7 \end{bmatrix}  \stackrel{\mbox{\small G. E.}}{\widetilde{\mbox{\quad\qquad}}} \begin{bmatrix} 1 & 2 & 0 & 2 & 3 \\ 0 & 0 & 1 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \quad \ 
\begin{array}{ccl} x_1 & = & -2r-2s-3t \\ x_2 & = & r \\ x_3 & = & -s+2t \\ x_4 & = & s \\ x_5 & = & t \end{array} \hspace*{-0.15in} {\bf x} = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} r + \begin{bmatrix} -2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} s + \begin{bmatrix} -3 \\ 0 \\ 2 \\ 0 \\ 1 \end{bmatrix} t \]

\vspace{-0.1in}

Therefore, $\displaystyle W = \mathrm{span} \left\{ \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} -2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} -3 \\ 0 \\ 2 \\ 0 \\ 1 \end{bmatrix} \right\} = \mathrm{Col}\left(B\right)$ (a column space) where $\displaystyle B = \begin{bmatrix} -2 & -2 & -3 \\ 1 & 0 & 0 \\ 0 & -1 & 2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$. 

\vspace{0.05in}

\noindent
Moreover, these 3 vectors form a basis for $W$, so we now know that $\dim(W)=3$. Also, notice that $W=N(A)=\mathrm{Col}(B)$, so $W$ can be viewed as both a null space and a column space. While not obvious, it is true that {\bf all} subspaces of $\mathbb{R}^n$ can be viewed as both null spaces and column spaces if we pick the right matrices.

\vspace{-0.1in}

\noindent
Let's ask the question: ``Is $\displaystyle {\bf w} = \begin{bmatrix} 1\\ 2\\ 3\\ 2\\ 1 \end{bmatrix} \in W$ ?''  There are 2 basic techniques for checking.

\vspace{-0.05in}

\begin{itemize}
\item Since $W$ is a nullspace, we can see if

\vspace{-0.375in}

``$A{\bf w}={\bf 0}$'' is satisfied. So ${\bf w} \not\in W$ because\dots
\hfill $\displaystyle A{\bf w} = \begin{bmatrix} 1 & 2 & -1 & 1 & 5 \\ 0 & 0 & 1 & 1 & -2 \\ -1 & -2 & 2 & 0 & -7 \end{bmatrix} \begin{bmatrix} 1\\ 2\\ 3\\ 2\\ 1 \end{bmatrix} = \begin{bmatrix} 9 \\ 3 \\ -6 \end{bmatrix} \not= {\bf 0} $

\vspace{-0.1in}

\item Alternatively, we can use the basis that we found above to check is our vector belongs to $W$.  This is a lot more work than our previous technique. However, if we have a subspace described as the 

\vspace{-0.05in}

\begin{minipage}{2.65in}
``span''  of a set of vectors, we are more-or-less forced to check this way. Specifically, we will adjoin the vector in question to the spanning set (which is actually a basis in this case) and then row reduce.
\end{minipage} \quad
\begin{minipage}{3in}
\[ [B \; : \; {\bf w} ] = \begin{bmatrix} -2 & -2 & -3 & : & 1 \\ 1 & 0 & 0 & : & 2 \\ 0 & -1 & 2 & : & 3 \\ 0 & 1 & 0 & : & 2 \\ 0 & 0 & 1 & : & 1 \end{bmatrix} \stackrel{\mbox{\small G. E.}}{\widetilde{\mbox{\quad\qquad}}} \begin{bmatrix} 1 & 0 & 0 & : & 0 \\ 0 & 1 & 0 & : & 0 \\ 0 & 0 & 1 & : & 0 \\ 0 & 0 & 0 & : & 1 \\ 0 & 0 & 0 & : & 0 \end{bmatrix} \]
\end{minipage}

\noindent 
Since the final column is a pivot column, the final column is {\bf not} contained in the span of the previous columns. Therefore, ${\bf w} \not\in W$.

This illustrates that null space membership is easier to check than column space membership.
\end{itemize}

Next, let's show that $\displaystyle S = \left\{ {\bf a}, {\bf b}, {\bf c} \right\}$ is a subset of $W$ where \ \  $\displaystyle {\bf a} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ -1 \\ 0  \end{bmatrix}$, \ \  $\displaystyle {\bf b} =   \begin{bmatrix} 2 \\ -2 \\ -1 \\ 1 \\ 0  \end{bmatrix}$, \  and \  $\displaystyle {\bf c} = \begin{bmatrix} 8 \\ -4 \\ 0 \\ 0 \\ 0  \end{bmatrix}$. 

\vspace{-0.05in}

\noindent
Again let's do this 2 ways. [First the easy way, then the hard way.]
\begin{itemize}
\item A quick check shows $A{\bf a}={\bf 0}$, $A{\bf b}={\bf 0}$, and $A{\bf c}={\bf 0}$ so ${\bf a}, {\bf b}, {\bf c} \in W$. So $S \subset W$ ($S$ is contained in $W$).

\vspace{-0.1in}

\item Alternatively, we can adjoin our three vectors to the spanning set from before and row reduce.

\vspace{-0.15in}

\[ [B \;:\; {\bf a}\;{\bf b}\;{\bf c}] = \begin{bmatrix} -2 & -2 & -3 & : & 0 & 2 & 8 \\ 1 & 0 & 0 & : & 1 & -2 & -4 \\ 0 & -1 & 2 & : & 1 & -1 & 0 \\ 0 & 1 & 0 & : & -1 & 1 & 0 \\ 0 & 0 & 1 & : & 0 & 0 & 0 \end{bmatrix} \stackrel{\mbox{\small G. E.}}{\widetilde{\mbox{\quad\qquad}}}  \begin{bmatrix} 1 & 0 & 0 & : & 1 & -2 & -4 \\ 0 & 1 & 0 & : & -1  & 1 & 0 \\ 0 & 0 & 1 & : & 0 & 0 & 0 \\ 0 & 0 & 0 & : & 0 & 0 & 0  \\ 0 & 0 & 0 & : & 0  & 0 & 0 \end{bmatrix} \]

\vspace{-0.05in}

So we put our ``known'' vectors to the left and the vectors to ``test'' to the right. Since there are no ``new'' pivot columns (coming from our test vectors), they must all lie in the span of our known vectors. In particular, ${\bf a}$ is just the difference between the first two vectors, ${\bf b}$ is $-2$ times the first vector plus the second vector, and ${\bf c}$ is just $-4$ times the first vector. Thus the new vectors are all elements of $W$. Hence $S \subset W$.
\end{itemize}

%\vspace{-0.1in}

We already know that $S$ is a subset of $W$. But is $S$ a linearly independent set? And, can we extend all (or part) of $S$ to a basis for $W$?

%\vspace{0.15in}

To answer both of these questions (at the same time) we should put the vectors from $S$ into a matrix and adjoin a known basis for $W$.  To guarantee that the vectors in $S$ are placed in the basis we are trying to compute, we should place them on the left (this gives them preferential treatment).

\vspace{0.05in}

\noindent
\begin{minipage}{4.75in}
$\displaystyle \begin{bmatrix} 0 &  2 &  8 & : & -2 & -2 & -3 \\
                               1 & -2 & -4 & : & 1  &  0 &  0 \\
                               1 & -1 &  0 & : & 0  & -1 & 2 \\
                              -1 &  1 &  0  & : & 0 & 1 & 0 \\
                               0 &  0  &  0 & : & 0 & 0 & 1 \end{bmatrix} \stackrel{\mbox{\small G. E.}}{\widetilde{\mbox{\quad\qquad}}}
   \begin{bmatrix} 1 & 0 & 4 & : & -1 & -2 & 0 \\
                                0 & 1 & 4 & : & -1 & -1 & 0 \\
                                0 & 0 & 0 & : & 0 & 0 & 1 \\
                                0 & 0 & 0 & : & 0 & 0 & 0 \\
                                0 & 0 & 0 & : & 0 & 0 & 0 \end{bmatrix} $
\end{minipage} \quad
\begin{minipage}{2.05in}
Notice that the third column is {\bf not} a pivot column. In fact, the linear correspondence says that it is 4 times the first column plus 4 times the second. 
Thus $S$ is linearly dependent.
\end{minipage}

\vspace{0.05in}

\noindent
\begin{minipage}{4.75in}

Next, notice that the fourth and fifth columns are also linear combinations of the first two columns. So they are also redundant. However, the last column is a pivot column, so it is not contained in the span of the first two columns. Adding this vector to the first two will yield a basis for $W$.
\end{minipage} \quad
\begin{minipage}{2.05in}
$\displaystyle 4\begin{bmatrix} 0\\1\\1\\-1\\0 \end{bmatrix}+4\begin{bmatrix} 2\\-2\\-1\\1\\0 \end{bmatrix}=\begin{bmatrix} 8\\-4\\0\\0\\0 \end{bmatrix}$
\end{minipage} 

\vspace{-0.1in}

$\beta = \left\{ \begin{bmatrix} 0\\1\\1\\-1\\0 \end{bmatrix}, \begin{bmatrix} 2\\-2\\-1\\1\\0 \end{bmatrix}, \begin{bmatrix} -3\\0\\2\\0\\1 \end{bmatrix}  \right\}$ is a basis for $W$ (which includes as much of $S$ as possible).

\vspace{0.05in}

Let's note one last thing. If we had listed the vectors from $S$ in a different order, we would end up with a different basis.

\vspace{-0.1in}

\[ \begin{bmatrix} 8 &  0 &  2 & : & \!\! -2 & \!\! -2 & \!\! -3 \\
                               -4 & 1 & \!\! -2 & : & 1  &  0 &  0 \\
                               0 &  1 & \!\! -1 & : & 0  & \!\! -1 & 2 \\
                               0 & \!\! -1 &  1 & : & 0 & 1 & 0 \\
                               0 & 0 &  0  & : & 0 & 0 & 1 \end{bmatrix} \stackrel{\mbox{\small G. E.}}{\widetilde{\mbox{\quad\qquad}}}
   \begin{bmatrix} 1 & 0 & 1/4 & : & \!\!\!\! -1/4 & \!\! -1/4 \!\! & 0 \\
                                0 & 1 & -1 & : & 0 & -1 & 0 \\
                                0 & 0 & 0 & : & 0 & 0 & 1 \\
                                0 & 0 & 0 & : & 0 & 0 & 0 \\
                                0 & 0 & 0 & : & 0 & 0 & 0 \end{bmatrix} 
\ \  \Longrightarrow \ \    
\beta = \left\{ \begin{bmatrix} 8\\-4\\0\\0\\0 \end{bmatrix}, \begin{bmatrix} 0\\1\\1\\-1\\0 \end{bmatrix}, \begin{bmatrix} -3\\0\\2\\0\\1 \end{bmatrix}  \right\}
                                \]

This is also a basis for $W$ and it also includes two vectors from $S$, but not the same vectors as before. This is due to our change in ``preferences'' (the change in the order in which we listed the vectors).


\end{document}
