\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, November 11, 2019 14:33:42}
%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{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\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): homework set 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 201-003 Fall 2019 (Darij Grinberg): homework set 3 with
solutions}
\end{center}

\begin{exercise}
\label{exe.detAB.2x2}Prove that
\[
\det\left(  AB\right)  =\det A\cdot\det B
\]
holds for any $2\times2$-matrices $A=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
c & d\\
c^{\prime} & d^{\prime}%
\end{array}
\right)  $.

[In class, I said that this holds for square matrices of any size, but I
didn't give a proof. You cannot use this general fact without proof here.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.detAB.2x2}.]Recall that every $2\times2$-matrix
$C$ satisfies
\begin{equation}
\det C=C_{1,1}C_{2,2}-C_{1,2}C_{2,1}. \label{sol.detAB.2x2.detC=}%
\end{equation}
(This is what the definition of a determinant boils down to when applied to a
$2\times2$-matrix.)

Let $A$ and $B$ be two $2\times2$-matrices. Write $A$ and $B$ in the forms%
\[
A=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ B=\left(
\begin{array}
[c]{cc}%
c & d\\
c^{\prime} & d^{\prime}%
\end{array}
\right)  .
\]
Thus,
\[
AB=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
c & d\\
c^{\prime} & d^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
ac+bc^{\prime} & ad+bd^{\prime}\\
a^{\prime}c+b^{\prime}c^{\prime} & a^{\prime}d+b^{\prime}d^{\prime}%
\end{array}
\right)
\]
(by the definition of the product of two matrices). Hence,
(\ref{sol.detAB.2x2.detC=}) yields%
\begin{equation}
\det\left(  AB\right)  =\left(  ac+bc^{\prime}\right)  \left(  a^{\prime
}d+b^{\prime}d^{\prime}\right)  -\left(  ad+bd^{\prime}\right)  \left(
a^{\prime}c+b^{\prime}c^{\prime}\right)  . \label{sol.detAB.2x2.1}%
\end{equation}
On the other hand, (\ref{sol.detAB.2x2.detC=}) also yields
\[
\det A=ab^{\prime}-ba^{\prime}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \det B=cd^{\prime}-dc^{\prime}.
\]
Multiplying these two equalities, we find%
\begin{equation}
\det A\cdot\det B=\left(  ab^{\prime}-ba^{\prime}\right)  \cdot\left(
cd^{\prime}-dc^{\prime}\right)  . \label{sol.detAB.2x2.2}%
\end{equation}


Now, straightforward expanding (and cancelling terms) shows that the right
hand sides of (\ref{sol.detAB.2x2.1}) and (\ref{sol.detAB.2x2.2}) are equal
(and, in fact, equal to $ab^{\prime}cd^{\prime}-ab^{\prime}dc^{\prime
}-ba^{\prime}cd^{\prime}+ba^{\prime}dc^{\prime}$). Thus, the left hand sides
of (\ref{sol.detAB.2x2.1}) and (\ref{sol.detAB.2x2.2}) are equal as well. In
other words, $\det\left(  AB\right)  =\det A\cdot\det B$. This solves the exercise.
\end{proof}

\begin{exercise}
\label{exe.ps4.5}Let $a,b,c,d,e,f,g,h,i,j,k,\ell,m,n,o,p$ be any numbers.

\textbf{(a)} Find a simple formula for the determinant%
\[
\det\left(
\begin{array}
[c]{cccc}%
a & b & c & d\\
\ell & 0 & 0 & e\\
k & 0 & 0 & f\\
j & i & h & g
\end{array}
\right)  .
\]


\textbf{(b)} Find a simple formula for the determinant%
\[
\det\left(
\begin{array}
[c]{ccccc}%
a & b & c & d & e\\
f & 0 & 0 & 0 & g\\
h & 0 & 0 & 0 & i\\
j & 0 & 0 & 0 & k\\
\ell & m & n & o & p
\end{array}
\right)  .
\]
(Do not mistake the \textquotedblleft$o$\textquotedblright\ for a
\textquotedblleft$0$\textquotedblright.)

[\textbf{Hint:} Part \textbf{(b)} is simpler than part \textbf{(a)}.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.ps4.5}.]Of course, both parts of Exercise
\ref{exe.ps4.5} can be proved by straightforward application of the definition
of a determinant, provided you are willing to write down a sum of $24$
products (for part \textbf{(a)}) and a sum of $120$ products (for part
\textbf{(b)}). But it is easier to \textquotedblleft haggle\textquotedblright%
\ the sizes of these sums down before doing so:

\textbf{(a)} Let $A$ be the matrix $\left(
\begin{array}
[c]{cccc}%
a & b & c & d\\
\ell & 0 & 0 & e\\
k & 0 & 0 & f\\
j & i & h & g
\end{array}
\right)  $. We want to find $\det A$.

Note that we have $A_{2,2}=0$ and $A_{2,3}=0$ and $A_{3,2}=0$ and $A_{3,3}=0$.
(These are the four $0$ entries in the middle of the matrix $A$.)

The definition of a determinant yields%
\begin{equation}
\det A=\sum_{\sigma\text{ is a permutation of }\left[  4\right]
}\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(  3\right)  }A_{4,\sigma
\left(  4\right)  }. \label{sol.ps4.5.a.1}%
\end{equation}


The sum on the right hand side of (\ref{sol.ps4.5.a.1}) has $24$ addends.
However, some of them are $0$. Namely, every addend corresponding to a
permutation $\sigma$ of $\left[  4\right]  $ satisfying $\sigma\left(
2\right)  \notin\left\{  1,4\right\}  $ must be $0$%
\ \ \ \ \footnote{\textit{Proof.} Let $\sigma$ be a permutaiton of $\left[
4\right]  $ such that $\sigma\left(  2\right)  \notin\left\{  1,4\right\}  $.
We must then show that the addend on the right hand side of
(\ref{sol.ps4.5.a.1}) corresponding to this $\sigma$ must be $0$. In other
words, we have to show that $\operatorname*{sign}\left(  \sigma\right)  \cdot
A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(
3\right)  }A_{4,\sigma\left(  4\right)  }=0$.
\par
We have $\sigma\left(  2\right)  \notin\left\{  1,4\right\}  $, and thus
$\sigma\left(  2\right)  \in\left\{  2,3\right\}  $. Hence, $A_{2,\sigma
\left(  2\right)  }=0$ (because $A_{2,2}=0$ and $A_{2,3}=0$), and thus
$\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}\underbrace{A_{2,\sigma\left(  2\right)  }}_{=0}A_{3,\sigma\left(  3\right)
}A_{4,\sigma\left(  4\right)  }=0$, qed.}. Hence, all such addends can be
removed from the sum (without changing the value of this sum). Similarly, all
addends corresponding to permutations $\sigma$ of $\left[  4\right]  $
satisfying $\sigma\left(  3\right)  \notin\left\{  1,4\right\}  $ must be $0$,
and can therefore also be removed from the sum. The addends that survive these
two removals are the ones that correspond to permutations $\sigma$ of $\left[
4\right]  $ satisfying $\sigma\left(  2\right)  \in\left\{  1,4\right\}  $ and
$\sigma\left(  3\right)  \in\left\{  1,4\right\}  $. It is easy to see that
there are exactly four such permutations: In two-line notation, these
permutations are
\[
\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
2 & 1 & 4 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
2 & 4 & 1 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
3 & 1 & 4 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
3 & 4 & 1 & 2
\end{array}
\right)  .
\]
The addends corresponding to these permutations are $A_{1,2}A_{2,1}%
A_{3,4}A_{4,3}$, $-A_{1,2}A_{2,4}A_{3,1}A_{4,3}$, $-A_{1,3}A_{2,1}%
A_{3,4}A_{4,2}$ and $A_{1,3}A_{2,4}A_{3,1}A_{4,2}$. Hence,
(\ref{sol.ps4.5.a.1}) simplifies to%
\begin{align*}
&  \det A\\
&  =\underbrace{A_{1,2}}_{=b}\underbrace{A_{2,1}}_{=\ell}\underbrace{A_{3,4}%
}_{=f}\underbrace{A_{4,3}}_{=h}-\underbrace{A_{1,2}}_{=b}\underbrace{A_{2,4}%
}_{=e}\underbrace{A_{3,1}}_{=k}\underbrace{A_{4,3}}_{=h}-\underbrace{A_{1,3}%
}_{=c}\underbrace{A_{2,1}}_{=\ell}\underbrace{A_{3,4}}_{=f}\underbrace{A_{4,2}%
}_{=i}+\underbrace{A_{1,3}}_{=c}\underbrace{A_{2,4}}_{=e}\underbrace{A_{3,1}%
}_{=k}\underbrace{A_{4,2}}_{=i}\\
&  =b\ell fh-bekh-c\ell fi+ceki.
\end{align*}
This is a simple enough formula to consider an answer to Exercise
\ref{exe.ps4.5} \textbf{(a)}, but we can simplify it even further. Namely,%
\[
\det A=b\ell fh-bekh-c\ell fi+ceki=\left(  bh-ci\right)  \left(  \ell
f-ek\right)  .
\]
Exercise \ref{exe.ps4.5} \textbf{(a)} is solved.

\textbf{(b)} Let $A$ be the matrix $\left(
\begin{array}
[c]{ccccc}%
a & b & c & d & e\\
f & 0 & 0 & 0 & g\\
h & 0 & 0 & 0 & i\\
j & 0 & 0 & 0 & k\\
\ell & m & n & o & p
\end{array}
\right)  $. We want to find $\det A$.

The most important property of $A$ is that the $3\times3$-submatrix in the
middle of $A$ is filled with zeroes. In other words,%
\begin{equation}
A_{u,v}=0\ \ \ \ \ \ \ \ \ \ \text{for every }u\in\left\{  2,3,4\right\}
\text{ and }v\in\left\{  2,3,4\right\}  . \label{sol.ps4.5.b.2}%
\end{equation}


Now, the definition of a determinant yields%
\begin{equation}
\det A=\sum_{\sigma\text{ is a permutation of }\left[  5\right]
}\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(  3\right)  }A_{4,\sigma
\left(  4\right)  }A_{5,\sigma\left(  5\right)  }. \label{sol.ps4.5.b.3}%
\end{equation}
But every permutation $\sigma$ of $\left[  5\right]  $ satisfies
$A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(  3\right)  }A_{4,\sigma
\left(  4\right)  }=0$\ \ \ \ \footnote{\textit{Proof.} Let $\sigma$ be a
permutation of $\left[  5\right]  $. Then, $\sigma$ is a bijective map, and
hence an injective map. Therefore, the numbers $\sigma\left(  2\right)
,\sigma\left(  3\right)  ,\sigma\left(  4\right)  $ are pairwise distinct.
\par
We now claim that there exists an $u\in\left\{  2,3,4\right\}  $ such that
$\sigma\left(  u\right)  \in\left\{  2,3,4\right\}  $. In order to prove this,
we assume the contrary. Thus, every $u\in\left\{  2,3,4\right\}  $ satisfies
$\sigma\left(  u\right)  \notin\left\{  2,3,4\right\}  $. Hence, every
$u\in\left\{  2,3,4\right\}  $ satisfies $\sigma\left(  u\right)  \in\left\{
1,5\right\}  $ (since $\sigma\left(  u\right)  \in\left\{  1,2,3,4,5\right\}
$ but $\sigma\left(  u\right)  \notin\left\{  2,3,4\right\}  $). In other
words, the numbers $\sigma\left(  2\right)  ,\sigma\left(  3\right)
,\sigma\left(  4\right)  $ belong to $\left\{  1,5\right\}  $. Hence,
$\sigma\left(  2\right)  ,\sigma\left(  3\right)  ,\sigma\left(  4\right)  $
are three distinct numbers belonging to the set $\left\{  1,5\right\}  $. But
this is absurd, since the set $\left\{  1,5\right\}  $ does not contain three
distinct numbers. Hence, we have obtained a contradiction. This shows that our
assumption was wrong.
\par
We thus have shown that there exists an $u\in\left\{  2,3,4\right\}  $ such
that $\sigma\left(  u\right)  \in\left\{  2,3,4\right\}  $. Consider such a
$u$. Applying (\ref{sol.ps4.5.b.2}) to $v=\sigma\left(  u\right)  $, we now
obtain $A_{u,\sigma\left(  u\right)  }=0$. But $u\in\left\{  2,3,4\right\}  $,
so that $A_{u,\sigma\left(  u\right)  }$ is a factor in the product
$A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(  3\right)  }A_{4,\sigma
\left(  4\right)  }$. Hence, the product $A_{2,\sigma\left(  2\right)
}A_{3,\sigma\left(  3\right)  }A_{4,\sigma\left(  4\right)  }$ is $0$ (since
its factor $A_{u,\sigma\left(  u\right)  }$ is $0$), qed.}. Hence,
(\ref{sol.ps4.5.b.3}) becomes%
\begin{align*}
\det A  &  =\sum_{\sigma\text{ is a permutation of }\left[  5\right]
}\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}\underbrace{A_{2,\sigma\left(  2\right)  }A_{3,\sigma\left(  3\right)
}A_{4,\sigma\left(  4\right)  }}_{=0}A_{5,\sigma\left(  5\right)  }\\
&  =\sum_{\sigma\text{ is a permutation of }\left[  5\right]  }%
\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}0A_{5,\sigma\left(  5\right)  }=0.
\end{align*}
Exercise \ref{exe.ps4.5} \textbf{(b)} is thus solved.
\end{proof}

\begin{exercise}
\label{exe.det.laplace-sudoku54321}Find%
\[
\det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right)  .
\]

\end{exercise}

\begin{proof}
[First solution to Exercise \ref{exe.det.laplace-sudoku54321} (sketched).]The
easiest way to solve this is by repeated Laplace expansion (i.e., expanding
the determinant along one row, then expanding the results along a row of
theirs, etc.). Indeed, usually, if $A$ is an $n\times n$-matrix, then Laplace
expansion along a row will express $\det A$ as a sum of $n$ addends, each of
which is (up to sign) a product of an entry of this row times a smaller
determinant. However, if this row has many zero entries, then the
corresponding addends are zero, and thus the expression greatly simplifies.
Here is how this works out for our matrix:

\begin{itemize}
\item We expand $\det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right)  $ along the $3$-rd row. We obtain a sum of $5$ addends:%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right) \\
&  =\left(  -1\right)  ^{3+1}2\det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right)  +\left(  -1\right)  ^{3+2}0\det\left(  \ast\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{3+3}0\det\left(  \ast\right)
+\left(  -1\right)  ^{3+4}0\det\left(  \ast\right)  +\left(  -1\right)
^{3+5}0\det\left(  \ast\right)  ,
\end{align*}
where the symbol \textquotedblleft$\ast$\textquotedblright\ signifies a matrix
that we need not compute because its determinant will be multiplied by $0$
anyway. This simplifies to%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right) \\
&  =\underbrace{\left(  -1\right)  ^{3+1}}_{=1}2\det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right)  =2\det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right)  .
\end{align*}


\item Thus, we need to find $\det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right)  $. We expand this determinant along its $2$-nd row:%
\begin{align*}
&  \det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right) \\
&  =\left(  -1\right)  ^{2+1}0\det\left(  \ast\right)  +\left(  -1\right)
^{2+2}0\det\left(  \ast\right)  +\left(  -1\right)  ^{2+3}3\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{2+4}0\det\left(  \ast\right) \\
&  =\underbrace{\left(  -1\right)  ^{2+3}}_{=-1}3\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)  =-3\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)  .
\end{align*}


\item Thus, we need to find $\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)  $. We expand this determinant along its $3$-rd row:%
\begin{align*}
\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)   &  =\left(  -1\right)  ^{3+1}0\det\left(  \ast\right)  +\left(
-1\right)  ^{3+2}1\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  +\left(  -1\right)  ^{3+3}0\det\left(  \ast\right) \\
&  =\underbrace{\left(  -1\right)  ^{3+2}}_{=-1}1\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  =-\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  .
\end{align*}


\item Thus, we need to find $\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  $. We can do this by playing the same game further (expanding it
along its $2$-nd row), but alternatively we can just use the simple formula
$\det\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  =ad-bc$ to realize that this determinant is $4\cdot0-1\cdot2=-2$.
\end{itemize}

Combining these arguments, we obtain%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right) \\
&  =2\underbrace{\det\left(
\begin{array}
[c]{cccc}%
4 & 3 & 2 & 1\\
0 & 0 & 3 & 0\\
2 & 4 & 3 & 0\\
0 & 1 & 2 & 0
\end{array}
\right)  }_{=-3\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)  }=\underbrace{2\left(  -3\right)  }_{=-6}\underbrace{\det\left(
\begin{array}
[c]{ccc}%
4 & 3 & 1\\
2 & 4 & 0\\
0 & 1 & 0
\end{array}
\right)  }_{=-\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  }\\
&  =\left(  -6\right)  \left(  -\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  \right)  =6\underbrace{\det\left(
\begin{array}
[c]{cc}%
4 & 1\\
2 & 0
\end{array}
\right)  }_{=-2}=6\left(  -2\right)  =-12.
\end{align*}

\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.det.laplace-sudoku54321} (sketched).]We
recall three properties of determinants:

\begin{itemize}
\item \textit{Property 1:} If we swap two rows of an $n\times n$-matrix, then
its determinant gets multiplied by $-1$ (that is, it flips its sign but
preserves its magnitude). (This is Theorem 1.2.6 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)

\item \textit{Property 2:} If we swap two columns of an $n\times n$-matrix,
then its determinant gets multiplied by $-1$ (that is, it flips its sign but
preserves its magnitude). (This is the analogue of Property 1 for columns
instead of rows. It can be deduced from Property 1, as we have seen in Theorem
1.6.1 in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the
class notes from 2019-10-30}.)

\item \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{itemize}

These properties suffice to quickly solve the exercise: Just keep swapping
rows and columns until the matrix becomes triangular. To wit:%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccccc}%
5 & 4 & 3 & 2 & 1\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
-3 & 0 & 1 & 2 & 0
\end{array}
\right)  \\
&  =-\det\left(
\begin{array}
[c]{ccccc}%
-3 & 0 & 1 & 2 & 0\\
1 & 0 & 0 & 3 & 0\\
2 & 0 & 0 & 0 & 0\\
2 & 2 & 4 & 3 & 0\\
5 & 4 & 3 & 2 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Property 1, since we have}\\
\text{swapped the }1\text{-st and }5\text{-th rows here}%
\end{array}
\right)  \\
&  =\det\left(
\begin{array}
[c]{ccccc}%
2 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 3 & 0\\
-3 & 0 & 1 & 2 & 0\\
2 & 2 & 4 & 3 & 0\\
5 & 4 & 3 & 2 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Property 1, since we have}\\
\text{swapped the }1\text{-st and }3\text{-rd rows here}%
\end{array}
\right)  \\
&  =-\underbrace{\det\left(
\begin{array}
[c]{ccccc}%
2 & 0 & 0 & 0 & 0\\
1 & 3 & 0 & 0 & 0\\
-3 & 2 & 1 & 0 & 0\\
2 & 3 & 4 & 2 & 0\\
5 & 2 & 3 & 4 & 1
\end{array}
\right)  }_{\substack{=2\cdot3\cdot1\cdot2\cdot1\\\text{(by Property 3,
since}\\\text{this matrix is lower-triangular)}}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Property 2, since we have}\\
\text{swapped the }2\text{-nd and }4\text{-th columns here}%
\end{array}
\right)  \\
&  =-2\cdot3\cdot1\cdot2\cdot1=-12.
\end{align*}

\end{proof}

\begin{exercise}
\label{exe.det.replace-0-by-1.1}Here is a $5\times5$-matrix: $\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
0 & 0 & 4 & 0 & 0\\
0 & 0 & 1 & 2 & 0\\
0 & 0 & 3 & 0 & 0\\
1 & 0 & 2 & 2 & 1
\end{array}
\right)  $. Its determinant is $0$.

\vspace{0.5038pc}

Find a $0$ entry which can be replaced by a $1$ to give a nonzero determinant.
(You can box this entry in the matrix. Note that you cannot replace more than
one entry simultaneously.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.det.replace-0-by-1.1} (sketched).]These $0$
entries are boxed: $\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
\fbox{$0$} & 0 & 4 & 0 & \fbox{$0$}\\
0 & 0 & 1 & 2 & 0\\
\fbox{$0$} & 0 & 3 & 0 & \fbox{$0$}\\
1 & 0 & 2 & 2 & 1
\end{array}
\right)  $.

Why is it these entries and no others? Well, you can just check every one
until you find one that works. But this requires some patience; there are
faster ways. Here is one: Recall Properties 1, 2 and 3 from the second
solution to Exercise \ref{exe.det.laplace-sudoku54321}. Let us transform our
matrix into a lower-triangular one by swapping rows and swapping columns:
\begin{align*}
&  \left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
0 & 0 & 4 & 0 & 0\\
0 & 0 & 1 & 2 & 0\\
0 & 0 & 3 & 0 & 0\\
1 & 0 & 2 & 2 & 1
\end{array}
\right)  \overset{\text{swap }1\text{-st and }3\text{-rd columns}%
}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
4 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 2 & 0\\
3 & 0 & 0 & 0 & 0\\
2 & 0 & 1 & 2 & 1
\end{array}
\right) \\
&  \overset{\text{swap }3\text{-rd and }4\text{-th columns}}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 0 & 0 & 0\\
4 & 0 & 0 & 0 & 0\\
1 & 0 & 2 & 0 & 0\\
3 & 0 & 0 & 0 & 0\\
2 & 0 & 2 & 1 & 1
\end{array}
\right) \\
&  \overset{\text{swap }1\text{-st and }2\text{-nd columns}}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
1 & 0 & 0 & 0 & 0\\
0 & 4 & 0 & 0 & 0\\
0 & 1 & 2 & 0 & 0\\
0 & 3 & 0 & 0 & 0\\
0 & 2 & 2 & 1 & 1
\end{array}
\right)  .
\end{align*}
We have thus obtained a lower-triangular matrix with diagonal entries
$1,4,2,0,1$. Thus, its determinant is $0$, but if we replace the $0$ on the
diagonal by a $1$, then it will become $1\cdot4\cdot2\cdot1\cdot1\neq0$. Thus
we have found a $0$ that we can replace by a $1$ to obtain a nonzero
determinant. All we need is to trace it through our swaps in order to learn
what cell it occupied in the original matrix. (This is left to the reader.)
\end{proof}

\begin{noncompile}
Exercise \ref{exe.det.replace-0-by-1.1} = work/linalg/msug2/0.1.
\end{noncompile}


\end{document}