\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:18:28}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{ComputeDefs=
%$A=\left(
%\begin{array}
%[c]{cc}%
%a & b\\
%c & d
%\end{array}
%\right)  $
%$B=\left(
%\begin{array}
%[c]{cc}%
%x & y\\
%z & w
%\end{array}
%\right)  $
%$x=\dfrac{97}{242}$
%$y=\dfrac{19}{121}$
%$z=\dfrac{35}{242}$
%}
%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/}}
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-09-25}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Introduction to matrices (continued)}

\subsection{Properties of matrix operations (continued)}

\textbf{Recall:} Multiplication of matrices is associative but not commutative.

So products of matrices don't need parentheses (i.e., for example, $ABCDE$
makes sense without putting parentheses in, as long as the little products
$AB,BC,CD,DE$ make sense), but the order of the matrices in the product
matters (so $AB\neq BA$ in general).

One more thing that does not work for matrices: Back in the set of real
numbers, we can cancel (i.e., if $a\neq0$ and $ab=ac$, then $b=c$).

For matrices, this is no longer true: It is easy to come up with an example
where $A$ is not all zeroes, and $AB=AC$, but nevertheless $B\neq C$.

\subsection{The zero matrix}

This section follows \cite[\S 2.10]{lina}.

\begin{definition}
Let $n,m\in\mathbb{N}$. Then, the $n\times m$ \textbf{zero matrix} means the
matrix $\left(  0\right)  _{1\leq i\leq n,\ 1\leq j\leq m}$. This is the
$n\times m$-matrix whose all entries are $0$. We denote it by $0_{n\times m}$
or, if ambiguity cannot arise, by $0$.
\end{definition}

For example, the $2\times3$ zero matrix is $0_{2\times3}=\left(
\begin{array}
[c]{ccc}%
0 & 0 & 0\\
0 & 0 & 0
\end{array}
\right)  $.

The following rules are easy to verify:

\begin{proposition}
Let $n,m\in\mathbb{N}$.

\textbf{(a)} We have $0_{n\times m}+A=A+0_{n\times m}=A$ for each $n\times
m$-matrix $A$.

\textbf{(b)} We have $0_{n\times m}A=0_{n\times p}$ for each $p\in\mathbb{N}$
and each $m\times p$-matrix $A$.

\textbf{(c)} We have $A0_{n\times m}=0_{p\times m}$ for each $p\in\mathbb{N}$
and each $p\times n$-matrix $A$.

\textbf{(d)} We have $0A=0_{n\times m}$ for each $n\times m$-matrix $A$.

\textbf{(e)} We have $\lambda0_{n\times m}=0_{n\times m}$ for each number
$\lambda$.
\end{proposition}

\subsection{The identity matrix}

This section follows \cite[\S 2.11]{lina}.

\begin{definition}
A \textbf{square matrix} means an $n\times n$-matrix for some $n\in\mathbb{N}$.
\end{definition}

For example, $\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  $ is a square matrix, but $\left(
\begin{array}
[c]{ccc}%
a & b & c\\
d & e & f
\end{array}
\right)  $ is not.

\begin{definition}
Let $n\in\mathbb{N}$. Let $A$ be an $n\times n$-matrix.

The \textbf{diagonal entries} of $A$ are the $n$ entries $A_{1,1}%
,A_{2,2},\ldots,A_{n,n}$.

All the other $n^{2}-n$ entries of $A$ are called \textbf{off-diagonal
entries}.
\end{definition}

For example, $\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  $ has diagonal entries $a,d$ and off-diagonal entries $b,c$.

\begin{definition}
If $i$ and $j$ are any two objects (e.g., numbers), then we set%
\[
\delta_{i,j}=%
\begin{cases}
1, & \text{if }i=j;\\
0, & \text{if }i\neq j.
\end{cases}
\]

\end{definition}

This is called the \textbf{Kronecker delta}. For example, $\delta_{2,3}=0$ but
$\delta_{3,3}=1$.

\begin{definition}
Let $n\in\mathbb{N}$. Then, the $n\times n$ \textbf{identity matrix} means the
matrix
\[
\left(  \delta_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}.
\]
This is the $n\times n$-matrix whose diagonal entries are all equal to $1$ and
whose off-diagonal entries are all equal to $0$. It is denoted by $I_{n}$ or
sometimes by $I$. (Some call it $E$.)
\end{definition}

For example,%
\[
I_{4}=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  .
\]


The following proposition is not hard to prove (see \cite[\S 2.12]{lina} for a
proof of part \textbf{(b)}):

\begin{proposition}
Let $n,m\in\mathbb{N}$.

\textbf{(a)} We have $I_{n}A=A$ for each $n\times m$-matrix $A$.

\textbf{(b)} We have $AI_{m}=A$ for each $n\times m$-matrix $A$.
\end{proposition}

\subsubsection{Powers of a matrix}

This section follows \cite[\S 2.13]{lina}.

Recall how powers of numbers are defined:%
\[
a^{0}=1;\ \ \ \ \ \ \ \ \ \ a^{1}=a;\ \ \ \ \ \ \ \ \ \ a^{2}%
=aa;\ \ \ \ \ \ \ \ \ \ a^{3}=aaa;\ \ \ \ \ \ \ \ \ \ a^{4}%
=aaaa;\ \ \ \ \ \ \ \ \ \ \ldots.
\]
Likewise, we can define powers of a square matrix:%
\[
A^{0}=I_{n};\ \ \ \ \ \ \ \ \ \ A^{1}=A;\ \ \ \ \ \ \ \ \ \ A^{2}%
=AA;\ \ \ \ \ \ \ \ \ \ A^{3}=AAA;\ \ \ \ \ \ \ \ \ \ A^{4}%
=AAAA;\ \ \ \ \ \ \ \ \ \ \ldots
\]
for any $n\times n$-matrix $A$.

(Note: Powers are only defined for square matrices.)

\begin{example}
\begin{itemize}
\item If $A=\left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  $, then%
\begin{align*}
A^{2} &  =\left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
4 & 0\\
0 & 1
\end{array}
\right)  ;\\
A^{3} &  =\left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
8 & 0\\
0 & 1
\end{array}
\right)  ;\\
&  \ldots;\\
A^{n} &  =\left(
\begin{array}
[c]{cc}%
2^{n} & 0\\
0 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{N}\text{.}%
\end{align*}


\item If $A=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  $, then%
\begin{align*}
A^{2} &  =\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
1 & 2\\
0 & 1
\end{array}
\right)  ;\\
A^{3} &  =A^{2}A=\left(
\begin{array}
[c]{cc}%
1 & 2\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
1 & 3\\
0 & 1
\end{array}
\right)  ;\\
A^{4} &  =\left(
\begin{array}
[c]{cc}%
1 & 4\\
0 & 1
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ \ A^{5}=\left(
\begin{array}
[c]{cc}%
1 & 5\\
0 & 1
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ \ \ldots;\\
A^{n} &  =\left(
\begin{array}
[c]{cc}%
1 & n\\
0 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{N}\text{.}%
\end{align*}

\end{itemize}
\end{example}

\begin{remark}
If $A$ is a square matrix, then $A^{u}A^{v}=A^{u+v}=A^{v}A^{u}$.

Thus, while not any two matrices commute (i.e., $XY=YX$ does not always hold),
we still have a lot of situations where matrices do commute: $XY=YX$ always
holds if $X=A^{u}$ and $Y=A^{v}$.
\end{remark}

\subsection{Products and transposes}

\begin{proposition}
Let $A$ be an $n\times m$-matrix and $B$ be an $m\times p$-matrix. Then,%
\[
\left(  AB\right)  ^{T}=B^{T}A^{T}.
\]

\end{proposition}

For a detailed proof, see \cite[Proposition 3.18 \textbf{(e)}]{lina}.

\begin{example}
Let $A=\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
x & y\\
z & w
\end{array}
\right)  $. Then,%
\begin{align*}
AB &  =\left(
\begin{array}
[c]{cc}%
ax+bz & bw+ay\\
cx+dz & dw+cy
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \text{so}\\
\left(  AB\right)  ^{T} &  =\left(
\begin{array}
[c]{cc}%
ax+bz & cx+dz\\
bw+ay & dw+cy
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \text{but}\\
B^{T}A^{T} &  =\left(
\begin{array}
[c]{cc}%
ax+bz & cx+dz\\
bw+ay & dw+cy
\end{array}
\right)  .
\end{align*}

\end{example}

Note: Any \textbf{row} of $A$ corresponds to a \textbf{column} of $A^{T}$.
More precisely, for any $j$, we have%
\[
\left(  \operatorname{row}_{j}A\right)  ^{T}=\operatorname{col}_{j}\left(
A^{T}\right)  .
\]
Similarly,%
\[
\left(  \operatorname{col}_{j}A\right)  ^{T}=\operatorname{row}_{j}\left(
A^{T}\right)  .
\]
Hence, transposing a matrix switches the roles of rows and columns.

\section{Gaussian elimination}

From now on, we mostly follow \cite{Strickland}.

\subsubsection{Reminder: solving systems of linear equations}

\begin{example}
Consider the following system of 3 equations in 3 unknowns $x,y,z$:%
\[%
\begin{cases}
3x+6y-z=2\\
7x+4y-3z=3\\
-y+8z=1
\end{cases}
.
\]
How do we solve it?
\end{example}

There is a method called \textbf{Gaussian elimination}. In its most systematic
form, it proceeds as follows:

\begin{itemize}
\item Try to get the variable $x$ to only appear in \textbf{one} equation. To
do so, we subtract appropriate multiples of one equation that contains $x$
from all the other equations that contain $x$.

\item After this is done, play the same game with the other variables.
\end{itemize}

First of all, why can we just subtract equations from each other?

Imagine we are solving a system%
\[%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
.
\]
Now, if we subtract the second equation from the first, we get%
\[%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  -A\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
.
\]


I claim that this new system has \textbf{exactly the same solutions} as the
old system.

Indeed:

\begin{itemize}
\item Every solution of $%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
$ is a solution of $%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  -A\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
$, because it satisfies $\underbrace{B\left(  x,y,z\right)  }_{=0}%
-\underbrace{A\left(  x,y,z\right)  }_{=0}=0-0=0$.

\item Conversely, every solution of $%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  -A\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
$ is a solution of $%
\begin{cases}
A\left(  x,y,z\right)  =0\\
B\left(  x,y,z\right)  =0\\
C\left(  x,y,z\right)  =0
\end{cases}
$, because it satisfies%
\[
B\left(  x,y,z\right)  =\underbrace{\left(  B\left(  x,y,z\right)  -A\left(
x,y,z\right)  \right)  }_{=0}+\underbrace{A\left(  x,y,z\right)  }%
_{=0}=0+0=0.
\]

\end{itemize}

Thus, when we subtract an equation from another, the system's solutions don't change.

The same holds if we multiply an equation by a nonzero number.

The same holds if we swap two equations.

So we have three transformations we can do with a system of equations without
changing its set of solutions:

\begin{itemize}
\item We can subtract an equation from another.

\item We can multiply an equation by a nonzero number.

\item We can swap two equations.
\end{itemize}

Let's try to use these transformations to simplify our system:%
\begin{align*}
&
\begin{cases}
3x+6y-z=2\\
7x+4y-3z=3\\
-y+8z=1
\end{cases}
\\
&  \overset{\text{multiply eq. 1 by }1/3}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
7x+4y-3z=3\\
-y+8z=1
\end{cases}
\\
&  \overset{\text{multiply eq. 2 by }1/7}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
x+\dfrac{4}{7}y-\dfrac{3}{7}z=\dfrac{3}{7}\\
-y+8z=1
\end{cases}
\\
&  \overset{\text{subtract eq. 1 from eq. 2}}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
-\dfrac{10}{7}y-\dfrac{2}{21}z=-\dfrac{5}{21}\\
-y+8z=1
\end{cases}
.
\end{align*}
Now, the $x$ only survives in the first equation.

Let us try to make the $y$ only survive in the second equation:%
\begin{align*}
&
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
-\dfrac{10}{7}y-\dfrac{2}{21}z=-\dfrac{5}{21}\\
-y+8z=1
\end{cases}
\\
&  \overset{\text{multiply eq. 2 by }-7/10}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
y+\dfrac{1}{15}z=\dfrac{1}{6}\\
-y+8z=1
\end{cases}
\\
&  \overset{\text{multiply eq. 3 by }-1}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
y+\dfrac{1}{15}z=\dfrac{1}{6}\\
y-8z=-1
\end{cases}
\\
&  \overset{\text{subtract eq. 2 from eq. 3}}{\longrightarrow}%
\begin{cases}
x+2y-\dfrac{1}{3}z=\dfrac{2}{3}\\
y+\dfrac{1}{15}z=\dfrac{1}{6}\\
-\dfrac{121}{15}z=-\dfrac{7}{6}%
\end{cases}
.
\end{align*}
At this point, we can solve eq. 3 for $z$, getting%
\[
z=\left(  -\dfrac{7}{6}\right)  /\left(  -\dfrac{121}{15}\right)  =\dfrac
{35}{242}.
\]
With this value found, we can solve eq. 2 for $y$, getting $y=\dfrac{1}%
{6}-\dfrac{1}{15}\cdot\dfrac{35}{242}=\dfrac{19}{121}$. Finally, with this
value found as well, we can solve eq. 1 for $x$, getting $x=\dfrac{2}%
{3}-2\cdot\dfrac{19}{121}+\dfrac{1}{3}\cdot\dfrac{35}{242}=\dfrac{97}{242}$.
So the only solution to our system is%
\[
\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\dfrac{97}{242}\\
\dfrac{19}{121}\\
\dfrac{97}{242}%
\end{array}
\right)  .
\]


Thus our method was successful: We have found a solution of our system, and we
know that it is the only solution.

Not all situations are this simple!

\begin{example}
Consider the system%
\[%
\begin{cases}
x-y=2\\
x-z=3\\
y-z=4
\end{cases}
.
\]
Use the same method:%
\begin{align*}
&
\begin{cases}
x-y=2\\
x-z=3\\
y-z=4
\end{cases}
\\
&  \overset{\text{subtract eq. 1 from eq. 2}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=1\\
y-z=4
\end{cases}
\\
&  \overset{\text{subtract eq. 2 from eq. 3}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=1\\
0=3
\end{cases}
.
\end{align*}
So this system has no solutions, because $0$ will not equal to $3$ no matter
what $x,y,z$ are.
\end{example}

\begin{example}
Consider the system%
\[%
\begin{cases}
x-y=2\\
x-z=6\\
y-z=4
\end{cases}
.
\]
Use the same method:%
\begin{align*}
&
\begin{cases}
x-y=2\\
x-z=6\\
y-z=4
\end{cases}
\\
&  \overset{\text{subtract eq. 1 from eq. 2}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=4\\
y-z=4
\end{cases}
\\
&  \overset{\text{subtract eq. 2 from eq. 3}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=1\\
0=0
\end{cases}
\\
&  \overset{\text{remove eq. 3, since it always holds}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=1
\end{cases}
.
\end{align*}
How to solve $%
\begin{cases}
x-y=2\\
y-z=1
\end{cases}
$ ?

Take $z$ arbitrary, and solve eq. 2 for $y$, getting $y=z+1$. With this value
found, solve eq. 1 for $x$, getting $x=\underbrace{y}_{=z+1}+2=z+3$. So the
solutions of our system are all triples $\left(  x,y,z\right)  =\left(
z+3,z+1,z\right)  $. In other words, they can be written as $\left(
z,z,z\right)  +\left(  3,1,0\right)  $.
\end{example}

So we have solved three systems of equations, and seen three different behaviors:

\begin{itemize}
\item A unique solution.

\item No solution.

\item Infinitely many solutions.
\end{itemize}

So it appears that the answer to an arbitrary system of linear equations will
be: Either there will be no solutions at all, or $\underbrace{\text{some}%
}_{\text{possibly none}}$ variables will be free and others will be determined
by them.

\subsection{Linear equations vs. matrices}

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

To get a better grip on solving system of linear equations, we are going to
restate them \textquotedblleft in matrix form\textquotedblright.

\begin{example}
Start again with our system%
\[%
\begin{cases}
3x+6y-z=2\\
7x+4y-3z=3\\
-y+8z=1
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{in three variables }x,y,z.
\]
I claim that it is equivalent to the matrix equation%
\[
\left(
\begin{array}
[c]{ccc}%
3 & 6 & -1\\
7 & 4 & -3\\
0 & -1 & 8
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
3\\
1
\end{array}
\right)  .
\]
Indeed,
\[
\left(
\begin{array}
[c]{ccc}%
3 & 6 & -1\\
7 & 4 & -3\\
0 & -1 & 8
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
3x+6y+\left(  -1\right)  z\\
7x+4y+\left(  -3\right)  z\\
0x+\left(  -1\right)  y+8z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
3x+6y-z\\
7x+4y-3z\\
-y+8z
\end{array}
\right)  .
\]
For this vector to be equal to $\left(
\begin{array}
[c]{c}%
2\\
3\\
1
\end{array}
\right)  $, we need precisely the equations%
\[%
\begin{cases}
3x+6y-z=2\\
7x+4y-3z=3\\
-y+8z=1
\end{cases}
.
\]
But this is exactly our system that we started with.
\end{example}

\begin{example}
The system%
\[%
\begin{cases}
x-y=2\\
x-z=6\\
y-z=4
\end{cases}
\]
rewrites as%
\[
\left(
\begin{array}
[c]{ccc}%
1 & -1 & 0\\
1 & 0 & -1\\
0 & 1 & -1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
6\\
4
\end{array}
\right)  .
\]


This form has some advantages: Now we are solving one equation instead of
three, and furthermore we are using matrices, which simplifies our life if we
know anything about matrices.
\end{example}

\textbf{Upshot:} For any system of $n$ linear equations in $m$ variables
$x_{1},x_{2},\ldots,x_{m}$, we can rewrite the system as a matrix equation%
\[
Ax=b,\ \ \ \ \ \ \ \ \ \ \text{where }x=\left(
\begin{array}
[c]{c}%
x_{1}\\
x_{2}\\
\vdots\\
x_{m}%
\end{array}
\right)  .
\]
Namely, if our equations are%
\[%
\begin{cases}
a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots+a_{1,m}x_{m}=b_{1}\\
a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots+a_{2,m}x_{m}=b_{2}\\
\vdots\\
a_{n,1}x_{1}+a_{n,2}x_{2}+\cdots+a_{n,m}x_{m}=b_{n}%
\end{cases}
,
\]
then the system is equivalent to $Ax=b$, where%
\[
A=\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & \cdots & a_{1,m}\\
a_{2,1} & a_{2,2} & \cdots & a_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n,1} & a_{n,2} & \cdots & a_{n,m}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ x=\left(
\begin{array}
[c]{c}%
x_{1}\\
x_{2}\\
\vdots\\
x_{m}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ b=\left(
\begin{array}
[c]{c}%
b_{1}\\
b_{2}\\
\vdots\\
b_{n}%
\end{array}
\right)  .
\]


Therefore, solving a system of linear equations is the same as
\textquotedblleft unmultiplying\textquotedblright\ a vector by a matrix: We
are looking for all $x$'s with $Ax=b$. In a way, we are thus looking for
\textquotedblleft$b$ divided by $A$\textquotedblright\ (except that this is
not a thing).

In our above \textquotedblleft method\textquotedblright\ for solving systems,
we have used three operations:

\begin{itemize}
\item Subtracting an equation from another.

\item Multiplying (i.e., scaling) an equation by some $\lambda\neq0$.

\item Swapping two equations.
\end{itemize}

What do these operations correspond to in terms of the matrix $A$ and the
vector $b$?

\begin{itemize}
\item Subtracting a row of $A$ from another row of $A$, and simultaneously
doing the same for $b$.

\item Scaling a row of $A$ by some $\lambda\neq0$, and doing the same for $b$.

\item Swapping two rows of $A$, and doing the same for $b$.
\end{itemize}

\begin{example}
Let us solve the system $%
\begin{cases}
x-y=2\\
x-z=6\\
y-z=4
\end{cases}
$ using this \textquotedblleft method\textquotedblright:%
\begin{align*}
&
\begin{cases}
x-y=2\\
x-z=6\\
y-z=4
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & -1 & 0\\
1 & 0 & -1\\
0 & 1 & -1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
6\\
4
\end{array}
\right)  \\
&  \overset{\text{subtract eq. 1 from eq. 2}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=4\\
y-z=4
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & -1 & 0\\
0 & 1 & -1\\
0 & 1 & -1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
4\\
4
\end{array}
\right)  \\
&  \overset{\text{subtract eq. 2 from eq. 3}}{\longrightarrow}%
\begin{cases}
x-y=2\\
y-z=1\\
0=0
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & -1 & 0\\
0 & 1 & -1\\
0 & 0 & 0
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2\\
4\\
0
\end{array}
\right)  .
\end{align*}
So our operations on the system of equations can be recast as operations on
$A$ and $b$.
\end{example}

\subsection{The augmented matrix}

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

The easiest way to do some operations on $A$ and $b$ simultaneously is to glue
the vector $b$ to the matrix $A$ (let's say on its right edge) and just
perform these operations on the resulting big matrix. This is called the
\textbf{augmented matrix} of our system of equations:

\begin{definition}
Let%
\[%
\begin{cases}
a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots+a_{1,m}x_{m}=b_{1}\\
a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots+a_{2,m}x_{m}=b_{2}\\
\vdots\\
a_{n,1}x_{1}+a_{n,2}x_{2}+\cdots+a_{n,m}x_{m}=b_{n}%
\end{cases}
\]
be a system of $n$ linear equations in $m$ unknowns $x_{1},x_{2},\ldots,x_{m}%
$. Then, the matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
a_{1,1} & a_{1,2} & \cdots & a_{1,m} & b_{1}\\
a_{2,1} & a_{2,2} & \cdots & a_{2,m} & b_{2}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
a_{n,1} & a_{n,2} & \cdots & a_{n,m} & b_{n}%
\end{array}
\right)
\]
is called the \textbf{augmented matrix} of the system. Often you put a
vertical bar between the last column and the other columns in this matrix, so
as to remind yourself that they serve different roles. I will instead put the
entries in the last column in boldface:%
\[
\left(
\begin{array}
[c]{ccccc}%
a_{1,1} & a_{1,2} & \cdots & a_{1,m} & \mathbf{b}_{1}\\
a_{2,1} & a_{2,2} & \cdots & a_{2,m} & \mathbf{b}_{2}\\
\vdots & \vdots & \ddots & \vdots & \mathbf{\vdots}\\
a_{n,1} & a_{n,2} & \cdots & a_{n,m} & \mathbf{b}_{n}%
\end{array}
\right)  .
\]

\end{definition}

Now, the operations we did on our equations (subtracting, scaling and
swapping) correspond directly to operations done on the rows of this augmented
matrix. As we already saw, the solutions of the system of equations do not
change when we do these operations.

\textbf{Question:} How simple can we make our augmented matrix just by
performing these operations?

We need to specify a notion of \textquotedblleft simple\textquotedblright%
\ matrices. The one we will use is called a \textquotedblleft reduced
row-echelon matrix\textquotedblright\ or a \textquotedblleft matrix in reduced
row-echelon form (RREF)\textquotedblright\ or \textquotedblleft RREF
matrix\textquotedblright.

\subsection{Reduced row-echelon form}

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

\begin{definition}
Let $A$ be a matrix. We say that $A$ is in \textbf{reduced row-echelon form
(RREF)} if the following conditions hold:

\begin{itemize}
\item \textbf{RREF0:} Any row of zeros is at the bottom of the matrix, after
all the nonzero rows. (A \textquotedblleft nonzero row\textquotedblright%
\ means a row that is not all zeros. It can still have some zeros.)

\item \textbf{RREF1:} In any nonzero row, the first nonzero entry is equal to
$1$. This entry is called the \textbf{pivot} of the row.

\item \textbf{RREF2:} The pivot of any nonzero row must be further to the
right than the pivot of the previous nonzero row.

\item \textbf{RREF3:} If a \textbf{column} contains a pivot, then all other
entries in the column are zero.
\end{itemize}
\end{definition}

\begin{example}
Here are some examples of matrices that are in RREF and matrices that aren't:

\begin{itemize}
\item If an $n\times n$-matrix is in RREF and has $n$ pivots, how does it look like?

It has to be the identity matrix.

For example, if $n=4$, then it has to be $\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  $.

\item Is the matrix $\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 3\\
0 & 0 & 1 & 5
\end{array}
\right)  $ in RREF? Yes.

\item Is the matrix $\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 3\\
0 & 0 & 1 & 3\\
0 & 0 & 1 & 0
\end{array}
\right)  $ in RREF? No, as it fails both RREF2 and RREF3.

\item Is the matrix $\left(
\begin{array}
[c]{ccc}%
0 & 1 & 0\\
0 & 0 & 1\\
1 & 0 & 0
\end{array}
\right)  $ in RREF? No, because it fails RREF2 (the pivot in row $3$ is not
right of the pivot in row $2$).

\item Is the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 0\\
0 & 0 & 0\\
0 & 0 & 1
\end{array}
\right)  $ in RREF? No, because it fails RREF0.
\end{itemize}
\end{example}

What is the purpose of RREF matrices? Idea:

\begin{enumerate}
\item We can transform any matrix into an RREF form by the row operations we
discussed (subtracting a row from another; scaling a row; swapping two rows).

\item If the augmented matrix of a system of linear equations is in RREF, then
this system is very easy to solve.
\end{enumerate}

Combined, these two points give a method for solving systems of linear equations:

Form the augmented matrix; transform it into RREF; then solve the resulting
easy system.

\textbf{Example for point 2:} For example, let's say the augmented matrix of
our system is%
\[
\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & \mathbf{3}\\
0 & 0 & 1 & \mathbf{5}%
\end{array}
\right)  .
\]
This means that our system is%
\begin{align*}
&
\begin{cases}
1x+0y+0z=3\\
0x+0y+1z=5
\end{cases}
,\ \ \ \ \ \ \ \ \ \ \text{i.e.}\\
&
\begin{cases}
x=3\\
z=5
\end{cases}
.
\end{align*}
This is already the solution. (Here, $y$ can be arbitrary.)

Slightly less trivial example: Let's say the augmented matrix is%
\[
\left(
\begin{array}
[c]{cccc}%
1 & 4 & 0 & \mathbf{3}\\
0 & 0 & 1 & \mathbf{5}%
\end{array}
\right)  .
\]
This means that our system is%
\begin{align*}
&
\begin{cases}
1x+4y+0z=3\\
0x+0y+1z=5
\end{cases}
,\ \ \ \ \ \ \ \ \ \ \text{i.e.}\\
&
\begin{cases}
x+4y=3\\
z=5
\end{cases}
.
\end{align*}
The solutions of this system are trivial to find: $z$ has to be $5$ (in order
to satisfy $z=5$); then, $y$ can be arbitrary; then, $x$ has to be $3-4y$ (in
order to satisfy $x+4y=3$).

\begin{thebibliography}{9999999999}                                                                                       %
\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}

\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}