\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=Tuesday, December 10, 2019 22:27:28}
%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): final exam}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Reminders}

\subsection{Matrix basics}

\begin{itemize}
\item For any two matrices $A$ and $B$, if the product $AB$ is well-defined,
then%
\[
\left(  AB\right)  _{i,j}=A_{i,1}B_{1,j}+A_{i,2}B_{2,j}+\cdots+A_{i,m}%
B_{m,j}=\operatorname*{row}\nolimits_{i}A\cdot\operatorname*{col}%
\nolimits_{j}B
\]
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}$.
\end{itemize}

\subsection{Operations and RREFs}

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

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

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

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

\begin{definition}
A matrix is \textbf{in 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}

The \textbf{RREF of a matrix }$A$ is the unique matrix $B$ that is in RREF and
can be obtained from $A$ by a sequence of EROs.
\end{definition}

\begin{definition}
Let $A$ be an $n\times n$-matrix. Then, the \textbf{determinant} $\det A$ of
$A$ is defined to be the sum%
\[
\sum_{\sigma\text{ is a permutation of }\left[  n\right]  }%
\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}A_{2,\sigma\left(  2\right)  }\cdots A_{n,\sigma\left(  n\right)  }.
\]

\end{definition}

Here, $\left[  n\right]  $ means $\left\{  1,2,\ldots,n\right\}  $.

\begin{theorem}
[Laplace expansion]Let $A$ be an $n\times n$-matrix. For each $p,q\in\left[
n\right]  $, we let $M_{p,q}$ be the $\left(  n-1\right)  \times\left(
n-1\right)  $-matrix obtained from $A$ by removing row $p$ and column $q$. Then:

\textbf{(a)} For each $p\in\left[  n\right]  $, we have%
\[
\det A=\sum_{q=1}^{n}\left(  -1\right)  ^{p+q}A_{p,q}\det\left(
M_{p,q}\right)  .
\]
(This is called \textbf{Laplace expansion along the }$p$\textbf{-th row}.)

\textbf{(b)} For each $q\in\left[  n\right]  $, we have%
\[
\det A=\sum_{p=1}^{n}\left(  -1\right)  ^{p+q}A_{p,q}\det\left(
M_{p,q}\right)  .
\]
(This is called \textbf{Laplace expansion along the }$q$\textbf{-th column}.)
\end{theorem}

\begin{definition}
Let $A$ be an $n\times n$-matrix. Let $\lambda$ be a scalar (i.e., a real number).

\textbf{(a)} A $\lambda$\textbf{-eigenvector of }$A$ means a nonzero vector
$v\in\mathbb{R}^{n}$ such that $Av=\lambda v$.

\textbf{(b)} We say that $\lambda$ is an \textbf{eigenvalue} of $A$ if and
only if there exists a $\lambda$-eigenvector of $A$.

\textbf{(c)} The \textbf{characteristic polynomial} of $A$ is the polynomial%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{n}\right)  .
\]

\end{definition}

\cleardoublepage


\section{Matrix basics}

\begin{exercise}
\label{exe.19fla-fin.mat1}Let $A$ be a $3\times2$-matrix. Which of the
following matrices are well-defined, and (if they are) what are their
dimensions? (For example, $A^{T}$ is a well-defined $2\times3$-matrix, i.e.,
has dimensions $2\times3$. But $A^{2}$ is not well-defined.)

\textbf{No justifications are required in this exercise. Just write the
dimensions (or \textquotedblleft N\textquotedblright\ for \textquotedblleft
not well-defined\textquotedblright) into the respective box!}

\textbf{(a)} $A+A^{T}$: \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$}

\bigskip

\textbf{(b)} $AA^{T}$: \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$}

\bigskip

\textbf{(c)} $A^{T}A$: \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$}

\bigskip

\textbf{(d)} $AA^{T}A$: \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$}

\bigskip

\textbf{(e)} $AA^{T}AA^{T}$: \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$}
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.mat1}.]Here are the answers:

\textbf{(a)} Not well-defined (since we cannot add a $3\times2$-matrix with a
$2\times3$-matrix).

\textbf{(b)} Well-defined and has dimensions $3\times3$.

\textbf{(c)} Well-defined and has dimensions $2\times2$.

\textbf{(d)} Well-defined and has dimensions $3\times2$.

\textbf{(e)} Well-defined and has dimensions $3\times3$.

[All four parts \textbf{(b)}, \textbf{(c)}, \textbf{(d)} and \textbf{(e)}
follow from the same principle: The product $XY$ of a $p\times q$-matrix $X$
with an $r\times s$-matrix $Y$ is well-defined if and only if $q=r$;
furthermore, in this case, it is a $p\times s$-matrix. Parts \textbf{(c)} and
\textbf{(d)} follow directly from this principle; parts \textbf{(d)} and
\textbf{(e)} require applying it twice or thrice.]
\end{proof}

\cleardoublepage


\section{RREF}

\begin{exercise}
\label{exe.19fla-fin.rref1}\textbf{(a)} Let $A_{3}$ be the $3\times3$-matrix
$\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 2 & 1\\
1 & 1 & 1
\end{array}
\right)  $. Find its RREF.

\bigskip

\textbf{(b)} Let $A_{5}$ be the $5\times5$-matrix $\left(
\begin{array}
[c]{ccccc}%
1 & 1 & 1 & 1 & 1\\
1 & 2 & 2 & 2 & 1\\
1 & 2 & 3 & 2 & 1\\
1 & 2 & 2 & 2 & 1\\
1 & 1 & 1 & 1 & 1
\end{array}
\right)  $. Find its RREF.
\end{exercise}

\begin{fineprint}
[\textbf{Note:} The pattern in $A_{3}$ and in $A_{5}$ is exactly what it looks
like: $1$'s along the border of the matrix, $2$'s one step further inward, etc.]
\end{fineprint}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.rref1}.]\textbf{(a)} Let us bring
$A_{3}$ into RREF using \cite[Method 6.4]{Strickland} (with the standard
allowance for not needlessly freezing rows when the matrix is already in
RREF):%
\begin{align*}
A_{3}  &  =\left(
\begin{array}
[c]{ccc}%
\fbox{$1$} & 1 & 1\\
1 & 2 & 1\\
1 & 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]{ccc}%
\fbox{$1$} & 1 & 1\\
0 & 1 & 0\\
1 & 1 & 1
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}3}{\longrightarrow}\left(
\begin{array}
[c]{ccc}%
\fbox{$1$} & 1 & 1\\
0 & \fbox{$1$} & 0\\
0 & 0 & 0
\end{array}
\right)  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}2\text{
to }\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccc}%
\fbox{$1$} & 0 & 1\\
0 & \fbox{$1$} & 0\\
0 & 0 & 0
\end{array}
\right)  .
\end{align*}
The resulting matrix is the RREF of $A_{3}$.

\bigskip

\textbf{(b)} Let us bring $A_{5}$ into RREF using \cite[Method 6.4]%
{Strickland} (with the standard allowance for not needlessly freezing rows
when the matrix is already in RREF):%
\begin{align*}
&  A_{5}=\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1\\
1 & 2 & 2 & 2 & 1\\
1 & 2 & 3 & 2 & 1\\
1 & 2 & 2 & 2 & 1\\
1 & 1 & 1 & 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]{ccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 0\\
1 & 2 & 3 & 2 & 1\\
1 & 2 & 2 & 2 & 1\\
1 & 1 & 1 & 1 & 1
\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 & 1\\
0 & 1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 0\\
1 & 2 & 2 & 2 & 1\\
1 & 1 & 1 & 1 & 1
\end{array}
\right)  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{
to }\operatorname{row}4}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 0\\
0 & 1 & 1 & 1 & 0\\
1 & 1 & 1 & 1 & 1
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}1\text{ to
}\operatorname{row}5}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 0\\
0 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right)  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{cccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 1 & 0 & \\
0 & 1 & 2 & 1 & 0 & \\
0 & 1 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 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 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 1 & 0 & \\
0 & 0 & 1 & 0 & 0 & \\
0 & 1 & 1 & 1 & 0 & \\
0 & 0 & 0 & 0 & 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 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 1 & 1 & 0 & \\
0 & 0 & \fbox{$1$} & 0 & 0 & \\
0 & 0 & 0 & 0 & 0 & \\
0 & 0 & 0 & 0 & 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$} & 1 & 1 & 1 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 1 & 0 & \\
0 & 0 & \fbox{$1$} & 0 & 0 & \\
0 & 0 & 0 & 0 & 0 & \\
0 & 0 & 0 & 0 & 0 &
\end{array}
\right) \\
&  \overset{\text{unfreeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 1 & 1 & 1 & 1\\
0 & \fbox{$1$} & 0 & 1 & 0\\
0 & 0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 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 & 1 & 0 & 1\\
0 & \fbox{$1$} & 0 & 1 & 0\\
0 & 0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right) \\
&  \overset{\text{add }\left(  -1\right)  \cdot\operatorname{row}3\text{ to
}\operatorname{row}1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 0 & 0 & 0 & 1\\
0 & \fbox{$1$} & 0 & 1 & 0\\
0 & 0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right)  .
\end{align*}
The resulting matrix is the RREF of $A_{5}$.

\bigskip

[\textit{Remark:} Similarly, for any $n\in\mathbb{N}$, you can define the
$n\times n$-matrix $A_{n}$ whose $\left(  i,j\right)  $-th entry is
\textquotedblleft the distance from cell $\left(  i,j\right)  $ to the
boundary of the matrix\textquotedblright\ (i.e., the number $\min\left\{
i,j,n+1-i,n+1-j\right\}  $). Its RREF looks exactly like the RREFs of $A_{3}$
and $A_{5}$ we found above: The entries in cells $\left(  i,i\right)  $ and
$\left(  i,n+1-i\right)  $ for all $i\in\left\{  1,2,\ldots,\left\lceil
n/2\right\rceil \right\}  $ equal $1$ (where $\left\lceil n/2\right\rceil $
denotes the smallest integer that is $n/2$), and all remaining entries equal
$0$.]
\end{proof}

\cleardoublepage


\section{Linear independence}

\begin{exercise}
\label{exe.19fla-fin.lind1}Consider the four matrices%
\[
A=\left(
\begin{array}
[c]{cc}%
2 & 1\\
1 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ B=\left(
\begin{array}
[c]{cc}%
1 & 2\\
1 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ C=\left(
\begin{array}
[c]{cc}%
1 & 1\\
2 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ D=\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 2
\end{array}
\right)  .
\]


\textbf{(a)} Are these matrices $A,B,C,D$ linearly independent?

\textbf{(b)} Do these matrices $A,B,C,D$ span the vector space $\mathbb{R}%
^{2\times2}$ ?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.lind1}.]\textbf{(a)} Yes.

\textit{Proof.} Let $aA+bB+cC+dD=0_{2\times2}$ be a relation between
$A,B,C,D$. We shall prove that this relation is trivial, i.e., that we have
$a=b=c=d=0$.

Indeed, the definitions of $A,B,C,D$ yield%
\begin{align*}
aA+bB+cC+dD  &  =a\left(
\begin{array}
[c]{cc}%
2 & 1\\
1 & 1
\end{array}
\right)  +b\left(
\begin{array}
[c]{cc}%
1 & 2\\
1 & 1
\end{array}
\right)  +c\left(
\begin{array}
[c]{cc}%
1 & 1\\
2 & 1
\end{array}
\right)  +d\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 2
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cc}%
2a+b+c+d & a+2b+c+d\\
a+b+2c+d & a+b+c+2d
\end{array}
\right)  .
\end{align*}
Comparing this with $aA+bB+cC+dD=0_{2\times2}$, we find%
\[
\left(
\begin{array}
[c]{cc}%
2a+b+c+d & a+2b+c+d\\
a+b+2c+d & a+b+c+2d
\end{array}
\right)  =0_{2\times2}=\left(
\begin{array}
[c]{cc}%
0 & 0\\
0 & 0
\end{array}
\right)  .
\]
In other words, the four equalities%
\[
\left\{
\begin{array}
[c]{c}%
2a+b+c+d=0\\
a+2b+c+d=0\\
a+b+2c+d=0\\
a+b+c+2d=0
\end{array}
\right.
\]
all hold. We can treat them as a system of linear equations in $a,b,c,d$ and
solve it using Gaussian elimination, but we can also proceed in a simpler way:
Subtracting the equality $a+2b+c+d=0$ from the equality $2a+b+c+d=0$, we
obtain $\left(  2a+b+c+d\right)  -\left(  a+2b+c+d\right)  =0$. This rewrites
as $a-b=0$. In other words, $b=a$. Similarly, $c=a$ and $d=a$. Now, the
equality $2a+b+c+d=0$ yields $0=2a+\underbrace{b}_{=a}+\underbrace{c}%
_{=a}+\underbrace{d}_{=a}=2a+a+a+a=5a$, so that $5a=0$ and therefore $a=0$.
Similarly, $b=0$ and $c=0$ and $d=0$. Hence, $a=b=c=d=0$. Thus, the relation
$aA+bB+cC+dD=0_{2\times2}$ is trivial.

We thus have shown that each any relation $aA+bB+cC+dD=0_{2\times2}$ between
$A,B,C,D$ must be trivial. In other words, $A,B,C,D$ are linearly independent.

\bigskip

\textbf{(b)} Yes.

We shall give two proofs of this fact:

\textit{First proof.} The list $\left(  A,B,C,D\right)  $ is $\mathbb{R}%
$-linearly independent (by part \textbf{(a)} of this exercise), i.e., is an
independent list of $\mathbb{R}^{2\times2}$ (using the terminology from our
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-12-04.pdf}{class notes
from 2019-12-04}).

The $\mathbb{R}$-vector space $\mathbb{R}^{2\times2}$ has dimension
$2\cdot2=4$ (since the list%
\[
\left(  \underbrace{\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 0
\end{array}
\right)  ,\ \ \left(
\begin{array}
[c]{cc}%
0 & 1\\
0 & 0
\end{array}
\right)  ,\ \ \left(
\begin{array}
[c]{cc}%
0 & 0\\
1 & 0
\end{array}
\right)  ,\ \ \left(
\begin{array}
[c]{cc}%
0 & 0\\
0 & 1
\end{array}
\right)  }_{\substack{\text{the four matrices, each of which has a }1\text{
in}\\\text{some position, and zeroes everywhere else}}}\right)
\]
is a basis of this space). In other words, $\dim\left(  \mathbb{R}^{2\times
2}\right)  =4$. Hence, Theorem 1.1.7 \textbf{(h)} from our
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-12-04.pdf}{class notes
from 2019-12-04} (applied to $\mathbb{K}=\mathbb{R}$ and $V=\mathbb{R}%
^{2\times2}$) shows that any independent list of $\mathbb{R}^{2\times2}$ that
has length $4$ must be a basis of $\mathbb{R}^{2\times2}$. Applying this to
the independent list $\left(  A,B,C,D\right)  $, we conclude that $\left(
A,B,C,D\right)  $ must be a basis of $\mathbb{R}^{2\times2}$ (since $\left(
A,B,C,D\right)  $ is an independent list of $\mathbb{R}^{2\times2}$). Thus, in
particular, the list $\left(  A,B,C,D\right)  $ spans $\mathbb{R}^{2\times2}$.
In other words, the matrices $A,B,C,D$ span the vector space $\mathbb{R}%
^{2\times2}$.

\textit{Second proof.} Any matrix in $\mathbb{R}^{2\times2}$ can be written as
a linear combination of $A,B,C,D$: Namely, if the matrix is $\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  $, then it can be written as
\[
\dfrac{4a-b-c-d}{5}A+\dfrac{4b-c-d-a}{5}B+\dfrac{4c-d-a-b}{5}C+\dfrac
{4d-a-b-c}{5}D.
\]
(You can find this by solving the equation $\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  =xA+yB+zC+wD$ for $x,y,z,w$.)
\end{proof}

\cleardoublepage


\section{Inverses}

\begin{exercise}
\label{exe.19fla-fin.inv1}\textbf{(a)} Is the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)  $ invertible?

\bigskip

\textbf{(b)} Is the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 2 & 1\\
1 & 1 & 1
\end{array}
\right)  $ invertible?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.inv1}.]\textbf{(a)} \textbf{Yes.}

\textit{Proof.} One way to see this is by constructing its inverse:%
\[
\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)  ^{-1}=\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & 1 & -1\\
1 & -1 & 0
\end{array}
\right)  .
\]


Another way is to observe that its determinant is $-1\neq0$, and thus it is
invertible (by the implication \textbf{(l)} $\Longrightarrow$ \textbf{(k)} in
Theorem 2.1.3 in our
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{class notes
from 2019-11-04}).

\bigskip

\textbf{(b)} \textbf{No.}

\textit{Proof.} The columns of this matrix are linearly dependent (since its
first and third columns are identical). Hence, the matrix is not invertible
(by the implication \textbf{(b')} $\Longrightarrow$ \textbf{(k')} in Theorem
2.1.4 in our
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{class notes
from 2019-11-04}).
\end{proof}

\cleardoublepage


\section{Determinants}

\begin{exercise}
\label{exe.19fla-fin.det1}\textbf{(a)} Compute $\det\left(
\begin{array}
[c]{cccc}%
a & 0 & 0 & 1\\
0 & b & 0 & 1\\
0 & 0 & c & 1\\
1 & 1 & 1 & 1
\end{array}
\right)  $, where $a,b,c,d$ are reals.

[\textbf{Hint:} The result will have the form $x-y-z-w$, where $x,y,z,w$ are
four simple expressions.]

\bigskip

\textbf{(b)} Compute $\det\left(
\begin{array}
[c]{cccc}%
a & b & c & d\\
b & b & c & d\\
c & c & c & d\\
d & d & d & d
\end{array}
\right)  $, where $a,b,c,d$ are reals. Write the result as a product of four
linear expressions in $a,b,c,d$.

[\textbf{Hint:} In part \textbf{(b)}, don't waste your time expanding the
determinant by its definition; the result will not be easy to factor. Instead,
try simplifying the determinant by appropriate transformations.]
\end{exercise}

\begin{fineprint}
[\textbf{Note:} The matrix in \textbf{(b)} has an $a$ in its top-left cell;
$b$'s in the three cells bordering it; $c$'s in the five cells bordering them;
$d$'s everywhere else.]
\end{fineprint}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.det1}.]\textbf{(a)} Let $a,b,c,d$ be
reals. Laplace expansion along the first row yields%
\begin{align*}
\det\left(
\begin{array}
[c]{cccc}%
a & 0 & 0 & 1\\
0 & b & 0 & 1\\
0 & 0 & c & 1\\
1 & 1 & 1 & 1
\end{array}
\right)   &  =\underbrace{\left(  -1\right)  ^{1+1}}_{=1}a\det\left(
\begin{array}
[c]{ccc}%
b & 0 & 1\\
0 & c & 1\\
1 & 1 & 1
\end{array}
\right)  +\underbrace{\left(  -1\right)  ^{1+2}0\det\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & c & 1\\
1 & 1 & 1
\end{array}
\right)  }_{=0}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  -1\right)  ^{1+3}0\det\left(
\begin{array}
[c]{ccc}%
0 & b & 1\\
0 & 0 & 1\\
1 & 1 & 1
\end{array}
\right)  }_{=0}+\underbrace{\left(  -1\right)  ^{1+4}}_{=-1}1\det\left(
\begin{array}
[c]{ccc}%
0 & b & 0\\
0 & 0 & c\\
1 & 1 & 1
\end{array}
\right) \\
&  =a\det\left(
\begin{array}
[c]{ccc}%
b & 0 & 1\\
0 & c & 1\\
1 & 1 & 1
\end{array}
\right)  -\det\left(
\begin{array}
[c]{ccc}%
0 & b & 0\\
0 & 0 & c\\
1 & 1 & 1
\end{array}
\right)  .
\end{align*}
The two determinants on the right hand side of this equality are easily
computed (either again by Laplace expansion along the first row, or by the
fairly manageable\footnote{in the case of a $3\times3$-matrix} explicit
definition of a determinant):%
\[
\det\left(
\begin{array}
[c]{ccc}%
b & 0 & 1\\
0 & c & 1\\
1 & 1 & 1
\end{array}
\right)  =bc-b-c;\ \ \ \ \ \ \ \ \ \ \det\left(
\begin{array}
[c]{ccc}%
0 & b & 0\\
0 & 0 & c\\
1 & 1 & 1
\end{array}
\right)  =bc.
\]
Thus, we can conclude our above computation as follows:%
\begin{align*}
\det\left(
\begin{array}
[c]{cccc}%
a & 0 & 0 & 1\\
0 & b & 0 & 1\\
0 & 0 & c & 1\\
1 & 1 & 1 & 1
\end{array}
\right)   &  =a\underbrace{\det\left(
\begin{array}
[c]{ccc}%
b & 0 & 1\\
0 & c & 1\\
1 & 1 & 1
\end{array}
\right)  }_{=bc-b-c}-\underbrace{\det\left(
\begin{array}
[c]{ccc}%
0 & b & 0\\
0 & 0 & c\\
1 & 1 & 1
\end{array}
\right)  }_{=bc}\\
&  =a\left(  bc-b-c\right)  -bc=abc-ab-ac-bc.
\end{align*}


[\textit{Remark:} An alternative solution can be obtained just by applying the
definition of a determinant and analyzing which of the $24$ permutations of
$\left[  4\right]  $ will give rise to nonzero terms. This is not as painful
as it sounds; only $4$ permutations give rise to nonzero terms. This method
can be generalized to the case of an $n\times n$-matrix, resulting in the
formula%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
a_{1} & 0 & \cdots & 0 & 1\\
0 & a_{2} & \cdots & 0 & 1\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & a_{n-1} & 1\\
1 & 1 & \cdots & 1 & 1
\end{array}
\right) \\
&  =a_{1}a_{2}\cdots a_{n-1}\\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the sum of all products of }n-2\text{ of
the }n-1\text{ numbers }a_{1}a_{2}\cdots a_{n-1}\right)  .
\end{align*}
If $a_{1},a_{2},\ldots,a_{n-1}$ are nonzero, then this can be simplified to
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
a_{1} & 0 & \cdots & 0 & 1\\
0 & a_{2} & \cdots & 0 & 1\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & a_{n-1} & 1\\
1 & 1 & \cdots & 1 & 1
\end{array}
\right) \\
&  =a_{1}a_{2}\cdots a_{n-1}-\left(  \dfrac{1}{a_{1}}+\dfrac{1}{a_{2}}%
+\cdots+\dfrac{1}{a_{n-1}}\right)  a_{1}a_{2}\cdots a_{n-1}.
\end{align*}
For an even more general statement, see \cite[Exercise 6 \textbf{(b)}%
]{18s-hw4s}.]

\bigskip

\textbf{(b)} Let $a,b,c,d$ be reals. Let us recall some properties of determinants:

\begin{statement}
\textit{Property 1:} Let $A$ be an $n\times n$-matrix, and let $p$ and $q$ be
two distinct elements of $\left[  n\right]  $. If we add $\lambda
\cdot\operatorname{row}_{p}A$ to the $q$-th row of $A$, then $\det A$ does not
change. (This is Corollary 1.2.5 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

\begin{statement}
\textit{Property 2:} Let $A$ be an $n\times n$-matrix, and let $p$ and $q$ be
two distinct elements of $\left[  n\right]  $. If we subtract
$\operatorname{row}_{p}A$ from the $q$-th row of $A$, then $\det A$ does not
change. (This follows from Property 1 (applied to $\lambda=-1$), because
adding $\left(  -1\right)  \cdot\operatorname{row}_{p}A$ to the $q$-th row of
$A$ is the same as subtracting $\operatorname{row}_{p}A$ from the $q$-th row
of $A$.)
\end{statement}

\begin{statement}
\textit{Property 3:} If an $n\times n$-matrix $A$ is triangular (i.e.,
upper-triangular or lower-triangular), then its determinant is the product of
its diagonal elements:
\[
\det A=A_{1,1}A_{2,2}\cdots A_{n,n}.
\]
(This is Theorem 1.1.2 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

Now,
\begin{align*}
&  \det\left(
\begin{array}
[c]{cccc}%
a & b & c & d\\
b & b & c & d\\
c & c & c & d\\
d & d & d & d
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
a-b & 0 & 0 & 0\\
b & b & c & d\\
c & c & c & d\\
d & d & d & d
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the }2\text{-nd row of our matrix}\\
\text{from the }1\text{-st row; this did not change the determinant}\\
\text{(by Property 2)}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
a-b & 0 & 0 & 0\\
b-c & b-c & 0 & 0\\
c & c & c & d\\
d & d & d & d
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the }3\text{-rd row of our matrix}\\
\text{from the }3\text{-rd row; this did not change the determinant}\\
\text{(by Property 2)}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
a-b & 0 & 0 & 0\\
b-c & b-c & 0 & 0\\
c-d & c-d & c-d & 0\\
d & d & d & d
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the }4\text{-th row of our matrix}\\
\text{from the }3\text{-rd row; this did not change the determinant}\\
\text{(by Property 2)}%
\end{array}
\right) \\
&  =\left(  a-b\right)  \left(  b-c\right)  \left(  c-d\right)  d
\end{align*}
(by Property 3, since our matrix is lower-triangular and its diagonal entries
are $a-b,b-c,c-d,d$).

[\textit{Remark:} See \cite[Remark 6.16]{detnotes} for a generalization of
this result to $n\times n$-matrices (and for a different proof).]
\end{proof}

\cleardoublepage


\section{Eigenvalues and eigenvectors}

\begin{exercise}
\label{exe.19fla-fin.diag1}Diagonalize the matrix $A:=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 5
\end{array}
\right)  $.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.diag1}.]The characteristic polynomial
of $A$ is%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{2}\right)  =\det\left(
\begin{array}
[c]{cc}%
1-t & 1\\
0 & 5-t
\end{array}
\right)  =\left(  1-t\right)  \left(  5-t\right)
\]
(since the determinant of an upper-triangular matrix equals the product of its
diagonal entries). Hence, the roots of $\chi_{A}\left(  t\right)  $ are $1$
and $5$.

Recall that the eigenvalues of $A$ are the roots of $\chi_{A}\left(  t\right)
$ (by Proposition 2.1.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}). But the roots of $\chi_{A}\left(  t\right)  $ are $1$
and $5$. Hence, the eigenvalues of $A$ are $1$ and $5$.

Next, we will find the eigenvectors. This is an easy matter of solving systems
of linear equations:

\begin{itemize}
\item The $1$-eigenvectors of $A$ are the nonzero vectors $v\in\mathbb{R}^{2}$
satisfying $Av=1v$. In other words, they are the nonzero vectors $\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  \in\mathbb{R}^{2}$ such that $A\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  =1\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $. This is a system of $2$ linear equations in the unknowns $x,y$;
solving it by Gaussian elimination, we obtain $\left\{  y=0\right.  $ (where
$x$ is a free variable). Thus, they are the nonzero scalar multiples of the
vector $\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $.

\item Likewise, the $5$-eigenvectors of $A$ are the nonzero scalar multiples
of the vector $\left(
\begin{array}
[c]{c}%
1\\
4
\end{array}
\right)  $. (Or, equivalently, of the vector $\left(
\begin{array}
[c]{c}%
1/4\\
1
\end{array}
\right)  $, but I like my entries integer if possible.)
\end{itemize}

Finally, let us diagonalize $A$ using the eigenvectors we found. We label our
two eigenvalues as $\lambda_{1}=1$ and $\lambda_{2}=5$, and we label the
corresponding eigenvectors as $u_{1}=\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $ and $u_{2}=\left(
\begin{array}
[c]{c}%
1\\
4
\end{array}
\right)  $. Then, the pair $\left(  u_{1},u_{2}\right)  $ is a basis of
$\mathbb{R}^{2}$ that consists of eigenvectors of $A$, and $\lambda
_{1},\lambda_{2}$ are the corresponding eigenvalues. Hence, we can find a
diagonalization of $A$ using Proposition 1.2.3 \textbf{(a)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-11.pdf}{the class
notes from 2019-11-11}: We set
\begin{align*}
U  &  =\left[  u_{1}\mid u_{2}\right]  =\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 4
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
D  &  =\operatorname*{diag}\left(  \lambda_{1},\lambda_{2}\right)
=\operatorname*{diag}\left(  1,5\right)  =\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 5
\end{array}
\right)  .
\end{align*}
The pair $U,D$ is a diagonalization of $A$ (that is, $U$ is invertible, and
$D$ is diagonal, and we have $A=UDU^{-1}$).
\end{proof}

\cleardoublepage


\section{General}

An $m\times n$-matrix $A$ is said to be \textbf{left-invertible} if it has a
left inverse (i.e., if there exists an $n\times m$-matrix $B$ such that
$BA=I_{n}$).

\begin{exercise}
\label{exe.19fla-fin.TF1}True or false? \textbf{No justifications are required
in this exercise. Just write Y or N into the respective box!}

\bigskip

\textbf{(a)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If a $3\times3$-matrix has at most $2$ nonzero entries, then its
determinant is $0$.

\bigskip

\textbf{(b)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If all entries of an $3\times3$-matrix are nonzero, then its determinant
is nonzero.

\bigskip

\textbf{(c)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The product of two invertible matrices is invertible (if this product is well-defined).

\bigskip

\textbf{(d)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The product of two left-invertible matrices is left-invertible (if this
product is well-defined).

\bigskip

\textbf{(e)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If $v$ and $w$ are two eigenvectors of a $2\times2$-matrix $A$, then $v+w$
is an eigenvector of $A$ as well.

\bigskip

\textbf{(f)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If $A$ and $B$ are two $2\times2$-matrices, then $\det\left(  A+B\right)
=\det A+\det B$.

\bigskip

\textbf{(g)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If $A$ and $B$ are two $2\times2$-matrices, then $\det\left(  AB\right)
=\det A\cdot\det B$.

\bigskip

\textbf{(h)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If two matrices $A$ and $B$ have the same determinant, then they have the
same characteristic polynomial.

\bigskip

\textbf{(i)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The eigenvalues of a matrix $A$ are also the eigenvalues of $A^{T}$.

\bigskip

\textbf{(j)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The eigenvectors of a matrix $A$ are also the eigenvectors of $A^{T}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-fin.TF1}.]\textbf{(a)} \textbf{YES.}

\textit{Proof.} Let $A$ be a $3\times3$-matrix that has at most $2$ nonzero
entries. We must prove that $\det A=0$.

The matrix $A$ has $3$ rows. Thus, if each row of $A$ had at least one nonzero
entry, then $A$ would have at least $3$ nonzero entries, which would
contradict our assumption that $A$ has at most $2$ nonzero entries. Hence, not
every row of $A$ has at least one nonzero entry. In other words, at least one
row of $A$ must have only zero entries. In other words, $A$ has a zero row.
Thus, Corollary 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30} shows that $\det A=0$.

\bigskip

\textbf{(b)} \textbf{NO.}

\textit{Proof.} All entries of the $3\times3$-matrix $\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
1 & 1 & 1\\
1 & 1 & 1
\end{array}
\right)  $ are nonzero, yet this matrix has determinant $0$.

\bigskip

\textbf{(c)} \textbf{YES.}

\textit{Proof.} Let $A_{1}$ and $A_{2}$ be two invertible matrices such that
the product $A_{1}A_{2}$ is well-defined. We must prove that $A_{1}A_{2}$ is invertible.

We have assumed that $A_{1}$ is invertible. In other words, $A_{1}$ has an
inverse. Let $B_{1}$ be this inverse. Recalling the definition of
\textquotedblleft inverse\textquotedblright, we see that this entails
$A_{1}B_{1}=I$ and $B_{1}A_{1}=I$ (where the \textquotedblleft$I$%
\textquotedblright s are identity matrices of appropriate sizes).

We have assumed that $A_{2}$ is invertible. In other words, $A_{2}$ has an
inverse. Let $B_{2}$ be this inverse. Recalling the definition of
\textquotedblleft inverse\textquotedblright, we see that this entails
$A_{2}B_{2}=I$ and $B_{2}A_{2}=I$ (where the \textquotedblleft$I$%
\textquotedblright s are identity matrices of appropriate sizes).

Now,%
\begin{align*}
\left(  A_{1}A_{2}\right)  \left(  B_{2}B_{1}\right)   &  =A_{1}%
\underbrace{A_{2}B_{2}}_{=I}B_{1}=A_{1}\underbrace{IB_{1}}_{=B_{1}}=A_{1}%
B_{1}=I\ \ \ \ \ \ \ \ \ \ \text{and}\\
\left(  B_{2}B_{1}\right)  \left(  A_{1}A_{2}\right)   &  =B_{2}%
\underbrace{B_{1}A_{1}}_{=I}A_{2}=B_{2}\underbrace{IA_{2}}_{=A_{2}}=B_{2}%
A_{2}=I.
\end{align*}
These two equalities show that $B_{2}B_{1}$ is an inverse of $A_{1}A_{2}$ (by
the definition of \textquotedblleft inverse\textquotedblright). Thus, the
matrix $A_{1}A_{2}$ has an inverse, i.e., is invertible.

\bigskip

\textbf{(d)} \textbf{YES.}

\textit{Proof.} Let $A_{1}$ and $A_{2}$ be two left-invertible matrices such
that the product $A_{1}A_{2}$ is well-defined. We must prove that $A_{1}A_{2}$
is left-invertible.

We have assumed that $A_{1}$ is left-invertible. In other words, $A_{1}$ has a
left inverse. Let $B_{1}$ be this left inverse. Recalling the definition of
\textquotedblleft left inverse\textquotedblright, we see that this entails
$B_{1}A_{1}=I$ (where the \textquotedblleft$I$\textquotedblright\ is an
identity matrix of appropriate size).

We have assumed that $A_{2}$ is left-invertible. In other words, $A_{2}$ has a
left inverse. Let $B_{2}$ be this left inverse. Recalling the definition of
\textquotedblleft left inverse\textquotedblright, we see that this entails
$B_{2}A_{2}=I$ (where the \textquotedblleft$I$\textquotedblright\ is an
identity matrix of appropriate size).

Now,%
\[
\left(  B_{2}B_{1}\right)  \left(  A_{1}A_{2}\right)  =B_{2}\underbrace{B_{1}%
A_{1}}_{=I}A_{2}=B_{2}\underbrace{IA_{2}}_{=A_{2}}=B_{2}A_{2}=I.
\]
This shows that $B_{2}B_{1}$ is a left inverse of $A_{1}A_{2}$ (by the
definition of \textquotedblleft left inverse\textquotedblright). Thus, the
matrix $A_{1}A_{2}$ has a left inverse, i.e., is left-invertible.

[\textit{Remark:} Clearly, an analogous argument can be used to prove the
analogous fact about right-invertible matrices.]

\bigskip

\textbf{(e)} \textbf{NO.}

\textit{Proof.} For a simple example, let us pick $A=\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 2
\end{array}
\right)  $. Then, both $v:=\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $ and $w:=\left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  $ are eigenvectors of $A$ (for eigenvalues $1$ and $2$,
respectively), but $v+w$ is not.

[\textit{Remark:} The claim can be salvaged: If $v$ and $w$ are two
eigenvectors of $A$ for \textbf{the same} eigenvalue, then $v+w$ is either the
zero vector or an eigenvector of $A$ for the same eigenvalue. In other words,
if $\lambda\in\mathbb{R}$ and if $A\in\mathbb{R}^{n\times n}$, then the sum of
any two $\lambda$-eigenvectors of $A$ is either the zero vector or a $\lambda
$-eigenvector of $A$ again.]

\bigskip

\textbf{(f)} \textbf{NO.}

\textit{Proof.} One of the simplest counterexamples is $A=I_{2}$ and $B=I_{2}%
$. These satisfy $\det\left(  A+B\right)  =4$ but $\underbrace{\det A}%
_{=1}+\underbrace{\det B}_{=1}=2$.

\bigskip

\textbf{(g)} \textbf{YES.}

\textit{Proof.} This was Exercise 1 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw3s.pdf}{homework set \#3}.
It is also a particular case of the fact that $\det\left(  AB\right)  =\det
A\cdot\det B$ whenever $A$ and $B$ are two square matrices of the same size.
(This is Theorem 1.5.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}, where I give two references to proofs of this fact.)

\bigskip

\textbf{(h)} \textbf{NO}.

\textit{Proof.} For example, the matrices $\left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & 2
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{cc}%
4 & 0\\
0 & 1
\end{array}
\right)  $ have the same determinant (namely, $4$), but different
characteristic polynomials (namely, $\left(  t-2\right)  ^{2}$ versus $\left(
t-4\right)  \left(  t-1\right)  $).

\bigskip

\textbf{(i)} \textbf{YES}.

\textit{Proof.} Let $A$ be an $n\times n$-matrix. We must prove that the
eigenvalues of $A$ are the eigenvalues of $A^{T}$.

It suffices to show that the characteristic polynomial of $A$ is the
characteristic polynomial of $A^{T}$ (since the eigenvalues of a matrix are
the roots of its characteristic polynomial\footnote{by Proposition 2.1.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}}).

The matrix $tI_{n}$ is a diagonal matrix (with $t$'s on the diagonal), and
thus equals its own transpose. In other words, $\left(  tI_{n}\right)
^{T}=tI_{n}$.

It is easy to see that $\left(  C-D\right)  ^{T}=C^{T}-D^{T}$ for any two
$n\times n$-matrices $C$ and $D$. Thus, $\left(  A-tI_{n}\right)  ^{T}%
=A^{T}-\underbrace{\left(  tI_{n}\right)  ^{T}}_{=tI_{n}}=A^{T}-tI_{n}$.
Taking determinants on both sides of this equality, we find $\det\left(
\left(  A-tI_{n}\right)  ^{T}\right)  =\det\left(  A^{T}-tI_{n}\right)  $.

But Theorem 1.3.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the class
notes from 2019-10-23} shows that $\det\left(  C^{T}\right)  =\det C$ for any
$n\times n$-matrix $C$. Applying this to $C=A-tI_{n}$, we obtain $\det\left(
\left(  A-tI_{n}\right)  ^{T}\right)  =\det\left(  A-tI_{n}\right)  $. Hence,%
\[
\det\left(  A-tI_{n}\right)  =\det\left(  \left(  A-tI_{n}\right)
^{T}\right)  =\det\left(  A^{T}-tI_{n}\right)  .
\]
The left hand side of this equality is $\chi_{A}\left(  t\right)  $ (since
this is how the characteristic polynomial $\chi_{A}$ is defined), whereas the
right hand side is $\chi_{A^{T}}\left(  t\right)  $ (since this is how the
characteristic polynomial $\chi_{A^{T}}$ is defined). Hence, this equality
rewrites as $\chi_{A}\left(  t\right)  =\chi_{A^{T}}\left(  t\right)  $. In
other words, the characteristic polynomial of $A$ is the characteristic
polynomial of $A^{T}$. This completes our proof.

\bigskip

\textbf{(j)} \textbf{NO}.

\textit{Proof.} For example, $\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $ is an eigenvector of the matrix $\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  $, but not of its transpose.
\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[18s-hw4s]{18s-hw4s}Darij Grinberg, \textit{UMN Fall 2018 Math 4707
homework set \#4 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw4s.pdf}

\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

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