% m211og58.tex - Review of Linear Independence
%  -p.3 added 2018
%  
\newcommand{\titlesize}{28pt}  % for title 
\input{m211oh.tex}
%
\newcommand{\vv}{\vec{v}}

%\begin{titlepage}
%\vspace*{-35pt}
\begin{center}\tcr{\rmH Review of Linear Independence} \end{center} 
%\vspace{-12pt}
\huge

\begin{description}  
\item[\tcr{Definition:}] A set of vectors \mc{\vv_1, \vv_2, \ldots, \vv_k\in \R^n} is 
called a \tcr{linear independent} set if
\begin{eqnarray}
&\tcb{c_1\vv_1 + \ldots + c_k\vv_k = \vec{0}},\; \tcb{c_1, \ldots,c_k\in\R}&  \label{eq1} \\
&\hspace*{5pt} \tcb{\Ra}\; \tcb{c_1=c_2= \ldots = c_k = 0.}& \nonumber
\end{eqnarray}  

\item[\tcr{Note:}] \tcg{Linear independence} can be checked by \tcr{row reduction}.
More precisely, if 
$$
 \tcb{A = (\vv_1|\vv_2| \ldots |v_k)}\; \mbox{is the associated \mc{n\times k} matrix,} 
$$
then condition \tcb{(\ref{eq1})} holds if and only if
\begin{equation}
\tcb{A\vec{w} = \vec{0}\; \Ra\; \vec{w} = \vec{0},\mbox{ for all } \vec{w}\in \R^k}
\label{eq2}
\end{equation}
because \mc{A(c_1,\ldots, c_k)^t = c_1\vv_1 + \ldots + c_k\vv_k}. By \tcg{row reduction},
\tcb{(\ref{eq2})} holds if and only if 
\begin{equation}
\tcb{\mbox{rank}(A)\, =\, k,}
\label{eq3}
\end{equation}
where, if \mc{R} is a \tcr{row echelon form} (REF) of \mc{A},
$$
\begin{array}{rcl}
\tcb{\mbox{rank}(A)} &\tcb{\stackrel{\mbox{\large defn}}{=} } & \tcb{\#}
\mbox{ of nonzero rows of \mc{R}} \\
& \tcb{=} & \tcb{\#}\mbox{ of leading $1$'s in \mc{R}.}  
\end{array}
$$
%Here \tcr{REF = row echelon form}.     
%\end{description}
%\end{titlepage}

%\begin{description}  
\item[\tcr{Refinement:}] As before, let  \mc{A = (\vv_1|\vv_2| \ldots |v_k)} be an 
\mc{n\times k} matrix, and let
\mc{R} be a REF of \mc{A}. Put
$$
\tcb{I = \{i :} \mbox{ column \mc{i} of \mc{R} contains a leading \mc{1}}\tcb{\}} 
$$ 
so that (by definition) \mc{\mbox{rank}(A) = \#I}.
%\end{description}  

\newpage

%\begin{description}  
\tcr{Then} we have:

\tcr{1)} the set \mc{\{\vv_i\}_{i\in I}} is a \tcg{linear independent} set;

\tcr{2)} the set  \mc{\{\vv_i\}_{i\in I}} \tcr{spans} the space 
\mc{V = \lb\vv_1,\ldots\vv_k\rb}.

Thus, \mc{\{\vv_i\}_{i\in I}} is a \tcr{basis} of \mc{V} and hence
$$
\tcb{\dim V = \mbox{rank}(A) = \#I.}
$$

\item[\tcr{Example.}] Find a basis of \mc{V = \lb\vv_1,\ldots,\vv_4\rb}, 
where \mc{\vv_1 = (1, 2, 3, 4, 5), \vv_2= (1, 2, 2, 2, 2),} \\
\mc{\vv_3 = (0, 0, 1, 2, 3), \vv_4= (1,1,1,1,1) \in \R^5.}
% w1 := [1, 2, 3, 4, 5],  w2 := [1, 2, 2, 2, 2], v0 := [0, 0, 1, 2, 3], w3 := [1,1,1,1,1]

\item[\tcr{Solution.}] Put \mc{A = (\vv_1|\vv_2|\vv_3|\vv_4)}. By row reduction we obtain
$$
\tcb{A =\left(\begin{array}{cccc} 
 1 & 1 & 0 & 1\\ 
 2 & 2 & 0 & 1\\
 3 & 2 & 1 & 1\\
 4 & 2 & 2 & 1\\
 5 & 2 & 3 & 1
\end{array}\right)
\leftrightarrow\left(\begin{array}{cccc} 
  1 & 1 & 0 & 1 \\
  0 & 1 & -1& 2 \\ 
  0 & 0 & 0 & 1 \\ 
  0 & 0 & 0 & 0 \\  
  0 & 0 & 0 & 0
 \end{array}\right) = R.}
$$
%matrix([[1, 1, 0, 1], [2, 2, 0, 1], [3, 2, 1, 1], [4, 2, 2, 1], [5, 2, 3, 1]])
%matrix([[1, 1, 0, 1], [0, -1, 1, -2], [0, 0, 0, -1], [0, 0, 0, 0], [0, 0, 0, 0]])
and so the leading \mc{1}'s of \mc{R} (REF) are in columns \mc{1, 2} and \mc{4}. 
Thus, \mc{I = \{1,2,4\}} 
and hence by \tcb{1), 2)}:
$$
 \tcb{\{\vv_1,\vv_2, \vv_4\}\quad \mbox{is a \tcg{basis} of \mc{V}.}}
$$
 In particular, 
\mc{\dim V = \mbox{rank}(A) = \#I = 3}, so \mc{V} is 3-dimensional.  
\newpage

\item[\tcr{Note:}] If \mc{n=k,} then the linear independence of the vectors 
 \mc{\vec{v}_1, \ldots, \vec{v}_n \in \R^n} is equivalent to several other properties
of the \mc{n\times n} matrix \mc{A = (\vec{v}_1|\cdots|\vv_n),}
as the following basic fact from Linear Algebra shows: 

\item[\tcr{Fact:}] If \mc{A} is an \mc{n\times n} matrix, then the following properties are equivalent: 

(i) \mc{A} is \tcr{invertible,} i.e., there is a matrix \mc{B} such that \mc{AB = BA = I.}

(ii) The columns of \mc{A} are linearly independent.

(iii) \mc{A\vec x = \vec0 \Ra \vec x = 0.}

(iv) \mc{A\vec x = \vec  y} has a solution \mc{\vec x} for every \mc{\vec y \in \R^n.}

(iv$'$) \mc{A\vec x = \vec  y} has a unique solution for every \mc{\vec y \in \R^n.}

(v) \tcb{rank$(A) = n$.}

(vi) \mc{\det(A)\ne0.} 

\tcr{Proof Sketch:} 

\tcb{(ii) $\Lra$ (iii) $\Lra$ (v):} See the above discussion.

\tcb{(i) $\Ra$ (iv)$'$ $\Ra$ (iv):} Take \mc{\vec{x} = B\vec{y}.} 

\tcb{(iv) $\Ra$ (i):} Take \mc{B = (\vv_1|\ldots|\vv_n)}, where \mc{A\vv_i = \vec{e}_i.}

\tcb{(i) $\Ra$ (vi):} \begin{minipage}[t]{13cm} 
Since \mc{\det(A)\det(B) = \det(AB) = \det(I) =1}, we have that \mc{\det(A)\ne0.}
\end{minipage}

\tcb{(vi) $\Ra$ (i):} Cofactor formula for \mc{B = A^{-1}.} 

\end{description}  

\end{document}                          