\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=Sunday, October 27, 2019 01:38:20}
%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 training 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Matrix operations}

\begin{exercise}
\label{exe.some-products.mt1p}\textbf{(a)} Let $A_{3}=\left(
\begin{array}
[c]{ccc}%
0 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 0
\end{array}
\right)  $ and $B_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 1
\end{array}
\right)  $. (These matrices are filled in \textquotedblleft checkerboard
patterns\textquotedblright: Entries that are $0$ alternate with entries that
are $1$.)

Compute $A_{3}^{2}$, $B_{3}^{2}$, $A_{3}B_{3}$ and $B_{3}A_{3}$.

\textbf{(b)} Let $A_{4}=\left(
\begin{array}
[c]{cccc}%
0 & 1 & 0 & 1\\
1 & 0 & 1 & 0\\
0 & 1 & 0 & 1\\
1 & 0 & 1 & 0
\end{array}
\right)  $ and $B_{4}=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 1 & 0\\
0 & 1 & 0 & 1\\
1 & 0 & 1 & 0\\
0 & 1 & 0 & 1
\end{array}
\right)  $. (These follow the same patterns as $A_{3}$ and $B_{3}$.)

Compute $A_{4}^{2}$, $B_{4}^{2}$, $A_{4}B_{4}$ and $B_{4}A_{4}$.

Now, let us generalize:

For any positive integer $n$, define two \textquotedblleft
checkerboard-pattern\textquotedblright\ $n\times n$-matrices $A_{n}$ and
$B_{n}$ by%
\[
A_{n}=\left(  \left(  i+j\right)  \%2\right)  _{1\leq i\leq n,\ 1\leq j\leq
n},\ \ \ \ \ \ \ \ \ \ B_{n}=\left(  \left(  i+j-1\right)  \%2\right)  _{1\leq
i\leq n,\ 1\leq j\leq n},
\]
where $k\%2$ denotes the remainder left when $k$ is divided by $2$ (so
$k\%2=1$ when $k$ is odd, and $k\%2=0$ when $k$ is even).

(This is just a formal way to define two matrices that are filled in the same
checkerboard way as $A_{3}$ and $B_{3}$ (or as $A_{4}$ and $B_{4}$).)

\textbf{(c)} Prove that each \textbf{even} $n\in\mathbb{N}$ satisfies
$A_{n}^{2}=B_{n}^{2}$ and $A_{n}B_{n}=B_{n}A_{n}$.

\textbf{(d)} Prove that each \textbf{odd} $n\geq3$ satisfies $A_{n}B_{n}\neq
B_{n}A_{n}$.
\end{exercise}

\section{Gaussian elimination}

\begin{exercise}
\label{exe.linsys.1361015.mt1p}Consider the system%
\[
\left\{
\begin{array}
[c]{l}%
a+b+c+d=e\\
a+2b+3c+4d=5e\\
a+3b+6c+10d=15e
\end{array}
\right.
\]
of linear equations in five unknowns $a,b,c,d,e$.

\textbf{(a)} Find the augmented matrix corresponding to this system.

\textbf{(b)} Find the RREF of this matrix.

\textbf{(c)} Solve the system.
\end{exercise}

\begin{exercise}
\label{exe.rref.A7A8}\textbf{(a)} Let $A_{7}$ be the $7\times7$-matrix%
\[
\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 0 & 0 & 0 & 0 & 1\\
1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1
\end{array}
\right)  .
\]
(Its diagonal entries are $1$; its entries just below the diagonal are $1$;
its entry in the top-right corner is $1$; all its other entries are $0$.)

Find the RREF of $A_{7}$.

\textbf{(b)} Let $A_{8}$ be the $8\times8$-matrix%
\[
\left(
\begin{array}
[c]{cccccccc}%
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1
\end{array}
\right)  .
\]
(It is given by the same rule as $A_{7}$, except for having one more row and column.)

Find the RREF of $A_{8}$.
\end{exercise}

\begin{exercise}
\label{exe.Ux=b.backsub.1}Let $U=\left(
\begin{array}
[c]{cccc}%
6 & 3 & -2 & 5\\
0 & 0 & -1 & 2\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0
\end{array}
\right)  $.

\textbf{(a)} Find all column vectors $x\in\mathbb{R}^{4}$ satisfying $Ux=b$,
where $b=\left(
\begin{array}
[c]{c}%
1\\
5\\
2\\
0
\end{array}
\right)  $.

\textbf{(b)} Find all column vectors $x\in\mathbb{R}^{4}$ satisfying
$Ux=b^{\prime}$, where $b^{\prime}=\left(
\begin{array}
[c]{c}%
1\\
5\\
2\\
1
\end{array}
\right)  $.

\textbf{(c)} Find all column vectors $x\in\mathbb{R}^{4}$ satisfying $Ux=x$.
\end{exercise}

\begin{noncompile}
This is 16f/hw2s/exe1.
\end{noncompile}

\section{Linear combinations, independence and spanning}

\begin{exercise}
\label{exe.bases.fi=ei+ei+1}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}.

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 $f_{1},f_{2},\ldots,f_{n}$. (Thus, $f_{i}=e_{i}+e_{i+1}$
for each $i\in\left\{  1,2,\ldots,n-1\right\}  $, and $f_{n}=e_{n}+e_{1}$.)

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

\textbf{(b)} Are these $n$ vectors $f_{1},f_{2},\ldots,f_{n}$ linearly
independent when $n=8$ ?

\textbf{(c)} Do these $n$ vectors $f_{1},f_{2},\ldots,f_{n}$ span
$\mathbb{R}^{n}$ when $n=7$ ?

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

\begin{exercise}
\label{exe.lincd.nxnmatsNESW}Fix an integer $n\geq3$. Consider the following
four $n\times n$-matrices:

\begin{itemize}
\item The $n\times n$-matrix $N$ has all entries in its $1$-st row equal to
$1$, while all other entries are $0$.

\item The $n\times n$-matrix $E$ has all entries in its $n$-th column equal to
$1$, while all other entries are $0$.

\item The $n\times n$-matrix $S$ has all entries in its $n$-th row equal to
$1$, while all other entries are $0$.

\item The $n\times n$-matrix $W$ has all entries in its $1$-st column equal to
$1$, while all other entries are $0$.
\end{itemize}

For example, for $n=3$, these matrices look as follows:%
\begin{align*}
N  &  =\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 0 & 0\\
0 & 0 & 0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ E=\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & 0 & 1\\
0 & 0 & 1
\end{array}
\right)  ,\\
S  &  =\left(
\begin{array}
[c]{ccc}%
0 & 0 & 0\\
0 & 0 & 0\\
1 & 1 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ W=\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 0 & 0\\
1 & 0 & 0
\end{array}
\right)  .
\end{align*}


(For $n=2$, these are precisely the matrices $N,E,S,W$ from Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw2s.pdf}{homework set \#2}.
But here we are assuming $n\geq3$.)

\textbf{(a)} Is the identity matrix $I_{n}$ a linear combination of $N,E,S,W$ ?

\textbf{(b)} Are $N,E,S,W$ linearly dependent?
\end{exercise}

\begin{noncompile}
\textbf{(a)} No, because the $\left(  2,2\right)  $-th entry is always $0$.

\textbf{(b)} No, because any linear combination has its coefficients reflected
in some cells.
\end{noncompile}

\section{Matrix inversion and invertibility}

\begin{exercise}
\label{exe.inverse.str-up-tri-4}Let $A$ be the $4\times4$-matrix $\left(
\begin{array}
[c]{cccc}%
1 & a & b & c\\
0 & 1 & b^{\prime} & c^{\prime}\\
0 & 0 & 1 & c^{\prime\prime}\\
0 & 0 & 0 & 1
\end{array}
\right)  $, where $a,b,c,b^{\prime},c^{\prime},c^{\prime\prime}$ are arbitrary
reals. Compute the inverse $A^{-1}$.
\end{exercise}

\begin{exercise}
\label{exe.inverse.which.mt1p}Which of the following matrices are invertible?

\vspace{0.8212pc}

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

\vspace{0.815pc}

\textbf{(d)} $\left(
\begin{array}
[c]{ccc}%
1 & 4 & 9\\
5 & -1 & 4
\end{array}
\right)  $.

\vspace{0.8212pc}

[\textbf{Hint:} These can be solved without paper.]
\end{exercise}

\begin{exercise}
\label{exe.inverse.transpose}Let $n$ be a nonnegative integer, and let $A$ be
an invertible $n\times n$-matrix. Prove that its transpose $A^{T}$ is also
invertible, and its inverse is $\left(  A^{T}\right)  ^{-1}=\left(
A^{-1}\right)  ^{T}$.

[\textbf{Hint:} By the definition of \textquotedblleft
inverse\textquotedblright, this means showing that $A^{T}\left(
A^{-1}\right)  ^{T}=I_{n}$ and $\left(  A^{-1}\right)  ^{T}A^{T}=I_{n}$. Show this.]
\end{exercise}

\section{Permutations}

Recall that we are using $\left[  n\right]  $ to denote the $n$-element set
$\left\{  1,2,\ldots,n\right\}  $ whenever $n$ is a nonnegative integer.

\begin{exercise}
\label{exe.perms.compos1.mt1p}Consider three maps $\alpha,\beta,\gamma$ from
$\left[  4\right]  $ to $\left[  4\right]  $ given in two-line notation as
follows:%
\[
\alpha=\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
2 & 4 & 1 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \beta=\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
3 & 4 & 1 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \gamma=\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
3 & 4 & 1 & 2
\end{array}
\right)  .
\]


\textbf{(a)} Which of $\alpha$, $\beta$ and $\gamma$ are permutations?

\textbf{(b)} Express $\alpha\circ\beta$ and $\beta\circ\alpha$ and
$\gamma\circ\gamma$ in two-line notation.

\textbf{(c)} Compute the signs of all permutations among $\alpha$, $\beta$ and
$\gamma$.
\end{exercise}

\newpage

\section{Solutions}

The following solutions are a bit rough at some places, but they have enough
detail to get full scores.

Some of these solutions use tricks instead of systematic methods. You are free
to use the methods -- but the tricks are often faster and reveal some ideas
that you would have missed if you just followed the methods.

\begin{proof}
[Solution to Exercise \ref{exe.some-products.mt1p}.]Recall the following fact
(\cite[Proposition 2.19 \textbf{(b)}]{lina}): If $A$ is an $n\times m$-matrix
and $B$ is an $m\times p$-matrix, then%
\[
\left(  AB\right)  _{i,j}=\operatorname{row}_{i}A\cdot\operatorname{col}%
_{j}B\ \ \ \ \ \ \ \ \ \ \text{for any }i\in\left\{  1,2,\ldots,n\right\}
\text{ and }j\in\left\{  1,2,\ldots,p\right\}  .
\]
Thus, in order to find the product $AB$, we need to multiply each row of $A$
with each column of $B$. This is particularly easy when $A$ has few different
rows and $B$ has few different columns. And this is exactly the situation we
have with our \textquotedblleft checkerboard pattern\textquotedblright\ matrices:

\textbf{(b)} The matrix $A_{4}$ has only $2$ different rows: Namely, all its
odd rows are $\left(
\begin{array}
[c]{cccc}%
0 & 1 & 0 & 1
\end{array}
\right)  $, and all its even rows are $\left(
\begin{array}
[c]{cccc}%
1 & 0 & 1 & 0
\end{array}
\right)  $. Likewise, all the odd columns of $B_{4}$ are $\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  $, and all even columns of $B_{4}$ are $\left(
\begin{array}
[c]{c}%
0\\
1\\
0\\
1
\end{array}
\right)  $. Thus, in order to find $A_{4}B_{4}$, we only need to compute $4$
different products:%
\begin{align*}
\underbrace{\left(
\begin{array}
[c]{cccc}%
0 & 1 & 0 & 1
\end{array}
\right)  }_{\text{an odd row of }A_{4}}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  }_{\text{an odd column of }B_{4}}  &
=0;\ \ \ \ \ \ \ \ \ \ \ \ \ \underbrace{\left(
\begin{array}
[c]{cccc}%
0 & 1 & 0 & 1
\end{array}
\right)  }_{\text{an odd row of }A_{4}}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
0\\
1\\
0\\
1
\end{array}
\right)  }_{\text{an even column of }B_{4}}=2;\\
& \\
\underbrace{\left(
\begin{array}
[c]{cccc}%
1 & 0 & 1 & 0
\end{array}
\right)  }_{\text{an even row of }A_{4}}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  }_{\text{an odd column of }B_{4}}  &
=2;\ \ \ \ \ \ \ \ \ \ \ \ \ \underbrace{\left(
\begin{array}
[c]{cccc}%
1 & 0 & 1 & 0
\end{array}
\right)  }_{\text{an even row of }A_{4}}\cdot\underbrace{\left(
\begin{array}
[c]{c}%
0\\
1\\
0\\
1
\end{array}
\right)  }_{\text{an even column of }B_{4}}=0,
\end{align*}
and place them in the appropriate cells of $A_{4}B_{4}$. Hence, we obtain
\[
A_{4}B_{4}=\left(
\begin{array}
[c]{cccc}%
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0
\end{array}
\right)  .
\]
Similarly,%
\[
B_{4}A_{4}=\left(
\begin{array}
[c]{cccc}%
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ \ A_{4}^{2}=\left(
\begin{array}
[c]{cccc}%
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ B_{4}^{2}=\left(
\begin{array}
[c]{cccc}%
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2\\
2 & 0 & 2 & 0\\
0 & 2 & 0 & 2
\end{array}
\right)  .
\]


\textbf{(a)} This is similar to our solution of part \textbf{(b)}. The result
is%
\begin{align*}
A_{3}B_{3}  &  =\left(
\begin{array}
[c]{ccc}%
0 & 1 & 0\\
2 & 0 & 2\\
0 & 1 & 0
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ \ B_{3}A_{3}=\left(
\begin{array}
[c]{ccc}%
0 & 2 & 0\\
1 & 0 & 1\\
0 & 2 & 0
\end{array}
\right)  ;\\
& \\
A_{3}^{2}  &  =\left(
\begin{array}
[c]{ccc}%
1 & 0 & 1\\
0 & 2 & 0\\
1 & 0 & 1
\end{array}
\right)  ;\ \ \ \ \ \ \ \ \ \ B_{3}^{2}=\left(
\begin{array}
[c]{ccc}%
2 & 0 & 2\\
0 & 1 & 0\\
2 & 0 & 2
\end{array}
\right)  .
\end{align*}


\textbf{(c)} Let $n\in\mathbb{N}$ be even. As in part \textbf{(b)}, we observe
that each odd row of $A_{n}$ is $\left(
\begin{array}
[c]{cccccc}%
0 & 1 & 0 & 1 & \cdots & 1
\end{array}
\right)  $ (with $n$ entries, and the last entry being $1$ because $n$ is
even), and each even row of $A_{n}$ is $\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 1 & 0 & \cdots & 0
\end{array}
\right)  $ (with $n$ entries, and the last entry being $0$ because $n$ is
even). Something similar holds for the columns of $B_{n}$. Thus, we can find
$A_{n}B_{n}$ by computing only the four products%
\begin{align*}
\left(
\begin{array}
[c]{cccccc}%
0 & 1 & 0 & 1 & \cdots & 1
\end{array}
\right)  \cdot\left(
\begin{array}
[c]{c}%
0\\
1\\
0\\
1\\
\vdots\\
1
\end{array}
\right)   &  =n/2;\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cccccc}%
0 & 1 & 0 & 1 & \cdots & 1
\end{array}
\right)  \cdot\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0\\
\vdots\\
0
\end{array}
\right)  =0;\\
& \\
\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 1 & 0 & \cdots & 0
\end{array}
\right)  \cdot\left(
\begin{array}
[c]{c}%
0\\
1\\
0\\
1\\
\vdots\\
1
\end{array}
\right)   &  =0;\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cccccc}%
1 & 0 & 1 & 0 & \cdots & 0
\end{array}
\right)  \cdot\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0\\
\vdots\\
0
\end{array}
\right)  =n/2
\end{align*}
(where each of the vectors has $n$ entries). We thus obtain%
\[
A_{n}B_{n}=\left(
\begin{array}
[c]{ccccccc}%
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0
\end{array}
\right)
\]
(note the chessboard pattern again!). Similarly,%
\begin{align*}
B_{n}A_{n}  &  =\left(
\begin{array}
[c]{ccccccc}%
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0
\end{array}
\right)  ;\\
& \\
A_{n}^{2}  &  =\left(
\begin{array}
[c]{ccccccc}%
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2
\end{array}
\right)  ;\\
& \\
B_{n}^{2}  &  =\left(
\begin{array}
[c]{ccccccc}%
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
n/2 & 0 & n/2 & 0 & \cdots & n/2 & 0\\
0 & n/2 & 0 & n/2 & \cdots & 0 & n/2
\end{array}
\right)  .
\end{align*}
Thus, $A_{n}B_{n}=B_{n}A_{n}$ and $A_{n}^{2}=B_{n}^{2}$.

\textbf{(d)} Let $n\geq3$ be odd. Then, the same reasoning that we used in
part \textbf{(c)} reveals that
\begin{align*}
A_{n}B_{n}  &  =\left(
\begin{array}
[c]{ccccccc}%
0 & \left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & \cdots & 0 & \left(
n-1\right)  /2\\
\left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & 0 & \cdots & \left(
n+1\right)  /2 & 0\\
0 & \left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & \cdots & 0 & \left(
n-1\right)  /2\\
\left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & 0 & \cdots & \left(
n+1\right)  /2 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & \left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & \cdots & 0 & \left(
n-1\right)  /2\\
\left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & 0 & \cdots & \left(
n+1\right)  /2 & 0
\end{array}
\right) \\
&  \text{and}\\
B_{n}A_{n}  &  =\left(
\begin{array}
[c]{ccccccc}%
0 & \left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & \cdots & 0 & \left(
n+1\right)  /2\\
\left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & 0 & \cdots & \left(
n-1\right)  /2 & 0\\
0 & \left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & \cdots & 0 & \left(
n+1\right)  /2\\
\left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & 0 & \cdots & \left(
n-1\right)  /2 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & \left(  n+1\right)  /2 & 0 & \left(  n+1\right)  /2 & \cdots & 0 & \left(
n+1\right)  /2\\
\left(  n-1\right)  /2 & 0 & \left(  n-1\right)  /2 & 0 & \cdots & \left(
n-1\right)  /2 & 0
\end{array}
\right)  .
\end{align*}
These two matrices clearly differ in their $\left(  1,2\right)  $-entry
(namely, $A_{n}B_{n}$ has $\left(  1,2\right)  $-entry $\left(  n-1\right)
/2$, while $B_{n}A_{n}$ has $\left(  1,2\right)  $-entry $\left(  n+1\right)
/2$). Thus, they are distinct. In other words, $A_{n}B_{n}\neq B_{n}A_{n}$.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.linsys.1361015.mt1p}.]\textbf{(a)} The system%
\[
\left\{
\begin{array}
[c]{l}%
a+b+c+d=e\\
a+2b+3c+4d=5e\\
a+3b+6c+10d=15e
\end{array}
\right.
\]
can be rewritten as%
\[
\left\{
\begin{array}
[c]{l}%
a+b+c+d+\left(  -1\right)  e=0\\
a+2b+3c+4d+\left(  -5\right)  e=0\\
a+3b+6c+10d+\left(  -15\right)  e=0
\end{array}
\right.  .
\]
Hence, its augmented matrix is%
\[
A:=\left(
\begin{array}
[c]{cccccc}%
1 & 1 & 1 & 1 & -1 & 0\\
1 & 2 & 3 & 4 & -5 & 0\\
1 & 3 & 6 & 10 & -15 & 0
\end{array}
\right)  .
\]
(Don't let the look of the system fool you into saying that the augmented
matrix is $\left(
\begin{array}
[c]{ccccc}%
1 & 1 & 1 & 1 & 1\\
1 & 2 & 3 & 4 & 5\\
1 & 3 & 6 & 10 & 15
\end{array}
\right)  $ ! The expressions $e$, $5e$ and $15e$ on the right hand sides of
the equations are not constants!)

\textbf{(b)} Let us transform $A$ into RREF using \cite[Method 6.4]%
{Strickland}:\footnote{As usual, pivots are boxed.}%
\begin{align*}
A  &  =\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0\\
1 & 2 & 3 & 4 & -5 & 0\\
1 & 3 & 6 & 10 & -15 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0\\
0 & 1 & 2 & 3 & -4 & 0\\
1 & 3 & 6 & 10 & -15 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}3}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0\\
0 & 1 & 2 & 3 & -4 & 0\\
0 & 2 & 5 & 9 & -14 & 0
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 3 & -4 & 0 & \\
0 & 2 & 5 & 9 & -14 & 0 &
\end{array}
\right) \\
&  \underset{\text{(keep in mind: frozen rows are not counted!)}%
}{\overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 3 & -4 & 0 & \\
0 & 0 & \fbox{$1$} & 3 & -6 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 3 & -4 & 0 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 3 & -6 & 0 &
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{now, the unfrozen part of the matrix is
in RREF, so we start unfreezing}\right) \\
&  \overset{\text{unfreeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 3 & -4 & 0 & \\
0 & 0 & \fbox{$1$} & 3 & -6 & 0 &
\end{array}
\right) \\
&  \overset{\text{add }\left(  -2\right)  \cdot\operatorname{row}2\text{ to
}\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & -3 & 8 & 0 & \\
0 & 0 & \fbox{$1$} & 3 & -6 & 0 &
\end{array}
\right) \\
&  \overset{\text{unfreeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 1 & 1 & -1 & 0\\
0 & \fbox{$1$} & 0 & -3 & 8 & 0\\
0 & 0 & \fbox{$1$} & 3 & -6 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}2\text{ to
}\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 0 & 1 & 4 & -9 & 0\\
0 & \fbox{$1$} & 0 & -3 & 8 & 0\\
0 & 0 & \fbox{$1$} & 3 & -6 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}3\text{ to
}\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 0 & 0 & 1 & -3 & 0\\
0 & \fbox{$1$} & 0 & -3 & 8 & 0\\
0 & 0 & \fbox{$1$} & 3 & -6 & 0
\end{array}
\right)  .
\end{align*}
Thus, $\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 0 & 0 & 1 & -3 & 0\\
0 & \fbox{$1$} & 0 & -3 & 8 & 0\\
0 & 0 & \fbox{$1$} & 3 & -6 & 0
\end{array}
\right)  $ is the RREF of our augmented matrix $A$.

\textbf{(c)} We have just computed the RREF of the augmented matrix. This RREF
corresponds to the simple system
\begin{equation}
\left\{
\begin{array}
[c]{c}%
a+d+\left(  -3\right)  e=0\\
b+\left(  -3\right)  d+8e=0\\
c+3d+\left(  -6\right)  e=0
\end{array}
\right.  . \label{sol.linsys.1361015.mt1p.c.1}%
\end{equation}
We can solve this using \cite[Method 5.4]{Strickland}: Since the pivots of our
matrix are in columns $1,2,3$, we see that the dependent variables will be the
$1$-st, $2$-nd and $3$-rd variables, i.e., the variables $a,b,c$. The
remaining two variables $d,e$ will thus be independent variables. Now, the
equations in (\ref{sol.linsys.1361015.mt1p.c.1}) can be solved for the
dependent variables simply by moving the independent variables on the right
hand sides:%
\[
\left\{
\begin{array}
[c]{c}%
a=-d+3e\\
b=3d-8e\\
c=-3d+6e
\end{array}
\right.  .
\]
This is the general solution of our system (with $d$ and $e$ being free parameters).
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.rref.A7A8}.]\textbf{(a)} Let us start bringing
$A_{7}$ into RREF using \cite[Method 6.4]{Strickland}:%
\begin{align*}
A_{7}  &  =\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1\\
1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0\\
0 & 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$} & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0 & -1\\
0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 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]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \\
0 & 0 & 1 & 0 & 0 & 0 & 1 & \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 & 1 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 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]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \\
0 & 0 & 0 & 1 & 0 & 0 & -1 & \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 0 & 1 & 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$ below it by
adding $\left(  -1\right)  \cdot\operatorname{row}1$ to $\operatorname{row}2$;
then we freeze $\operatorname{row}1$; rinse, repeat. As we keep doing this,
the first $n-1$ columns of our matrix turn into the first $n-1$ columns of the
identity matrix $I_{n}$ (that is, all their off-diagonal entries become $0$,
while the diagonal entries remain $1$), whereas the $n$-th column takes the
form%
\[
\left(
\begin{array}
[c]{c}%
1\\
-1\\
1\\
-1\\
\vdots
\end{array}
\right)
\]
(that is, its entries alternate between $1$ and $-1$, starting with a $1$),
except for its bottommost entry. To see what happens with the bottommost
entry, we take a closer look at the final steps of this procedure:%
\begin{align*}
\cdots &  \longrightarrow\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & -1 & \\
0 & 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]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & -1 & \\
0 & 0 & 0 & 0 & 0 & 0 & 2 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$2$} &
\end{array}
\right)  .
\end{align*}
Thus, the bottommost entry of the $n$-th column becomes a $2$ (because it was
already $1$ before we added $\left(  -1\right)  \cdot\left(  -1\right)  =1$ to
it). After thus freezing the first $n-1$ rows of our matrix, we obtain the
matrix%
\[
\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$2$} &
\end{array}
\right)  .
\]
Then, we scale the last row by $1/2$ in order to make its pivot equal to $1$:%
\[
\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right)  .
\]
Thus, the unfrozen part of our matrix is in RREF, so we unfreeze rows and
clear out the nonzero entries above the pivots. (These nonzero entries only
exist in the $n$-th column, and can be cleared out by adding appropriate
multiples of the last row to the rows above it.) At the end of this procedure,
we obtain the identity matrix%
\[
\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 0\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 0\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 0\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$}%
\end{array}
\right)  ,
\]
which of course is in RREF. So this is the RREF of $A_{7}$.

\textbf{(b)} The row reduction proceeds as it did for $A_{7}$ in part
\textbf{(a)} of this exercise, but a surprise happens as we reach the last
row:%
\begin{align*}
\cdots &  \longrightarrow\left(
\begin{array}
[c]{ccccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 1 & \\
0 & 0 & 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]{ccccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 1 & \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 0 & -1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 1 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
\end{array}
\right)  .
\end{align*}
As you see, the bottommost entry in the $n$-th column is now $0$ rather than
$2$ (because it was initially $1$, but now we added $\left(  -1\right)
\cdot1$ to it rather than $\left(  -1\right)  \cdot\left(  -1\right)  $). This
means that the last remaining unfrozen row has no pivot at all, and so it is
already in RREF. We thus start unfreezing the frozen rows. As we do this, we
realize that the columns containing pivots have already been cleared, so we
don't need to perform any further row operations; our matrix at this point is
already in RREF. Thus, the RREF of $A_{8}$ is%
\[
\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 0 & -1\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0 & -1\\
0 & 0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 0 & -1\\
0 & 0 & 0 & 0 & 0 & 0 & \fbox{$1$} & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right)  .
\]


[\textit{Remark:} The different behaviors in parts \textbf{(a)} and
\textbf{(b)} come from the fact that $7$ is odd while $8$ is even. By the same
logic, we can find the RREF of the analogous matrices of any given size:

Let $n\geq2$ be an integer. Let $A_{n}$ be the $n\times n$-matrix
\[
\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 0 & 0 & \cdots & 0 & 1\\
1 & 1 & 0 & 0 & \cdots & 0 & 0\\
0 & 1 & 1 & 0 & \cdots & 0 & 0\\
0 & 0 & 1 & 1 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 0\\
0 & 0 & 0 & 0 & \cdots & 1 & 1
\end{array}
\right)  .
\]
(Its diagonal entries are $1$; its entries just below the diagonal are $1$;
its entry in the top-right corner is $1$; all its other entries are $0$.) Then:

\begin{itemize}
\item If $n$ is odd, then the RREF of $A_{n}$ is the identity matrix $I_{n}$.

\item If $n$ is even, then the RREF of $A_{n}$ is the $n\times n$-matrix%
\[
\left(
\begin{array}
[c]{ccccccc}%
\fbox{$1$} & 0 & 0 & 0 & \cdots & 0 & 1\\
0 & \fbox{$1$} & 0 & 0 & \cdots & 0 & -1\\
0 & 0 & \fbox{$1$} & 0 & \cdots & 0 & 1\\
0 & 0 & 0 & \fbox{$1$} & \cdots & 0 & -1\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & \fbox{$1$} & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 0
\end{array}
\right)
\]
(whose first $n-1$ columns are the corresponding columns of $I_{n}$, while its
last column is $\left(
\begin{array}
[c]{ccccccc}%
1 & -1 & 1 & -1 & \cdots & 1 & 0
\end{array}
\right)  ^{T}$).]
\end{itemize}
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.Ux=b.backsub.1}.]\textbf{(a)} Write the unknown
vector $x$ as $x=\left(
\begin{array}
[c]{c}%
x_{1}\\
x_{2}\\
x_{3}\\
x_{4}%
\end{array}
\right)  $. Then, the equation $Ux=b$ rewrites as the system $\left\{
\begin{array}
[c]{l}%
6x_{1}+3x_{2}+\left(  -2\right)  x_{3}+5x_{4}=1\\
\left(  -1\right)  x_{3}+2x_{4}=5\\
1x_{4}=2\\
0=0
\end{array}
\right.  $. This system can be solved by Gaussian elimination, or simpler by
back-substitution: The fourth equation ($0=0$) is automatically satisfied; the
third equation can be solved for $x_{4}$ (yielding $x_{4}=2$); the second
equation can then be solved for $x_{3}$ using our already-obtained value of
$x_{4}$ (yielding $x_{3}=-1$); the lack of an equation with \textquotedblleft
leading variable\textquotedblright\ $x_{2}$ shows that $x_{2}$ will be a free
variable; finally, the first equation can be solved for $x_{1}$ using our
already-obtained values for $x_{2},x_{3},x_{4}$ (this yields $x_{1}=-\dfrac
{1}{2}x_{2}-\dfrac{11}{6}$). Thus, the solution is%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}=-\dfrac{1}{2}x_{22}-\dfrac{11}{6},\\
x_{3}=-1\\
x_{4}=2
\end{array}
\right.  ,\ \ \ \ \ \ \ \ \ \ \text{that is,}\ \ \ \ \ \ \ \ \ \ x=\left(
\begin{array}
[c]{c}%
-\dfrac{1}{2}x_{2}-\dfrac{11}{6}\\
x_{2}\\
-1\\
2
\end{array}
\right)  .
\]


\textbf{(b)} Write the unknown vector $x$ as $x=\left(
\begin{array}
[c]{c}%
x_{1}\\
x_{2}\\
x_{3}\\
x_{4}%
\end{array}
\right)  $. Then, the equation $Ux=b^{\prime}$ rewrites as the system
$\left\{
\begin{array}
[c]{l}%
6x_{1}+3x_{2}+\left(  -2\right)  x_{3}+5x_{4}=1\\
\left(  -1\right)  x_{3}+2x_{4}=5\\
1x_{4}=2\\
0=1
\end{array}
\right.  $. This system can be solved by back-substitution: The fourth
equation ($0=1$) is unsatisfiable, so \textbf{there are no solutions}.

\textbf{(c)} Write the unknown vector $x$ as $x=\left(
\begin{array}
[c]{c}%
x_{1}\\
x_{2}\\
x_{3}\\
x_{4}%
\end{array}
\right)  $. Then, the equation $Ux=x$ rewrites as the system $\left\{
\begin{array}
[c]{l}%
6x_{1}+3x_{2}+\left(  -2\right)  x_{3}+5x_{4}=x_{1}\\
\left(  -1\right)  x_{3}+2x_{4}=x_{2}\\
1x_{4}=x_{3}\\
0=x_{4}%
\end{array}
\right.  $. Bringing the $x_{1},x_{2},x_{3},x_{4}$ onto the left hand sides
transforms this into $\left\{
\begin{array}
[c]{l}%
5x_{1}+3x_{2}+\left(  -2\right)  x_{3}+5x_{4}=0\\
\left(  -1\right)  x_{2}+\left(  -1\right)  x_{3}+2x_{4}=0\\
\left(  -1\right)  x_{3}+1x_{4}=0\\
\left(  -1\right)  x_{4}=0
\end{array}
\right.  $. This system can again be solved by back-substitution, leading to
the only solution%
\[
\left\{
\begin{array}
[c]{c}%
x_{1}=0\\
x_{2}=0\\
x_{3}=0\\
x_{4}=0
\end{array}
\right.  ,\ \ \ \ \ \ \ \ \ \ \text{that is,}\ \ \ \ \ \ \ \ \ \ x=\left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
0
\end{array}
\right)  .
\]
(Or, alternatively, you can take a look at the augmented matrix of the system
and immediately see that it has a pivot in each of its first $4$ columns; we
know already that this forces the system to have a unique solution. Since
$\left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
0
\end{array}
\right)  $ is obviously a solution to $Ux=x$, we thus can conclude that
$\left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
0
\end{array}
\right)  $ is the only solution.)
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.bases.fi=ei+ei+1}.]\textbf{(a)} Yes.

\textit{Proof.} Let $n=7$.

Recall the method we learned for checking whether some vectors in
$\mathbb{R}^{n}$ are linearly independent (see \cite[Method 8.8]{Strickland}
or Theorem 1.1.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-07.pdf}{the notes
from 2019-10-07}). Following this method, in order to check whether the $n$
vectors $f_{1},f_{2},\ldots,f_{n}$ are linearly independent, we need to form
the $n\times7$-matrix $A:=\left[  f_{1}\mid f_{2}\mid\cdots\mid f_{n}\right]
$, then bring it into RREF and check whether every column of the resulting
matrix will have a pivot. But the $n\times7$-matrix $A=\left[  f_{1}\mid
f_{2}\mid\cdots\mid f_{n}\right]  $ is precisely the matrix $A_{7}$ from
Exercise \ref{exe.rref.A7A8} \textbf{(a)}\footnote{because we have
$f_{i}=e_{i}+e_{i+1}=\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1\\
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)  $ (with the $1$'s in positions $i$ and $i+1$) for each $i\in\left\{
1,2,\ldots,n-1\right\}  $, and because we have $f_{n}=e_{n}+e_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
\vdots\\
0\\
1
\end{array}
\right)  $}. Thus, we already know how it RREF looks like from the solution of
Exercise \ref{exe.rref.A7A8} \textbf{(a)}. In particular, we know that this
RREF is the identity matrix $I_{7}$, and thus has a pivot in every column.
Hence, the $n$ vectors $f_{1},f_{2},\ldots,f_{n}$ are linearly independent.

\textbf{(b)} No.

\textit{Proof.} Let $n=8$.

We use the same method as in the solution to part \textbf{(a)}. But now, the
$n\times8$-matrix $A=\left[  f_{1}\mid f_{2}\mid\cdots\mid f_{n}\right]  $
will be the matrix $A_{8}$ from Exercise \ref{exe.rref.A7A8} \textbf{(b)}
rather than the matrix $A_{7}$ from Exercise \ref{exe.rref.A7A8} \textbf{(a)}.
We have computed the RREF of this matrix $A_{8}$ in our solution of Exercise
\ref{exe.rref.A7A8} \textbf{(b)}. In particular, we know that some column of
this RREF has no pivot (namely, the $8$-th column has no pivot). Thus, the $n$
vectors $f_{1},f_{2},\ldots,f_{n}$ are linearly dependent.

\textbf{(c)} Yes.

\textit{Proof.} Let $n=7$.

We know (from the answer to part \textbf{(a)}) that the $n$ vectors
$f_{1},f_{2},\ldots,f_{n}$ in $\mathbb{R}^{n}$ are linearly independent.
Hence, \cite[Proposition 10.12 (a)]{Strickland} (or, equivalently, Proposition
1.2.7 \textbf{(a)} 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 $f_{1},f_{2},\ldots,f_{n}$ is a basis
of $\mathbb{R}^{n}$. Thus, in particular, $f_{1},f_{2},\ldots,f_{n}$ span
$\mathbb{R}^{n}$.

\textbf{(d)} No.

\textit{Proof.} Let $n=8$.

We must prove that $f_{1},f_{2},\ldots,f_{n}$ don't span $\mathbb{R}^{n}$.
Indeed, assume the contrary. Thus, the $n$ vectors $f_{1},f_{2},\ldots,f_{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 $f_{1},f_{2},\ldots,f_{n}$ is a basis
of $\mathbb{R}^{n}$. Thus, in particular, $f_{1},f_{2},\ldots,f_{n}$ are
linearly independent. But this contradicts our result from solving part
\textbf{(b)} of this exercise. This contradiction shows that our assumption
was false. Hence, part \textbf{(d)} is solved.

[\textit{Remark:} There are alternative ways to solve this exercise. We have
solved parts \textbf{(a)} and \textbf{(b)} first, and then used them to get
answers to \textbf{(c)} and \textbf{(d)}. It could also be done the other way
round. In particular, the positive answer to part \textbf{(c)} can also be
obtained by explicitly writing the standard basis vectors $e_{1},e_{2}%
,\ldots,e_{7}$ as linear combinations of $f_{1},f_{2},\ldots,f_{7}$, namely as
follows:%
\begin{align*}
e_{1}  &  =\dfrac{1}{2}\left(  f_{1}+f_{3}+f_{5}+f_{7}-f_{2}-f_{4}%
-f_{6}\right)  ;\\
e_{2}  &  =\dfrac{1}{2}\left(  f_{2}+f_{4}+f_{6}+f_{1}-f_{3}-f_{5}%
-f_{7}\right)  ;\\
e_{3}  &  =\dfrac{1}{2}\left(  f_{3}+f_{5}+f_{7}+f_{2}-f_{4}-f_{6}%
-f_{1}\right)  ;\\
e_{4}  &  =\dfrac{1}{2}\left(  f_{4}+f_{6}+f_{1}+f_{3}-f_{5}-f_{7}%
-f_{2}\right)  ;\\
e_{5}  &  =\dfrac{1}{2}\left(  f_{5}+f_{7}+f_{2}+f_{4}-f_{6}-f_{1}%
-f_{3}\right)  ;\\
e_{6}  &  =\dfrac{1}{2}\left(  f_{6}+f_{1}+f_{3}+f_{5}-f_{7}-f_{2}%
-f_{4}\right)  ;\\
e_{7}  &  =\dfrac{1}{2}\left(  f_{7}+f_{2}+f_{4}+f_{6}-f_{1}-f_{3}%
-f_{5}\right)  .
\end{align*}
(Note that there is a cyclic symmetry inherent in the problem\footnote{Namely,
if you arrange the vectors $e_{1},e_{2},\ldots,e_{n}$ on a circle, then each
$f_{i}$ is the sum of two consecutive vectors.}, which makes it sufficient to
find one of these $7$ equations; the others can then be obtained by cyclically
rotating the subscripts.) More generally, for each odd $n$, we have%
\[
e_{1}=\dfrac{1}{2}\left(  f_{1}+f_{3}+f_{5}+\cdots+f_{n}-f_{2}-f_{4}%
-f_{6}-\cdots-f_{n-1}\right)  =\dfrac{1}{2}\left(  \sum_{i\text{ is odd}}%
f_{i}-\sum_{i\text{ is even}}f_{i}\right)
\]
and similar equalities for $e_{2},e_{3},\ldots,e_{n}$.

It is even easier to solve part \textbf{(b)} by a good guess: Just observe
that when $n$ is even, we have%
\[
f_{1}+f_{3}+f_{5}+\cdots+f_{n-1}=e_{1}+e_{2}+\cdots+e_{n}=f_{2}+f_{4}%
+f_{6}+\cdots+f_{n}%
\]
and thus%
\[
f_{1}-f_{2}+f_{3}-f_{4}\pm\cdots+f_{n-1}-f_{n}=0,
\]
which is a nontrivial relation between $f_{1},f_{2},\ldots,f_{n}$. Hence,
$f_{1},f_{2},\ldots,f_{n}$ are linearly dependent whenever $n$ is even.]
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.lincd.nxnmatsNESW}.]\textbf{(a)} No.

\textit{Proof.} Any linear combination of $N,E,S,W$ has the form $aN+bE+cS+dW$
for some $a,b,c,d\in\mathbb{R}$ (by the definition of a linear combination).
Thus, its $\left(  2,2\right)  $-th entry is
\begin{align*}
&  \left(  aN+bE+cS+dW\right)  _{2,2}\\
&  =a\underbrace{N_{2,2}}_{=0}+b\underbrace{E_{2,2}}_{=0}+c\underbrace{S_{2,2}%
}_{=0}+d\underbrace{W_{2,2}}_{=0}\\
&  =a\cdot0+b\cdot0+c\cdot0+d\cdot0=0.
\end{align*}
But the $\left(  2,2\right)  $-th entry of $I_{n}$ is not $0$ (indeed, it is
$1$, since it is a diagonal entry). Thus, a linear combination of $N,E,S,W$
cannot be $I_{2}$ (since it has the wrong $\left(  2,2\right)  $-th entry). Qed.

\textbf{(b)} No.

\textit{Proof.} We want to prove that $N,E,S,W$ are linearly independent. In
other words, we must prove that every relation between $N,E,S,W$ is trivial.

So let $aN+bE+cS+dW=0$ be any relation between $N,E,S,W$. We must prove that
this relation is trivial, i.e., that $a=b=c=d=0$.

From $aN+bE+cS+dW=0$, we obtain $\left(  aN+bE+cS+dW\right)  _{1,2}=0$ (since
the $\left(  1,2\right)  $-th entry of a zero matrix is $0$). Thus,%
\begin{align*}
0  &  =\left(  aN+bE+cS+dW\right)  _{1,2}\\
&  =a\underbrace{N_{1,2}}_{\substack{=1\\\text{(since the }\left(  1,2\right)
\text{-th}\\\text{entry of an }n\times n\text{-matrix}\\\text{belongs to its
}1\text{-st row)}}}+b\underbrace{E_{1,2}}_{\substack{=0\\\text{(since }%
n\geq3\text{, so the }\left(  1,2\right)  \text{-th}\\\text{entry of an
}n\times n\text{-matrix}\\\text{does not belong to its }n\text{-th column)}%
}}\\
&  \ \ \ \ \ \ \ \ \ \ +c\underbrace{S_{1,2}}_{\substack{=0\\\text{(since
}n\geq3>1\text{, so the }\left(  1,2\right)  \text{-th}\\\text{entry of an
}n\times n\text{-matrix}\\\text{does not belong to its }n\text{-th row)}%
}}+d\underbrace{W_{1,2}}_{\substack{=0\\\text{(since the }\left(  1,2\right)
\text{-th}\\\text{entry of an }n\times n\text{-matrix}\\\text{does not belong
to its }1\text{-st column)}}}\\
&  =a\cdot1+b\cdot0+c\cdot0+d\cdot0=a.
\end{align*}
Thus, $a=0$.

So we have obtained $a=0$ by comparing the $\left(  1,2\right)  $-th entries
in the equality $aN+bE+cS+dW=0$. Similarly,

\begin{itemize}
\item we can obtain $b=0$ by comparing the $\left(  2,n\right)  $-th entries
in the equality $aN+bE+cS+dW=0$.

\item we can obtain $c=0$ by comparing the $\left(  n,2\right)  $-th entries
in the equality $aN+bE+cS+dW=0$.

\item we can obtain $d=0$ by comparing the $\left(  2,1\right)  $-th entries
in the equality $aN+bE+cS+dW=0$.
\end{itemize}

Altogether, we now know that $a=0$ and $b=0$ and $c=0$ and $d=0$. Thus,
$a=b=c=d=0$. And this completes our proof.

[\textit{Remark:} Let us illustrate this argument in the case $n=3$:%
\begin{align*}
&  aN+bE+cS+dW\\
&  =a\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 0 & 0\\
0 & 0 & 0
\end{array}
\right)  +b\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & 0 & 1\\
0 & 0 & 1
\end{array}
\right)  +c\left(
\begin{array}
[c]{ccc}%
0 & 0 & 0\\
0 & 0 & 0\\
1 & 1 & 1
\end{array}
\right)  +d\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 0 & 0\\
1 & 0 & 0
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{ccc}%
a+d & a & a+b\\
d & 0 & b\\
c+d & c & b+c
\end{array}
\right)  .
\end{align*}
If this matrix is to be $0$, then in particular its entries $a,b,c,d$ (which
are its $\left(  1,2\right)  $-th entry, its $\left(  2,n\right)  $-th entry,
its $\left(  n,2\right)  $-th entry and its $\left(  2,1\right)  $-th entry,
respectively) must be $0$.]
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.inverse.str-up-tri-4}.]The inverse of $A$
always exists (i.e., the matrix $A$ is invertible), and equals%
\[
A^{-1}=\left(
\begin{array}
[c]{cccc}%
1 & -a & ab^{\prime}-b & ac^{\prime}-c+bc^{\prime\prime}-ab^{\prime}%
c^{\prime\prime}\\
0 & 1 & -b^{\prime} & b^{\prime}c^{\prime\prime}-c^{\prime}\\
0 & 0 & 1 & -c^{\prime\prime}\\
0 & 0 & 0 & 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}):%
\begin{align*}
\left[  A\mid I_{4}\right]  =  &  \left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & a & b & c & 1 & 0 & 0 & 0\\
0 & 1 & b^{\prime} & c^{\prime} & 0 & 1 & 0 & 0\\
0 & 0 & 1 & c^{\prime\prime} & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1
\end{array}
\right) \\
\overset{\text{add }-a\cdot\operatorname{row}2\text{ to }\operatorname{row}%
1}{\longrightarrow}  &  \left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & b-ab^{\prime} & c-ac^{\prime} & 1 & -a & 0 & 0\\
0 & 1 & b^{\prime} & c^{\prime} & 0 & 1 & 0 & 0\\
0 & 0 & 1 & c^{\prime\prime} & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1
\end{array}
\right) \\
\longrightarrow &  \cdots\longrightarrow\left(
\begin{array}
[c]{cccccccc}%
\fbox{$1$} & 0 & 0 & 0 & 1 & -a & ab^{\prime}-b & ac^{\prime}-c+bc^{\prime
\prime}-ab^{\prime}c^{\prime\prime}\\
0 & \fbox{$1$} & 0 & 0 & 0 & 1 & -b^{\prime} & b^{\prime}c^{\prime\prime
}-c^{\prime}\\
0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1 & -c^{\prime\prime}\\
0 & 0 & 0 & \fbox{$1$} & 0 & 0 & 0 & 1
\end{array}
\right) \\
=  &  \left[  I_{4}\mid\left(
\begin{array}
[c]{cccc}%
1 & -a & ab^{\prime}-b & ac^{\prime}-c+bc^{\prime\prime}-ab^{\prime}%
c^{\prime\prime}\\
0 & 1 & -b^{\prime} & b^{\prime}c^{\prime\prime}-c^{\prime}\\
0 & 0 & 1 & -c^{\prime\prime}\\
0 & 0 & 0 & 1
\end{array}
\right)  \right]
\end{align*}
(where I am leaving out the intermediate steps because you have seen row
reduction happen quite a few times by now).
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.inverse.which.mt1p}.]\textbf{(a)} This matrix
is invertible.

\textit{Proof.} One way to see it is simply to compute its inverse; namely,
its inverse is $\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & 1 & -1\\
1 & -1 & 0
\end{array}
\right)  $.

But here is a quicker way, which you can do in your head: It is easy to see
that the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)  $ can be turned into an identity matrix by row operations (namely,
first swap row $1$ with row $3$, thus obtaining the lower-triangular matrix
$\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 1 & 0\\
1 & 1 & 1
\end{array}
\right)  $, and then use the $1$'s on the diagonal to clear out the entries
below them, obtaining the identity matrix $I_{3}$). In other words, the matrix
$\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)  $ 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 our matrix is invertible.

\bigskip

\textbf{(b)} This matrix is 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}$ (since both $v_{1}$ and $v_{3}$ equal
$\left(  1,0,1\right)  ^{T}$); in other words, $1v_{1}+0v_{2}+\left(
-1\right)  v_{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{(c)} This matrix is invertible.

\textit{Proof.} One way to see it is simply to compute its inverse; namely,
its inverse is $\left(
\begin{array}
[c]{ccc}%
-3 & 0 & 2\\
0 & \dfrac{1}{2} & 0\\
2 & 0 & -1
\end{array}
\right)  $.

But here is a quicker way, which you can do in your head: It is easy to see
that the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 2\\
0 & 2 & 0\\
2 & 0 & 3
\end{array}
\right)  $ can be turned into an identity matrix by row operations (namely,
first add $\left(  -2\right)  \cdot$row $1$ with row $3$, thus obtaining the
upper-triangular matrix $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 2\\
0 & 2 & 0\\
0 & 0 & -1
\end{array}
\right)  $, and then scale the rows to turn the pivots into $1$'s, and finally
use the pivots to clear out the entries above them, obtaining the identity
matrix $I_{3}$). In other words, the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 2\\
0 & 2 & 0\\
2 & 0 & 3
\end{array}
\right)  $ 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 our matrix is invertible.

\bigskip

\textbf{(d)} This matrix is 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.
\end{proof}

For the solution of Exercise \ref{exe.inverse.transpose}, we will need the
following fact (\cite[Proposition 3.18 \textbf{(e)}]{lina}):

\begin{proposition}
\label{prop.transpose.opers.e}Let $n\in\mathbb{N}$, $m\in\mathbb{N}$ and
$p\in\mathbb{N}$. Let $A$ be an $n\times m$-matrix. Let $B$ be an $m\times
p$-matrix. Then, $\left(  AB\right)  ^{T}=B^{T}A^{T}$.
\end{proposition}

\begin{proof}
[Solution to Exercise \ref{exe.inverse.transpose}.]We need to prove that
$\left(  A^{-1}\right)  ^{T}$ is an inverse of $A^{T}$. By the definition of
an \textquotedblleft inverse\textquotedblright, this means that we need to
prove the two equalities%
\begin{equation}
A^{T}\left(  A^{-1}\right)  ^{T}=I_{n}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left(  A^{-1}\right)  ^{T}A^{T}=I_{n}
\label{sol.inverse.transpose.goal}%
\end{equation}
(because these equalities are what makes $\left(  A^{-1}\right)  ^{T}$ into an
inverse of $A^{T}$).

So let us prove them. The identity matrix $I_{n}$ is diagonal; thus, it has
the same numbers below and above the diagonal (namely, zeroes). Hence, it does
not change if we transpose it. In other words, $\left(  I_{n}\right)
^{T}=I_{n}$.

Proposition \ref{prop.transpose.opers.e} (applied to $m=n$, $p=n$ and
$B=A^{-1}$) yields $\left(  AA^{-1}\right)  ^{T}=\left(  A^{-1}\right)
^{T}A^{T}$. Hence, $\left(  A^{-1}\right)  ^{T}A^{T}=\left(
\underbrace{AA^{-1}}_{=I_{n}}\right)  ^{T}=\left(  I_{n}\right)  ^{T}=I_{n}$.

Also, Proposition \ref{prop.transpose.opers.e} (applied to $n$, $n$, $A^{-1}$
and $A$ instead of $m$, $p$, $A$ and $B$) yields $\left(  A^{-1}A\right)
^{T}=A^{T}\left(  A^{-1}\right)  ^{T}$. Hence, $A^{T}\left(  A^{-1}\right)
^{T}=\left(  \underbrace{A^{-1}A}_{=I_{n}}\right)  ^{T}=\left(  I_{n}\right)
^{T}=I_{n}$.

Thus, we have proved the two equalities in (\ref{sol.inverse.transpose.goal}).
This shows that $\left(  A^{-1}\right)  ^{T}$ is an inverse of $A^{T}$. Hence,
the matrix $A^{T}$ is invertible, and its inverse is $\left(  A^{T}\right)
^{-1}=\left(  A^{-1}\right)  ^{T}$. This solves Exercise
\ref{exe.inverse.transpose}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.perms.compos1.mt1p}.]From $\alpha=\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
2 & 4 & 1 & 3
\end{array}
\right)  $, we read off all values of $\alpha$, namely%
\[
\alpha\left(  1\right)  =2,\ \ \ \ \ \ \ \ \ \ \alpha\left(  2\right)
=4,\ \ \ \ \ \ \ \ \ \ \alpha\left(  3\right)  =1,\ \ \ \ \ \ \ \ \ \ \alpha
\left(  4\right)  =3.
\]
Similarly,%
\[
\beta\left(  1\right)  =3,\ \ \ \ \ \ \ \ \ \ \beta\left(  2\right)
=4,\ \ \ \ \ \ \ \ \ \ \beta\left(  3\right)  =1,\ \ \ \ \ \ \ \ \ \ \beta
\left(  4\right)  =3
\]
and%
\[
\gamma\left(  1\right)  =3,\ \ \ \ \ \ \ \ \ \ \gamma\left(  2\right)
=4,\ \ \ \ \ \ \ \ \ \ \gamma\left(  3\right)  =1,\ \ \ \ \ \ \ \ \ \ \gamma
\left(  4\right)  =2.
\]


\bigskip

\textbf{(a)} The maps $\alpha$ and $\gamma$ are permutations, but $\beta$ is not.

\textit{Proof.} The map $\beta$ is not injective (indeed, it sends the
distinct elements $1$ and $4$ to the same image, because $\beta\left(
1\right)  =3=\beta\left(  4\right)  $). Thus, $\beta$ is not bijective. Hence,
$\beta$ is not a permutation.

The map $\alpha$ sends the elements $1,2,3,4$ to the distinct elements
$2,4,1,3$; thus, it is injective. Furthermore, all of the $4$ elements of
$\left[  4\right]  $ appear as values of $\alpha$. Thus, $\alpha$ is
surjective. Hence, the map $\alpha$ is both injective and surjective. In other
words, $\alpha$ is bijective. Hence, $\alpha$ is a permutation (since $\alpha$
is a map from $\left[  4\right]  $ to $\left[  4\right]  $).

A similar argument shows that $\gamma$ is a permutation.

\bigskip

\textbf{(b)} We have%
\begin{align*}
\left(  \alpha\circ\beta\right)  \left(  1\right)   &  =\alpha\left(
\underbrace{\beta\left(  1\right)  }_{=3}\right)  =\alpha\left(  3\right)
=1;\\
\left(  \alpha\circ\beta\right)  \left(  2\right)   &  =\alpha\left(
\underbrace{\beta\left(  2\right)  }_{=4}\right)  =\alpha\left(  4\right)
=3;\\
\left(  \alpha\circ\beta\right)  \left(  3\right)   &  =\alpha\left(
\underbrace{\beta\left(  3\right)  }_{=1}\right)  =\alpha\left(  1\right)
=2;\\
\left(  \alpha\circ\beta\right)  \left(  4\right)   &  =\alpha\left(
\underbrace{\beta\left(  4\right)  }_{=3}\right)  =\alpha\left(  3\right)  =1.
\end{align*}
Tabulating these values of $\alpha\circ\beta$, we obtain%
\[
\alpha\circ\beta=\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
1 & 3 & 2 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{in two-line notation.}%
\]
Similarly,%
\begin{align*}
\beta\circ\alpha &  =\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
4 & 3 & 3 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{in two-line notation;}\\
\gamma\circ\gamma &  =\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
1 & 2 & 3 & 4
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{in two-line notation.}%
\end{align*}
(Thus, $\gamma\circ\gamma$ is the identity map $\operatorname*{id}%
\nolimits_{\left[  4\right]  }$.)

\bigskip

\textbf{(c)} We have $\operatorname*{sign}\left(  \alpha\right)  =-1$ and
$\operatorname*{sign}\left(  \gamma\right)  =1$.

\textit{Proof.} The inversions of $\alpha$ are $\left(  1,3\right)  $ (since
$\alpha\left(  1\right)  >\alpha\left(  3\right)  $) and $\left(  2,3\right)
$ (since $\alpha\left(  2\right)  >\alpha\left(  3\right)  $) and $\left(
2,4\right)  $ (since $\alpha\left(  2\right)  >\alpha\left(  4\right)  $).
Hence, $\alpha$ has $3$ inversions. In other words, the Coxeter length of
$\alpha$ is $\ell\left(  \alpha\right)  =3$. Hence, the definition of sign
yields $\operatorname*{sign}\left(  \alpha\right)  =\left(  -1\right)
^{\ell\left(  \alpha\right)  }=\left(  -1\right)  ^{3}=-1$.

A similar argument shows that $\operatorname*{sign}\left(  \gamma\right)  =1$.
(Alternatively, you can conclude this from the corollary in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the notes
from 2019-10-23}, once you realize that $\gamma=t_{2,3}\circ\alpha$.)
\end{proof}

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