% Linear combinations were treated earlier in the text.
\begin{comment}

\textbf{Definition:} A vector $\vec{w}$ is said to be a linear combination of the vectors $\vec{v_1} , \vec{v_2} , \ldots , \vec{v_n}$ if there exist numbers $c_1 , c_2 , \ldots , c_n$ such that:
\[\vec{w} = c_1 \vec{v_1} + c_2\vec{v_2} + \ldots + c_n\vec{v_n}\]

\begin{example}
  Is $\vec{w} = (1,2,3)$ a linear combination of $\vec{v_1} = (1,1,1)$ , $\vec{v_2} = (0,1,2)$ and $\vec{v_3} = (1,0,1)?$

  \begin{align*}
    \vec{w} &= c_1\vec{v_1} + c_2\vec{v_2} + c_3\vec{v_3}\\
    (1,2,3) &= c_1(1,1,1) + c_2(0,1,2) + c_3(1,0,1)\\
    (1,2,3) &= (c_1 + c_3 , c_1 + c_2 , c_1 + 2c_2 + c_3)\\
    &\Rightarrow \begin{cases}
      c_1 + c_3 = 1\\
      c_1 + c_2 = 2\\
      c_1 + 2c_2 + c_3 = 3\\
    \end{cases}\\
    &\Rightarrow \begin{bmatrix}
    1&0&1\\1&1&0\\1&2&1
    \end{bmatrix}\begin{bmatrix}
      c_1\\c_2\\c_3
    \end{bmatrix} = \begin{bmatrix}
    1\\2\\3
    \end{bmatrix} &\Leftarrow \begin{bmatrix}
    \vec{v_1} & \vec{v_2} & \ldots & \vec{v_n}\\
    \downarrow & \downarrow & & \downarrow
    \end{bmatrix} \begin{bmatrix}
      c_1\\c_2\\\vdots\\c_n
    \end{bmatrix} = \begin{bmatrix}
    \vec{w}\\\downarrow
    \end{bmatrix}\\
    &\Rightarrow \begin{bmatrix}[ccc|c]
      1&0&1&1\\1&1&0&2\\1&2&1&3    
    \end{bmatrix}\\
  \rowop{R_2}{R_2 - R_1}\\
  \rowop{R_3}{R_3 - R_1}\\
  &\Rightarrow \begin{bmatrix}
  [ccc|c] 1&0&1&1\\0&1&-1&1\\0&2&0&2
  \end{bmatrix}\\
  \rowop{R_3}{\frac{1}{2}R_3}\\
  &\Rightarrow \begin{bmatrix}
  [ccc|c] 1&0&1&1\\0&1&-1&1\\0&1&0&1
  \end{bmatrix}\\
\rowop{R_3}{R_3 - R_2}\\
&\Rightarrow \begin{bmatrix}
[ccc|c] 1&0&1&1\\0&1&-1&1\\0&0&1&0
\end{bmatrix}\\
c_3 &= 0\\
c_2 - c_3 &= 1 \\
c_2 &= 1\\
c_1 + c_3 &= 1\\
c_1 &= 1
  \end{align*}
  Thus $\vec{w} = (1)\vec{v_1} + (1)\vec{v_2} + 0\vec{v_3}$ 
\end{example}

\begin{example}
  Is $\vec{w} = (1,1,1)$ a linear combination of $\vec{v_1} = (2,-1,3)$ and $\vec{v_2} = (1,1,2)$?
  \begin{align*}
    \vec{w} &= c_1\vec{v_1} + c_2\vec{v_2}\\
    &\Rightarrow \begin{bmatrix}
    \vec{v_1} & \vec{v_2}
    \end{bmatrix}\begin{bmatrix}
    c_1\\c_2
    \end{bmatrix} = \vec{w}\\
    &\Rightarrow \begin{bmatrix}
    2&1\\-1&1\\3&2
    \end{bmatrix}\begin{bmatrix}
    c_1\\c_2
    \end{bmatrix} = \begin{bmatrix}
    1\\1\\1
    \end{bmatrix}\\
    &\Rightarrow \begin{bmatrix}
    [cc|c] 2&1&1\\-1&1&1\\3&2&1
    \end{bmatrix}\\
    \rowswap{R_1}{R_2}\\
    &\Rightarrow \begin{bmatrix}
    [cc|c] -1&1&1\\2&1&1\\3&2&1
    \end{bmatrix}\\
    \rowop{R_2}{R_2 + 2R_1}\\
    R_3 \rightarrow R_3 + 3R_1\\
    &\Rightarrow \begin{bmatrix}[cc|c]
    -1&1&1\\0&3&3\\0&5&4
    \end{bmatrix}\\
    \rowop{R_2}{\frac{1}{3}R_2}\\
    &\Rightarrow \begin{bmatrix}
    [cc|c] -1&1&1\\0&1&1\\0&5&4
    \end{bmatrix}\\
    \rowop{R_3}{R_3 - 5R_2}\\
    &\Rightarrow \begin{bmatrix}
    [cc|c] -1&1&1\\0&1&1\\0&0&-1
    \end{bmatrix}
  \end{align*}
  There is no solution because of a contradiction. $\therefore \vec{w}$ cannot be written as a linear combination.
\end{example}
\end{comment}

\section{Subspaces of $\mathset{R}^n$}
As the name suggests, a subspace $S$ of $\mathset{R}^n$ is a set of vectors contained within $\mathset{R}^n$.  It inherits all the properties of $\mathset{R}^n$.  Additionally we require it be closed.
  
\definition{A non-empty subset $S$ of vectors from $\mathset{R}^n$ that is \textbf{closed} under vector addition and scalar multiplication is called a \textbf{subspace} of $\mathset{R}^n$. Closure means that the vectors $\lvec{u}+\lvec{v}$ and $c\lvec{u}$ are also in $S$ for any vectors $\lvec{u}$ and $\lvec{v}$ in $S$ and scalar $c$.}

\theorem{The zero vector $\lvec{0}_n$ is an element of $S$ for any subspace $S$ of $\mathset{R}^n$.}

\textbf{Proof:}
Since $S$ is non-empty let $\lvec{u}$ be a vector in $S$.  Then $(-1)\lvec{u}=-\lvec{u}$ is also in $S$ due to scalar closure and so $\lvec{u}+(-\lvec{u})=\lvec{u}-\lvec{u}=\lvec{0}$ lies in $S$ due to closure under addition.

Note that $S=\{\lvec{0}_n\}$ is a subspace of $\mathset{R}^n$.  Also $S=\mathset{R}^n$ itself is a subspace of $\mathset{R}^n$.  

\definition{A set of vectors $B=\{\lvec{u_1},\lvec{u_2},\ldots,\lvec{u_k}\}$ in subspace $S$ is said to \textbf{span} $S$ if every vector $\lvec{v}$ in $S$ can be written as a linear combination of vectors from $B$. That is, there exist scalars $c_1, \ldots, c_k$ such that
  \[\lvec{v}=c_1\lvec{u}_1+c_2\lvec{u}_2+\ldots+\lvec{u}_k\,,\]
for every $\lvec{v}$ in $S$\,.}

\begin{example}
  The standard basis $B=\{\lvec{e}_1,\ldots,\lvec{e_n}\}$ spans $\mathset{R}^n$.
\end{example}

Conversely we can define the span of a set of vectors.

\definition{Let $B=\{\lvec{u_1},\lvec{u_2},\ldots,\lvec{u_k}\}$ be a set of $k$ vectors from $\mathset{R}^n$.  Then the \textbf{span of the set}, denoted by $\lspanf{B}=\lspan\{\lvec{u_1},\lvec{u_2},\ldots,\lvec{u_k}\}$, is the set of all linear combinations of the vectors in the set, i.e. all vectors
\[\lvec{v}=c_1\lvec{u_1}+c_2\lvec{u_2}+\cdots+c_k\lvec{u}_k\]
where $c_i$ are scalars.}

Since clearly the sum of two such linear combinations will still be a linear combination and the scalar product of such a linear combination will also be so, we have the following non-trivial subspaces.

\theorem{The span of a set of vectors $B=\{\lvec{u}_1,\lvec{u}_2,\ldots,\lvec{u}_n\}$ from $\mathset{R}^n$, $\lspanf{B}$, is a subspace of~$\mathset{R}^n$.}

\begin{example}
  \label{example:line}%
  Let $\lvec{v}$ be a nonzero vector in $\mathset{R}^2$ or $\mathset{R}^3$ and let $t$ be a parameter.  Then the line through the origin given by the set
  \[L=\{\lvec{x}(t)=t\lvec{v}\ \text{such that}\ t\ \text{is in}\ \mathset{R}\}\]
  is a subspace of $\mathset{R}^2$ or $\mathset{R}^3$ respectively.
\end{example}

\begin{example}
  \label{example:plane}%
  Let $\lvec{u}$ and $\lvec{v}$ be two nonzero, noncollinear vectors in $\mathset{R}^3$ and let $s$ and $t$ be parameters.  Then the plane through the origin given by the set
  \[P=\{\lvec{x}(s,t)=s\lvec{u}+t\lvec{v}\ \text{such that}\ s\ \text{and}\ t\ \text{are in}\ \mathset{R}\}\]
  is a subspace of $\mathset{R}^3$.
\end{example}

So in the previous examples the sum of two vectors or the product of one of them by a scalar will remain in the subspace, line or plane, respectively.

As a final non-trivial subspace example consider the following.

\definition{If $L$ is a linear transformation from $\mathset{R}^n$ to $\mathset{R}^m$ then the \textbf{null space} or \textbf{kernel} of $L$ is the set of all vectors in $\mathset{R}^n$ satisfying $L(\lvec{u})=\lvec{0}_m$.}

If $L$ equals matrix transformation $L_A$ for matrix $A$ then it follows that the null space of $L$ is the set of solutions of the homogeneous linear system
\[A\lvec{x}=\lvec{0}\,.\]

\theorem{The null space of a linear transformation $L$ from $\mathset{R}^n$ to $\mathset{R}^m$ is a subspace of $\mathset{R}^n$.}

\textbf{Proof:}
Let $\lvec{u}$ and $\lvec{v}$ be vectors of $\mathset{R}^n$ in the null space of linear transformation $L$ and let $c$ be a scalar.  Then
\begin{align*}
  L(\lvec{u}+\lvec{v}) & = L(\lvec{u})+L(\lvec{v})=\lvec{0}+\lvec{0}=\lvec{0} \\
  L(c\lvec{u})&=cL(\lvec{u})=c\lvec{0}=\lvec{0}
\end{align*}

Thus $\lvec{u}+\lvec{v}$ and $c\lvec{u}$ will also lie in the null space of $L$ and it is therefore closed under addition and scalar multiplication and hence a subspace of $\mathset{R}^n$\,.

\section{Linear Independence}

We are often interested in finding the fewest number of vectors required to span a subspace $S$.  To that end we define the following concept.

\definition{A set $B= \{\lvec{v}_1 , \lvec{v}_2 , \ldots , \lvec{v}_n\}$ of vectors from $\mathset{R}^m$ is \textbf{linearly independent} if the vector equation 
\[c_1 \lvec{v}_1 + c_2 \lvec{v}_2 + \ldots + c_n \lvec{v}_n = \lvec{0}\]
has only the solution $c_i=0$ for $i=1,\ldots,n$\,.  Otherwise the set $B$ is called \textbf{linearly dependent}.}

Note the following:
\begin{itemize}
  \item A set of two or more vectors is linearly dependent if and only if one of them can be expressed as a linear combination of the others. 

  \item A linearly independent set of vectors cannot contain the zero vector as, assuming it is the first vector, $\lvec{v}_1=\lvec{0}$, then $c_1$ could be set to anything and all other scalars could be set to $0$ thereby providing a solution to the equation which was not identically zero.

  \item If we let $A$ be the matrix whose $i\textsuperscript{th}$ column is the vector $\lvec{v}_i$, so
    \[A=[\lvec{v}_1 \lvec{v}_2 \cdots \lvec{v}_n]\]
    then the previous vector equation is equivalent to a homogeneous system given by:
\[\begin{bmatrix}
\lvec{v}_1 & \lvec{v}_2 & \cdots & \lvec{v}_n
\end{bmatrix}\begin{bmatrix}
c_1\\c_2\\\vdots\\c_n
\end{bmatrix} = \begin{bmatrix}
0\\0\\\vdots\\0
\end{bmatrix}\]
or
\[A\lvec{c}=\lvec{0}\,.\]

If the system has the unique (trivial) solution $\lvec{c}=\lvec{0}$, then the set $B=\{\lvec{v}_1 , \lvec{v}_2 , \ldots , \lvec{v}_n\}$ is linearly independent. If this system has infinitely many solutions, then the set $B$ is linearly dependent.
\item If the matrix $A$ is square this is further simplified.  If $\det A\neq0$ then we have the unique (trivial) solution and the set is independent.  If $\det A=0$ then there are infinitely many solutions and the set is dependent.
\end{itemize}

\begin{example}
  Determine whether the given set of vectors is linearly dependent or independent.

  \begin{enumerate}
  \item $B=\{\lvec{v}_1,\lvec{v}_2\}$ where $\lvec{v}_1 = (1,1)$, $\lvec{v}_2=(-1,2)$\,.
    
    Solution:
    \begin{align*}
      c_1\lvec{v}_1 + c_2\lvec{v}_2 &= \lvec{0}\\
      \iff \begin{bmatrix*}[r]
      1&-1\\1&2
      \end{bmatrix*}\begin{bmatrix}
      c_1\\c_2
      \end{bmatrix} &= \begin{bmatrix}
      0\\0
      \end{bmatrix}\\
      A\lvec{c}&=\lvec{0}
    \end{align*}

\textbook{\newpage}    
    Solving the system $[A|\lvec{0}]$ directly we have:
      \[\begin{bmatrix}[rr|r] 1&-1&0\\1&2&0
      \end{bmatrix}\]
      \[\Downarrow\]
      \[\rowopmatrix{ \\\rowop{R_2}{R_2 - R_1}}{\begin{bmatrix}[rr|r] 1&-1&0\\0&3&0
      \end{bmatrix}}\ \Leftrightarrow\ \parbox{5em}{\begin{align*} c_1-c_2&=0 \\ 3c_2&=0 \end{align*}}\]
      Using back-substitution:
      \begin{itemize}
      \item $3c_2=0 \implies \boxed{c_2=0}$
      \item $c_1-c_2=0 \implies c_1-0=0 \implies \boxed{c_1=0}$
      \end{itemize}
    So $\lvec{c}=(0,0)$ is the only solution and therefore $B=\{ \lvec{v}_1 , \lvec{v}_2\}$ is a linearly independent set.
    Alternatively, since $A$ is square we can use the determinant:
    \[\det A = \begin{vmatrix*}[r] 1 & -3 \\ 0 & 3 \end{vmatrix*} =1(2) - (-1)(1) = 3 \neq 0\]
    which implies $B$ is a linearly independent set.
    
  \item $B=\{\lvec{v}_1,\lvec{v}_2,\lvec{v}_3\}$ where $\lvec{v}_1 = (1,1,-2)$, $\lvec{v}_2 = (2,5,-1)$, and $\lvec{v}_3 = (0,1,1)$\,.
    
    Solution:\\
We must consider the solutions $\lvec{c}=(c_1,c_2,c_3)$ for the following system:    
\begin{align*}
  c_1\lvec{v}_1 + c_2\lvec{v}_2 + c_3\lvec{v}_3 &= \lvec{0}\\
  \iff \begin{bmatrix*}[r]
  1&2&0\\1&5&1\\-2&-1&1
  \end{bmatrix*}\begin{bmatrix}
  c_1\\c_2\\c_3
  \end{bmatrix} &= \begin{bmatrix}
  0\\0\\0
  \end{bmatrix} \\
  A\lvec{c}&=0
\end{align*}
Expanding coefficient matrix $A$ along the first row, we have
\[\det A= \begin{vmatrix*}[r]
  1&2&0\\1&5&1\\-2&-1&1
  \end{vmatrix*} = (1)(+1)(5+1)+2(-1)(1+2)+0= 6 - 2(3)= 0\]
Therefore there are infinitely many solutions for $\lvec{c}=(c_1,c_2,c_3)$ and set $B=\{\lvec{v}_1 , \lvec{v}_2 , \lvec{v}_3\}$ is linearly dependent.

\item $B=\{\lvec{v}_1,\lvec{v}_2,\lvec{v}_3\}$ where $\lvec{v}_1 = (0,0,2,2)$, $\lvec{v}_2 = (3,3,0,0)$, and $\lvec{v}_3 = (1,1,0,-1)$\,.

  Solution:\\
\begin{align*}
  c_1\lvec{v}_1 + c_2\lvec{v}_2 + c_3\lvec{v}_3 & = \lvec{0}\\
  \iff \begin{bmatrix*}[r]
  0&3&1\\0&3&1\\2&0&0\\2&0&-1
  \end{bmatrix*}\begin{bmatrix*}
  c_1\\c_2\\c_3
  \end{bmatrix*} &= \begin{bmatrix*}
  0\\0\\0\\0
  \end{bmatrix*}\\
  A\lvec{c}&=\lvec{0}
  \end{align*}
Since $A$ is not square so solve the system using $[A|\lvec{0}]$\,:
\[\begin{bmatrix}[rrr|r] 0&3&1&0\\0&3&1&0\\2&0&0&0\\2&0&-1&0
\end{bmatrix}\hspace{2.7em}\]
\[\Downarrow\hspace{3em}\]
\begin{flalign*}&\rowopmatrix[15em]{\rowswap{R_1}{R_3}\\ \\ \\ }{\begin{bmatrix}[rrr|r]
      2&0&0&0\\0&3&1&0\\0&3&1&0\\2&0&-1&0
  \end{bmatrix}}&\end{flalign*}
\[\Downarrow\hspace{3em}\]
\begin{flalign*}&\rowopmatrix[15em]{\\ \\ \rowop{R_3}{R_3 - R_2}\\ \rowop{R_4}{R_4 - R_1}}{\begin{bmatrix}[rrr|r]
      2&0&0&0\\0&3&1&0\\0&0&0&0\\0&0&-1&0
  \end{bmatrix}}&\end{flalign*}
\[\Downarrow\hspace{3em}\]
\begin{flalign*}&\rowopmatrix[15em]{ \\ \\ \rowswap{R_3}{R_4} \\ }{\begin{bmatrix}[rrr|r] 2&0&0&0\\0&3&1&0\\0&0&-1&0\\0&0&0&0
      \end{bmatrix}}
 \ \Leftrightarrow\ \parbox{5em}{\begin{align*} 2c_1&=0 \\ 3c_2+c_3&=0 \\ -c_3&=0\\0&=0 \end{align*}}\hspace{10.5em}&\end{flalign*}
      Using back-substitution:
      \begin{itemize}
      \item $-c_3=0 \implies \boxed{c_3=0}$
      \item $3c_2+c_3=0 \implies 3c_2+0=0 \implies \boxed{c_2=0}$
      \item $2c_1=0 \implies \boxed{c_1=0}$
      \end{itemize}
Therefore the only solution is $(c_1,c_2,c_3)=\lvec{0}$ and $B=\{\lvec{v}_1 , \lvec{v}_2 , \lvec{v}_3\}$ is linearly independent.
  \end{enumerate}
\end{example}

\definition{Let $S$ be a subspace of $\mathset{R}^n$ then if $B=\{\lvec{u}_1,\lvec{u}_2,\ldots\lvec{u}_k\}$ is a linearly independent set of vectors that spans $S$, then $B$ is called a \textbf{basis} for $S$.}

\begin{example}
  The standard basis $B=\{\lvec{e}_1, \lvec{e}_2, \ldots, \lvec{e}_n\}$ is a basis for $\mathset{R}^n$.
\end{example}

\begin{example}
  The set $B=\{\lvec{v}\}$ where $\lvec{v}$ is a nonzero vector is a basis for the line $L$ in $\mathset{R}^2$ or $\mathset{R}^3$ given in Example~\ref{example:line}\,.
\end{example}

\begin{example}
  The set $B=\{\lvec{u}, \lvec{v}\}$ where $\lvec{u}$ and $\lvec{v}$ are nonzero, noncollinear vectors is a basis for the plane $P$ in $\mathset{R}^3$ given in Example~\ref{example:plane}\,.
\end{example}

Note the following:
\begin{itemize}
  \item A basis for $S$  is made up of the smallest number of vectors that will span $S$.
  \item While the vectors that make up a basis for $S$ are not unique, it can be shown that every basis must have the same number of elements.  This is called the \textbf{dimension} of $S$. So the line $L$ in $\mathset{R}^2$ or $\mathset{R}^3$ has dimension of 1, and the plane $P$ in $\mathset{R}^3$ has dimension of 2 as expected.
  \item If $\mathset{R}^n$ is equipped with the usual dot product, note that the vectors in the basis for a subspace $S$ need not be unit vectors nor do they need to be mutually orthogonal.  However it can be shown that given such a basis one can always construct a new basis that has these properties.  One such procedure is called the \textbf{Gram-Schmidt process}.  Such a basis is called an \textbf{orthonormal basis}.
\end{itemize}

%TODO Consider moving more examples of linear combinations earlier in the book.
% These have been commented out above.
%
% State as a theorem that the basic solutions arising from Gauss-Jordan elimination are linearly independent.  We can then refer to that when talking about bases of eigenspaces later.
%
% Add diagrams to the examples involving lines and planes through the origin
% as subspaces.
%
% Maybe talk about how to get a LI basis from a set of vectors that span a
% space.  This could be done in exercises.
