\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{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, October 28, 2019 18:00:26}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\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{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[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}}
\allowdisplaybreaks
\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}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\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{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 201-003 Fall 2019 (Darij Grinberg): midterm 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 201-003 Fall 2019 (Darij Grinberg): midterm 1}
\end{center}

\section{Reminders}

\begin{itemize}
\item For any two matrices $A$ and $B$, if the product $AB$ is well-defined,
then%
\begin{align}
\left(  AB\right)  _{i,j}  &  =A_{i,1}B_{1,j}+A_{i,2}B_{2,j}+\cdots
+A_{i,m}B_{m,j}\label{eq.19fla-mt1.reminders.ABij.1}\\
&  =\operatorname*{row}\nolimits_{i}A\cdot\operatorname*{col}\nolimits_{j}B
\label{eq.19fla-mt1.reminders.ABij.2}%
\end{align}
for all indices $i$ and $j$.

\item The transpose $A^{T}$ of an $n\times m$-matrix $A$ is the $m\times
n$-matrix whose entries are $\left(  A^{T}\right)  _{i,j}=A_{j,i}$.

\item A matrix is in \textit{RREF} if and only if it satisfies the following
four conditions:

\begin{itemize}
\item \textbf{RREF0:} Any zero row (= row full of zeros) is below any nonzero
row (= row with at least some nonzero entries).

\item \textbf{RREF1:} In any nonzero row, the first nonzero entry is equal to
$1$. This entry is called the \textit{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{itemize}

For the last exercise:

\begin{itemize}
\item If $n$ is a nonnegative integer, then $\left[  n\right]  $ means the
$n$-element set $\left\{  1,2,\ldots,n\right\}  $.

\item The composition $\alpha\circ\beta$ of two maps $\alpha$ and $\beta$ is
defined by $\left(  \alpha\circ\beta\right)  \left(  x\right)  =\alpha\left(
\beta\left(  x\right)  \right)  $ for all $x$.

\item A \textit{permutation} of $\left[  n\right]  $ means a map from $\left[
n\right]  $ to $\left[  n\right]  $ that is bijective (i.e., both injective
and surjective). Equivalently, it is a map from $\left[  n\right]  $ to
$\left[  n\right]  $ that is invertible (i.e., has an inverse map).

\item The \textit{transposition} $t_{u,v}$ between two distinct elements $u$
and $v$ of $\left[  n\right]  $ is the permutation of $\left[  n\right]  $
that interchanges $u$ with $v$ and leaves all other elements of $\left[
n\right]  $ unchanged.

\item Writing a map $f:\left[  n\right]  \rightarrow\left[  n\right]  $ in
\textit{two-line notation} means writing it as a table of values: $\left(
\begin{array}
[c]{cccc}%
1 & 2 & \cdots & n\\
f\left(  1\right)  & f\left(  2\right)  & \cdots & f\left(  n\right)
\end{array}
\right)  $.
\end{itemize}

\section{Matrix operations}

\begin{exercise}
\label{exe.19fla-mt1.A3B3}For each $n\in\mathbb{N}$, let%
\[
A_{n}=\left(
\begin{array}
[c]{ccccc}%
1 & 0 & 0 & \cdots & 0\\
1 & 1 & 0 & \cdots & 0\\
1 & 1 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 1
\end{array}
\right)
\]
be the lower-triangular $n\times n$-matrix whose entries on and below the
diagonal are all $1$. Let furthermore $B_{n}$ be its transpose (that is,
$B_{n}=\left(  A_{n}\right)  ^{T}$).

\textbf{(a)} Compute $A_{3}B_{3}$ and $B_{3}A_{3}$.

\textbf{(b)} Compute $A_{10}B_{10}$ and $B_{10}A_{10}$. (Feel free to describe
the matrices in words instead of writing down each entry.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.A3B3}.]\textbf{(a)} Multiplying%
\[
A_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 1 & 0\\
1 & 1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{with}\ \ \ \ \ \ \ \ \ \ B_{3}=\left(
A_{3}\right)  ^{T}=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1
\end{array}
\right)  ,
\]
we obtain%
\[
A_{3}B_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 2 & 2\\
1 & 2 & 3
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ B_{3}A_{3}=\left(
\begin{array}
[c]{ccc}%
3 & 2 & 1\\
2 & 2 & 1\\
1 & 1 & 1
\end{array}
\right)  .
\]


\textbf{(b)} We have%
\[
A_{10}B_{10}=\left(
\begin{array}
[c]{cccccccccc}%
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\
1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3\\
1 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4\\
1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5\\
1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 & 6\\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 7 & 7 & 7\\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 8 & 8\\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 9\\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
\end{array}
\right)
\]
and%
\[
B_{10}A_{10}=\left(
\begin{array}
[c]{cccccccccc}%
10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\
9 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\
8 & 8 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\
7 & 7 & 7 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\
6 & 6 & 6 & 6 & 6 & 5 & 4 & 3 & 2 & 1\\
5 & 5 & 5 & 5 & 5 & 5 & 4 & 3 & 2 & 1\\
4 & 4 & 4 & 4 & 4 & 4 & 4 & 3 & 2 & 1\\
3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 & 1\\
2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{array}
\right)  .
\]


More generally, we can compute $A_{n}B_{n}$ and $B_{n}A_{n}$. For this, we
need a piece of notation:

\begin{itemize}
\item If $S$ is any nonempty finite set of real numbers, then let $\min S$
denote the smallest element of $S$.
\end{itemize}

Now, fix $n\in\mathbb{N}$. We claim that%
\begin{align}
A_{n}B_{n}  &  =\left(  \min\left\{  i,j\right\}  \right)  _{1\leq i\leq
n,\ 1\leq j\leq n}\label{sol.19fla-mt1.A3B3.AnBn=}\\
&  =\left(
\begin{array}
[c]{ccccc}%
1 & 1 & 1 & \cdots & 1\\
1 & 2 & 2 & \cdots & 2\\
1 & 2 & 3 & \cdots & 3\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 2 & 3 & \cdots & n
\end{array}
\right) \nonumber
\end{align}
and%
\begin{align}
B_{n}A_{n}  &  =\left(  \min\left\{  n+1-i,n+1-j\right\}  \right)  _{1\leq
i\leq n,\ 1\leq j\leq n}\label{sol.19fla-mt1.A3B3.BnAn=}\\
&  =\left(
\begin{array}
[c]{ccccc}%
n & n-1 & n-2 & \cdots & 1\\
n-1 & n-1 & n-2 & \cdots & 1\\
n-2 & n-2 & n-2 & \cdots & 1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 1
\end{array}
\right)  .\nonumber
\end{align}


\textit{Proof of (\ref{sol.19fla-mt1.A3B3.AnBn=}):} We must prove that
$A_{n}B_{n}=\left(  \min\left\{  i,j\right\}  \right)  _{1\leq i\leq n,\ 1\leq
j\leq n}$. In other words, we must prove that%
\[
\left(  A_{n}B_{n}\right)  _{i,j}=\min\left\{  i,j\right\}  \text{ for each
}i,j\in\left\{  1,2,\ldots,n\right\}  .
\]
So let $i,j\in\left\{  1,2,\ldots,n\right\}  $. Then,
\[
\operatorname{row}_{i}\left(  A_{n}\right)  =\left(  1,1,\ldots,1,0,0,\ldots
,0\right)
\]
(with the first $i$ entries equal to $1$ and the remaining $n-i$ entries equal
to $0$) and
\begin{equation}
\operatorname{row}_{j}\left(  A_{n}\right)  =\left(  1,1,\ldots,1,0,0,\ldots
,0\right)  \label{sol.19fla-mt1.A3B3.BnAn=.pf.1}%
\end{equation}
(with the first $j$ entries equal to $1$ and the remaining $n-j$ entries equal
to $0$). Also, recall that transposing a matrix turns rows into columns (or,
more precisely, the columns of the transpose of a matrix are the transposes of
the rows of the original matrix). Hence, from $B_{n}=\left(  A_{n}\right)
^{T}$, we obtain%
\[
\operatorname{col}_{j}\left(  B_{n}\right)  =\left(  \operatorname{row}%
_{j}\left(  A_{n}\right)  \right)  ^{T}=\left(
\begin{array}
[c]{c}%
1\\
1\\
\vdots\\
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)
\]
(with the first $j$ entries equal to $1$ and the remaining $n-j$ entries equal
to $0$), because of (\ref{sol.19fla-mt1.A3B3.BnAn=.pf.1}).

Now, (\ref{eq.19fla-mt1.reminders.ABij.2}) (applied to $A=A_{n}$ and $B=B_{n}%
$) yields%
\begin{align}
\left(  A_{n}B_{n}\right)  _{i,j}  &  =\underbrace{\operatorname{row}%
_{i}\left(  A_{n}\right)  }_{\substack{=\left(  1,1,\ldots,1,0,0,\ldots
,0\right)  \\\text{(with the first }i\text{ entries}\\\text{equal to
}1\text{)}}}\cdot\underbrace{\operatorname{col}_{j}\left(  B_{n}\right)
}_{\substack{=\left(
\begin{array}
[c]{c}%
1\\
1\\
\vdots\\
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)  \\\text{(with the first }j\text{ entries}\\\text{equal to }1\text{)}%
}}\nonumber\\
&  =\underbrace{\left(  1,1,\ldots,1,0,0,\ldots,0\right)  }%
_{\substack{\text{with the first }i\text{ entries}\\\text{equal to }1}%
}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
1\\
1\\
\vdots\\
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)  }_{\substack{\text{with the first }j\text{ entries}\\\text{equal to
}1}}. \label{sol.19fla-mt1.A3B3.AnBn=.pf.1}%
\end{align}
Multiplying out the right hand side yields a sum of $n$ terms, each of which
is either $1\cdot1$ or $1\cdot0$ or $0\cdot1$ or $0\cdot0$. More precisely,
the first $\min\left\{  i,j\right\}  $ addends in this sum are $1\cdot1$
(because in order to get a $1\cdot1$, you have to multiply one of the first
$i$ entries of $\underbrace{\left(  1,1,\ldots,1,0,0,\ldots,0\right)
}_{\substack{\text{with the first }i\text{ entries}\\\text{equal to }1}}$ with
one of the first $j$ entries of $\underbrace{\left(
\begin{array}
[c]{c}%
1\\
1\\
\vdots\\
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)  }_{\substack{\text{with the first }j\text{ entries}\\\text{equal to
}1}}$, and this is what is happening for the first $\min\left\{  i,j\right\}
$ entries of the product\footnote{whereas from entry $\min\left\{
i,j\right\}  +1$ on, at least one of your factors will be $0$}), while all the
remaining addends have one of the forms $1\cdot0$ and $0\cdot1$ and $0\cdot0$
(we don't care which one, since all these forms evaluate to $0$). Thus, the
whole sum is%
\begin{align*}
&  \underbrace{1\cdot1+1\cdot1+\cdots+1\cdot1}_{\min\left\{  i,j\right\}
\text{ times}}+\underbrace{\left(  \text{a sum of addends of the forms }%
1\cdot0\text{ and }0\cdot1\text{ and }0\cdot0\right)  }_{=0}\\
&  =\underbrace{1\cdot1+1\cdot1+\cdots+1\cdot1}_{\min\left\{  i,j\right\}
\text{ times}}=\min\left\{  i,j\right\}  \cdot1\cdot1=\min\left\{
i,j\right\}  .
\end{align*}
Hence, (\ref{sol.19fla-mt1.A3B3.AnBn=.pf.1}) rewrites as%
\[
\left(  A_{n}B_{n}\right)  _{i,j}=\min\left\{  i,j\right\}  .
\]
This completes our proof of (\ref{sol.19fla-mt1.A3B3.AnBn=}).]

The proof of (\ref{sol.19fla-mt1.A3B3.BnAn=}) is similar, except that we now
have to analyze the product
\begin{align*}
&  \operatorname{row}_{i}\left(  B_{n}\right)  \cdot\operatorname{col}%
_{j}\left(  A_{n}\right) \\
&  =\underbrace{\left(  0,0,\ldots,0,1,1,\ldots,1\right)  }%
_{\substack{\text{with the last }n+1-i\text{ entries}\\\text{equal to }%
1}}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1\\
1\\
\vdots\\
1
\end{array}
\right)  }_{\substack{\text{with the last }n+1-j\text{ entries}\\\text{equal
to }1}}.
\end{align*}

\end{proof}

\section{Gaussian elimination}

\textbf{Note:} When row-reducing a matrix, you have to either show all row
operations or describe them verbally (if they follow a common pattern) and
show the result. You don't need to follow the Gaussian elimination algorithm;
you can use any sequence of row operations that leads to a matrix in
RREF.\footnote{Any given matrix has only one RREF; thus, no matter which way
you get to a RREF, you will always get to the same RREF.} In particular, you
don't need to freeze rows. When solving a system of linear equations, you are
free to use any method.

\begin{exercise}
\label{exe.19fla-mt1.abcd-sys}Solve the system%
\[
\left\{
\begin{array}
[c]{c}%
a+b=c+d\\
a+c=b+d\\
a+d=b+c
\end{array}
\right.
\]
of linear equations in four unknowns $a,b,c,d$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.abcd-sys}.]Here is the
straightforward way of solving this system: Its augmented matrix is%
\[
\left(
\begin{array}
[c]{ccccc}%
1 & 1 & -1 & -1 & 0\\
1 & -1 & 1 & -1 & 0\\
1 & -1 & -1 & 1 & 0
\end{array}
\right)  .
\]
We transform this matrix into RREF by the usual row reduction algorithm:%
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0\\
1 & -1 & 1 & -1 & 0\\
1 & -1 & -1 & 1 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0\\
0 & 2 & -2 & 0 & 0\\
1 & -1 & -1 & 1 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}3}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0\\
0 & 2 & -2 & 0 & 0\\
0 & -2 & 0 & 2 & 0
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$2$} & -2 & 0 & 0 & \\
0 & -2 & 0 & 2 & 0 &
\end{array}
\right) \\
&  \overset{\text{scale }\operatorname{row}1\text{ by }1/2}{\longrightarrow
}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -1 & 0 & 0 & \\
0 & -2 & 0 & 2 & 0 &
\end{array}
\right) \\
&  \overset{\text{add }2\cdot\operatorname{row}1\text{ to }\operatorname{row}%
2}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -1 & 0 & 0 & \\
0 & 0 & -2 & 2 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$-2$} & 2 & 0 &
\end{array}
\right) \\
&  \overset{\text{scale }\operatorname{row}1\text{ by }-1/2}{\longrightarrow
}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & -1 & 0 &
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{now our (non-frozen)
matrix is in RREF}\right) \\
&  \overset{\text{unfreeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -1 & 0 & 0 & \\
0 & 0 & \fbox{$1$} & -1 & 0 &
\end{array}
\right) \\
&  \overset{\text{add }1\cdot\operatorname{row}2\text{ to }\operatorname{row}%
1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & -1 & 0 & \\
0 & 0 & \fbox{$1$} & -1 & 0 &
\end{array}
\right) \\
&  \overset{\text{unfreeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & -1 & -1 & 0\\
0 & \fbox{$1$} & 0 & -1 & 0\\
0 & 0 & \fbox{$1$} & -1 & 0
\end{array}
\right) \\
&  \overset{\text{add }1\cdot\operatorname{row}3\text{ to }\operatorname{row}%
1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & 0 & -2 & 0\\
0 & \fbox{$1$} & 0 & -1 & 0\\
0 & 0 & \fbox{$1$} & -1 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}2\text{ to
}\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 0 & 0 & -1 & 0\\
0 & \fbox{$1$} & 0 & -1 & 0\\
0 & 0 & \fbox{$1$} & -1 & 0
\end{array}
\right)  .
\end{align*}
The resulting matrix is the augmented matrix of the system%
\[
\left\{
\begin{array}
[c]{c}%
a-d=0\\
b-d=0\\
c-d=0
\end{array}
\right.  .
\]
The solutions of this system can be read off from it immediately: The variable
$d$ is a free variable, and the other three variables are given by $a=d$,
$b=d$ and $c=d$. In other words, the solutions of our system are precisely the
$4$-tuples $\left(  a,b,c,d\right)  $ consisting of four equal numbers.

[\textit{Remark:} Here is an easier way to see this, without computing an
RREF: Consider any solution $\left(  a,b,c,d\right)  $ of the system $\left\{
%
\begin{array}
[c]{c}%
a+b=c+d\\
a+c=b+d\\
a+d=b+c
\end{array}
\right.  $. Then, adding together the first two equations of this system, we
find $\left(  a+b\right)  +\left(  a+c\right)  =\left(  c+d\right)  +\left(
b+d\right)  $. This simplifies to $2a+b+c=2d+b+c$. After subtracting $b+c$
from both sides of this, we obtain $2a=2d$. Hence, $a=d$. Likewise, we find
$a=b$ (by adding together the last two equations of the system) and $a=c$ (by
adding together the first and the last equations of the system). Combining
$a=b$ with $a=c$ and $a=d$, we obtain $a=b=c=d$. In other words, the $4$-tuple
$\left(  a,b,c,d\right)  $ consists of four equal numbers. Thus, we have shown
that any solution $\left(  a,b,c,d\right)  $ of our system must be a $4$-tuple
consisting of four equal numbers. Conversely, it is clear that every $4$-tuple
consisting of four equal numbers is a solution of our system. Combining these
observations, we conclude that the solutions of our system are precisely the
$4$-tuples $\left(  a,b,c,d\right)  $ consisting of four equal numbers.]
\end{proof}

\begin{exercise}
\label{exe.19fla-mt1.B6}Let $B_{6}$ be the $6\times6$-matrix%
\[
\left(
\begin{array}
[c]{cccccc}%
1 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 0 & 1
\end{array}
\right)  .
\]
(Its diagonal entries are $1$; its entries just above the diagonal are $1$;
its entry in the bottom-left corner is $1$; all its other entries are $0$.)

Find the RREF of $B_{6}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.B6}.]Let us start bringing $B_{6}$
into RREF using \cite[Method 6.4]{Strickland}:%
\begin{align*}
B_{6}  &  =\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 0 & 1
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}6}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 1\\
0 & -1 & 0 & 0 & 0 & 1
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \\
0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & \\
0 & -1 & 0 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{add }1\cdot\operatorname{row}1\text{ to }\operatorname{row}%
5}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \\
0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & \\
0 & 0 & 1 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & \\
0 & 0 & 1 & 0 & 0 & 1 &
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}4}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 1 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & \\
0 & 0 & 0 & -1 & 0 & 1 &
\end{array}
\right) \\
&  \longrightarrow\cdots.
\end{align*}
At this point it should be clear how the procedure goes on: We pick the
topmost $1$ on the diagonal as pivot; then we clear out the $1$ or the $-1$ in
the last cell of its column by adding either $\left(  -1\right)
\cdot\operatorname{row}1$ or $1\cdot\operatorname{row}1$ to the last row; then
we freeze $\operatorname{row}1$; rinse, repeat. As we keep doing this, the
entries of our matrix on the diagonal and above the diagonal do not change,
whereas the entries below the diagonal become $0$. Let us take a closer look
at the final step of this procedure:\footnote{It is important to keep track of
the last row of the matrix. Every time we pick a new pivot, the column that
contains this pivot has either a $1$ or a $-1$ in the bottommost position,
whereas all other columns except for the last column of the matrix have $0$'s
in their bottommost position. (Thus, the last row of the matrix has only two
nonzero entries.) We clear out the $1$ or the $-1$ in the bottommost position
of the column with the current pivot by adding $\left(  -1\right)
\cdot\operatorname{row}1$ or $1\cdot\operatorname{row}1$ to the last row.
Thus, this $1$ or $-1$ disappears, but the neighboring entry to its right
(previously a $0$) becomes a $-1$ or a $1$ (which will have to be cleared in
the next step). Thus, we can imagine that there is a \textquotedblleft
wandering\textquotedblright\ $1$ in the last row of our matrix, which starts
in the leftmost position and then moves a step to the right every time we
perform a row operation; it also flips its sign when doing so. Thus, after $k$
row operations, it will have flipped its sign $k$ times (so it will equal
$\left(  -1\right)  ^{k}$) and will have taken $k$ steps to the right (so it
will be in the $\left(  k+1\right)  $-st column of the matrix).}
\begin{align*}
\cdots &  \longrightarrow\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 1 & \\
0 & 0 & 0 & 0 & 1 & 1 &
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 0 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 0 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 1 & 0 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 1 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 1 & \\
0 & 0 & 0 & 0 & 0 & 0 &
\end{array}
\right)  .
\end{align*}
At this point, the unfrozen part of our matrix is in RREF, so we unfreeze rows
and clear out the nonzero entries above the pivots. At the end of this
procedure, we obtain the matrix%
\[
\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 1\\
0 & \fbox{$1$} & 0 & 0 & 0 & -1\\
0 & 0 & \fbox{$1$} & 0 & 0 & 1\\
0 & 0 & 0 & \fbox{$1$} & 0 & -1\\
0 & 0 & 0 & 0 & \fbox{$1$} & 1\\
0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right)  ,
\]
which differs from the identity matrix only in its last column. The last
column has a $0$ at the very bottom and then alternates between $1$'s and
$-1$'s (starting with a $1$) as you move upwards. This matrix is in RREF. So
this is the RREF of $B_{6}$.

[\textit{Remark:} For any $n\in\mathbb{N}$, we can define an $n\times
n$-matrix $B_{n}$ similarly to $B_{6}$. We then get a similar answer for the
RREF of $B_{n}$ whenever $n$ is even: namely, the RREF differs from $I_{n}$
only in its last column, which has a $0$ at the very bottom and then
alternates between $1$'s and $-1$'s (starting with a $1$) as you move upwards.
When $n$ is odd, the RREF of $B_{n}$ is simply the identity matrix $I_{n}$.]
\end{proof}

\section{Linear combinations, independence and spanning}

\begin{exercise}
\label{exe.19fla-mt1.lincomb}Let%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
2\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ w=\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  .
\]


\textbf{(a)} Are the vectors $v_{1},v_{2}$ linearly dependent?

\textbf{(b)} Is $w$ a linear combination of $v_{1},v_{2}$ ? (If yes, then find
the coefficients $\lambda_{1},\lambda_{2}$ such that $w=\lambda_{1}%
v_{1}+\lambda_{2}v_{2}$.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.lincomb}.]\textbf{(a)} No. They are
linearly \textbf{independent}.

\textit{Proof.} We must show that any linear relation between $v_{1}$ and
$v_{2}$ is trivial.

So let $\lambda_{1}v_{1}+\lambda_{2}v_{2}=0$ be any linear relation between
$v_{1}$ and $v_{2}$. We must show that it is trivial, i.e., that $\lambda
_{1}=\lambda_{2}=0$.

From $v_{1}=\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  $ and $v_{2}=\left(
\begin{array}
[c]{c}%
2\\
1
\end{array}
\right)  $, we obtain%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}=\lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
2\\
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\lambda_{1}\cdot1+\lambda_{2}\cdot2\\
\lambda_{1}\cdot2+\lambda_{2}\cdot1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\lambda_{1}+2\lambda_{2}\\
2\lambda_{1}+\lambda_{2}%
\end{array}
\right)  ,
\]
so that%
\[
\left(
\begin{array}
[c]{c}%
\lambda_{1}+2\lambda_{2}\\
2\lambda_{1}+\lambda_{2}%
\end{array}
\right)  =\lambda_{1}v_{1}+\lambda_{2}v_{2}=0.
\]
In other words, the two equalities $\lambda_{1}+2\lambda_{2}=0$ and
$2\lambda_{1}+\lambda_{2}=0$ hold. We could now treat these two equalities as
a system of equations and solve it, but it is easier to use a common-sense
strategy: Subtracting the equality $\lambda_{1}+2\lambda_{2}=0$ from the
equality $2\lambda_{1}+\lambda_{2}=0$, we obtain $\lambda_{1}-\lambda_{2}=0$.
Thus, $\lambda_{1}=\lambda_{2}$. Hence, the equality $\lambda_{1}+2\lambda
_{2}=0$ rewrites as $\lambda_{2}+2\lambda_{2}=0$, i.e., as $3\lambda_{2}=0$.
Thus, $\lambda_{2}=0$. Hence, $\lambda_{1}=\lambda_{2}=0$, which is precisely
what we desired to show.

\textbf{(b)} Yes. Indeed, $w=\dfrac{1}{3}v_{1}+\dfrac{1}{3}v_{2}$.

[This is easily seen by eyeballing: Just observe that $v_{1}+v_{2}=\left(
\begin{array}
[c]{c}%
3\\
3
\end{array}
\right)  =3w$. Of course, you can also obtain the answer by solving a system
of linear equations.]
\end{proof}

\begin{exercise}
\label{exe.19fla-mt1.diff-vecs}Let $n\geq2$ be an integer. Recall the vectors
$e_{1},e_{2},\ldots,e_{n}$ in $\mathbb{R}^{n}$ that were defined in Exercise 4
of \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw2s.pdf}{homework set
\#2}. (Thus, $e_{i}=\left(  0,0,\ldots,0,1,0,0,\ldots,0\right)  ^{T}$ with the
$1$ in position $i$.)

Now, consider the $n$ vectors%
\[
e_{1}-e_{2},\ \ e_{2}-e_{3},\ \ e_{3}-e_{4},\ \ \ldots,\ \ e_{n-1}%
-e_{n},\ \ e_{n}-e_{1}.
\]
Let us denote them by $d_{1},d_{2},\ldots,d_{n}$. (Thus, $d_{i}=e_{i}-e_{i+1}$
for each $i\in\left\{  1,2,\ldots,n-1\right\}  $, and $d_{n}=e_{n}-e_{1}$.)

\textbf{(a)} Are these $n$ vectors $d_{1},d_{2},\ldots,d_{n}$ linearly
independent when $n=7$ ?

\textbf{(b)} Do these $n$ vectors $d_{1},d_{2},\ldots,d_{n}$ span
$\mathbb{R}^{n}$ when $n=7$ ?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.diff-vecs}.]We shall ignore the
\textquotedblleft when $n=7$\textquotedblright\ part, since the answers and
the proofs work equally for all values of $n\geq2$.

\textbf{(a)} The $n$ vectors $d_{1},d_{2},\ldots,d_{n}$ are linearly
\textbf{dependent}.

\textit{Proof.} The following is a nontrivial linear relation between them:%
\begin{align*}
&  1d_{1}+1d_{2}+\cdots+1d_{n}\\
&  =d_{1}+d_{2}+\cdots+d_{n}\\
&  =\left(  e_{1}-e_{2}\right)  +\left(  e_{2}-e_{3}\right)  +\cdots+\left(
e_{n-1}-e_{n}\right)  +\left(  e_{n}-e_{1}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }d_{i}=e_{i}-e_{i+1}\text{ for each
}i\in\left\{  1,2,\ldots,n-1\right\}  \text{, and }d_{n}=e_{n}-e_{1}\right) \\
&  =0\ \ \ \ \ \ \ \ \ \ \left(  \text{since all addends and subtrahends
cancel}\right)  .
\end{align*}


\textbf{(b)} The $n$ vectors $d_{1},d_{2},\ldots,d_{n}$ do not span
$\mathbb{R}^{n}$.

\textit{First proof.} A vector $w\in\mathbb{R}^{n}$ shall be called
\textit{zero-sum} if the sum of its entries is $0$. (Thus, a vector $w=\left(
w_{1},w_{2},\ldots,w_{n}\right)  ^{T}\in\mathbb{R}^{n}$ is zero-sum if and
only if $w_{1}+w_{2}+\cdots+w_{n}=0$.) Each of the vectors $d_{1},d_{2}%
,\ldots,d_{n}$ is zero-sum (since one of its entries is $1$, another of its
entries is $-1$, and all the remaining entries are $0$). Thus, any linear
combination of $d_{1},d_{2},\ldots,d_{n}$ is zero-sum as well (because it is
easy to see that any linear combination of zero-sum vectors is again
zero-sum). But there are certainly vectors in $\mathbb{R}^{n}$ that are not
zero-sum (for example, $e_{1}$). Thus, there are vectors in $\mathbb{R}^{n}$
that are not linear combinations of $d_{1},d_{2},\ldots,d_{n}$. In other
words, $d_{1},d_{2},\ldots,d_{n}$ do not span $\mathbb{R}^{n}$.

\textit{Second proof.} We must prove that the $n$ vectors $d_{1},d_{2}%
,\ldots,d_{n}$ do not span $\mathbb{R}^{n}$. Indeed, assume the contrary.
Thus, the $n$ vectors $d_{1},d_{2},\ldots,d_{n}$ span $\mathbb{R}^{n}$. Hence,
\cite[Proposition 10.12 (b)]{Strickland} (or, equivalently, Proposition 1.2.7
\textbf{(b)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{the notes
from 2019-10-09}) yields that the list $\left(  d_{1},d_{2},\ldots
,d_{n}\right)  $ is a basis of $\mathbb{R}^{n}$. Thus, in particular,
$d_{1},d_{2},\ldots,d_{n}$ are linearly independent. But this contradicts our
result from solving part \textbf{(a)} of this exercise. This contradiction
shows that our assumption was false. Hence, part \textbf{(b)} is solved.
\end{proof}

\section{Matrix inversion and invertibility}

\begin{exercise}
\label{exe.19fla-mt1.invert-lt2}Let $A$ be the $2\times2$-matrix $\left(
\begin{array}
[c]{cc}%
1 & 0\\
a & 1
\end{array}
\right)  $, where $a$ is any real. Compute the inverse $A^{-1}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.invert-lt2}.]The inverse of $A$
always exists (i.e., the matrix $A$ is invertible), and equals%
\[
A^{-1}=\left(
\begin{array}
[c]{cc}%
1 & 0\\
-a & 1
\end{array}
\right)  .
\]


\textit{Proof.} There are many ways to find this. The simplest one is probably
using our method for finding inverses via row-reduction (Theorem 1.3.5 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16}):%
\[
\left[  A\mid I_{2}\right]  =\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 1 & 0\\
a & 1 & 0 & 1
\end{array}
\right)  \overset{\text{add }-a\cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 1 & 0\\
0 & 1 & -a & 1
\end{array}
\right)  =\left[  I_{2}\mid\left(
\begin{array}
[c]{cc}%
1 & 0\\
-a & 1
\end{array}
\right)  \right]
\]
(that's it, we're done).

Alternatively, you can just \textquotedblleft guess\textquotedblright\ that
the inverse should be $\left(
\begin{array}
[c]{cc}%
1 & 0\\
-a & 1
\end{array}
\right)  $, and then verify this by checking that $\left(
\begin{array}
[c]{cc}%
1 & 0\\
-a & 1
\end{array}
\right)  \cdot A=I_{2}$ and $A\cdot\left(
\begin{array}
[c]{cc}%
1 & 0\\
-a & 1
\end{array}
\right)  =I_{2}$. (By some results we proved in class, it suffices to verify
only one of these two equalities.)
\end{proof}

\begin{exercise}
\label{exe.19fla-mt1.which-invertible}Which of the following matrices are invertible?

\vspace{0.8305pc}

\textbf{(a)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 1 & 0\\
0 & 1 & 0
\end{array}
\right)  $.$\qquad\qquad$\textbf{(b)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 1 & 0\\
0 & 1 & 1
\end{array}
\right)  $.$\qquad\qquad$\textbf{(c)} $\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
0 & 0 & 0 & 5\\
0 & 0 & 0 & 6\\
0 & 0 & 0 & 7
\end{array}
\right)  $.

\vspace{0.8305pc}

\textbf{(d)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 1 & 0
\end{array}
\right)  $.$\qquad\qquad$\textbf{(e)} $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
4 & 5 & 6\\
7 & 8 & 9
\end{array}
\right)  $.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.which-invertible}.]\textbf{(a)} This
matrix is \textbf{not invertible}.

\textit{Proof.} Denote the columns of this matrix by $v_{1},v_{2},v_{3}$ (from
first to last). Then, $v_{3}=0$; in other words, $0v_{1}+0v_{2}+1v_{3}=0$.
This is a nontrivial relation between the columns of this matrix. Thus, the
columns of this matrix are linearly dependent. Hence, the matrix cannot be
invertible (because if it was invertible, then the Inverse Matrix Theorem
(Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16})\footnote{More specifically, we are using the implication
\textbf{(k)} $\Longrightarrow$ \textbf{(b)} of the Inverse Matrix Theorem.}
would show that its columns are linearly independent).

\bigskip

\textbf{(b)} This matrix is \textbf{invertible}.

\textit{Proof.} It is easy to see that the RREF of this matrix is $I_{3}$
(indeed, row-reduction will get rid of the two $1$'s below the diagonal
without disturbing any other entries of the matrix). Thus, the matrix can be
row-reduced to $I_{3}$. Hence, the Inverse Matrix Theorem (Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16})\footnote{More specifically, we are using the implication
\textbf{(a)} $\Longrightarrow$ \textbf{(k)} of the Inverse Matrix Theorem.}
shows that it is invertible.

\bigskip

\textbf{(c)} This matrix is \textbf{not invertible}.

\textit{Proof.} Let $A$ be this matrix. Denote the columns of the matrix
$A^{T}$ by $v_{1},v_{2},v_{3},v_{4}$ (from first to last). Then,
$6v_{2}=5v_{3}$ (since $v_{2}=\left(  0,0,0,5\right)  ^{T}$ and $v_{3}=\left(
0,0,0,6\right)  ^{T}$). In other words, $0v_{1}+6v_{2}+\left(  -5\right)
v_{3}+0v_{4}=0$. This is a nontrivial relation between the columns of the
matrix $A^{T}$. Thus, the columns of $A^{T}$ are linearly dependent. Hence,
the matrix $A$ cannot be invertible (because if it was invertible, then the
Inverse Matrix Theorem (Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16})\footnote{More specifically, we are using the implication
\textbf{(k)} $\Longrightarrow$ \textbf{(f)} of the Inverse Matrix Theorem.}
would show that the columns of $A^{T}$ are linearly independent).

\bigskip

\textbf{(d)} This matrix is \textbf{not invertible}.

\textit{Proof.} Corollary 1.2.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16} shows that if an $n\times m$-matrix has an inverse, then
$n=m$. In other words, if a matrix has an inverse, then it is a square matrix.
Hence, our matrix does not have an inverse (since it is not a square matrix).
In other words, it is not invertible.

\bigskip

\textbf{(e)} This matrix is \textbf{not invertible}.

\textit{Proof.} Denote the columns of this matrix by $v_{1},v_{2},v_{3}$ (from
first to last). Then, $v_{1}+v_{3}=2v_{2}$ (because each entry in the middle
column of the matrix is the average of its left and right neighbors); in other
words, $1v_{1}+\left(  -2\right)  v_{2}+1v_{3}=0$. This is a nontrivial
relation between the columns of this matrix. Thus, the columns of this matrix
are linearly dependent. Hence, the matrix cannot be invertible (because if it
was invertible, then the Inverse Matrix Theorem (Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16})\footnote{More specifically, we are using the implication
\textbf{(k)} $\Longrightarrow$ \textbf{(b)} of the Inverse Matrix Theorem.}
would show that its columns are linearly independent).
\end{proof}

\section{Permutations}

\begin{exercise}
\label{exe.19fla-mt1.perms1}\textbf{(a)} Write the three transpositions
$t_{1,2}$, $t_{1,3}$ and $t_{2,3}$ of $\left[  3\right]  $ in two-line notation.

\textbf{(b)} Compute $t_{1,2}\circ t_{2,3}$.

\textbf{(c)} Compute $\operatorname*{sign}\left(  t_{1,2}\circ t_{2,3}\right)
$.

\textbf{(d)} Which of the maps (written in two-line notation as)%
\[
\alpha=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 1 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \beta=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 3 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \gamma=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 1 & 3
\end{array}
\right)
\]
are permutations of $\left[  3\right]  $ ?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt1.perms1}.]\textbf{(a)} We have%
\[
t_{1,2}=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 1 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ t_{1,3}=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 2 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ t_{2,3}=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 3 & 2
\end{array}
\right)  .
\]


\textbf{(b)} We have
\[
t_{1,2}\circ t_{2,3}=\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 3 & 1
\end{array}
\right)  .
\]
This is because%
\begin{align*}
\left(  t_{1,2}\circ t_{2,3}\right)  \left(  1\right)   &  =t_{1,2}\left(
\underbrace{t_{2,3}\left(  1\right)  }_{=1}\right)  =t_{1,2}\left(  1\right)
=2;\\
\left(  t_{1,2}\circ t_{2,3}\right)  \left(  2\right)   &  =t_{1,2}\left(
\underbrace{t_{2,3}\left(  2\right)  }_{=3}\right)  =t_{1,2}\left(  3\right)
=3;\\
\left(  t_{1,2}\circ t_{2,3}\right)  \left(  3\right)   &  =t_{1,2}\left(
\underbrace{t_{2,3}\left(  3\right)  }_{=2}\right)  =t_{1,2}\left(  2\right)
=1.
\end{align*}


\textbf{(c)} One way to do this is by counting the inversions: The inversions
of $t_{1,2}\circ t_{2,3}$ are $\left(  1,2\right)  $ and $\left(  1,3\right)
$ (as you can easily see from the two-line notation of $t_{1,2}\circ t_{2,3}%
$). Thus, $t_{1,2}\circ t_{2,3}$ has $2$ inversions. In other words,
$\ell\left(  t_{1,2}\circ t_{2,3}\right)  =2$. Hence, the definition of sign
yields $\operatorname*{sign}\left(  t_{1,2}\circ t_{2,3}\right)  =\left(
-1\right)  ^{\ell\left(  t_{1,2}\circ t_{2,3}\right)  }=\left(  -1\right)
^{2}=1$.

An alternative way to do this is by recalling the following two facts:

\begin{enumerate}
\item We have $\operatorname*{sign}\left(  \sigma\circ t_{p,q}\right)
=-\operatorname*{sign}\left(  \sigma\right)  $ for any permutation $\sigma$ of
$\left[  n\right]  $ and any two distinct elements $p$ and $q$ of $\left[
n\right]  $. (This is part of the Corollary in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the notes
from 2019-10-23}.)

\item We have $\operatorname*{sign}\left(  t_{p,q}\right)  =-1$ for any two
distinct elements $p$ and $q$ of $\left[  n\right]  $. (This is a Proposition
in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the notes
from 2019-10-23}.)
\end{enumerate}

Applying fact 2 to $p=1$ and $q=2$, we find $\operatorname*{sign}\left(
t_{1,2}\right)  =-1$. Now, applying fact 1 to $\sigma=t_{1,2}$, $p=2$ and
$q=3$, we find $\operatorname*{sign}\left(  t_{1,2}\circ t_{2,3}\right)
=-\underbrace{\operatorname*{sign}\left(  t_{1,2}\right)  }_{=-1}=-\left(
-1\right)  =1$. Thus, part \textbf{(c)} is solved again.

\textbf{(d)} The maps $\alpha$ and $\beta$ are permutations (indeed, they are
both injective and surjective), whereas the map $\gamma$ is not a permutation
(indeed, $\gamma\left(  1\right)  =3=\gamma\left(  3\right)  $ shows that
$\gamma$ is not injective, and thus $\gamma$ is not bijective, so that
$\gamma$ cannot be a permutation).
\end{proof}

\begin{noncompile}
\begin{exercise}
Compute the sign of the permutation $\alpha$ of $\left[  9\right]  $ written
in two-line notation as follows:%
\[
\left(
\begin{array}
[c]{ccccccccc}%
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5
\end{array}
\right)  .
\]

\end{exercise}
\end{noncompile}

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