Linear-Algebra-Applications-Content.tex

\chapter{Linear Algebra Applications}

This chapter covers the following ideas.  The purpose of this chapter
is to show you a variety of applications of linear algebra and provide you with ample opportunities to practice and polish the skills learned in the arithmetic unit.  

\input{Applications/Linear-Algebra-Applications-objectives}




\section{Vector Fields}

Vectors help us understand motion, forces, acceleration, and more. Imagine that you were a dust particle floating through the air.  Along the way, wind pushes you in various directions, sometimes causing you to swirl around, increasing your speed, or changing your direction. As you move through space, you encounter forces (vectors) pushing you around everywhere you go. This field of vectors provides an example of a vector field in space.  Magnetic fields, electrical fields, force fields, velocity fields, flow fields, and more are key ideas studied throughout the sciences. Meteorologists study air flow, physicists study magnetic and electric fields, and engineers study heat flow and fluid flow. In business, economists study the flow of money, which again results in studying vector fields. Pretty much every study of motion or change comes back to studying an underlying field of vectors.  In this section, we will explore some simple two-dimensional vector fields arising from matrices, and then learn to physically observe the eigenvalues and eigenvectors from a plot of the vector field.  When studying more complicated vector fields, researchers use high dimensional calculus to simplify the complicated field to the vector fields we will study in this section. Eigenvalues and eigenvectors will play a major role.

Let's start with some notation. 
When you hear that $y$ is a function of $x$, you often write $y=f(x)$ to remind yourself that when you put in $x$ you get out $y$. 
For most of your lower-level math courses, you have always thought of $x$ and $y$ as real numbers. 
In this case, the domain of the function (the $x$-values) is the set of all real numbers, which we denote with the symbol \RR. \marginpar{\RR\ means all real numbers.} 
The potential $y$ values (the range) are also real numbers.  
If we want to pay attention to the domain and range of the function, we could write $f\colon D\to R$ \marginpar{$f\colon D\to R$ notation} where $D$ is the domain and $R$ is the range.  
For a function such as $y=f(x)$, where both $x$ and $y$ are real numbers (written $x\in \RR$ and $y\in \RR$), we could write $f\colon{\RR}\to{\RR}$. 
With this notation, we can generalize the concept of functions to allow us to input vectors and output vectors.  
If we want to input a 2D vector and get out a 3D vector, then we could write $f\colon{\RR}^2\to{\RR}^3$.  
We'll use the notation ${\RR}^n$ to represent the set of $n$ dimensional vectors. 
Throughout this semester, we'll be studying functions of the form $f\colon{\RR}^n\to {\RR}^m$. In particular, we'll be studying special types of functions called linear transformations which can often be represented by matrices.\note{In this discussion, range=codomain; maybe we should use codomain and image, and mention that range could be one or the other, depending on who you talk with}

A \define{vector field} is a function where you input a vector and receive back a vector of the same dimension. 
\marginpar{A vector field takes vectors of size $n$ to vectors of size $n$, $$f\colon{\RR}^n\to{\RR}^n.$$}%
If $\vec x$ is a 2D vector, then a vector field is a function of the form $\vec F\colon{\RR}^2\to {\RR}^2$ (we put a vector above $\vec F$ because the output is a vector).  
Any square matrix represents a vector field---if $A$ is a square matrix, then the function $\vec F(\vec x) = A\vec x$ means that the output $\vec y=A\vec x$. Let's look at an example and a graph.


\begin{example}
The matrix $\begin{bmatrix}2&1\\1&2\end{bmatrix}$ gives us the vector field $$\vec F(x,y)=\begin{bmatrix}2&1\\1&2\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=(2x+y,x+2y).$$ We input the point $(x,y)\in {\RR}^2$ and get out the vector $(2x+y,x+2y)\in {\RR}^2$.  For example, we compute $\vec F(1,0) = (2(1)+0,(1)+2(0)) = (2,1)$. To visualize this input and output, we place the vector $(2,1)$ (the output) in the plane with its base at the point $(1,0)$ (the input). To visualize the function $\vec F$, we can pick an assortment of input points and at each input point $\vec x$, draw the output vector $\vec F(\vec x)$.  The example below shows how to place the vectors corresponding to the 9 points with $x$ or $y$ coordinate $0, \pm 1$.  

\begin{center}
\begin{tikzpicture}
\node (A) {$\begin{array}{l|l}
(x,y) & \vec F(x,y)\\
\hline
(0,0) & (0,0) \\
(1,0) & (2,1) \\
(1,1) & (3,3) - \text{an eigenvalue is 3}\\
(0,1) & (1,2) \\
(-1,1) & (-1,1) - \text{an eigenvalue is 1}\\
(-1,0) & (-2,1) \\
(-1,-1) & (-3,-3) \\
(0,-1) & (-1,-2) \\
(1,-1) & (1,-1)
\end{array}$};
\node (vf) [right=of A] {
\includegraphics[height=2in]{Applications/support/vf21128points}};
\end{tikzpicture}
\end{center}


Notice that (1,1) is an eigenvector corresponding to the eigenvalue 3 because $A(1,1) = 3(1,1)$. 
Also, note that $(-1,1)$ is an eigenvector corresponding to the eigenvalue 1 because $A(-1,1)=(-1,1)$. 
These two eigenvectors represent the directions in which the vector field pushes objects radially outwards.   \marginpar{Eigenvectors tell you where vector fields push radially outwards or inwards.  Eigenvalues tell the strength and direction (outward or inward) of the push.}%
Anywhere along the line spanned by an eigenvector, the vector field pushes radially outward (as shown in the middle figure).  The vector field will never push you from one side of an eigenvector to the other side.
The eigenvalue for the eigenvector tells you the strength of the push, which explains why the vectors in the $(1,1)$ direction are three times as long as the vectors in the $(-1,1)$ direction. 
The middle plot in Figure \ref{vf2112} includes two lines representing the eigenvector directions.

\begin{figure}[bth]
\begin{tikzpicture}[inner sep=0mm]
\node (A) 
{
\includegraphics[height=1.3in]{Applications/support/vf211225points}
};
\node (B) [right=of A] 
{
\includegraphics[height=1.3in]{Applications/support/vf2112com}
};
\node (C) [right=of B] 
{
\includegraphics[height=1.3in]{Applications/support/vf2112flow}
};
\end{tikzpicture}
\caption{\label{vf2112} Three views of the vector field $\vec F(x,y) =(2x+y,x+2y)$. The first plot shows the appropriate lengths.  The second plot includes two lines which come from the eigenvector directions. The third plot includes flow lines which describe the path of an object flowing through the vector field. Because flow is outward in all directions, this vector field is called a source.}
\end{figure}

When a computer draws a vector field, it creates hundreds of vectors, takes the longest vector and shrinks its length so that it won't cross any others, and then proportionally shrinks every other vector. This creates lots of tiny vectors which represent the directions (not magnitudes) of the vectors (see the last two plots in Figure \ref{vf2112}). You can think of a vector field as the flow of water---if you were to drop a particle into the field, then it would follow the vectors (just as drift wood follows the flow of a river). These flow lines are represented in the last plot of Figure \ref{vf2112}.
\end{example} 

Figure \ref{vflots} contains other examples. Again, the eigenvalues and eigenvectors determine how to draw flow lines in the graph.

\begin{figure}
\begin{tikzpicture}[inner sep=0mm]
\node (B0) 
{
\includegraphics[width=1.3in]{Applications/support/vfsinkhand}
};
\node (A0) [left=of B0] 
{
\begin{tabular}{c}
Sink (inward flow)
\\ \hline
$A=
\begin{bmatrix}
 -2 & 2 \\
 1 & -2
\end{bmatrix}
$
\\
Eigenvalues: $-2-\sqrt{2},\sqrt{2}-2$
\\
Eigenvectors: $(-\sqrt{2} ,1), (\sqrt{2}, 1)$
\end{tabular}
};
\node (C0) [right=of B0] 
{
\includegraphics[width=1.3in]{Applications/support/vfsinkcom}
};

\node (B1) [below=of B0]
{
\includegraphics[width=1.3in]{Applications/support/vfrotationalhand}
};
\node (A1) [left=of B1] 
{
\begin{tabular}{c}
Rotational
\\ \hline
$A=
\begin{bmatrix}
 0 & -1 \\
 1 & 0
\end{bmatrix}
$
\\
Eigenvalues: $i,-i$
\\
Eigenvectors: $(i,1), (-1, 1)$
\end{tabular}
};
\node (C1) [right=of B1] 
{
\includegraphics[width=1.3in]{Applications/support/vfrotationalcom}
};

\node (B2) [below=of B1] 
{
\includegraphics[width=1.3in]{Applications/support/vfsaddlehand}
};
\node (A2) [left=of B2]
{
\begin{tabular}{c}
Saddle (both in and out)
\\ \hline
$A=
\begin{bmatrix}
 1 & 4 \\
 2 & 3
\end{bmatrix}
$
\\
Eigenvalues: $5,-1$
\\
Eigenvectors: $(1,1), (-2, 1)$
\end{tabular}
};
\node (C2) [right=of B2] 
{
\includegraphics[width=1.3in]{Applications/support/vfsaddlecom}
};

\node (B3) [below=of B2] 
{
\includegraphics[width=1.3in]{Applications/support/vfspiralhand}
};
\node (A3) [left=of B3]
{
\begin{tabular}{c}
Outward Spiral
\\ \hline
$A=
\begin{bmatrix}
 1 & -1 \\
 1 & 1
\end{bmatrix}
$
\\
Eigenvalues: $1+i, 1-i$
\\
Eigenvectors: $(i ,1), (-i, 1)$
\end{tabular}
};
\node (C3) [right=of B3] 
{
\includegraphics[width=1.3in]{Applications/support/vfspiralcom}
};




\end{tikzpicture}
\caption{\label{vflots}
Different kinds of vector fields.  Every 2 by 2 matrix represents a vector field.  When the eigenvalues are real, the eigenvectors help determine direction of flow. Positive eigenvalues result in outward flow along the corresponding eigenvector. Negative eigenvalues result in inward flow. Pure imaginary eigenvalues yield rotational flow. When the eigenvalues involve both real and imaginary parts, the real part determines whether the flow is inward or outward, and the complex part determines rotation.
}
\end{figure}











\section{The Second Derivative Test}

In this section, we'll explore how eigenvalues and eigenvectors of a matrix are the key tool needed to generalize the second derivative test from first semester calculus to all dimensions. The key application is that eigenvalues tell you about concavity of a function in the eigenvector directions.  If all eigenvalues are negative, then a function is concave downwards in all directions, which means that a critical point must correspond to a maximum.    

Let's start with a review from first semester calculus. 
If a function $y=f(x)$ has a relative extreme value at $x=c$, then $f^\prime(c)=0$ or the derivative is undefined. 
The places where the derivative is either zero or undefined are called critical values of the function. 
The first derivative test allows you to check the value of the derivative on both sides of the critical value and then interpret whether that point is a maximum or minimum using increasing/decreasing arguments.  
The second derivative test requires you to compute the second derivative at $x=c$ and then make an observation. 
If $f''(c)>0$ (the function is concave upwards), then the function has a minimum at $x=c$. 
If $f''(c)<0$ (the function is concave downwards), then the function has a maximum at $x=c$. 
If $f''(c)=0$, then the second derivative test fails. 
\note{picture of the smiley and frowny face would probably be good here}

\begin{example}
The function $f(x) = x^3-3x$ has derivatives $f^\prime = 3x^2-3$ and $f^{\prime\prime}=6x$.  The first derivative is zero when $3(x^2-1)=3(x-1)(x+1)=0$, or $x=\pm 1$.  
The second derivative at $x=1$ is $f''(1)=6$ (concave upwards), so there is a minimum at $x=1$.  
The second derivative at $x=-1$ is $f''(-1)=-6$ (concave downwards),
so there is a maximum at that point. This is all illustrated in the margin.
\marginpar{\includegraphics[width=\marginparwidth]{Applications/support/sage0.png}}
\end{example}

\subsection{Partial Derivatives}

Before extending the second derivative test to all dimensions, we have to talk about taking derivatives.
If a function has more than one input variable, say $f(x,y)=9-x^2+3y$ which has 2 input variables, then we have to take multiple derivatives, one with respect to each variable.  
These derivatives (called partial derivatives) are found by holding all variables constant except the one you want the derivative with respect to, and then just computing a normal derivative.
For the function $f(x,y)$, we define the partial derivative of $f$ with respect to $x$ as 
$$\ds f_x(x,y)=f_x = \frac{\partial f}{\partial x}= \lim_{h\to 0}\frac{f(x+h,y)-f(x,y)}{h},$$
and the partial derivative of $f$ with respect to $y$ as 
$$\ds f_y(x,y)=f_y =\frac{\partial f}{\partial y}= \lim_{k\to 0}\frac{f(x,y+k)-f(x,y)}{k}.$$
Notice that $f_x$ computes a limit as $y$ is held constant and we vary $x$. 

\begin{example}
For $f(x,y)=3x^2+4xy+\cos(xy)+y^3$, we obtain $f_x=6x+4y-y\sin(xy)+0$ and $f_y=0+4x-x\sin(xy)+3y^2$. 
Partial derivatives are found by holding all other variables constant, and then differentiating with respect to the variable in question.
\end{example}

\subsection{The Derivative}
The derivative of a function $\vec f\colon\RR^n\to\RR^m$
is an $m\times n$ matrix written $D\vec f(\vec x)$, where the columns
of the matrix are the partial derivatives of the function with respect
to an input variable (the first column is the partial derivative with
respect to the first variable, and so on). Some people call this
derivative the ``total'' derivative instead of the derivative, to
emphasize that the ``total'' derivative combines the ``partial''
derivatives into a matrix. Some examples of functions and their
derivative are in Table \ref{dertable}. Remember that each column of
the matrix corresponds to the partial derivatives with respect to an input variable.
\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Function&Derivative\\ \hline
{$f(x)=x^2$}& {$Df(x) = \begin{bmatrix}2x\end{bmatrix} $}\\ \hline
{$\vec r(t) = \left<3\cos(t),2\sin(t)\right>$}&  {$D\vec r(t) = \begin{bmatrix}-3\sin t\\ 2\cos t\end{bmatrix} $}\\ \hline
{$\vec r(t) = \left<\cos(t),\sin(t),t\right>$}&  {$D\vec r(t) = \begin{bmatrix}-\sin t \\ \cos t \\ 1\end{bmatrix} $}\\ \hline
{$f(x,y)=9-x^2-y^2$}&  {$Df(x,y) = \begin{bmatrix}-2x & -2y\end{bmatrix} $}\\ \hline
{$f(x,y,z)=x^2+y+xz^2$}&  {$Df(x,y,z) = \begin{bmatrix}2x+z^2 & 1 &2xz\end{bmatrix} $}\\ \hline
{$\vec F(x,y)=\left<-y,x\right>$}&  {$D\vec F(x,y) = \begin{bmatrix}0&-1\\ 1&0\end{bmatrix} $}\\ \hline
{$\vec F(r,\theta,z)=\left<r\cos\theta,r\sin\theta,z\right>$}&  {$D\vec F(r,\theta,z) = 
\begin{bmatrix}
\cos \theta &-r\sin\theta&0\\ 
\sin\theta&r\cos\theta&0\\ 
0&0&1
\end{bmatrix} $}\\ \hline
{$\vec r (u,v)=\left<u,v,9-u^2-v^2\right>$}&  {$D\vec r(u,v) = \begin{bmatrix}1&0\\ 0&1\\ -2u&-2v\end{bmatrix} $}\\ \hline
\end{tabular}
\end{center}
\caption{\label{dertable} Derivatives of functions are found by creating a matrix whose columns are the partial derivatives of the function.  If the function has multiple outputs, then the columns of the matrix will have one row for each output.  Hence a function with 2 inputs and 3 outputs will have 2 columns with 3 rows in each column.}
\end{table}

\subsection{The Second Derivative Test}
We're now ready to extend the second derivative test to all dimensions. We'll focus on only functions of the form $f\colon{\RR}^2\to{\RR}$, as this gives you the tools needed to study optimization in all dimensions. Because the output is one-dimensional, it makes sense to talk about a largest or smallest number.

The first derivative test does not work when the domain has more than one dimension because there are infinitely many ways to approach a point---you can't just look at the left and right side to decide if you are at an optimum value. 
However, at a local extreme value the derivative is still zero, which results in solving a system of equations to find any critical points. 
In higher dimensions, there are three classifications of critical points: maximum, minimum, or saddle point (a point where the tangent plane is horizontal, but in some directions you increase and in other directions you decrease). 

The second derivative test does work when the domain has dimension greater than one. Consider the function $z=f(x,y)$. 
Its derivative $Df(x,y) = \begin{bmatrix}f_x&f_y\end{bmatrix}$ is a function with two inputs $(x,y)$ and two outputs $(f_x,f_y)$. 
The second derivative {$D^2f (x,y)= \begin{bmatrix}f_{xx}&f_{xy}\\f_{yx}&f_{yy}\end{bmatrix} $} is a {$2\times 2$} square matrix called the Hessian of $f$. 
This matrix will always be symmetric, in that the transpose of the matrix equals itself (because $f_{xy}=f_{yx}$ from a theorem in multivariable calculus).  
At a critical point (where the first derivative is zero), the eigenvalues of $D^2f$ give the directional second derivative in the direction of a corresponding eigenvector. 
The largest eigenvalue is the largest possible value of the second derivative in any direction and the smallest eigenvalue is the smallest possible value of the second derivative in any direction. 

\marginpar{the second derivative test with eigenvalues}%
The \textbf{second derivative test} is the following. Start by finding all the critical points (places where the derivative is zero). Then find the eigenvalues of the second derivative. Each eigenvalue represents the directional 2nd derivative in the direction of a corresponding eigenvector. In every other direction, the directional 2nd derivative is between the smallest and largest eigenvalue.  
\begin{enumerate}
	\item If the eigenvalues are all positive at a critical point, then in every direction the function is concave upwards. The function has a minimum at that critical point.
	\item If the eigenvalues are all negative at a critical point, then in every direction the function is concave downwards. The function has a maximum there.
	\item If there is a positive eigenvalue and a negative eigenvalue, the function has a saddle point there.  
	\item If either the largest or smallest eigenvalue is zero, then the second derivative test fails. 
\end{enumerate}
Eigenvalues are the key numbers needed to generalize optimization to all dimensions. A proof of this fact is beyond the scope of this class. 

\begin{example}
For the function {$f(x,y)=x^2+xy+y^2$}, the derivative is $Df = \begin{bmatrix}2x+y&x+2y \end{bmatrix}$, which is zero only at $x=0,y=0$ (solve the system of equations $2x+y=0,x+2y=0$). 
\marginpar{The Hessian ($D^2f$) is always symmetric.}
The Hessian is $D^2f = \begin{bmatrix}2&1 \\1&2\end{bmatrix}$. The eigenvalues are found by solving $0=\det \begin{bmatrix}2-\lambda &1 \\1&2-\lambda \end{bmatrix} = (2-\lambda)^2-1 = 4-4\lambda+\lambda^2 -1 = (\lambda-3)(\lambda-1)$, so $\lambda = 3,1$ are the eigenvalues.  Since both eigenvalues are positive, the function is concave upwards in all directions, so there is a minimum at $(0,0)$.  

The eigenvectors of the Hessian help us understand more about the graph of the function.  An eigenvector corresponding to 3 is $(1,1)$, and corresponding to 1 is $(-1,1)$. These vectors are drawn in the graph of the function in the margin, together with two parabolas whose 2nd derivatives are precisely 3 and 1.  The parabola which opens upwards the most quickly has a 2nd derivative of 3.  The other parabola has a second derivative of 1. In every other direction, the 2nd derivative would be between 1 and 3.
\marginpar{\includegraphics[width=\marginparwidth]{Applications/support/2nddertest1}}
\end{example}

\begin{example}
For the function {$f(x,y)=x^3-3x+y^2-4y$}, the derivative is $Df = \begin{bmatrix}3x^2-3&2y-4 \end{bmatrix}$, which is zero at $x=1,y=2$ or $x=-1,y=2$. Hence there are two critical points, so we have to find two sets of eigenvalues. The Hessian is $D^2f = \begin{bmatrix}6x&0 \\0&2\end{bmatrix}$. When $x=-1,y=2$, the eigenvalues of $\begin{bmatrix}-6&0 \\0&2\end{bmatrix}$ are $\lambda=-6,2$. Since one is positive and one is negative, there is a saddle point at $(-1,2)$. When $x=1,y=2$, the eigenvalues of $\begin{bmatrix}6&0 \\0&2\end{bmatrix}$ are $\lambda=6,2$. Since both are positive, there is a minimum at $(-1,2)$ (as in every direction the function is concave upwards).

Again the eigenvectors help us understand how the function behaves, as illustrated in the margin.  At $(1,2)$, we have an eigenvector $(1,0)$ corresponding to 6, and $(0,1)$ corresponding to 2. In both eigenvector directions, the function is concave upwards, but opens more steeply in the $(1,0)$ direction since \mbox{$6>2$}.  At $(-1,2)$, we have an eigenvector $(1,0)$ corresponding to $-6$, and $(0,1)$ corresponding to 2. The functions opens steeply downwards in the $(1,0)$ direction, and upwards in the $(0,1)$ direction.
\marginpar{\includegraphics[width=\marginparwidth]{Applications/support/2nddertest2}}
\end{example}

\note{Can we draw a connection between positive eigenvalues in a
  vector field and positive eigenvalues in the second derivative test?}

\section{Markov Processes}

Matrices can be used to model a process called a Markov process. To fit this kind of model, a process must have specific states, and the matrix which models the process is a transition matrix which specifies how each state will change through a given transition. An example of a set of states is ``open'' or ``closed'' in an electrical circuit, or ``working properly'' and ``working improperly'' for operation of machinery at a manufacturing facility. A car rental company which rents vehicles in different locations can use a Markov Process to keep track of where their inventory of cars will be in the future. Stock market analysts use Markov processes and generalizations, liked stochastic processes and hidden Markov models, to make predictions about future stock values.  The algorithm that powers Google's internet search is based on the idea that browsing the web is a Markov process.

\begin{example} Let's illustrate a Markov Process related to classifying land in some region as ``Residential,'' ``Commercial,'' or ``Industrial.'' Suppose in a given region over a 5 year time span that 80\% of residential land will remain residential, 10\% becomes commercial, and 10\%  becomes industrial. For commerical land, 70\% remains commercial, 20\% becomes residential, and 10\% becomes industrial.  For industrial land, 70\% remains industrial, 30\% becomes commercial, and 0\% becomes residential.  To predict what happens to the land zoning at the end of a 5 year period, provided we know the current $R$, $C$, and $I$ values, we would compute \marginpar{Notice that the percentages go in columns. The residential percentages $(.8,.1,.1)$ become the first column. This gives us the transistion matrix
$$ \begin{array}{rl}
&\begin{array}{ccc} R&C&I \end{array} \\
 \begin{array}{c} \text{to }R\\ \text{to }C\\ \text{to }I \end{array}& 
\begin {bmatrix}  .8&.2&0\\.1&.7&.3\\.1&.1&.7 \end {bmatrix} \\
\multicolumn{2}{c}{\text{Transition Matrix}}
\end{array}.
$$ 
}
$$
\begin{array}{rl}
R_{\text{new}} &= .8 R+ .2 C+0 I\\ 
C_{\text{new}} &= .1 R+ .7 C+.3 I\\ 
I_{\text{new}} &= .1 R+ .1 C+.7 I 
\end{array}
\xrightarrow{\text{matrix form}}
\begin{bmatrix}
R_{\text{new}}\\ 
C_{\text{new}}\\ 
I_{\text{new}} 
\end{bmatrix}
=
\begin{bmatrix}
.8& .2 &0 \\ 
.1& .7 &.3\\ 
.1& .1 &.7 
\end{bmatrix}
\begin{bmatrix}
R\\ 
C\\ 
I 
\end{bmatrix}
$$
The matrix on the right above is called the transition matrix of the Markov process. 
It is a matrix where each column relates to one of the ``states,'' and the numbers in that column are the proportions of the column state that will change to the row state through the transition (the ordering on row and column states is the same). 
We calculate the next ``state'' by multiplying our current state by the transition matrix. If current land use is about 50\% residential, 30\% commercial, and 20\% industrial, then 5 years later the land use would be 
$$ 
A\vec x= \begin {bmatrix} .8&.2&0\\.1&.7&.3\\.1&.1&.7 \end {bmatrix}
 \begin {bmatrix} 50\\30\\20 \end {bmatrix}
 =   \begin {bmatrix} 46\\ 32 \\ 22\end {bmatrix}
$$  If the same transitions in land use continue, we can multiply the previous projection (state) by the transition matrix to obtain a 10 and 15 year projection for land use:  
\begin{center}\begin{tabular}{cc}
$A(A \vec x) =A^2 \vec x$&$A(A^2\vec x)=A^3\vec x$\\
$
\begin {bmatrix} .8&.2&0\\.1&.7&.3\\.1&.1&.7 \end {bmatrix}
\begin {bmatrix} 46\\ 32 \\ 22 \end {bmatrix}
 =   \begin {bmatrix} 43.2\\ 33.6 \\ 23.2\end {bmatrix}
$ 
&
$
\begin {bmatrix} .8&.2&0\\.1&.7&.3\\.1&.1&.7 \end {bmatrix}
\begin {bmatrix} 43.2\\ 33.6 \\ 23.2 \end {bmatrix}
 =   \begin {bmatrix} 41.28\\ 34.8\\ 23.92\end {bmatrix}
$ 
\\
10 Year Projection 
&15 Year Projection 
\end{tabular}\end{center}
Each time we multiply on the left by our transition matrix, we add 5 more years to our projection. This projection is valid as long as the same trends continue. 
\end{example}










\subsection{Steady State Solutions}


Consider the land use example from above.  Let $\vec x_0$ be our initial state. If our transition matrix $A$ remains the same forever, what will eventually be the proportion of land devoted to residential, commercial, or industrial use? We can write each new state as powers of the transition matrix $A$ by writing 
$$\vec x_{1} = A \vec x_{0}, \quad \vec x_{2}=A \vec x_{1} = AA\vec x_{0} = A^2\vec x_{0},\quad \vec x_{3}= A^3\vec x_{0},\quad \vec x_{n}= A^n\vec x_{0}.$$  What happens to the product $A^n\vec x_0$ as $n\to \infty$? Can we reach a state $\vec x = (R,C,I)$ such that $A \vec x=\vec x$, where the next state is the same as the current? If this occurs, then any future transitions will not change the state either. This state $\vec x$ is called a \emph{steady state}, since it does not change when multiplied by the transition matrix (it remains steady). 

Let's look more closely at the steady state equation $$A\vec x = \vec x = 1\vec x.$$ 
Do you see the eigenvalue-eigenvector notation $A\vec x = \lambda \vec x$? 
\marginpar{The number $\lambda =1$ is always an eigenvalue of the transition matrix.  Steady states are eigenvectors of the transition matrix.}
The eigenvalue is 1 and the steady state is an eigenvector. 
Without even thinking that an eigenvalue was important, we reduced finding a steady state to an eigenvalue-eigenvector problem. 
For any Markov process (the columns of the matrix must sum to 1), the number $\lambda = 1$ will always be an eigenvalue. All we have to do is find the eigenvectors corresponding to the eigenvalue 1. 
The solution to $\ds\lim_{n\to\infty}A^n \vec x_0$ is this steady state, and is an eigenvector of the transition matrix.
 
\begin{example}
For the land use Markov process from the previous example, an eigenvector corresponding to 1 is $\left(\frac{3}{2},\frac32,1\right)$. 
Since any nonzero multiple of an eigenvector is again an eigenvector, we can multiply by a constant so that the proportions sum to 100. 
Multiplying by 2 we have $(3,3,2)$, which means that the ratio of land will be 3 acres residential to 3 acres commercial to 2 acres industrial. 
\marginpar{Divide each entry by the sum to get percentages.}
To write this in terms of percentages, divide each component by 8 (the sum $3+3+2$) to obtain $3/8:3/8:2/8$. Multiply by 100 to get the percentages $37.5\%:37.5\%:25\%$, the long term percentages of land use.
\end{example}


















\section{Kirchoff's Electrial Laws}
Gustav Kirchoff discovered two laws of electricity that pertain to the conservation of charge and energy. 
%In short, his two laws state that current in equals current out, and volts in equals volts out. 
To fully describe these laws, we must first discuss voltage, resistance, and current.  
Current is the flow of electricity; often you can compare it to the flow of water.  As a current passes across a conductor, it encounters resistance. 
Ohm's law states that the product of the resistance $R$ and current $I$ across a conductor equals a drop in voltage $V$, i.e. $RI=V$. \marginpar{\begin{center}Ohm's law: \\ Voltage = Resistance $\times$ Current$$V=RI$$\end{center}}
If the voltage remains constant, then a large resistance corresponds to a small current. 
A resistor is an object with high resistance which is placed in an electrical system to slow down the flow (current) of electricity. 
Resistors are measured in terms of ohms, and the larger the ohms, the smaller the current.  Figure \ref{ecir} illustrates two introductory electrical systems. 



\begin{figure}[htb]
\begin{center}
\begin{tabular}{cc}
\input{Applications/electric-circuit-2-loops}
&
\input{Applications/electric-circuit-3-loops}
\\
Two Loop System & Three Loop System
\end{tabular}\end{center}
\caption{Electrical Circuit Diagrams.}
\label{ecir}\end{figure}
In this diagram, wires meet at nodes (illustrated with a dot).  
Batteries and voltage sources (represented by 
\begin{tikzpicture}[scale=.15,rotate=-90]
%	\useasboundingbox (-.5,-3) rectangle (.5,3);
	\clip (-1,-2) rectangle (1,2);
	\draw (0,0) circle (1cm);
	\draw (.3,.5) -- (-.3,.5);
	\draw (0,.2) -- (0,.8);
	\draw (.3,-.5) -- (-.3,-.5);
	\draw (0,1) -- (0,3);
	\draw (0,-1) -- (0,-3);
\end{tikzpicture}
or other symbols)
supply a voltage of $E$ volts.  At each node the current may change, so the arrows and letters $i$ represent the different currents in the electrical system. The electrical current on each wire may or may not follow the arrows drawn (a negative current means that the current flows opposite the arrow). Resistors are depicted with the symbol 	\begin{tikzpicture}[scale=.2,rotate=90]
%	\useasboundingbox (0,-3) rectangle (0,3);
	\clip (-.5,-2) rectangle (.5,2);
	\draw (0,-3) -- ++(0,1.8) -- ++(.5,.2) 
		-- ++(-1,.4) -- ++(1,.4)
		-- ++(-1,.4) -- ++(1,.4)
		-- ++(-1,.4) -- ++(.5,.2)
		-- ++(0,1.8) ;
	\end{tikzpicture}
, and the letter $R$ represents the ohms. 

Kirchoff discovered two laws which help us find the currents in a system, provided we know the voltage of any batteries and the resistance of any resistors. 
\begin{enumerate}
	\item Kirchoff's current law states that at every node, the current flowing in equals the current flowing out (at nodes, current in = current out). 
	\item Kirchoff's voltage law states that on any loop in the system, the directed sum of voltages supplied equals the directed sum of voltage drops (in loops, voltage in = voltage out). 
\end{enumerate}

Let's use Kirchoff's laws to generate some equations for the two loop system. 
\begin{enumerate}
	\item First we will examine Kirchoff's current law. 
	At the first node (top middle), current $i_1$ flows in while $i_2$ and $i_3$ flow out. 
	Kirchoff's current law states that 
	\marginpar{At each node, current in equals current out.}
	$$i_1=i_2+i_3$$ or $i_1-i_2-i_3=0$.  
	At the second node, both $i_2$ and $i_3$ are flowing in while $i_1$ flows out. 
	This means that $i_2+i_3=i_1$ or $-i_1+i_2+i_3=0$. 
	This second equation is the same as multiplying both sides of the first by $-1$ (so we say the 2nd equation depends on the first). 
	\item We now look at Kirchoff's voltage law. 
	Pick a loop and work your way around the loop in a clockwise fashion. 
	Each time you encounter a battery or resistor, include a term for the voltage supplied $E$ on the left side of an equation, and the voltage drop (resistance times current $Ri$) on the right. 
	If you encounter a battery or resistor as you work against the current, then times that term by $-1$. 
	
	The left loop has a battery with voltage $E$ (voltage in). 
	While moving along the wire containing $i_i$ we encounter a resistor with resistance $R_1$ which contributes a voltage drop of $R_1i_1$ volts. 
	Along $i_2$ we encounter $R_2$ for a drop of $R_2i_2$ volts. An equation for the first loop is 
	\marginpar{On loops, voltage in equals voltage out.}
	$$E=R_1i_1+R_2i_2.$$
	 
	On the right loop we encounter along current $i_3$ a resistor with resistance $R_3$ ohms.  
	While working our way against the arrow drawn on $i_2$, we encounter an $R_2$ ohm resistor (hence we have to put a negative sign in front of $R_2i_2$. \marginpar{Remember to change the sign when you cross a resistor while moving against the current.}
	There are no batteries on the second loop. The two resistors give us the equation $$0=-R_2 i_2 +R_3i_3.$$ 
\end{enumerate}
We can now write a system of equations involving the unknowns $i_1,i_2,i_3$, put it in matrix form, and then row reduce to solve
$$
\begin{array}{rl}
i_1-i_2-i_3&=0\\
-i_1+i_2+i_3&=0\\
R_1i_1+R_2i_2&=E\\
-R_2 i_2 +R_3i_3&=0
\end{array}
\xrightarrow{\text{matrix form}}
\begin{bmatrix}[ccc|c]
1&-1&-1&0\\
-1&1&1&0\\
R_1&R_2&0&E\\
0&-R_2&R_3&0
\end{bmatrix}
$$$$
\xrightarrow{\rref}
\begin{bmatrix}[ccc|c]
 1 & 0 & 0 & \dfrac{E R_2+ E R_3}{R_1 R_2+R_1 R_3+R_2R_3} \\
 0 & 1 & 0 & \dfrac{E R_3}{R_1 R_2+R_1 R_3+R_2R_3} \\
 0 & 0 & 1 & \dfrac{E R_2}{R_1 R_2+R_1 R_3+R_2R_3} \\
 0 & 0 & 0 & 0
\end{bmatrix}.
$$
The reason we have a row of zeros at the bottom of our system is because the two rows corresponding to the nodes are linearly dependent.  
When we reduce the matrix, this row dependence results in a row of zeros.

A similar computation can be done for the three loop system. 
There are 6 unknown currents, 4 nodes, and 3 loops.  
This will give us 7 equations with 6 unknowns.  
The 4 equations from the nodes will again contribute rows which are linearly dependent, which means you can always ignore an equation from one of the nodes. \marginpar{If there are $n$ nodes in a problem, you only need to consider $n-1$ of them, as the $n$ equations are dependent.}
In electrical network problem, row reduction will always give a unique solution. 
In the homework, you are asked to setup systems of equations for various electrical systems, and then solve them. 


\begin{example} \label{electrical example}Let's look at an example which involves numbers.  Suppose $E=12$ (a 12 volt battery) and the resistors have $R_1=2, R_2=R_3=4$ ohms. The top node gives the equation $i_1=i_2+i_3$ (remember flow in equals flow out). We'll skip the bottom node, as it contributes another row which is dependent on the first.  The left loop gives the equation $12 = 2i_1+4i_2$, while the right loop gives the equation $0=-4r_2+4r_3$.  We write this in matrix form
$$
\begin{array}{rl}
i_1-i_2-i_3&=0\\
2i_1+4i_2&=12\\
-4 i_2 +4i_3&=0
\end{array}
\xrightarrow{\text{matrix form}}
\begin{bmatrix}[ccc|c]
1&-1&-1&0\\
2&4&0&12\\
0&-4&4&0
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[ccc|c]
 1 & 0 & 0 & 3\\
 0 & 1 & 0 & 3/2\\
 0 & 0 & 1 & 3/2
\end{bmatrix}
$$
which tells us the currents are $i_1=3$, $i_2=3/2$, and $i_3=3/2$.
\end{example}






\subsection{Cramer's Rule}
Cramer's rule is a theoretical tool which gives the solution to any linear system $A\vec x = \vec b$ with $n$ equations and $n$ unknowns, provided that there is a unique solution.  
Let $D=\det(A)$. 
Let $D_i$ be the determinant of the matrix formed by replacing the $i$th column of $A$ with $\vec b$.  
Then Cramer's rule states that $$x_1 = \frac{D_1}{D},x_2 = \frac{D_2}{D},\ldots, x_n = \frac{D_n}{D}.$$ 
\note{We may prove it in class with pictures which connect determinants to area (eventually I'll add this to an appendix)}. 
This method of solving a system of equations is quickly doable for 2 by 2 and 3 by 3 systems, but becomes computationally inefficient beyond (as computing determinants is time consuming and numerically unstable on large matrices). 
\marginpar{Cramer's rule works great on 2 by 2 and 3 by 3 systems, where determinants are easy to compute.}
For large systems, it is better to use Gaussian elimination. 
However, Cramer's rule is a powerful theoretical tool, and can simplify symbolic computations for small systems. Let's look at a few examples.

\begin{example}
Let's solve $
\begin {bmatrix} 1&2&0\\-2&0&1\\0&3&-2\end {bmatrix} 
\begin {bmatrix} x_1\\x_2\\x_3\end {bmatrix} 
=  \begin{bmatrix} 2\\-2\\1\end {bmatrix}
$ using Cramer's rule.  
We compute the determinant of the coefficient matrix first to obtain
$$D=\begin{vmatrix} 1&2&0\\-2&0&1\\0&3&-2\end {vmatrix} = -11.$$ Next we replace each column of the coefficient matrix with the right column of our augmented system and compute the three determinants to obtain
$$
\begin{vmatrix} 
\tikz \draw node[fill=pink,inner sep=0cm]{$\cl{2\\-2\\1}$};
& \tikz \draw node[inner sep=0cm]{$\cl{2\\0\\3}$};
&\tikz\draw node[inner sep=0cm]{$\cl{0\\1\\-2}$};
\end {vmatrix}  
 =-12,
\begin{vmatrix} 
\tikz \draw node[inner sep=0cm]{$\cl{1\\-2\\0}$};
& \tikz \draw node[fill=pink,inner sep=0cm]{$\cl{2\\-2\\1}$};
&\tikz\draw node[inner sep=0cm]{$\cl{0\\1\\-2}$};
\end {vmatrix}  
=-5, 
\begin{vmatrix} 
\tikz \draw node[inner sep=0cm]{$\cl{1\\-2\\0}$};
& \tikz \draw node[inner sep=0cm]{$\cl{2\\0\\3}$};
&\tikz \draw node[fill=pink,inner sep=0cm]{$\cl{2\\-2\\1}$};
\end {vmatrix}  
=-2 .$$
Cramer's rule requires that we divide each of these determinants by the original determinant, giving the solution $x_1=12/11, x_2 = 5/11, x_3 = 2/11$.  Using Gaussian Elimination, we obtain the same solution 
$$ \begin {bmatrix}[ccc|c] 1&2&0&2\\-2&0&1&-2\\0&3&-2&1\end {bmatrix}\xrightarrow{\rref}
\begin {bmatrix}[cccc] 1&0&0&12/11
\\0&1&0&5/11\\0&0&1&2/11\end {bmatrix} 
, $$
however the arithmetic involved in keeping track of fractions or really large integers becomes much more difficult by hand without Cramer's rule.
\end{example}

\begin{example}
Consider the electrical system in Example \ref{electrical example}, where $E=12$, $R_1=2$, and $R_2=R_3=4$. 
The corresponding augmented matrix we used to solve this system was 
$$
\begin{bmatrix}[ccc|c]
1&-1&-1&0\\
2&4&0&12\\
0&-4&4&0
\end{bmatrix}, 
A=
\begin{bmatrix}1&-1&-1\\2&4&0\\0&-4&4\end{bmatrix}, 
\vec b=\begin{bmatrix}
0\\
12\\
0
\end{bmatrix},D=\begin{vmatrix} 1&-1&-1\\2&4&0\\0&-4&4 \end {vmatrix} =32. 
$$ 
We now replace each column with $\vec b$ and compute the determinant of the corresponding matrix (remember to cofactor along the column which contains $0,12,0$ to do this quickly)
$$ 
D_1=\begin{vmatrix} 0&-1&-1\\12&4&0\\0&-4&4 \end {vmatrix} =96,
D_2=\begin{vmatrix} 1&0&-1\\2&12&0\\0&0&4 \end {vmatrix} =48, 
D_3=\begin{vmatrix} 1&-1&0\\2&4&12\\0&-4&0 \end {vmatrix} =48. 
$$
Dividing each of these by the determinant of the original matrix gives the solution $i_1 = 96/32 = 3$, $i_2=i_3=48/32 = 3/2$, which matches the solution we found using row reduction in the previous section. 
\end{example}



















\section{Fitting Curves to Data}
Our discussion and examples in this section will involve data in the $xy$ plane ($\RR^2$).  However, the concepts and formulas generalize to any number of dimensions
\subsection{Interpolating Polynomials}
Through any two points (with different $x$-values) there is a unique line of the form $y=mx+b$. If you know two points, then you can use them to find the values $m$ and $b$.  
Through any three points (with different $x$-values) there is a unique parabola of the form $y=ax^2+bx+c$, and you can use the three points to find the values $a$, $b$, and $c$.  
\marginpar{For any $n+1$ points (with different $x$-values), there is a unique polynomial of degree $n$ which passes through those points.}%
The pattern holds: for any $n+1$ points (with different $x$-values), there is a unique polynomial (called an \define{interpolating polynomial}) of degree $n$ which passes through those points. 
In this section, we will illustrate how to find interpolating polynomials from a list of points, and show how the solution requires solving a linear system.

To organize our work, let's first standardize the notation.  
Rather than writing $y=mx+b$, let's write $y=a_0+a_1 x$ (where $a_0=b$ and $a_1=m$). 
For a parabola, let's write $\ds y=a_0 + a_1 x+ a_2 x^2 = \sum_{k=0}^{2} a_k x^k$. 
We can now write any polynomial in the form 
\marginpar{Standardizing the notation makes a problem easier to
  generalize.}%
$$\ds y = a_0 + a_1 x+ \cdots + a_n x^n = \sum_{k=0}^n a_k x^k.$$ 
By standardizing the coefficients, we can use summation notation to express a polynomial of any degree by changing the $n$ on the top of the summation sign. 
Now that our notation is organized, let's use it to find a polynomial through 3 points.

\begin{example}
Let's find a parabola through the three points $(0, 1)$, $(2, 4)$, $(4, 5)$.  The polynomial is $y=a_0 +a_1 x+a_2 x^2$ and our job is to find the three constants $a_0$,  $a_1$, $a_2$.  Since we have three points, we put these points into the equation to obtain a system of three equations:
$$
a_{{0}}=1, \quad \quad 
a_{{0}}+2\,a_{{1}}+4\,a_{{2}}=4, \quad \quad 
a_{{0}}+4\,a_{{1}}+16\,a_{{2}}=5.
$$
This is a linear system with 3 equations and 3 unknowns.  We now write the system in matrix form and reduce it
$$
\begin{bmatrix}[ccc|c] 
1&0&0&1\\
1&2&4&4\\
1&4&16&5
\end {bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[ccc|c]
1&0&0&1\\
0&1&0&2\\
0&0&1&-1/4
\end {bmatrix} 
.$$
The reduced row echelon form tells us that the coefficients are $a_0 = 1$, $a_1= 2$, $a_2=-1/4$, which means our parabola is $y=1+2 x- \frac 14 x^2$. Cramer's rule gives $D=16$, $D_1=16$, $D_2=32$, $D_3=-4$, so $a_0 = 16/16=1$, $a_1=32/16=2$, and $a_2=-4/16=-1/4$, confirming our result from Gaussian elimination.

\marginpar{
  \begin{tikzpicture}
    \begin{axis}[ footnotesize, xmin=-1, xmax=5, axis equal =true]
      % use TeX as calculator: 
      \addplot+[only marks] coordinates { (0,1) (2,4) (4,5)};
      \addplot[mark=none] {1+2*x-x^2/4};
   \end{axis}
  \end{tikzpicture}
}%
\marginpar{Check your work by plugging the points back into your solution.}%
Once you have obtained the interpolating polynomial, you can always check your work by plugging the points into the interpolating polynomial. When $x=0$, we have $y=1+0+0=1$; when $x=2$, we have $y=1+2-1=2$; and when $x=4$, we have $y=1+8-4=5$.  In other words,  the parabola passes through the three points $(0,1)$, $(2,4)$, and $(4,5)$, as needed.  This parabola is shown in the margin.  
\end{example}

In the example above, notice that powers of $x$ appear as the coefficients in our coefficient matrix, and we augment that matrix by the $y$ values. This is the general pattern for finding an interpolating polynomial. The diagram below shows the general method for finding an interpolating polynomial through three points.  Note that each entry of the first column of the matrix is 1 since $x_1^0=1$, $x_2^0=1$, and $x_3^0=1$.
\begin{center}
\begin{tabular}{c}
$(x_1,y_1),(x_2,y_2),(x_3,y_3)$ \\
 $
\begin{bmatrix}[ccc|c] 
1&x_1^1&x_1^2&y_1\\
1&x_2^1&x_2^2&y_2\\
1&x_3^1&x_3^2&y_3
\end {bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[ccc|c]
1&0&0&a_0\\
0&1&0&a_1\\
0&0&1&a_2
\end {bmatrix} 
$
\\
 $y=a_0+a_1x+a_2x^2$
\end{tabular}
\end{center}
Finding an interpolating polynomial through four points is very similar---just add one more row and column to the matrix and repeat the process.
\begin{center}
\begin{tabular}{c}
$(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$\\
$
\begin{bmatrix}[cccc|c] 
1&x_1^1&x_1^2&x_1^3&y_1\\
1&x_2^1&x_2^2&x_2^3&y_2\\
1&x_3^1&x_3^2&x_3^3&y_3\\
1&x_4^1&x_4^2&x_4^3&y_4
\end {bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[cccc|c]
1&0&0&0&a_0\\
0&1&0&0&a_1\\
0&0&1&0&a_2\\
0&0&0&1&a_3
\end {bmatrix} 
$\\
$y=a_0+a_1x+a_2x^2+a_3x^3$
\end{tabular}
\end{center}
This pattern generalizes to all dimensions (and the corresponding
algorithm is coded into spreadsheet programs such as Microsoft Excel
and OpenOffice Calc, as well as many mathematics and statistics
software packages). Remember that the $x$-values must be different
(since a function requires only one output for each input). Once you have obtained your solution, remember that you can easily check if your solution is correct by plugging the points into your polynomial.



\subsection{Least Squares Regression}
Interpolating polynomials give a polynomial which passes through every point in a set of data. 
While they pass through every point in a set of data, the more points the polynomial must pass through, the more the polynomial may have to make large oscillations in order to pass through each point.\note{Graph Runge example}  Furthermore, often data points from real-life measurements have error associated with them, so we don't necessarily want to mandate that our function go through the data point.
Often we just need a simple line or parabola that passes near the points and gives a good approximation of a trend. 

Here's an example that saved me money when buying a minivan. 
When I needed to purchase a minivan for my expanding family, I gathered mileage and price data for about 40 cars from the internet. 
I plotted this data and discovered an almost linear downward trend (as mileage increased, the price dropped).  
I created a line to predict the price of a car based on mileage.  
I then used this data to talk the dealer into dropping the price of the car I wanted by over \$1000. 
\note{I need to find this data on our computer and put a graph here, or even just construct the data from blue book values}

How do you find a line that is ``closest'' to a set of points, and is the best line to approximate your data?  Finding an equation of this line, called the \define{least squares regression} line, is the content of this section.  The least squares regression line is used to find trends in many branches of science and business.   Let's introduce the idea with an example. 

\begin{example}\label{regression1ex}
Find a line that is closest to passing through the three points $(0,1)$, $(2,4)$, and $(4,5)$.  Since the points are not collinear\marginpar{collinear means lie on the same line}, there is not a line through all three points.  Suppose for a moment that there was a line of the form $y=mx+b=a_0+a_1x$ that did pass through the points. Plugging our 3 points into the equation $a_0+a_1x=y$ gives the system of equations 
$$\begin{cases}a_0=1\\a_0+2a_1=4\\a_0+4a_1=5\end{cases}
\xrightarrow{\text{augmented matrix}}
\begin{bmatrix}[cc|c]1&0&1\\1&2&4\\1&4&5\end{bmatrix}
\xrightarrow{\text{matrix eqn}}
\begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}
\begin{bmatrix}a_0\\a_1\end{bmatrix}
=\begin{bmatrix}1\\4\\5\end{bmatrix}.
$$
Notice that the system can be written in matrix form $A\vec x = \vec b$, where $A$ contains a column of 1's and $x$-values, $\vec x$ is the vector of coefficients $a_i$, and $\vec b$ is a column of $y$-values. 
If you try to reduce this matrix, you will discover the system is inconsistent (has no solution), which should not be a surprise since there is no line which passes through these three points. 
Notice that there are more equations (3 equations) than variables ($a_0$ and $a_1$), which means the system is overdetermined.
\marginpar{Recall that if a system has more equations than variables, we say the system is overdetermined.} 

While there is no solution, can we still use our matrix equation to find a solution? 
Is there a way to reduce the number of rows in our system, so that the resulting system has only 2 rows? 
If we multiply on the left by a 2 by 3 matrix, we would obtain a system with 2 rows instead of 3, and the rows of the new matrix would be linear combinations of the rows of our original matrix.  
The only 2 by 3 matrix in this problem is the transpose of A.  
So let's multiply both sides of the matrix equation by the transpose of A, and see what happens:
\begin{gather*}
A = \begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}, \quad
A^T = \begin{bmatrix}1&1&1\\0&2&4\end{bmatrix},\\
A^T A =\begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}\begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}= \begin{bmatrix}3&6\\6&20\end{bmatrix},\\% \quad
A^T\vec b =  \begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}\begin{bmatrix}1\\4\\5\end{bmatrix} = \begin{bmatrix}10\\28\end{bmatrix}.
\end{gather*}
\marginpar{Multiply both sides by $A^T$, the transpose of $A$, to obtain a system that has a solution.}%
Multiplying both sides of the equation $A\vec x = \vec b$ on the left by $A^T$ gives us the equation 
$A^T A \vec x = A^T\vec b$, or 
$$\begin{bmatrix}3&6\\6&20\end{bmatrix} \begin{bmatrix}a_0\\a_1\end{bmatrix}=\begin{bmatrix}10\\28\end{bmatrix}.$$ 
This is a system of 2 equations with 2 unknowns, and it has a unique solution.  
Reducing $\begin{bmatrix}[cc|c]3&6&10\\6&20&28\end{bmatrix}$ to $\begin{bmatrix}[cc|c]1&0&4/3\\0&1&1\end{bmatrix}$ means the solution is $y=\frac{4}{3}+x$ (illustrated in the margin).  
\marginpar{
  \begin{tikzpicture}
    \begin{axis}[ footnotesize, xmin=-1, xmax=5, axis equal =true]
      % use TeX as calculator: 
      \addplot+[only marks] coordinates { (0,1) (2,4) (4,5)};
      \addplot[mark=none] {4/3+x};
   \end{axis}
  \end{tikzpicture}
}


We will see exactly why this works in Section~\ref{sec:vector-spaces-why} when we start looking at the columns of our matrix as a basis for a vector space and asking questions about linear combinations, spans, and projections.   
For now, let's just use the transpose to solve least squares regression problems.
\end{example}

In general, a least squares regression problem requires the following:
\begin{enumerate}
	\item Assume the form of a solution, such as $y=a_0+a_1x$ for a line. 
	\item Plug in values to get a matrix equation $A\vec x=\vec b$. 
	\item Multiply both sides by $A^T$.
	\item Solve the simplified system (elimination, Cramer's rule, an inverse, or other more sophisticated methods). 
\end{enumerate}
When trying to find a least squares regression line, the simplified system will have a 2 by 2 coefficient matrix, so Cramer's rule provides an extremely quick solution.

\begin{example}
Let's find the least squares regression line which passes nearest the four points $(0,0)$, $(-1,2)$, $(-2,4)$, and $(0,-1)$. We are after an equation of the form $y=a_0+a_1x$.  The four points give the equations $a_0=0$, $a_0-a_1=2$, $a_0-2a_1=4$,  and $a_0=-1$. In matrix form, we write 
\begin{gather*}
\begin{bmatrix}
1&0\\
1&-1\\
1&-2\\
1&0
\end{bmatrix}
\begin{bmatrix}
a_0\\
a_1
\end{bmatrix}
=
\begin{bmatrix}
0\\
2\\
4\\
-1
\end{bmatrix}
, \text{ where }
A=
\begin{bmatrix}
1&0\\
1&-1\\
1&-2\\
1&0
\end{bmatrix}, \quad
\vec b = 
\begin{bmatrix}
0\\
2\\
4\\
-1
\end{bmatrix}, \\
A^T=
\begin{bmatrix}
1&1&1&1\\
0&-1&-2&0
\end{bmatrix}, \text{ so }
A^TA = 
\begin{bmatrix}
4&-3\\
-3&5
\end{bmatrix}, \quad
A^T\vec b =
\begin{bmatrix}
5\\
-10
\end{bmatrix}. 
\end{gather*}
Now solve the matrix equation 
$A^TA\vec x=
\begin{bmatrix}
4&-3\\
-3&5
\end{bmatrix}\begin{bmatrix}
a_0\\
a_1
\end{bmatrix}
=
\begin{bmatrix}
5\\
-10
\end{bmatrix}=A^T\vec b.
$
Cramer's rule gives the solution as
$$
a_0
=\frac{\begin{vmatrix}
5&-3\\
-10&5
\end{vmatrix}}{\begin{vmatrix}
4&-3\\
-3&5
\end{vmatrix}}
=\dfrac{-5}{11}
, \quad\quad\quad
a_1
=\frac{\begin{vmatrix}
4&5\\
-3&-10
\end{vmatrix}}{\begin{vmatrix}
4&-3\\
-3&5
\end{vmatrix}}
=\dfrac{-25}{11}
.$$
The least square regression line is $y=-\frac{5}{11}-\frac{25}{11}x$ (illustrated in the margin).
\marginpar{
  \begin{tikzpicture}
    \begin{axis}[ footnotesize, xmin=-3,xmax=1,axis equal =true]
      % use TeX as calculator: 
      \addplot+[only marks] coordinates { (0,0) (-1,2) (-2,4) (0,-1)};
      \addplot[mark=none] {-5/11-25/11*x};
   \end{axis}
  \end{tikzpicture}
}

\end{example}


\subsection{A Quick 2 by 2 Inverse}\label{sec:quick-2-2-inverse}
Finding the least square regression line requires solving the system $A^TA\vec x = A^T \vec b$ for $\vec x$. Symbolically we can solve this system by multiplying both sides on the left by $(A^TA)^{-1}$ (this inverse will exist), giving the solution 
$$\vec x = \begin{bmatrix}a_0\\a_1\end{bmatrix}= (A^TA)^{-1}A^T \vec b.$$ 

For 2 by 2 matrices, there is quick way to find the inverse. 
To find the inverse of a 2 by 2 matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$, we need to reduce $\begin{bmatrix}[cc|c]a&b&1\\c&d&0\end{bmatrix}$ to find the first column of the inverse, and $\begin{bmatrix}[cc|c]a&b&0\\c&d&1\end{bmatrix}$ to find the second column.  
Cramer's rule gives the formula 
\marginpar{To find the inverse of a 2 by 2, 
\begin{enumerate}
	\item switch the diagonal entries, 
	\item change the sign on the off-diagonals, and 
	\item divide by the determinant.
\end{enumerate}

$
\begin{bmatrix}
a&b \\ c&d
\end{bmatrix}^{-1} 
= \frac{1}{ad-bc}
\begin{bmatrix}
d&-b \\ -c&a
\end{bmatrix}
$

}%
$$A^{-1}=
\begin{bmatrix}
\begin{vmatrix}1&b\\0&d\end{vmatrix}/|A|&\begin{vmatrix}0&b\\1&d\end{vmatrix}/|A|\\ \\
\begin{vmatrix}a&1\\c&0\end{vmatrix}/|A|&\begin{vmatrix}a&0\\c&1\end{vmatrix}/|A|\end{bmatrix} 
= \frac{1}{|A|}
\begin{bmatrix}d&-b\\-c&a\end{bmatrix}
$$
To find the inverse of a 2 by 2 matrix, just interchange the diagonal entries, change the sign on the others, and divide by the determinant.

\begin{example} 
$
\begin{bmatrix}
 1 & 3 \\
 2 & 4
\end{bmatrix}\inv =
\ds\frac{1}{-2}\begin{bmatrix}
 4 & -3 \\
 -2 & 1
\end{bmatrix}
$, and $
\begin{bmatrix}
 13 & 3 \\
 -7 & 2
\end{bmatrix}\inv
=
\ds\frac{1}{47}\begin{bmatrix}
 2 & -3 \\
 7 & 13
\end{bmatrix}
$.
\end{example}



\begin{example}
Let's repeat the introductory example (\ref{regression1ex}) from the last section by using an inverse to find the line closest to passing through the three points $(0,1)$, $(2,3)$, and $(4,6)$. The matrix equation and relevant matrices are
\begin{gather*}
A = \begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}, \quad
A^T = \begin{bmatrix}1&1&1\\0&2&4\end{bmatrix},\\
A^T A =\begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}\begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}= \begin{bmatrix}3&6\\6&20\end{bmatrix},\\% \quad
A^T\vec b =  \begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}\begin{bmatrix}1\\3\\6\end{bmatrix} = \begin{bmatrix}10\\28\end{bmatrix}.
\end{gather*}
The inverse of $(A^TA)$ is $\ds\frac{1}{60-36}\begin{bmatrix}20&-6\\-6&3\end{bmatrix}$, which means our solution is 
$$
\begin{bmatrix}a_0\\a_1\end{bmatrix} 
= (A^TA)^{-1}A^T b 
= \ds\frac{1}{24}\begin{bmatrix}20&-6\\-6&3\end{bmatrix}\begin{bmatrix}10\\28\end{bmatrix}
= \ds\frac{1}{24}\begin{bmatrix}32\\24\end{bmatrix}  
= \begin{bmatrix}4/3\\1\end{bmatrix}. 
$$
We of course obtained the same solution $y=\frac{4}{3}+x$.
\end{example}


One advantage of using an inverse to solve a least square regression problem is that the product $W=(A^TA)^{-1}A^T$ can be computed once, and then solutions to similar least squares regression problems are found by the simple product $\vec x=W\vec b$. 
A different set of data points where the $x$-values remain the same but the $y$-values change can then be solved by just changing $\vec b$ and using the same results as before. 

\begin{example}
Let's find the least square regression line for the two data sets 
\begin{enumerate}
	\item $(0,2)$, $(2,1)$, and $(4,3)$
	\item $(0,6)$, $(2,3)$, and $(4,-1)$
\end{enumerate}
Notice that both of the data sets have the same $x$ values as the previous example.  Hence we can still use 
$$
A = \begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix},\quad
A^T= \begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}, \quad
A^T A= \begin{bmatrix}3&6\\6&20\end{bmatrix}, \quad
(A^TA)^{-1}=\ds\frac{1}{24}\begin{bmatrix}20&-6\\-6&3\end{bmatrix}.
$$ 
The change occurred with the $y$-values, which means that $\vec b$ changed for each problem.  Before solving either, we compute 
$$W=(A^TA)^{-1}A^T 
= \ds\frac{1}{24}\begin{bmatrix}20&-6\\-6&3\end{bmatrix}\begin{bmatrix}1&1&1\\0&2&4\end{bmatrix}
= \ds\frac{1}{24}\begin{bmatrix}20&8&-4\\-6&0&6\end{bmatrix}.
$$
We can now solve both problems rapidly by multiplying $W$ and $\vec b$.
\begin{enumerate}
	\item The $y$ values are $2,1,3$, so we compute
$$\frac{1}{24}\begin{bmatrix}20&8&-4\\-6&0&6\end{bmatrix} \begin{bmatrix}2\\1\\3\end{bmatrix}
= \frac{1}{24}\begin{bmatrix}36\\6\end{bmatrix}
$$ which means that our line is (after simplifying fractions) $y=\frac{3}{2}+\frac{1}{4}x$.
\marginpar{
  \begin{tikzpicture}
    \begin{axis}[ footnotesize, xmin=-1, xmax=5, axis equal =true]
      % use TeX as calculator: 
      \addplot+[only marks] coordinates { (0,2) (2,1) (4,3)};
      \addplot[mark=none] {3/2+1/4*x};
   \end{axis}
  \end{tikzpicture}
}%
	\item The $y$ values are $6,3,-1$, so we compute
$$\frac{1}{24}\begin{bmatrix}20&8&-4\\-6&0&6\end{bmatrix} \begin{bmatrix}6\\3\\-1\end{bmatrix}
= \frac{1}{24}\begin{bmatrix}148\\-42\end{bmatrix}
$$ which means that our line is (after simplifying fractions) $y=\frac{37}{6}-\frac{7}{4}x$.
\marginpar{
  \begin{tikzpicture}
    \begin{axis}[ footnotesize, xmin=-1, xmax=5, axis equal =true]
      % use TeX as calculator: 
      \addplot+[only marks] coordinates { (0,6) (2,3) (4,-1)};
      \addplot[mark=none] {37/6 - 7/4*x};
   \end{axis}
  \end{tikzpicture}
}%
\end{enumerate}
\end{example}

Least squares regression is not limited to just finding a best fit line.  We can use the same ideas to find a best fitting parabola through many points.  To do this, we would start by assuming the data fit a parabola $y=a_0+a_1x+a_2x^2$, plug in the $x$ and $y$ values to obtain a linear system with 3 unknowns, write the system in matrix form (the columns of the matrix would involve ones, $x$ values, and $x^2$ values), multiply both sides by the transpose to obtain a system that was not overdetermined (3 by 3), and then solve the system.  Most spreadsheet programs have this feature built in for any size polynomial you choose.


\section{Vector Spaces}
\label{sec:vector-spaces-why}

To understand why we need to use the transpose of $A$ when doing regression, we need to introduce some of the most fundamental, powerful, and far-reaching ideas in linear algebra: vector spaces.  We will study these ideas more deeply throughout the semester.
 
In this section, we will define vector spaces and look at particular examples like the column space and null space of a matrix.  We will find that the solution to the linear regression problem is very naturally phrased using this language.  Along the way, we will obtain geometric interpretations of these ideas in preparation for a more general approach to vectors which is coming in the next chapter.

\subsection{The Vector Space ${\RR}^n$}

We have already been using 2D and 3D vectors quite a bit prior to now.  The symbol $\RR^n$ represents the set of all vectors in $n$-dimensional space.  What does the word dimension really mean? We'll answer that now by looking at an example.

\begin{example}
Recall that the span of a set of vectors is the set of all possible linear combinations of those vectors.  So the span of the vector $(2,1)$ in $\RR^2$ is the set of all vectors of the form $c(2,1)=(2c,c)$, which represents a line through the origin with slope $1/2$.  Since $(0,1)$ is not a multiple of $(2,1)$, the vector $(0,1)$ is not in the span of $(2,1)$ (i.e., $(0,1)$ does not lie on the line $y=\frac{1}{2}x$).  In other words, the set $\{(2,1),(0,1)\}$ is linearly independent (neither vector is in the span of the other).  The span of $\{(2,1),(0,1)\}$ is larger than the line---it is the entire plane. Every other vector in the plane is a linear combination of these two vectors since they form a linearly independent set. You can check this by trying to find the linear combination to equal an arbitrary vector $(x,y)$:
\begin{equation*}
\begin{bmatrix}
\cl{2\\1}&
\cl{0\\1}
\end{bmatrix}
\begin{bmatrix}c_1\\c_2\end{bmatrix}
=\begin{bmatrix}x\\y\end{bmatrix}
\xrightarrow{\text{augmented matrix}}
\begin{bmatrix}[cc|c]
\cl{2\\1}&
\cl{0\\1}&
\cl{x\\y}
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[cc|c]
\cl{1\\0}&
\cl{0\\1}&
\cl{\frac{x}{2}\\{y-\frac{x}{2}}}
\end{bmatrix}.
\end{equation*}
So, for example, the vector $(x,y)=(3,5)$ is the linear combination $\frac{x}{2}(2,1)+(y-\frac{x}{2})(0,1)=\frac{3}{2}(2,1)+(5-\frac{3}{2})(0,1)$.
Notice that since the first two columns are always pivot columns (since the two vectors form a linearly independent set), the system will always have a single solution. We call the scalars in the linear combination ($\frac{x}{2}$ and $y-\frac{x}{2}$) the \define{coordinates} of the vector relative to the basis $\{(2,1),\, (0,1)\}$. For example, the coordinates of $(3,5)$ relative to the basis $\{(2,1),\, (0,1)\}$ are $\frac{3}{2}$ and $5-\frac{3}{2}$.  A basis gives us a way of writing any vector by writing the coordinates.

Here is the crucial point about dimension: because we were able to obtain the entire plane as the span of \emph{two} linearly independent vectors, we say the dimension of $\RR^2$ is \emph{two}. 

Notice that the dimension does not depend on the particular two vectors I chose.  The only requirement was that the two vectors form a linearly independent set.  Then the first two columns in the above rref will always be pivot columns, so I will always be able to write any vector in the plane as a linear combination of my two linearly independent vectors.  We call a set of two linearly independent vectors, like $\{(2,1), (0,1)\}$, a \define{basis} for $\RR^2$.
\end{example}

\marginpar{The dimension of a vector space is the number of vectors in a basis. }%
The \define{dimension} of a vector space (like $\RR^2$) is the number of linearly independent vectors needed to span the vector space.  A basis for a vector space is a set of vectors that are:
\begin{itemize}
\item linearly independent and
\item span the vector space.
\end{itemize}
If a vector space has dimension $n$, then any $n$ linearly independent vectors will be a basis for the vector space.

For $\RR^n$, the \definemargin{standard basis vectors} are 
$$\vec e_1=(1,0,0,\ldots,0),\,
\vec e_2=(0,1,0,\ldots,0),\,\ldots,\,
\vec e_n=(0,0,0,\ldots,1).$$ 
Every other vector in $\RR^n$ is a linear combination of these standard basis vectors.  If not specified otherwise, we assume that any coordinates are relative to this standard basis.  We will find that using a different basis for our coordinates can simplify various problems.  For example, we'll often use eigenvectors as some of our basis vectors.

 

\subsection{Vector Subspaces of ${\RR}^n$}

The span of the vector (1,2,0) can be represented as a line through the origin in 3D.  The span of the vectors $\{(1,2,0), (0,0,1)\}$ represents a plane through the origin.  These spans are examples of vector spaces.  

A set of vectors $V$ from $\RR^n$ is called a \definemargin{vector subspace} of $\RR^n$ if any linear combination of vectors in $V$ is also in $V$.  We can break this definition down into two parts.  The set of vectors $V$ is a vector subspace of $\RR^n$ if:
\begin{enumerate}
	\item The sum of any two vectors in the set is still in the set. In notation, we write for any $\vec u,\vec v\in V$ the sum $\vec u+\vec v\in V$.  We say ``$V$ is closed under addition.''
	\item Any scalar multiple of a vector is still in the set. In notation, we write for any $\vec v\in V$ and $c\in \RR$, the vector $c\vec v\in V$.  We say ``$V$ is closed under scalar multiplication.''
\end{enumerate}

The span of a set of vectors is always a vector subspace. The simplest way to show that a set of vectors is a subspace is to show that it is a span of some vectors.

A basis of vectors for a subspace $V$ is a set of linearly independent vectors whose span is the set $V$.  The dimension of a subspace is the number of vectors in a basis. Lines through the origin are one-dimensional subspaces, planes through the origin are two-dimensional subspaces, and so on.

\begin{example}\label{RR subspace examples}
Here are three examples of vector subspaces.
\begin{enumerate}
	\item 
The set of vectors $V=\{(2c,3c)\st \text{where $c$ is any real number}\}$ is a vector subspace of $\RR^2$. It represents a line through the origin.  A basis for $V$ is $\{(2,3)\}$, since every vector in the subspace is a scalar multiple of $(2,3)$.  Since there is one vector in the basis, $V$ is one-dimensional.
  \item
The set of vectors $V=\{(2c,c+d,4d)\st c,d\in \RR\}$ is a two-dimensional vector subspace of $\RR^3$. It represents a plane through the origin. We can rewrite any vector in $V$ in the form $c(2,1,0)+d(0,1,4)$, so $V=\vspan\{(2,1,0),\, (0,1,4)\}$.  Since these two vectors are linearly independent, the set $\{(2,1,0)\, (0,1,4)\}$ is a basis for the subspace, and the space is two-dimensional.
\item
The set of vectors $V=\{(c+2e,2c+4e,d-2e)\st c,d,e\in \RR\}$ is a two-dimensional vector subspace of $\RR^3$. You might first think this subspace is three-dimensional because you can choose 3 different numbers ($c$, $d$, and $e$) and we can write any vector in the form $c(1,2,0)+d(0,0,1)+e(2,4,-2)$.  However, the three vectors are linearly dependent.  We can see this from the rref:
\begin{equation*}
\begin{bmatrix}
\cl{1\\2\\0}&
\cl{0\\0\\1}&
\cl{2\\4\\-2}
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
\cl{1\\0\\0}&
\cl{0\\1\\0}&
\cl{2\\-2\\0}
\end{bmatrix}.
\end{equation*}
Because the third column is not a pivot column, the third vector depends on the first two vectors.  Since the first two columns are pivot columns, the first two vectors form a linearly independent set, so a basis for $V$ is simply $\{(1,2,0),(0,0,1)\}$.  That is why the space is actually two-dimensional (it is a plane through the origin).
\end{enumerate}
\end{example}
\begin{example}\label{RR subspace nonexamples}

Here are three examples of sets that are \emph{NOT} vector subspaces.
\begin{enumerate}
	\item The set of vectors on the positive $x$-axis, $V=\{(a,0)\st a\geq0\}$, is not a vector subspace because if you multiply vector in $V$ by $-1$, the result is not in $V$.
	\item The set of vectors in $\RR^2$ whose magnitude is less than one (i.e., any vector from the origin to a point inside the unit circle) is not a vector subspace.  One reason why is that $(1/2,0)$ is in the set, but $4(1/2,0)=(2,0)$ is outside the circle and not in the set.  
	\item The set of vectors in $\RR^2$ which are on either the $x$ or $y$-axis is not a vector subspace. For example, both $(1,0)$ and $(0,1)$ are in the set, but the sum $(1,0)+(0,1) = (1,1)$ is not on either axis, so is not in set.
\end{enumerate}
\end{example}

Now let's look at some of the most common vector subspaces that come up in practice.

\subsubsection{The column and row space of a matrix}
Remember that a matrix can be viewed as a collection of column vectors or as a collection of row vectors.  The span of the columns of a matrix is called the \definemargin{column space} of the matrix, denoted $\col(A)$.  The span of the rows of the matrix is called the \definemargin{row space} of the matrix, denoted $\row(A)$.  The reduced row echelon form of a matrix tells us how to find a basis for column space and how to find a basis for the row space.  


\begin{example}\label{colspace1ex}
Let's find a basis for the column space of
$$A=\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
\cl{1\\0\\0}
&\cl{0\\1\\0}
&\cl{-1\\2\\0}
\end{bmatrix}.
$$
Of course, every vector in the column space is already a linear combination of the three column vectors (by definition, since the column space is the span of the columns).  If the columns are linearly independent, then they would form a basis for the column space.  However, from the reduced row echelon form, we see that the third column is a linear combination of the first two. A basis for the column space is $\{(1,2,0),\,(2,0,3)\}$ (i.e., the pivot columns). 
The coordinates of $(3,-2,6)$ relative to this basis are $-1$ and $2$.  In other words, we can write $(3,-2,6)$ as the linear combination 
 $$\begin{bmatrix}3\\-2\\6\end{bmatrix}
=-1\begin{bmatrix}1\\2\\0\end{bmatrix}+2\begin{bmatrix}2\\0\\3\end{bmatrix} 
=\begin{bmatrix}\cl{1\\2\\0}&\cl{2\\0\\3}\end{bmatrix}\begin{bmatrix}-1\\2\end{bmatrix} .$$ 
\marginpar{
\includegraphics[width=\marginparwidth]{Applications/support/colspace1}

Each column of a matrix is a linear combination of the pivot columns.  The coordinates of each column vector are the numbers in the corresponding column of the rref (excluding zero rows).
}
We can write all three columns of the matrix in terms of the basis vectors as 
\begin{align*}
A=\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix}
&=
\begin{bmatrix}
\begin{bmatrix}\cl{1\\2\\0}&\cl{2\\0\\3}\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}&
\begin{bmatrix}\cl{1\\2\\0}&\cl{2\\0\\3}\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}&
\begin{bmatrix}\cl{1\\2\\0}&\cl{2\\0\\3}\end{bmatrix}\begin{bmatrix}-1\\2\end{bmatrix}
\end{bmatrix}
\\
&=
\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
\end{bmatrix}
\begin{bmatrix}
\cl{1\\0}
&\cl{0\\1}
&\cl{-1\\2}
\end{bmatrix}.
\end{align*}
\end{example}

We see from the example that we can write any matrix as the product of its pivot columns and the nonzero rows of its rref. We can factor any matrix $A$ as $A=CR$, where $C$ is the matrix of pivot columns of $A$ and $R$ is the matrix whose rows are the nonzero rows from $\rref(A)$.

\begin{example}\label{ex:row-space}
Let's find a basis for the row space of the same matrix, 
$$A=\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
\cl{1\\0\\0}
&\cl{0\\1\\0}
&\cl{-1\\2\\0}
\end{bmatrix}.
$$
We will see that a basis is the nonzero rows of the rref. Using $A=CR$ as above, and remembering that multiplication can be thought of as linear combinations of rows, we can write  
\begin{align*}
A
=
\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix}
=
\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
\end{bmatrix}
\begin{bmatrix}
\cl{1\\0}
&\cl{0\\1}
&\cl{-1\\2}
\end{bmatrix}
=
\begin{bmatrix}
1\begin{bmatrix}1&0&-1\end{bmatrix} + 2 \begin{bmatrix}0&1&2\end{bmatrix}\\
2\begin{bmatrix}1&0&-1\end{bmatrix} + 0 \begin{bmatrix}0&1&2\end{bmatrix}\\
0\begin{bmatrix}1&0&-1\end{bmatrix} + 3 \begin{bmatrix}0&1&2\end{bmatrix}
\end{bmatrix}
.
\end{align*}

This shows us that every row of the original matrix is a linear combination of the nonzero rows of rref. The row space is the span of the rows, and since the rows of $A$ depend on the nonzero rows of rref, we can span the row space using these nonzero rows. Since the nonzero rows of the rref are linearly independent (placing these rows into columns and reducing won't change the pivots), we know that the nonzero rows of rref form a basis for the row space.  
\marginpar{
\includegraphics[width=\marginparwidth]{Applications/support/rowspace2}

Each row is a linear combination of the nonzero rows of rref.  The coordinates of each row are found in the pivot columns.
}\end{example}

Since the number of pivots (the rank of the matrix) equals the number of nonzero rows in the rref, we can see that the size of the basis for the column space and the size of the basis for the row space are equal.  Therefore the dimensions of the column space and the row space are equal (and are equal to the rank of the matrix).

Let's summarize what we learned in the previous examples.
\begin{enumerate}
	\item The pivot columns are a basis for the column space. 
	\item The nonzero rows of the rref are a basis for the row space.
	\item Every matrix can be decomposed as $A=CR$, where $C$ is a matrix of the pivot columns and $R$ is the nonzero rows of the rref.
	\item The dimension of the column space equals the dimension of the row space, which equals the rank of the matrix.
\end{enumerate}

The transpose of $A$ interchanges the rows and columns, so the row space of $A^T$ is the same as the column space of $A$, and the column space of $A^T$ is the same as the row space of $A$.
 
\begin{example}\label{colspace2ex}
Let's use the transpose to find different bases for the column space and row space of the same matrix from the previous examples:  
$$
A=
\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix},\quad
A^T
=
\begin{bmatrix}
 1 & 2 & 0 \\
 2 & 0 & 3 \\
 3 & -2 & 6
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
 1 & 0 & {3}/{2} \\
 0 & 1 & -{3}/{4} \\
 0 & 0 & 0
\end{bmatrix}.
$$
\marginpar{Recall that the coordinates of a vector relative to a basis are the scalars you need to recreate the vector using a linear combination of the basis vectors. Hence the coordinates of $(0,3,6)$ relative to the basis $\{(1,2,3), (2,0,-2)\}$ are $(3/2,-3/4)$ since 
$$\begin{bmatrix}0\\3\\6\end{bmatrix}
=
\frac{3}{2}\begin{bmatrix}1\\2\\3\end{bmatrix}
-
\frac{3}{4}\begin{bmatrix}2\\0\\-2\end{bmatrix}
$$.}%
The set of pivot columns of $A^T$, $\{(1,2,3),\, (2,0,-2)\}$, is a basis for the column space of $A^T$ and the row space of $A$.
The coordinates of the third column of $A^T$ (the third row of $A$), $(0,3,6)$, relative to this basis are $(3/2,-3/4)$. 

The nonzero rows of the rref of $A^T$, namely $\{(1,0,3/2),\, (0,1,-3/4)\}$ are a basis for the row space of $A^T$ and the column space of $A$.  Every column of $A$ can be written as a linear combination of these two vectors. The coordinates of $(1,2,0)$ relative to this basis are $(1,2)$. The coordinates of $(2,0,3)$ are $(2,0)$. The coordinates of $(3,-2,6)$ are $(3,-2)$.
\end{example}

In the last few examples, we have two different ways to obtain a basis for the column space and row space of a matrix. Table~\ref{column and row space table} provides graphs of all 4 bases. You can either reduce $A$ or $A^T$, and use the pivot columns and/or nonzero rows of rref to obtain a basis. Which basis is preferred?  The short answer is ``both.''  Each basis has a different use.  We'll revisit this topic more later.

\begin{table}

\begin{tabular}{ccc}
\multicolumn{3}{c}{
Visualizing two different bases for the column and row space. 
}
\\\hline
\multicolumn{3}{c}{
$
A=
\begin{bmatrix}
\cl{1\\2\\0}
&\cl{2\\0\\3}
&\cl{3\\-2\\6}
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
\cl{1\\0\\0}
&\cl{0\\1\\0}
&\cl{-1\\2\\0}
\end{bmatrix}
$}
\\ \\
\multicolumn{3}{c}{
$
A^T
=
\begin{bmatrix}
 1 & 2 & 0 \\
 2 & 0 & 3 \\
 3 & -2 & 6
\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}
 1 & 0 & {3}/{2} \\
 0 & 1 & -{3}/{4} \\
 0 & 0 & 0
\end{bmatrix}
$
}
\\ \\
\hline\hline \multicolumn{3}{c}{Bases for the column space of $A$, $\col(A)$}\\
\hline Using Pivot Columns of $A$ & Using nonzero rows of rref$(A^T)$ & Both\\ \\
\includegraphics[height=2in]{Applications/support/colspace1}
&\includegraphics[height=2in]{Applications/support/colspace2}
&\includegraphics[height=2in]{Applications/support/colspace3}
\\ \\
\hline\hline \multicolumn{3}{c}{Bases for the row space of $A$, $\row(A)$}\\
\hline Using Pivot Columns of $A^T$ & Using nonzero rows of rref$(A)$ & Both\\ \\
\includegraphics[height=2in]{Applications/support/rowspace1}
&\includegraphics[height=2in]{Applications/support/rowspace2}
&\includegraphics[height=2in]{Applications/support/rowspace3}
\end{tabular}

\caption{\label{column and row space table} In examples \ref{colspace1ex}, \ref{ex:row-space}, and \ref{colspace2ex}, we found two different bases for the column and row space. This table shows graphs to help us visualize the differences between these bases.  In all the graphs, the blue vectors represent columns or rows in the matrix and the red vectors represent the vectors in the basis.  
The top row of graphs shows us visualizations of column space where (1) we use the pivot columns to create our basis, (2) we use the nonzero rows of the rref of $A^T$, and (3) both bases are drawn on top of each other.
The bottom row of graphs repeats this visualization for the row space.}
\end{table}

\subsubsection{The null space of a matrix}
The column and row spaces provide two examples of vector
subspaces. These two spaces are defined as the span of a set of
vectors, hence are automatically closed under addition and scalar
multiplication. We'll now explore another set of vectors, called the
null space or kernel of a matrix, where it is not immediately obvious that the set is closed under addition and scalar multiplication.

The \define{null space} (or \define{kernel})
\marginpar{null space=$\nullspace(A)$=$\{\vec x \st A\vec x = \vec 0\}$}%
of a matrix $A$ is the set of vectors $\vec x$ that satisfy the equation $A\vec x=\vec 0$. Notice that the zero vector is always in this set. If there are no other vectors in this set, then we say that null space is the trivial vector space and has dimension zero.  

The null space is closed under addition and scalar multiplication.  If both $\vec x$ and $\vec y$ are in the null space, then $A\vec x=\vec 0$ and $A\vec y=\vec 0$. The sum $\vec x+\vec y$ satisfies 
\begin{align*}
A(\vec x+\vec y)
&= A\vec x+A\vec y &\text{(distribute)}\\
&= \vec 0 +\vec 0 = \vec 0 &(A\vec x = \vec 0 =A\vec y)\\
\end{align*}
This shows that $\vec x+\vec y$ is also in the null space.  
To show that the null space is closed under scalar multiplication, we observe that if $\vec x$ is in the null space and $c$ is any real number, then $$A(c\vec x) = cA\vec x = c\vec 0 = \vec 0,$$
which shows that the null space is closed under scalar multiplication.

We have already seen the null space. Finding eigenvectors requires that we solve $(A-\lambda I)\vec x = 0$, so eigenvectors come from the null space of $A-\lambda I$.  When we compute the null space of $A-\lambda I$, we call it the \define{eigenspace} of $A$ for eigenvalue $\lambda$.

\begin{example}
Let's redo example \ref{eigenvalueexample3} related to eigenvectors, but this time use the vocabulary of null spaces.  
The matrix 
$A=\begin{bmatrix}2&1&4\\ 1&2&4\\ 0&0&1\end{bmatrix}$ has eigenvalues $1,1,3$. 
When $\lambda=1$, we compute $A-\lambda I =\begin{bmatrix}1&1&4\\ 1&1&4\\ 0&0&0\end{bmatrix} $. To find the null space, we solve $(A-\lambda I )\vec x=0$. Row reduction (after augmenting the matrix) gives us the rref $\begin{bmatrix}[ccc|c]1&1&4&0\\ 0&0&0&0\\ 0&0&0&0\end{bmatrix}$, which shows we have two free variables. The solution is $\begin{bmatrix} x_1\\x_2\\ x_3\end{bmatrix} = x_2\begin{bmatrix} -1\\1\\0\end{bmatrix}+x_3\begin{bmatrix} -4\\0\\1\end{bmatrix} $. The null space is this entire solution set (called the eigenspace corresponding to $\lambda = 1$), and is a vector subspace of dimension 2. A basis for the null space is $\{(-1,1,0),\,(-4,0,1)\}$.
Every nonzero vector in this null space is an eigenvector of $A$ with eigenvalue 1.  A similar computation (computing the null space for $A-3I$) shows the eigenspace for $\lambda = 3$ is a one-dimensional vector space with basis $\{(1,1,0)\}$. Example \ref{eigenvalueexample3} has all the details.
\end{example}



\subsection{Why does regression require the transpose?}
We finish this unit with a brief explanation of why we used the transpose to solve the least square regression problem.  We will use the column space of $A$ and the null space of $A^T$. We'll also focus on a specific example in 3D so we can draw pictures.  Later,  we will revisit this idea and develop everything in full generality along with a more powerful vocabulary and theory.  Until then, we'll stick to a visual example.\note{put in a reference to the right chapter}

\marginpar{The two vectors $(1,1,1)$ and $(-2,3,1)$ are orthogonal because their dot product is $-2+3-1=0$.}%
Before getting started, recall that the dot product of two vectors is 0 if and only if the vectors meet at a 90 degree angle. When this occurs, we say that the vectors are orthogonal.
How do you find all the vectors that are orthogonal to a set of vectors $V$? The answer is ``Place all the vectors into the columns of $A$, and then find the null space of $A^T$.'' This null space is called the \define{orthogonal complement} of the set $V$. 
\marginpar{The orthogonal complement to a vector space $V$ is the set of vectors that are orthogonal to every vector in the space.  

The orthogonal complement of the column space of $A$ is the null space of $A^T$.}%

\begin{example}
Let's find all vectors that are orthogonal to $\vec v = (1,2,-3)$.  In other words, we want all vectors $\vec u = (u_1,u_2,u_3)$ such that 
$$
0=(1,2,-3)\cdot(u_1,u_2,u_3) 
=
\begin{bmatrix}1&2&-3\end{bmatrix}
\begin{bmatrix}u_1\\u_2\\u_3\end{bmatrix}
=\vec v^T \vec u
$$
(where $\vec v^T$ is the row matrix with the single row $\vec v$).  This is the same problem as finding the null space of the matrix $v^T=\begin{bmatrix}1&2&-3\end{bmatrix}$. Since the free variables are $u_2$ and $u_3$, we have the solution 
$$
\begin{bmatrix}
u_1\\u_2\\u_3
\end{bmatrix}
=
\begin{bmatrix}
-2u_2+3u_3\\u_2\\u_3
\end{bmatrix}
=u_2
\begin{bmatrix}
-2\\1\\0
\end{bmatrix}
+u_3\begin{bmatrix}
3\\0\\1
\end{bmatrix}
.$$
The set of vectors that are orthogonal to $\vec v$ is a vector space of dimension 2 with basis $\{(-2,1,0),(3,0,1)\}$. This is a plane passing through the origin.
\end{example}

If you are given a set of vectors $\vec v_1,\vec v_2$, how you do find all the vectors that are orthogonal to both?  
If you let $A = [\vec v_1\ \vec v_2]$ (columns of $A$ are the vectors), then a vector $\vec x$ is orthogonal to both $\vec v_1$ and $\vec v_2$ if $A^T\vec x=\vec 0$.
Hence the null space of the transpose of $A$ is the set of vectors that are orthogonal to the columns of $A$.

We're now ready to understand linear regression.


\begin{example}
Recall example \ref{regression1ex}, in which we found the line closest
to passing through the three points $(0,1)$, $(2,4)$, and $(4,5)$.  

In order to find the closest line to several points, the first question is, ``Is there a line that passes through all three points?''  If there is a line $y=a_0+a_1x$ that passes through all of the points, then we have a system of equations
\begin{equation*}
\begin{matrix}a_0=1\\a_0+2a_1=4\\a_0+4a_1=5\end{matrix}
\xrightarrow{\text{augmented matrix}}
\begin{bmatrix}[cc|c]1&0&1\\1&2&4\\1&4&5\end{bmatrix}
\xrightarrow{\text{matrix eqn}}
\begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}
\begin{bmatrix}a_0\\a_1\end{bmatrix}
=\begin{bmatrix}1\\4\\5\end{bmatrix}.
\end{equation*}
Notice that the system can be written in matrix form $A\vec x = \vec b$, where $A$ contains a column of 1's and $x$-values, $\vec x$ is the vector of coefficients $a_i$, and $\vec b$ is a column of $y$-values.  
\marginpar{Recall that the system $A\vec x=b$ is consistent if $b$ is a linear combination of columns of $A$.}%
The line $y=a_0+a_1x$ passes through the points if there is a solution to $A\vec x=\vec b$ (i.e., the system of equations is consistent).  This will happen if $(1,4,5)$ is in the column space of $A$.  The question ``Is there a line that passes through all of the points?'' is equivalent to asking ``Is $\vec b$ in the column space of $A$?''

However, in this example, $A\vec x=\vec b$ is not consistent since the rref is
\begin{equation*}
\begin{bmatrix}[cc|c]1&0&1\\1&2&4\\1&4&5\end{bmatrix}
\xrightarrow{\rref}
\begin{bmatrix}[cc|c]1&0&0\\0&1&0\\0&0&1\end{bmatrix}.
\end{equation*}
So the answer is ``No, $\vec b$ is not in the column space of $A$.''  Since $\vec b$ is not in the column space of $A$, we ask for the next best thing: ``What vector in the column space of $A$ is closest to $\vec b$?''  In fact, if $\vec b$ is in the column space of $A$, then the answer to the last question is $\vec b$ itself.  So really, the second question is the question we want to answer.  

The key to linear regression is answering the question
\begin{quote}
  What vector $\vec w=A\vec x$ in the column space of $A$ is the closest vector to $\vec b$?
\end{quote}
If $\vec b$ is in the column space of $A$, then the answer is $\vec b$, the system of equation is consistent, we can find $a_0$ and $a_1$, and the line passes through all of the points.  If $\vec b$ is not in the column space of $A$, then we have to do more work.

\marginpar{ \begin{center} \begin{tikzpicture}[x={(0.3cm,0.7cm)},y={(1cm,-0.2cm)},z={(-.5cm,1cm)}]
      \coordinate (origin) at (0,0,0);
      \coordinate (u) at  (1,1,1);
      \coordinate (v) at  (0,2,4);
      \coordinate (b) at  (1,4,5);
      \coordinate (w) at  ($4/3*(u)+(v)$);
      \coordinate (bprime) at ($3*(b)-3*(w)$); % exaggerated b
      \coordinate (r) at ($(b)-(w)$);
    
      \fill[->,fill=lightgray] (origin) -- ($4/3*(u)$) -- (w) -- (v) -- cycle;
      \draw[->] (origin) -- (u);
      \draw[->] (origin) -- (v);
      \draw[->] (origin) -- node[below right, pos=0.9] {$\vec b$} (b) ;
      \draw[->] (origin) -- (u);
      \draw[->] (origin) -- node[left,pos=0.7] {$\vec w$} (w);
      \draw[->] (w) -- node[above right] {$\vec r$} (b);
      

      %right angle
      \draw[thin] ($0.95*(w)$) -- ($0.95*(w)+0.2*(r)$) -- ($(w)+0.2*(r)$);
      % coordinate axes
      %\draw[->,ultra thick] (origin) -- (1,0,0);
      %\draw[->,ultra thick] (origin) -- (0,1,0);
      %\draw[->,ultra thick] (origin) -- (0,0,1);
 \end{tikzpicture}
\end{center}%
%\marginpar{\includegraphics[width=\marginparwidth]{Applications/support/regressionpic1}

Because $\vec b$ is not in the column space of $A$, we find the vector $\vec w$ closest to $\vec b$ in the columns space of $A$.  The difference $\vec b-\vec w$ is a vector $\vec r$ that is orthogonal to the column space.}%
To be closest to $\vec b$, a vector $\vec r$ (the ``residual'' vector) with base at $\vec w$ and
head at $\vec b$ must meet the column space of $A$ (a plane) at a 90 degree angle.  So the vector $\vec r = \vec b-\vec w$ is orthogonal to every vector in the column space, or every column of $A$, hence is in the null space of $A^T$ (so $A^T\vec r=\vec 0$). Solving for $\vec w$ gives us $\vec w = \vec b-\vec r$.  Multiplying both sides on the left by $A^T$ and remembering $A\vec x = \vec w$ gives us the regression equation
$$A^TA\vec x=A^T\vec w
=A^T(\vec b-\vec r) 
= A^T\vec b - A^T\vec r 
= A^T\vec b - \vec 0 =
A^T\vec b.$$

Solving for $\vec x$, as before, gives us $\vec x = (a_0,a_1)=(4/3,1)$.
The line closest to the points was $y=\frac{4}{3} + x$. 


The vector $\vec w=A\vec x$ is in the plane spanned by the columns of $A$. Because we already know the solution, in this example we can compute the vector $\vec w$ as
$$
\vec w = A \vec x = \begin{bmatrix}1&0\\1&2\\1&4\end{bmatrix}\begin{bmatrix}4/3\\1\end{bmatrix} = \begin{bmatrix}4/3\\10/3\\16/3  \end{bmatrix}.
$$
We can also compute the residual vector $\vec r=\vec b - \vec w=(-1/3,2/3,-1/3)$, and check that $\vec w \cdot \vec r = (1/9)(-4+20-16)=0$.  The magnitude of the residual vector tells us how close $\vec b$ is to $\vec w$, which gives us an idea of how closely the line fits the points.  In this case, $|\vec r|=\sqrt{2/3}\approx 0.864$.

Note that the vector $\vec x$, $(4/3,1)$, is the vector of coordinates of $\vec w$ relative to the pivot columns of $A$ (here we used the pivot columns of $A$ for our basis).  In the picture in the margin above, the gray parallelogram (part of the plane that is the column space of $A$) was formed by stretching (1,1,1) by $4/3$ and (0,2,4) by $1$, illustrating the linear combination that gives $\vec w$.  

You can think of $\vec w$ as the projection of $\vec b$ onto the column space of $A$.  The solution to the least squares problem, $\vec x$, is the just the vector of coordinates of the projection of $\vec b$ onto the column space of $A$.
Regression is really a problem about projecting a vector onto a vector space, then writing a vector in coordinates relative to a specific basis.


% a pgfplots version of the regression vector picture
 % \begin{tikzpicture}
 %    \begin{axis}[ axis equal =true,xlabel=$x$,ylabel=$y$,view={-10}{30}]
 %      \coordinate (origin) at (axis cs:0,0,0);
 %      \coordinate (u) at  (axis cs:1,1,1);
 %      \coordinate (v) at  (axis cs:0,2,4);
 %      \coordinate (b) at  (axis cs:1,4,5);
 %      \coordinate (w) at  ($4/3*(u)+(v)$);
 %      \coordinate (bprime) at ($3*(b)-3*(w)$);
 %      \addplot3+[arrows=->,mark=none] coordinates {(0,0,0) (1,4,5)};
     
 %      \fill[->,fill=lightgray] (origin) -- ($4/3*(u)$) -- (w) -- (v) -- cycle;
 %      \draw[->] (origin) -- (u);
 %      \draw[->] (origin) -- (v);
 %      \draw[->] (origin) -- node[left, pos=0.9] {$\vec b$} (b) ;
 %      \draw[->] (origin) -- (u);
 %      \draw[->] (origin) -- (w);
 %      \draw[->] (w) -- node[above] {$\vec r$} (b);
      
 %  \end{axis}
 %  \end{tikzpicture}

\end{example}


\section{Summary}
We have used matrix multiplication in all 3 ways:
\begin{enumerate}
\item linear combinations of columns (transition matrices and regression)
\item row dot column (projections in regression)
\item linear combination of rows (electrical networks and curve fitting)
\end{enumerate}
We have seen how Gaussian elimination helps solve problems.  We have seen how the inverse and determinants (Cramer's rule) can rapidly help us find solutions.  We have used eigenvalues and eigenvectors to understand geometric properties like flow in vector fields and maxima and minima of surfaces, as well as find steady state solutions in stochastic processes.  This is a small sample of the beginning of the applications of linear algebra. We also started learning the vocabulary of vector spaces, finding bases and dimensions, which will be the key to extending what we have learned to many more places.  The next unit will help us learn to discover patterns and show us how to use definitions and theorems to explicitly state the patterns we find.  

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../linear-algebra"
%%% End: