\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:05:42}
%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/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-09-30}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Gaussian elimination (continued)}

\subsection{Solving systems that are in RREF}

Recall the definition of RREF:

\begin{definition}
\textbf{(repeated from last time, but slightly restated:)}

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 zero row is below any nonzero row.

(\textquotedblleft Zero row\textquotedblright\ means \textquotedblleft row
filled with zeroes\textquotedblright, but \textquotedblleft nonzero
row\textquotedblright\ means a row with at least one nonzero entry. So the row
$\left(  0,1,0\right)  $ is nonzero.)

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

(Slogan: The pivots move right as you walk down the matrix.)

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

(Slogan: Pivots clear their columns.)
\end{itemize}
\end{definition}

\begin{definition}
A system of linear equations is said to be in \textbf{RREF} if the augmented
matrix that corresponds to it is in RREF.
\end{definition}

\begin{definition}
Henceforth, \textquotedblleft\textbf{system}\textquotedblright\ means
\textquotedblleft system of linear equations\textquotedblright.
\end{definition}

Now, we claim the following theorem (\cite[Method 5.4]{Strickland}):

\begin{theorem}
There is an easy way to solve any system that is in RREF. Namely, let $A$ be
the augmented matrix corresponding to the system:

\textbf{(a)} Any zero row of $A$ can be discarded.

\textbf{(b)} If $A$ has a pivot in the last column, then the system has no
solution. (This is because the row with that pivot corresponds to the equation
$0=1$ in the system.)

\textbf{(c)} Now, assume that $A$ has no pivot in the last column, but there
is a pivot in each of the other columns. Then, the system has a unique
solution, and it can be read off from the last column: Each variable equals
the corresponding entry of the last column of $A$.

\textbf{(d)} Consider the general situation, assuming that $A$ has no pivot in
the last column. Each row of $A$ corresponds to an equation, and each column
of $A$ corresponds to an unknown (=variable). We shall refer to the variables
corresponding to the pivot columns (= columns containing pivots) as
\textbf{dependent variables}, and to the other variables as \textbf{free
variables }(aka \textbf{independent variables}). The free variables will be
unconstrained; any choice of values for the free variables will give exactly
$1$ solution to the system. Once the values of the free variables have been
chosen, we can find unique values for the dependent variables by solving each
equation of our system for the corresponding dependent variable.
\end{theorem}

\begin{example}
Let%
\[
A=\left(
\begin{array}
[c]{ccccc}%
1 & 0 & 0 & 1 & \mathbf{0}\\
0 & 1 & 1 & 0 & \mathbf{0}\\
0 & 0 & 0 & 0 & \mathbf{1}\\
0 & 0 & 0 & 0 & \mathbf{0}%
\end{array}
\right)  .
\]
The corresponding system is%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}+x_{4}=0\\
x_{2}+x_{3}=0\\
0=1\\
0=0
\end{array}
\right.  ,
\]
so it has no solution. This is an instance of part \textbf{(b)} of the theorem.
\end{example}

\begin{example}
Let%
\[
A=\left(
\begin{array}
[c]{ccccc}%
1 & 0 & 0 & 0 & \mathbf{10}\\
0 & 1 & 0 & 0 & \mathbf{11}\\
0 & 0 & 1 & 0 & \mathbf{12}\\
0 & 0 & 0 & 1 & \mathbf{13}%
\end{array}
\right)  .
\]
This corresponds to the system%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}=10\\
x_{2}=11\\
x_{3}=12\\
x_{4}=13
\end{array}
\right.  ,
\]
which is already its solution. This is an example of part \textbf{(c)}.
\end{example}

\begin{example}
Let $A$ be the matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 0 & 3 & \mathbf{10}\\
0 & 0 & 1 & 4 & \mathbf{20}%
\end{array}
\right)  .
\]
This corresponds to the system%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}+2x_{2}+3x_{4}=10\\
x_{3}+4x_{4}=20
\end{array}
\right.  .
\]
The pivot columns are $1$ and $3$. Thus, the dependent variables are $x_{1}$
and $x_{3}$, whereas the free variables are $x_{2}$ and $x_{4}$. So part
\textbf{(d)} of the above theorem tells us that we can choose \textbf{any}
values for $x_{2}$ and $x_{4}$ and get a unique set of matching values for
$x_{1}$ and $x_{3}$ by solving the equations (specifically: solving
$x_{1}+2x_{2}+3x_{4}=10$ for $x_{1}$ and solving $x_{3}+4x_{4}=20$ for $x_{3}%
$). So the general solution is%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}=10-2x_{2}-3x_{4}\\
x_{3}=20-4x_{4}%
\end{array}
\right.  .
\]

\end{example}

\subsection{Row operations}

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

\begin{definition}
The following operations on a matrix $A$ are called \textbf{elementary row
operations} (for short \textbf{EROs}, or just \textbf{row operations}):

\begin{itemize}
\item \textbf{ERO1:} Exchange two rows.

\item \textbf{ERO2:} Scale a row by a nonzero constant.

\item \textbf{ERO3:} Add a multiple of one row to another row. (That is, add
$\lambda\operatorname{row}_{i}A$ to $\operatorname{row}_{j}A$ for some
$\lambda\in\mathbb{R}$ and $i\neq j$.)
\end{itemize}
\end{definition}

\begin{example}
Let us transform the $3\times3$-matrix $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
4 & 5 & 6\\
7 & 8 & 9
\end{array}
\right)  $ using a sequence of row operations:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
4 & 5 & 6\\
7 & 8 & 9
\end{array}
\right)  \underset{\text{exchange rows }2\text{ and }3}{\overset{\text{ERO1}%
}{\longrightarrow}}\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
7 & 8 & 9\\
4 & 5 & 6
\end{array}
\right)  \\
&  \underset{\text{scale row }1\text{ by }2}{\overset{\text{ERO2}%
}{\longrightarrow}}\left(
\begin{array}
[c]{ccc}%
2 & 4 & 6\\
7 & 8 & 9\\
4 & 5 & 6
\end{array}
\right)  \\
&  \underset{\text{add }2\cdot\text{row }3\text{ to row }%
1}{\overset{\text{ERO3}}{\longrightarrow}}\left(
\begin{array}
[c]{ccc}%
2+2\cdot4 & 4+2\cdot5 & 6+2\cdot6\\
7 & 8 & 9\\
4 & 5 & 6
\end{array}
\right)  =\left(
\begin{array}
[c]{ccc}%
10 & 14 & 18\\
7 & 8 & 9\\
4 & 5 & 6
\end{array}
\right)  .
\end{align*}

\end{example}

\begin{remark}
We already discussed row operations previously, back when we were looking at
systems. We did it slightly differently, since instead of ERO3 we had the
following operation:

\begin{itemize}
\item \textbf{ERO3':} Subtract a row from another row.
\end{itemize}

This operation ERO3' is, of course, a particular case of ERO3, since
\textquotedblleft subtract a row\textquotedblright\ = \textquotedblleft add
the $\left(  -1\right)  $-multiple of this row\textquotedblright.

However, conversely, ERO3 can be \textquotedblleft simulated\textquotedblright%
\ by applying ERO2 and ERO3'. Indeed, if you want to add $\lambda
\operatorname{row}_{i}A$ to $\operatorname{row}_{j}A$ using only the
operations ERO2 and ERO3', then you can proceed as follows:

\begin{itemize}
\item If $\lambda\neq0$, then you first scale the $i$-th row by $-\lambda$,
then subtract it from the $j$-th row, and then scale the $i$-th row by
$-1/\lambda$ again (so that the $i$-th row returns to its original state).

\item If $\lambda=0$, then you can just sit back and relax (indeed, adding
$\lambda\operatorname{row}_{i}A$ does not change $\operatorname{row}_{j}A$ in
this case, so there is nothing to do).
\end{itemize}

\noindent Thus, the operation ERO3 does not add any more power compared to
ERO3'; we just use it for convenience.
\end{remark}

\begin{proposition}
Let $A$ be a matrix, and let $A^{\prime}$ be a matrix obtained from $A$ by a
sequence of EROs. Then, the systems corresponding to $A$ and to $A^{\prime}$
have the same set of solutions.
\end{proposition}

\begin{example}%
\[
A=\left(
\begin{array}
[c]{ccc}%
1 & 2 & \mathbf{3}\\
4 & 5 & \mathbf{6}\\
7 & 8 & \mathbf{9}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and }\ \ \ \ \ \ \ \ \ \ A^{\prime}=\left(
%
\begin{array}
[c]{ccc}%
10 & 14 & \mathbf{18}\\
7 & 8 & \mathbf{9}\\
4 & 5 & \mathbf{6}%
\end{array}
\right)  .
\]
Then, the corresponding systems are%
\[
\left\{
\begin{array}
[c]{c}%
x+2y=3\\
4x+5y=6\\
7x+8y=9
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left\{
\begin{array}
[c]{c}%
10x+14y=18\\
7x+8y=9\\
4x+5y=6
\end{array}
\right.  .
\]

\end{example}

\begin{proof}
We need to check that none of the three operations ERO1, ERO2, ERO3 changes
the set of solutions.

In terms of the system, these three operations correspond to

\begin{enumerate}
\item exchanging two equations;

\item scaling an equation by a nonzero constant;

\item adding a multiple of one equation to another.
\end{enumerate}

Clearly, the first two of these do not change the set of solutions. As for the
third one, we have to prove that the solution set of a system does not change
if we add a multiple of one equation to another. So we have to prove that if
we start with a system%
\[
\left\{
\begin{array}
[c]{c}%
A\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0\\
B\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0\\
\vdots
\end{array}
\right.
\]
and replace it by%
\[
\left\{
\begin{array}
[c]{c}%
A\left(  x_{1},x_{2},\ldots,x_{n}\right)  +\lambda B\left(  x_{1},x_{2}%
,\ldots,x_{n}\right)  =0\\
B\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0\\
\vdots
\end{array}
\right.  ,
\]
then the set of solutions does not change. But this is easy: Either system
contains the equation $B\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0$, and
therefore the equations
\[
A\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ A\left(  x_{1},x_{2},\ldots,x_{n}\right)  +\lambda
B\left(  x_{1},x_{2},\ldots,x_{n}\right)  =0
\]
are equivalent.
\end{proof}

\subsection{Gaussian elimination: transforming a matrix into RREF}

The following is \cite[Method 6.3]{Strickland}, one of the main ideas in this course:

\begin{theorem}
Let $A$ be a matrix. Then, we can transform $A$ into RREF by a sequence of
EROs as follows:

\textbf{(a)} If all rows of $A$ are zero, then we are done ($A$ is in RREF already).

\textbf{(b)} Otherwise, we find a nonzero entry that is as far left as
possible. (This entry is going to become a pivot.)

\textbf{(c)} By exchanging rows, we move this entry into row $1$.

\textbf{(d)} By scaling row $1$, we turn this entry into $1$.

\textbf{(e)} By adding multiples of row $1$ to the other rows, we ensure that
all other entries in its column are $0$.

\textbf{(f)} We now forget about row $1$ and apply the same algorithm to the
matrix consisting of all other rows, bringing that matrix into RREF.

\textbf{(g)} We end up with a matrix whose row $1$ has a pivot, and whose
remaining rows are in RREF, with all \textbf{their} pivots being further right
than the pivot in row $1$. It remains to ensure that the entries in row $1$
above the pivots are $0$s. To do so, we subtract appropriate multiples of the
pivot rows from row $1$.
\end{theorem}

This is a recursive algorithm, because in step \textbf{(f)}, it calls itself
again. But it calls itself \textbf{for a smaller matrix}, so it will not get
into an infinite loop.

\begin{example}
Let us use this algorithm to transform
\[
A=\left(
\begin{array}
[c]{ccccc}%
0 & 0 & -2 & -1 & -13\\
-1 & -2 & -1 & 1 & -2\\
-1 & -2 & 0 & -1 & -8
\end{array}
\right)
\]
into RREF. (We shall put the entries that we choose in step \textbf{(b)} of
the above algorithm into boxes.)%
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
0 & 0 & -2 & -1 & -13\\
\fbox{$-1$} & -2 & -1 & 1 & -2\\
-1 & -2 & 0 & -1 & -8
\end{array}
\right) \\
&  \overset{\text{exchange rows}}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$-1$} & -2 & -1 & 1 & -2\\
0 & 0 & -2 & -1 & -13\\
-1 & -2 & 0 & -1 & -8
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 1 & -1 & 2\\
0 & 0 & -2 & -1 & -13\\
-1 & -2 & 0 & -1 & -8
\end{array}
\right) \\
&  \overset{\text{add }1\cdot\text{row }1\text{ to row }3}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 1 & -1 & 2\\
0 & 0 & -2 & -1 & -13\\
0 & 0 & 1 & -2 & -6
\end{array}
\right)
\end{align*}
Now, forget about row $1$ and look at the remaining rows:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
0 & 0 & -2 & -1 & -13\\
0 & 0 & \fbox{$1$} & -2 & -6
\end{array}
\right) \\
&  \overset{\text{exchange rows }1\text{ and }2}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
0 & 0 & \fbox{$1$} & -2 & -6\\
0 & 0 & -2 & -1 & -13
\end{array}
\right) \\
&  \overset{\text{add }2\cdot\text{row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
0 & 0 & \fbox{$1$} & -2 & -6\\
0 & 0 & 0 & -5 & -25
\end{array}
\right)  .
\end{align*}
Now, forget about row $1$ and look at the remaining row:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
0 & 0 & 0 & \fbox{$-5$} & -25
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1/5}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\end{align*}
Now, forget about row $1$ and look at the remaining rows, of which there are
none (i.e., they form a $0\times5$-matrix). Since there are none, they are
already in RREF.

Now, this empty matrix is in RREF, so we add the previously removed row back
in again, getting%
\[
\left(
\begin{array}
[c]{ccccc}%
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\]
This is in RREF as well, so we add the previously removed row back in again,
getting%
\[
\left(
\begin{array}
[c]{ccccc}%
0 & 0 & \fbox{$1$} & -2 & -6\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\]
This is almost in RREF, except that the fourth column is a pivot column with a
nonzero non-pivot entry. We fix this by adding $2\cdot$row $2$ to row $1$:%
\[
\left(
\begin{array}
[c]{ccccc}%
0 & 0 & \fbox{$1$} & -2 & -6\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccccc}%
0 & 0 & \fbox{$1$} & 0 & 4\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\]
Now, our matrix is in RREF, so we again add the previously removed row back
in:%
\[
\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 1 & -1 & 2\\
0 & 0 & \fbox{$1$} & 0 & 4\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\]
This is almost in RREF, except that two of the pivots still need to clear out
the first entries of their columns. Again, we achieve this by adding multiples
of rows:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 1 & -1 & 2\\
0 & 0 & \fbox{$1$} & 0 & 4\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  \overset{\text{add }-1\cdot\text{row }2\text{ to row }%
1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 0 & -1 & -2\\
0 & 0 & \fbox{$1$} & 0 & 4\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right) \\
&  \overset{\text{add }1\cdot\text{row }3\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 0 & 0 & 3\\
0 & 0 & \fbox{$1$} & 0 & 4\\
0 & 0 & 0 & \fbox{$1$} & 5
\end{array}
\right)  .
\end{align*}
This is in RREF, so we have brought $A$ to an RREF by EROs.
\end{example}

In practice, when applying this algorithm, it is easiest not to remove the top
row in step \textbf{(f)} and add it back in step \textbf{(g)}, but simply keep
it around remembering that it is \textquotedblleft frozen\textquotedblright%
\ for the time being. It becomes \textquotedblleft unfrozen\textquotedblright%
\ later when the rows below it have already been put into RREF. As long as a
row is frozen, it is ignored by all operations (in particular, it does not get
counted, it does not get exchanged or scaled or added, and it does not get
taken into account when we check if our matrix is in RREF).

\begin{example}
Let us bring the matrix $\left(
\begin{array}
[c]{cccccc}%
0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1 & 0
\end{array}
\right)  $ into RREF:%
\begin{align*}
&  \left(
\begin{array}
[c]{cccccc}%
0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1 & 0
\end{array}
\right) \\
&  \overset{\text{exchange rows }1\text{ and }2}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1 & 0
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \\
0 & 1 & 0 & 1 & 0 & 0 & \\
0 & 0 & 1 & 0 & 1 & 0 & \\
0 & 0 & 0 & 1 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \underset{\text{(frozen rows are not counted)}}{\overset{\text{add }%
-1\cdot\text{row }1\text{ to row }2}{\longrightarrow}}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 1 & 0 & 1 & 0 & \\
0 & 0 & 0 & 1 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 1 & 0 & 1 & 0 & \\
0 & 0 & 0 & 1 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{exchange rows }1\text{ and }2}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{add }-1\cdot\text{row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 1 & \\
0 & 0 & 0 & 0 & 1 & 0 &
\end{array}
\right) \\
&  \overset{\text{exchange rows }1\text{ and }2}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \
\begin{array}
[c]{c}%
\text{The unfrozen part is RREF}\\
\text{(since it is empty).}%
\end{array}
\\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 1 & 0 & \\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{not an RREF!}\\
&  \overset{\text{add }-1\cdot\text{row }3\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 1 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF again}\\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 1 & 0 & 0 & 0 & 0 & \\
0 & 0 & 1 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{not an RREF}\\
&  \overset{\text{add }-1\cdot\text{row }3\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{RREF, done!}%
\end{align*}
Note that we got an identity matrix.

If we instead start with $\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 0
\end{array}
\right)  $, then we don't get the identity matrix, but instead get a matrix
with only $4$ pivots.
\end{example}

This has consequences for the system%
\[
\left\{
\begin{array}
[c]{c}%
x_{2}=0\\
x_{1}+x_{3}=0\\
x_{2}+x_{4}=0\\
x_{3}=1\\
x_{4}=0
\end{array}
\right.  .
\]


\begin{proposition}
Let $A$ be a matrix, and let $A^{\prime}$ be a matrix obtained from $A$ by a
sequence of EROs.

Let $B$ and $B^{\prime}$ be obtained from $A$ and $A^{\prime}$ by removing
some columns (the same for $B$ as for $B^{\prime}$).

Then, $B^{\prime}$ is obtained from $B$ by the same sequence of EROs as
$A^{\prime}$ from $A$.
\end{proposition}

Note, however, that if $A^{\prime}$ is RREF, then $B^{\prime}$ may or may not
be a RREF.

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