\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, December 05, 2019 22:40:49}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-10-02}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-10-02}
\author{Darij Grinberg}
\date{\today}
\maketitle

\section{Gaussian elimination (continued)}

\subsection{Solving linear systems: summary}

Reminder: \textquotedblleft system\textquotedblright\ means \textquotedblleft
system of linear equations\textquotedblright.

We now have a \textbf{method for solving systems} (\cite[Method 6.9]%
{Strickland}):

\textbf{(a)} Write down the augmented matrix corresponding to the system.

\textbf{(b)} Transform this matrix into RREF using row operations (ERO1, ERO2, ERO3).

\textbf{(c)} Transform this back into a system.

\textbf{(d)} Solve this system.

The reason why this works is that row operations do not change the set of solutions.

\begin{example}
Let us solve the system%
\[
\left\{
\begin{array}
[c]{c}%
2x+y+z=1\\
4x+2y+3z=-1\\
6x+3y-z=11
\end{array}
\right.  .
\]


Step \textbf{(a)}: The augmented matrix is%
\[
\left(
\begin{array}
[c]{cccc}%
2 & 1 & 1 & \mathbf{1}\\
4 & 2 & 3 & \mathbf{-1}\\
6 & 3 & -1 & \mathbf{11}%
\end{array}
\right)  .
\]


Step \textbf{(b)}: Bring this matrix into RREF:%
\begin{align*}
&  \left(
\begin{array}
[c]{cccc}%
\fbox{$2$} & 1 & 1 & 1\\
4 & 2 & 3 & -1\\
6 & 3 & -1 & 11
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }1/2}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2\\
4 & 2 & 3 & -1\\
6 & 3 & -1 & 11
\end{array}
\right) \\
&  \overset{\text{add }-4\cdot\text{row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2\\
0 & 0 & 1 & -3\\
6 & 3 & -1 & 11
\end{array}
\right) \\
&  \overset{\text{add }-6\cdot\text{row }1\text{ to row }3}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2\\
0 & 0 & 1 & -3\\
0 & 0 & -4 & 8
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & 1 & -3 & \\
0 & 0 & -4 & 8 &
\end{array}
\right) \\
&  \overset{\text{add }4\cdot\text{row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \\
0 & 0 & 0 & -4 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \leftarrow\text{frozen}\\
0 & 0 & 0 & -4 &
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1/4}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \text{\fbox{$1$}} &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & \leftarrow\text{frozen}%
\end{array}
\right) \\
&  \overset{\text{unfreeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{unfreeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -3 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{not an RREF!}\\
&  \overset{\text{add }3\cdot\text{row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & \\
0 & 0 & 0 & \text{\fbox{$1$}} &
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF}\\
&  \overset{\text{unfreeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 1/2 & 1/2\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \text{\fbox{$1$}}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{not an RREF!}\\
&  \overset{\text{add }-1/2\cdot\text{row }3\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 1/2 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \text{\fbox{$1$}}%
\end{array}
\right) \\
&  \overset{\text{add }-1/2\cdot\text{row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \text{\fbox{$1$}}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF.}%
\end{align*}


\textbf{(c)} This RREF $\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 1/2 & 0 & \mathbf{0}\\
0 & 0 & \fbox{$1$} & \mathbf{0}\\
0 & 0 & 0 & \text{\textbf{\fbox{$1$}}}%
\end{array}
\right)  $ corresponds to the system $\left\{
\begin{array}
[c]{c}%
x+\left(  1/2\right)  y=0\\
z=0\\
0=1
\end{array}
\right.  $.

\textbf{(d)} This system has no solutions.
\end{example}

This method is called \textbf{(systematic) Gaussian elimination}. The only
choice we have in the above formulation of this method is at the point where
we pick a leftmost nonzero entry. This is called \textbf{pivoting}, since the
entry we pick will be a pivot. There are several strategies to do this:

\begin{itemize}
\item Pick any nonzero entry among the options.

\item Pick the topmost nonzero entry among the options.

\item Pick a $1$ if possible, just so that you don't have to scale its row.

\item Pick an entry that is as large as possible, so that the scaling step
does not introduce too much numerical error. (This is a good thing to do when
the entries of your matrix are approximate.) $\leftarrow$ Numerical linear
algebra / scientific computing.
\end{itemize}

So we have some freedom in following the algorithm. Whatever we do, we end up
with an RREF, so we can solve the system. Better yet:

\begin{theorem}
Any matrix has \textbf{exactly one} RREF.

In other words: Any choice of row operations that brings $A$ into RREF
produces the exact same RREF.
\end{theorem}

We might prove this later.

\subsection{SageMath demo}

SageMath (short: Sage) is a computer algebra system that is particularly
suited for exact (i.e., non-approximate) computations. The easiest way to
access it (if your computations don't take too much time) is through
\url{https://sagecell.sagemath.org/} .

Let us define the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 4\\
2 & 5 & 7
\end{array}
\right)  $ in SageMath:

\texttt{A = Matrix(QQ, [[1, 0, 4], [2, 5, 7]])}

Here, the \textquotedblleft\texttt{QQ}\textquotedblright\ stands for the set
$\mathbb{Q}$ of rational numbers, and signifies that Sage should treat the
matrix as a matrix with rational entries. (Alternatively, you could use
\textquotedblleft\texttt{RR}\textquotedblright\ to get a matrix with real
entries; but this opens a whole new can of worms, because real numbers can
only be stored as approximate values on a computer, and linear algebra
algorithms can be very fragile against even minor errors.)

Note that the placement of the brackets matters! They mark where rows begin
and end. If you typed

\texttt{A = Matrix(QQ, [[1, 0], [4, 2], [5, 7]])}

instead, then you would obtain the matrix $\left(
\begin{array}
[c]{cc}%
1 & 0\\
4 & 2\\
5 & 7
\end{array}
\right)  $.

Now that you have defined \texttt{A}, try out:

\begin{itemize}
\item \texttt{A.echelon\_form()} $\leftarrow$ This computes the RREF of $A$.

\item \texttt{A.solve\_right(vector(QQ, [3, 7, 1]))} $\leftarrow$ This
computes \textbf{one} solution of the system $A\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
3\\
7\\
1
\end{array}
\right)  $. (Of course, \texttt{A} should be a matrix with $3$ columns here,
such as $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 4\\
2 & 5 & 7
\end{array}
\right)  $.)
\end{itemize}

Also useful:

\begin{itemize}
\item \texttt{A+B} $\leftarrow$ sum of two matrices \texttt{A} and \texttt{B}.

\item \texttt{A*B} $\leftarrow$ product of two matrices \texttt{A} and
\texttt{B}.

\item \texttt{MatrixSpace(QQ, 3, 5)(0)} $\leftarrow$ zero matrix $0_{3\times
5}$ with $3$ rows and $5$ columns.

\item \texttt{MatrixSpace(QQ, 3, 3)(1)} $\leftarrow$ identity matrix $I_{3}$
of size $3$.

\item \texttt{Matrix(QQ, [[1/(i+j) for j in range(1, 5)] for i in range(1,
3)])} $\leftarrow$ the matrix $\left(  \dfrac{1}{i+j}\right)  _{1\leq
i\leq4,\ 1\leq j\leq2}=\left(
\begin{array}
[c]{rrrr}%
\frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5}\\
\frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6}%
\end{array}
\right)  $. (Note that SageMath's \texttt{range(1, 5)} stands for the numbers
$1,2,3,4$ (not $1,2,3,4,5$); more generally, \texttt{range(a, b)} stands for
the numbers $a,a+1,\ldots,b-1$. Note also that the column index
(\textquotedblleft\texttt{for j in range(1, 5)}\textquotedblright) has to be
entered before the row index (\textquotedblleft\texttt{for i in range(1,
3)}\textquotedblright), since the input is meant to specify a list of lists.

\item \texttt{Matrix(QQ, [[floor(random()*200-100) for j in range(1, 5)] for i
in range(1, 3)])} $\leftarrow$ a matrix with random integer entries between
$-100$ and $99$; useful for experimentation.

\item \texttt{latex(A)} $\leftarrow$ a LaTeX representation of a matrix
\texttt{A}; helpful if you want to write homework solutions in LaTeX.
\end{itemize}

\subsection{Solving the \textquotedblleft generic\textquotedblright%
\ $2\times2$-system}

Consider the system%
\[
\left\{
\begin{array}
[c]{c}%
ax+by=c\\
a^{\prime}x+b^{\prime}y=c^{\prime}%
\end{array}
\right.
\]
in two variables $x,y$, where $a,b,c,a^{\prime},b^{\prime},c^{\prime}$ are
arbitrary constants. Can we solve it for $x$ and $y$ ?

We can try following the above method, and see what we get.

\textbf{(a)} The augmented matrix is%
\[
\left(
\begin{array}
[c]{ccc}%
a & b & \mathbf{c}\\
a^{\prime} & b^{\prime} & \mathbf{c}^{\prime}%
\end{array}
\right)  .
\]


\textbf{(b)} Transforming it into RREF:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{\textbf{Assume} that }a\neq0\text{.}\\
&  \overset{\text{scale row }1\text{ by }1/a}{\longrightarrow}\left(
\begin{array}
[c]{ccc}%
1 & b/a & c/a\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right) \\
&  \overset{\text{add }-a^{\prime}\cdot\text{row }1\text{ to row
}2}{\longrightarrow}\left(
\begin{array}
[c]{ccc}%
1 & b/a & c/a\\
0 & b^{\prime}-a^{\prime}b/a & c^{\prime}-a^{\prime}c/a
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
1 & b/a & c/a & \leftarrow\text{frozen}\\
0 & b^{\prime}-a^{\prime}b/a & c^{\prime}-a^{\prime}c/a &
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cccc}%
1 & b/a & c/a & \leftarrow\text{frozen}\\
0 & \left(  ab^{\prime}-a^{\prime}b\right)  /a & \left(  ac^{\prime}%
-a^{\prime}c\right)  /a &
\end{array}
\right) \\
&  \overset{\text{scale row }2\text{ by }a/\left(  ab^{\prime}-a^{\prime
}b\right)  }{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
1 & b/a & c/a & \leftarrow\text{frozen}\\
0 & 1 & \dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b} &
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we are assuming that }ab^{\prime
}-a^{\prime}b\neq0\right) \\
&  \underset{\text{(we treat this as one step, since it changes nothing)}%
}{\overset{\text{freeze and unfreeze row }1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & b/a & c/a & \leftarrow\text{frozen}\\
0 & 1 & \dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b} &
\end{array}
\right) \\
&  \overset{\text{unfreeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccc}%
1 & b/a & c/a\\
0 & 1 & \dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b}%
\end{array}
\right) \\
&  \overset{\text{add }-b/a\cdot\text{row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccc}%
1 & 0 & \dfrac{cb^{\prime}-bc^{\prime}}{ab^{\prime}-ba^{\prime}}\\
0 & 1 & \dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF.}%
\end{align*}


\textbf{(c)} Transform this into the system%
\[
\left\{
\begin{array}
[c]{c}%
x=\dfrac{cb^{\prime}-bc^{\prime}}{ab^{\prime}-ba^{\prime}}\\
y=\dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b}%
\end{array}
\right.  .
\]


\textbf{(d)} Obvious.

\textbf{Caveat:} We have assumed that $a\neq0$, and we have assumed that
$ab^{\prime}-ba^{\prime}\neq0$.

If $ab^{\prime}-ba^{\prime}=0$, then our above process looks different, and we
get a different RREF and a different answer.

If $a=0$, then our above process looks different, although (surprisingly?) the
result will be the same.

\textbf{Upshot:} (if you check these alternative cases):

The system%
\[
\left\{
\begin{array}
[c]{c}%
ax+by=c\\
a^{\prime}x+b^{\prime}y=c^{\prime}%
\end{array}
\right.
\]
has:

\begin{itemize}
\item \textbf{a unique solution} (namely, $\left\{
\begin{array}
[c]{c}%
x=\dfrac{cb^{\prime}-bc^{\prime}}{ab^{\prime}-ba^{\prime}}\\
y=\dfrac{ac^{\prime}-a^{\prime}c}{ab^{\prime}-a^{\prime}b}%
\end{array}
\right.  $) if $ab^{\prime}-ba^{\prime}\neq0$.

\item \textbf{no solutions} or \textbf{infinitely many solutions} if
$ab^{\prime}-ba^{\prime}=0$.
\end{itemize}

So the value $ab^{\prime}-ba^{\prime}$ determines the structure of the
solutions of the system (at least to the extent that it tells us whether they
are unique).

We will later learn that this is no coincidence. Something similar exists for
systems of 3 $3$ equations in $3$ variables, $4$ equations in $4$ variables, etc.

The analogues of $ab^{\prime}-ba^{\prime}$ are called \textbf{determinants}
(of $n\times n$-matrices).

\section{Linear combinations, linear independence and spans}

\subsection{Linear combinations}

This section follows \cite[\S 7]{Strickland}.

\begin{definition}
Fix $n\in\mathbb{N}$. Then, $\mathbb{R}^{n}$ denotes the set of all column
vectors of size $n$ (that is, $n\times1$-matrices) with real entries.
\end{definition}

\begin{definition}
Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in $\mathbb{R}^{n}$. A
\textbf{linear combination} of $v_{1},v_{2},\ldots,v_{k}$ means a vector
$w\in\mathbb{R}^{n}$ that can be written as%
\[
w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}%
\ \ \ \ \ \ \ \ \ \ \text{for some numbers }\lambda_{1},\lambda_{2}%
,\ldots,\lambda_{k}.
\]

\end{definition}

\begin{example}
Given three vectors $a,b,c$, all of the following are linear combinations of
$a,b,c$:%
\begin{align*}
a+b+c  &  =1a+1b+1c,\ \ \ \ \ \ \ \ \ \ a+b-c=1a+1b+\left(  -1\right)  c,\\
a+b  &  =1a+1b+0c,\ \ \ \ \ \ \ \ \ \ a-b+c=1a+\left(  -1\right)  b+1c,\\
a  &  =1a+0b+0c,\ \ \ \ \ \ \ \ \ \ 0_{n\times1}=0a+0b+0c,\\
&  2849a+5815b-384c,\ \ \ \ \ \ \ \ \ \ \dfrac{1}{3}a+\sqrt{2}b-\pi
c,\ \ \ \ \ \ \ \ \ \ \ldots
\end{align*}

\end{example}

\textbf{Question:} Given some vectors $v_{1},v_{2},\ldots,v_{k}\in
\mathbb{R}^{n}$ and a vector $w\in\mathbb{R}^{n}$, how can we tell whether $w$
is a linear combination of the $v_{1},v_{2},\ldots,v_{k}$ ? And if it is, how
do we find the corresponding coefficients $\lambda_{1},\lambda_{2}%
,\ldots,\lambda_{k}$ ?

\textbf{Example:} Let $n=2$ and $k=2$. Is $\left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  $ a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
2\\
4
\end{array}
\right)  $ ?

This means: Are there $\lambda_{1},\lambda_{2}\in\mathbb{R}$ such that
$\left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  =\lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
2\\
4
\end{array}
\right)  $ ?

Let us rewrite this equation:%
\begin{align*}
&  \ \ \ \left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  =\lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
2\\
4
\end{array}
\right) \\
&  \Longleftrightarrow\ \ \ \left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\lambda_{1}\cdot1\\
\lambda_{1}\cdot3
\end{array}
\right)  +\left(
\begin{array}
[c]{c}%
\lambda_{2}\cdot2\\
\lambda_{2}\cdot4
\end{array}
\right) \\
&  \Longleftrightarrow\ \ \ \left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\lambda_{1}\cdot1+\lambda_{2}\cdot2\\
\lambda_{1}\cdot3+\lambda_{2}\cdot4
\end{array}
\right) \\
&  \Longleftrightarrow\ \ \ \left\{
\begin{array}
[c]{c}%
0=\lambda_{1}\cdot1+\lambda_{2}\cdot2\\
5=\lambda_{1}\cdot3+\lambda_{2}\cdot4
\end{array}
\right. \\
&  \Longleftrightarrow\ \ \ \left\{
\begin{array}
[c]{c}%
\lambda_{1}+2\lambda_{2}=0\\
3\lambda_{1}+4\lambda_{2}=5
\end{array}
\right.  .
\end{align*}
This is a linear system in $\lambda_{1}$ and $\lambda_{2}$. It has a unique
solution, which is $\left\{
\begin{array}
[c]{c}%
\lambda_{1}=5\\
\lambda_{2}=-5/2
\end{array}
\right.  $. Thus,%
\[
\left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  =\lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
2\\
4
\end{array}
\right)
\]
with $\lambda_{1}=5$ and $\lambda_{2}=-5/2$. Thus, $\left(
\begin{array}
[c]{c}%
0\\
5
\end{array}
\right)  $ is a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
2\\
4
\end{array}
\right)  $.

\textbf{Example:} Is $\left(
\begin{array}
[c]{c}%
2\\
2\\
2
\end{array}
\right)  $ a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
3\\
4\\
5
\end{array}
\right)  $ ?

We can solve this with the same method.

But you might just be able to eyeball the answer: $\left(
\begin{array}
[c]{c}%
2\\
2\\
2
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
3\\
4\\
5
\end{array}
\right)  -\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $.

\textbf{Example:} Is $\left(
\begin{array}
[c]{c}%
0\\
0\\
1
\end{array}
\right)  $ a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
1\\
1\\
2
\end{array}
\right)  $ ?

We can solve this with the same method, but the linear system will now have
\textbf{no} solution.

This means that the answer is \textquotedblleft no\textquotedblright.

There is an easier way to see this: Both vectors $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
1\\
1\\
2
\end{array}
\right)  $ have the property that%
\[
\left(  \text{top entry}\right)  +\left(  \text{middle entry}\right)  =\left(
\text{bottom entry}\right)  .
\]
This is a property that is preserved under linear combination (i.e., if some
vectors have this property, then any of their linear combinations has it as
well). Therefore, if $\left(
\begin{array}
[c]{c}%
0\\
0\\
1
\end{array}
\right)  $ was a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
1\\
1\\
2
\end{array}
\right)  $, then it would too have this property. But it does not.

\textbf{General method for answering the above question} (\cite[Method
7.6]{Strickland})\textbf{:}

Consider $k$ vectors $v_{1},v_{2},\ldots,v_{k}\in\mathbb{R}^{n}$ and a vector
$w\in\mathbb{R}^{n}$. How can we tell whether $w$ is a linear combination of
$v_{1},v_{2},\ldots,v_{k}$ ?

We want to find $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$ such that
$w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}$.

This can be rewritten as $w=A\lambda$, where
\[
A=\underbrace{\left(  v_{1}\mid v_{2}\mid\cdots\mid v_{k}\right)
}_{\substack{\text{This is the }n\times k\text{-matrix}\\\text{whose columns
are }v_{1},v_{2},\ldots,v_{k}}}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{k}%
\end{array}
\right)  .
\]


This is a system in the unknowns $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$,
thus can be solved using Gaussian elimination. If there is no solution, then
$w$ is \textbf{not} a linear combination of $v_{1},v_{2},\ldots,v_{k}$. If
there is a solution, then $w$ is a linear combination of $v_{1},v_{2}%
,\ldots,v_{k}$, and the solution gives us the required coefficients
$\lambda_{i}$.

\textbf{Example:} Is $\left(
\begin{array}
[c]{c}%
2\\
2\\
2
\end{array}
\right)  $ a linear combination of $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
3\\
4\\
5
\end{array}
\right)  $ ?

We already answered this by eyeballing it, but let us do this systematically now:

$A=\left(
\begin{array}
[c]{cc}%
1 & 3\\
2 & 4\\
3 & 5
\end{array}
\right)  $, $\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}%
\end{array}
\right)  $ and $w=\left(
\begin{array}
[c]{c}%
2\\
2\\
2
\end{array}
\right)  $.

So we are solving $\left(
\begin{array}
[c]{cc}%
1 & 3\\
2 & 4\\
3 & 5
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
2\\
2
\end{array}
\right)  $.

Augmented matrix:%
\[
\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
2 & 4 & \mathbf{2}\\
3 & 5 & \mathbf{2}%
\end{array}
\right)  .
\]
Bringing it into RREF:%
\begin{align*}
\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
2 & 4 & \mathbf{2}\\
3 & 5 & \mathbf{2}%
\end{array}
\right)   &  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
0 & -2 & \mathbf{-2}\\
3 & 5 & \mathbf{2}%
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
0 & -2 & \mathbf{-2}\\
0 & -4 & \mathbf{-4}%
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
0 & 1 & \mathbf{1}\\
0 & -4 & \mathbf{-4}%
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 3 & \mathbf{2}\\
0 & 1 & \mathbf{1}\\
0 & 0 & \mathbf{0}%
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 0 & \mathbf{-1}\\
0 & 1 & \mathbf{1}\\
0 & 0 & \mathbf{0}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF.}%
\end{align*}
So the system becomes%
\[
\left\{
\begin{array}
[c]{c}%
\lambda_{1}=-1\\
\lambda_{2}=1
\end{array}
\right.  .
\]
Thus,%
\[
w=\lambda_{1}v_{1}+\lambda_{2}v_{2}=-1v_{1}+1v_{2}=v_{2}-v_{1}.
\]


\subsection{A few words on the geometric meaning of vectors}

How can we think about vectors? Why are they called vectors to begin with, if
they are just tuples of numbers?

In high-school plane geometry, a vector is a \textquotedblleft movable
arrow\textquotedblright\ somewhere in the plane. You can place its tail
anywhere, and then its head will be in some specific position. The only thing
that is really determined about the vector are its direction and its length.

Mathematically, the plane is just $\mathbb{R}^{2}$: the set of pairs of real
numbers. Each point in the plane corresponds to the pair $\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $ of real numbers $x$ and $y$, its Cartesian coordinates. Thus, a
point in the plane can be viewed as a column vector of size $2$.

We shall now identify this point $\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $ with the vector that starts at the origin and whose head is
$\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $. This way,
\[
\text{points}=\text{vectors (in high-school sense)}=\text{column vectors of
size }2.
\]


Addition of column vectors corresponds to addition of vectors from mechanics
(superposition of forces, aka parallelogram law).

Scaling of column vectors corresponds to stretching them from the origin (aka homothety).

Now, consider two vectors $v_{1},v_{2}\in\mathbb{R}^{2}$. If these two vectors
$v_{1}$ and $v_{2}$ fall on one line with the origin, then all their linear
combinations fall on the same line, and thus vectors outside of this line are
not linear combinations of $v_{1},v_{2}$. If $v_{1}$ and $v_{2}$ do not fall
on one line, then every point in $\mathbb{R}^{2}$ is a linear combination of
$v_{1},v_{2}$.

Something similar (but more complicated) works for $\mathbb{R}^{3}$.

\subsection{Linear dependence}

\begin{definition}
Let $\mathcal{V}=\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ be a list of $k$
vectors in $\mathbb{R}^{n}$.

A \textbf{linear relation} between the list $\mathcal{V}$ will mean a choice
of numbers $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$ (formally: a $k$-tuple
$\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $ of numbers) such
that%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}=0_{n\times1}.
\]


There is always the \textbf{trivial relation}, which is defined as the
$k$-tuple $\left(  0,0,\ldots,0\right)  $. In fact, $0v_{1}+0v_{2}%
+\cdots+0v_{k}=0_{n\times1}$.

We say that the list $\mathcal{V}$ is

\begin{itemize}
\item \textbf{linearly independent} if this trivial relation is its only
relation, and

\item \textbf{linearly dependent} otherwise.
\end{itemize}
\end{definition}

\textbf{Example.} Consider the list $\mathcal{V}$ consisting of%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{4}=\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)  .
\]
What are its relations?

Its relations are the $4$-tuples $\left(  \lambda_{1},\lambda_{2},\lambda
_{3},\lambda_{4}\right)  $ satisfying%
\begin{align*}
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\lambda_{3}v_{3}+\lambda_{4}v_{4}  &
=0_{4\times1},\ \ \ \ \ \ \ \ \ \ \text{that is,}\\
\lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  +\lambda_{3}\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  +\lambda_{4}\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)   &  =0_{4\times1},\ \ \ \ \ \ \ \ \ \ \text{that is,}\\
\left(
\begin{array}
[c]{c}%
\lambda_{1}+\lambda_{3}\\
\lambda_{1}+\lambda_{4}\\
\lambda_{2}+\lambda_{4}\\
\lambda_{2}+\lambda_{3}%
\end{array}
\right)   &  =\left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
0
\end{array}
\right)  .
\end{align*}
This is a system. What are its solutions? Its general solution is%
\[
\left\{
\begin{array}
[c]{c}%
\lambda_{1}=-\lambda_{4},\\
\lambda_{2}=-\lambda_{4},\\
\lambda_{3}=\lambda_{4}%
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \left(  \text{with }\lambda_{4}\text{ a free
variable}\right)  .
\]
So, in particular, $\left(  \lambda_{1},\lambda_{2},\lambda_{3},\lambda
_{4}\right)  =\left(  1,1,-1,-1\right)  $ is a solution, i.e., a linear
relation between $v_{1},v_{2},v_{3},v_{4}$. Thus,%
\[
v_{1}+v_{2}-v_{3}-v_{4}=0_{4\times1}.
\]
This shows that $\mathcal{V}$ is linearly dependent.

\textbf{Example:} Let $\mathcal{V}$ be the list consisting of%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
12\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
-1\\
-1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{4}=\left(
\begin{array}
[c]{c}%
3\\
1
\end{array}
\right)  .
\]
This is \textquotedblleft even more\textquotedblright\ linearly dependent;
there are many linear relations, such as%
\[
3v_{1}+v_{2}+3v_{3}-4v_{4}=0_{2\times1}.
\]


\textbf{Example:} Let $\mathcal{V}$ be the list consisting of%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
2\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  .
\]
This list is linearly dependent, because $2v_{1}-1v_{2}+0v_{3}=0_{2\times1}$.

\textbf{Next time:}

\begin{itemize}
\item Two vectors are linearly dependent if and only if one is a multiple of
the other.

\item More generally: $k$ vectors are linearly dependent if and only if one is
a linear combination of the others.

\item Spanning and bases.
\end{itemize}

\begin{thebibliography}{9999999999}                                                                                       %
\bibitem[Strickland]{Strickland}Neil Strickland, \textit{MAS201 Linear
Mathematics for Applications}, lecture notes, 28 September 2013.\newline\url{http://neil-strickland.staff.shef.ac.uk/courses/MAS201/}
\end{thebibliography}


\end{document}