\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, February 12, 2021 19:55:24}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-10-21}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Block matrices (aka partitioned matrices)}

This little chapter follows \cite[\S 2.4]{Lay}.

We have already seen constructions like $\left[
\begin{array}
[c]{c}%
A\\
B
\end{array}
\right]  $ or $\left[  A\mid B\right]  $: these were two ways of gluing two
matrices $A$ and $B$ together.

This can be generalized. For example, you can glue four matrices $A,B,C,D$
together to $\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  $ if their dimensions match appropriately. You can do this with more
than four matrices, too. Essentially, you can start with any \textquotedblleft
matrix of matrices\textquotedblright, and glue them together into a single big matrix.

\begin{definition}
\label{def.block.block}Let $n$ and $m$ be two nonnegative integers. Assume you
have $nm$ many matrices $A_{1,1},A_{1,2},\ldots,A_{n,m}$ (that is, you have a
matrix $A_{i,j}$ for each $i\in\left\{  1,2,\ldots,n\right\}  $ and each
$j\in\left\{  1,2,\ldots,m\right\}  $). Then,%
\[
\left[
\begin{array}
[c]{cccc}%
A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
A_{n,1} & A_{n,2} & \cdots & A_{n,m}%
\end{array}
\right]
\]
denotes the matrix obtained by gluing all these $nm$ many matrices together
into a single big matrix. This is only defined if their dimensions match: that is,

\begin{itemize}
\item For any given $j\in\left\{  1,2,\ldots,m\right\}  $, the $n$ matrices
$A_{1,j},A_{2,j},\ldots,A_{n,j}$ must have the same number of columns.

\item For any given $i\in\left\{  1,2,\ldots,n\right\}  $, the $m$ matrices
$A_{i,1},A_{i,2},\ldots,A_{i,m}$ must have the same number of rows.
\end{itemize}
\end{definition}

\begin{example}
Let
\begin{align*}
A  &  =\left(
\begin{array}
[c]{cc}%
a & a^{\prime}\\
a^{\prime\prime} & a^{\prime\prime\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ B=\left(
\begin{array}
[c]{cc}%
b & b^{\prime}\\
b^{\prime\prime} & b^{\prime\prime\prime}%
\end{array}
\right)  ,\\
C  &  =\left(
\begin{array}
[c]{cc}%
c & c^{\prime}\\
c^{\prime\prime} & c^{\prime\prime\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ D=\left(
\begin{array}
[c]{cc}%
d & d^{\prime}\\
d^{\prime\prime} & d^{\prime\prime\prime}%
\end{array}
\right)  .
\end{align*}
Then,%
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  =\left(
\begin{array}
[c]{cccc}%
a & a^{\prime} & b & b^{\prime}\\
a^{\prime\prime} & a^{\prime\prime\prime} & b^{\prime\prime} & b^{\prime
\prime\prime}\\
c & c^{\prime} & d & d^{\prime}\\
c^{\prime\prime} & c^{\prime\prime\prime} & d^{\prime\prime} & d^{\prime
\prime\prime}%
\end{array}
\right)  .
\]

\end{example}

\begin{example}
Let
\begin{align*}
A  &  =\left(
\begin{array}
[c]{cc}%
a & a^{\prime}\\
a^{\prime\prime} & a^{\prime\prime\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ B=\left(
\begin{array}
[c]{c}%
b\\
b^{\prime\prime}%
\end{array}
\right)  ,\\
C  &  =\left(
\begin{array}
[c]{cc}%
c & c^{\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ D=\left(
\begin{array}
[c]{c}%
d
\end{array}
\right)  .
\end{align*}
Then,%
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  =\left(
\begin{array}
[c]{ccc}%
a & a^{\prime} & b\\
a^{\prime\prime} & a^{\prime\prime\prime} & b^{\prime\prime}\\
c & c^{\prime} & d
\end{array}
\right)  .
\]

\end{example}

\begin{convention}
The matrix%
\[
\left[
\begin{array}
[c]{cccc}%
A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
A_{n,1} & A_{n,2} & \cdots & A_{n,m}%
\end{array}
\right]
\]
in Definition \ref{def.block.block} is called the \textbf{block matrix} (or
\textbf{partitioned matrix}) built from the $nm$ matrices $A_{1,1}%
,A_{1,2},\ldots,A_{n,m}$. Its construction is called the \textbf{block-matrix
construction}. We will always use \textbf{square brackets} $\left[  {}\right]
$ to signalize that we are gluing together a bunch of matrices, whereas
\textbf{parentheses} $\left(  {}\right)  $ simply mean that we are forming a
matrix out of numbers. So, the things inside square brackets are matrices to
be glued together, rather than just numbers to be put each in a single cell.

(This notation is not standard; texts like \cite{Strickland} use square
brackets for \textbf{any} matrix.)

The little matrices $A_{i,j}$ are called the \textbf{blocks} in the block
matrix $\left[
\begin{array}
[c]{cccc}%
A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
A_{n,1} & A_{n,2} & \cdots & A_{n,m}%
\end{array}
\right]  $.

You can imagine the blocks being separated by horizontal and vertical lines as
follows:%
\[%
\begin{tabular}
[c]{|c|c|c|c|}\hline
$A_{1,1}$ & $A_{1,2}$ & $\cdots$ & $A_{1,m}$\\\hline
$A_{2,1}$ & $A_{2,2}$ & $\cdots$ & $A_{2,m}$\\\hline
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$\\\hline
$A_{n,1}$ & $A_{n,2}$ & $\cdots$ & $A_{n,m}$\\\hline
\end{tabular}
\ .
\]
These lines are called the \textbf{dividers} of our block matrix. (Of course,
they are not a property of the resulting matrix, but of the way it has been
glued together.)
\end{convention}

So, on the surface, block matrices are a way to just pigeonhole the contents
of a matrix into some sort of boxes -- an organizational tool. However, it
turns out to have extra advantages in the sense that \textbf{sometimes}, you
can manipulate block matrices on the level of blocks.

The most important such situation is when you want to multiply two block
matrices: For example, it would be great if the equality%
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
AU+BW & AV+BT\\
CU+DW & CV+DT
\end{array}
\right]
\]
was true, meaning that we could multiply two block matrices \textquotedblleft
as if their blocks were entries\textquotedblright.

In full generality, this is not true, because depending on the dimensions of
the blocks, products like $AU$ might not even be well-defined. But let us
assume that they are defined. For example:

\begin{example}
Let
\begin{align*}
A  &  =\left(
\begin{array}
[c]{c}%
a
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ B=\left(
\begin{array}
[c]{cc}%
b & b^{\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ C=\left(
\begin{array}
[c]{c}%
c\\
c^{\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ D=\left(
\begin{array}
[c]{cc}%
d & d^{\prime}\\
d^{\prime\prime} & d^{\prime\prime\prime}%
\end{array}
\right)  ,\\
U  &  =\left(
\begin{array}
[c]{c}%
u
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ V=\left(
\begin{array}
[c]{cc}%
v & v^{\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ W=\left(
\begin{array}
[c]{c}%
w\\
w^{\prime}%
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ T=\left(
\begin{array}
[c]{cc}%
t & t^{\prime}\\
t^{\prime\prime} & t^{\prime\prime\prime}%
\end{array}
\right)  .
\end{align*}
Then,%
\begin{align*}
&  \left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right] \\
&  =\left(
\begin{array}
[c]{ccc}%
a & b & b^{\prime}\\
c & d & d^{\prime}\\
c^{\prime} & d^{\prime\prime} & d^{\prime\prime\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
u & v & v^{\prime}\\
w & t & t^{\prime}\\
w^{\prime} & t^{\prime\prime} & t^{\prime\prime\prime}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{ccc}%
au+bw+b^{\prime}w^{\prime} & av+bt+b^{\prime}t^{\prime\prime} & av^{\prime
}+bt^{\prime}+b^{\prime}t^{\prime\prime\prime}\\
cu+dw+d^{\prime}w^{\prime} & cv+dt+d^{\prime}t^{\prime\prime} & cv^{\prime
}+dt^{\prime}+d^{\prime}t^{\prime\prime\prime}\\
d^{\prime\prime}w+c^{\prime}u+d^{\prime\prime\prime}w^{\prime} &
d^{\prime\prime}t+c^{\prime}v+d^{\prime\prime\prime}t^{\prime\prime} &
d^{\prime\prime}t^{\prime}+d^{\prime\prime\prime}t^{\prime\prime\prime
}+v^{\prime}c^{\prime}%
\end{array}
\right)
\end{align*}
and%
\begin{align*}
&  \left[
\begin{array}
[c]{cc}%
AU+BW & AV+BT\\
CU+DW & CV+DT
\end{array}
\right] \\
&  =\left(
\begin{array}
[c]{ccc}%
au+bw+b^{\prime}w^{\prime} & av+bt+b^{\prime}t^{\prime\prime} & av^{\prime
}+bt^{\prime}+b^{\prime}t^{\prime\prime\prime}\\
cu+dw+d^{\prime}w^{\prime} & cv+dt+d^{\prime}t^{\prime\prime} & cv^{\prime
}+dt^{\prime}+d^{\prime}t^{\prime\prime\prime}\\
d^{\prime\prime}w+c^{\prime}u+d^{\prime\prime\prime}w^{\prime} &
d^{\prime\prime}t+c^{\prime}v+d^{\prime\prime\prime}t^{\prime\prime} &
d^{\prime\prime}t^{\prime}+d^{\prime\prime\prime}t^{\prime\prime\prime
}+v^{\prime}c^{\prime}%
\end{array}
\right)  .
\end{align*}
Thus,
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
AU+BW & AV+BT\\
CU+DW & CV+DT
\end{array}
\right]
\]
is true in this case!
\end{example}

This holds more generally:

\begin{theorem}
\label{thm.block.2x2.mul}Let $A$, $B$, $C$, $D$, $U$, $V$, $W$ and $T$ be
matrices that can be glued together to block matrices $\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  $ and $\left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  $. Then,
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
AU+BW & AV+BT\\
CU+DW & CV+DT
\end{array}
\right]
\]
if
\begin{align*}
\left(  \text{the number of columns of }A\right)   &  =\left(  \text{the
number of rows of }U\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
\left(  \text{the number of columns of }B\right)   &  =\left(  \text{the
number of rows of }W\right)  .
\end{align*}

\end{theorem}

\begin{proof}
[Proof idea.]The product
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]
\]
has as many rows as $\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  $ and as many columns as $\left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  $. Thus, we can write this product as a block matrix $\left[
\begin{array}
[c]{cc}%
P & Q\\
R & S
\end{array}
\right]  $ whose horizontal divider is at the same position as the horizontal
divider of $\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  $ (that is, $P$ has as many rows as $A$, and $R$ has as many rows as
$C$) and whose vertical divider is at the same position as the vertical
divider of $\left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]  $ (that is, $P$ has as many columns as $U$, and $Q$ has as many
columns as $V$).

Now, consider the $\left(  i,j\right)  $-th entry of $S$ for some integers $i$
and $j$. This is an entry of the block matrix%
\[
\left[
\begin{array}
[c]{cc}%
P & Q\\
R & S
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]
\]
that lies $i$ rows below the horizontal divider and $j$ columns east of the
vertical divider. Hence, it must equal%
\begin{align*}
&  \operatorname{row}_{i}\left[
\begin{array}
[c]{cc}%
C & D
\end{array}
\right]  \cdot\operatorname{col}_{j}\left[
\begin{array}
[c]{c}%
V\\
T
\end{array}
\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by \cite[Proposition 2.19
\textbf{(b)}]{lina}}\right) \\
&  =\left[
\begin{array}
[c]{cc}%
\operatorname{row}_{i}C & \operatorname{row}_{i}D
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{c}%
\operatorname{col}_{j}V\\
\operatorname{col}_{j}T
\end{array}
\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\operatorname{row}_{i}\left[
\begin{array}
[c]{cc}%
C & D
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
\operatorname{row}_{i}C & \operatorname{row}_{i}D
\end{array}
\right]  \text{ and }\operatorname{col}_{j}\left[
\begin{array}
[c]{c}%
V\\
T
\end{array}
\right]  =\left[
\begin{array}
[c]{c}%
\operatorname{col}_{j}V\\
\operatorname{col}_{j}T
\end{array}
\right]  \right) \\
&  =\underbrace{\left(  \operatorname{row}_{i}C\right)  \cdot\left(
\operatorname{col}_{j}V\right)  }_{=\left(  CV\right)  _{i,j}}%
+\underbrace{\left(  \operatorname{row}_{i}D\right)  \cdot\left(
\operatorname{col}_{j}T\right)  }_{=\left(  DT\right)  _{i,j}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because when you multiply the row vector }\left[
\begin{array}
[c]{cc}%
\operatorname{row}_{i}C & \operatorname{row}_{i}D
\end{array}
\right] \\
\text{with the column vector }\left[
\begin{array}
[c]{c}%
\operatorname{col}_{j}V\\
\operatorname{col}_{j}T
\end{array}
\right]  \text{,}\\
\text{you get a sum where the first few addends are products}\\
\text{of an entry of }\operatorname{row}_{i}C\text{ with an entry of
}\operatorname{col}_{j}V\text{,}\\
\text{while the remaining addends are products}\\
\text{of an entry of }\operatorname{row}_{i}D\text{ with an entry of
}\operatorname{col}_{j}T
\end{array}
\right) \\
&  =\left(  CV\right)  _{i,j}+\left(  DT\right)  _{i,j}=\left(  CV+DT\right)
_{i,j}.
\end{align*}
Thus, $S=CV+DT$. This explains why a part of the matrix
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
C & D
\end{array}
\right]  \left[
\begin{array}
[c]{cc}%
U & V\\
W & T
\end{array}
\right]
\]
(namely, the bottom-right part) is a copy of $CV+DT$. Similarly, you can find
copies of $AU+BW$ and $AV+BT$ and $CU+DW$ in the appropriate positions. Thus,
the matrix equals $\left[
\begin{array}
[c]{cc}%
AU+BW & AV+BT\\
CU+DW & CV+DT
\end{array}
\right]  $.
\end{proof}

Even more generally, you can always multiply two block matrices
\textquotedblleft as if the blocks were entries\textquotedblright, provided
that the products are well-defined (i.e., that the sizes of the parts into
which the vertical dividers subdivide the left matrix are exactly the sizes of
the parts into which the horizontal dividers subdivide the right matrix). Here
is a more rigorous (and probably clearer, too) way to state this:

\begin{theorem}
Consider two block matrices%
\[
\left[
\begin{array}
[c]{cccc}%
A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
A_{n,1} & A_{n,2} & \cdots & A_{n,m}%
\end{array}
\right]  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left[
\begin{array}
[c]{cccc}%
B_{1,1} & B_{1,2} & \cdots & B_{1,p}\\
B_{2,1} & B_{2,2} & \cdots & B_{2,p}\\
\vdots & \vdots & \ddots & \vdots\\
B_{m,1} & B_{m,2} & \cdots & B_{m,p}%
\end{array}
\right]
\]
such that for each $j\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align*}
&  \left(  \text{the number of columns of }A_{i,j}\text{ for any }i\right) \\
&  =\left(  \text{the number of rows of }B_{j,k}\text{ for any }k\right)  .
\end{align*}
Then,%
\begin{align*}
&  \left[
\begin{array}
[c]{cccc}%
A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\
\vdots & \vdots & \ddots & \vdots\\
A_{n,1} & A_{n,2} & \cdots & A_{n,m}%
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cccc}%
B_{1,1} & B_{1,2} & \cdots & B_{1,p}\\
B_{2,1} & B_{2,2} & \cdots & B_{2,p}\\
\vdots & \vdots & \ddots & \vdots\\
B_{m,1} & B_{m,2} & \cdots & B_{m,p}%
\end{array}
\right] \\
&  =\left[
\begin{array}
[c]{ccc}%
A_{1,1}B_{1,1}+A_{1,2}B_{2,1}+\cdots+A_{1,m}B_{m,1} & \cdots & A_{1,1}%
B_{1,p}+A_{1,2}B_{2,p}+\cdots+A_{1,m}B_{m,p}\\
A_{2,1}B_{1,1}+A_{2,2}B_{2,1}+\cdots+A_{2,m}B_{m,1} & \cdots & A_{2,1}%
B_{1,p}+A_{2,2}B_{2,p}+\cdots+A_{2,m}B_{m,p}\\
\vdots & \ddots & \vdots\\
A_{n,1}B_{1,1}+A_{n,2}B_{2,1}+\cdots+A_{n,m}B_{m,1} & \cdots & A_{n,1}%
B_{1,p}+A_{n,2}B_{2,p}+\cdots+A_{n,m}B_{m,p}%
\end{array}
\right]  .
\end{align*}
(The right hand side here is a block matrix, whose $\left(  i,j\right)  $-th
block is $A_{i,1}B_{1,j}+A_{i,2}B_{2,j}+\cdots+A_{i,m}B_{m,j}$.)
\end{theorem}

Block matrices have even nicer properties when some of the blocks are zero matrices:

\begin{definition}
Let $D_{1},D_{2},\ldots,D_{n}$ be any $n$ square matrices (not necessarily of
the same size). Then, the block matrix%
\[
\left[
\begin{array}
[c]{cccc}%
D_{1} & 0 & \cdots & 0\\
0 & D_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & D_{n}%
\end{array}
\right]
\]
(where the $0$s stand for zero matrices of the appropriate sizes) is called a
\textbf{block-diagonal matrix} with diagonal blocks $D_{1},D_{2},\ldots,D_{n}$.
\end{definition}

\begin{example}
For example,
\[
\left(
\begin{array}
[c]{ccc}%
a & a^{\prime} & 0\\
a^{\prime\prime} & a^{\prime\prime\prime} & 0\\
0 & 0 & b
\end{array}
\right)
\]
is a block-diagonal matrix with blocks $D_{1}=\left(
\begin{array}
[c]{cc}%
a & a^{\prime}\\
a^{\prime\prime} & a^{\prime\prime\prime}%
\end{array}
\right)  $ and $D_{2}=\left(
\begin{array}
[c]{c}%
b
\end{array}
\right)  $.
\end{example}

Of course, any square matrix is a block-diagonal matrix, with a single
diagonal block. But you don't gain much from this point of view.
Block-diagonality is at its most useful when the blocks are small.

\begin{proposition}
Consider two block-diagonal matrices%
\[
\left[
\begin{array}
[c]{cccc}%
D_{1} & 0 & \cdots & 0\\
0 & D_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & D_{n}%
\end{array}
\right]  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left[
\begin{array}
[c]{cccc}%
E_{1} & 0 & \cdots & 0\\
0 & E_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & E_{n}%
\end{array}
\right]  ,
\]
where the size of each block $D_{i}$ equals the size of the corresponding
$E_{i}$. Then, the product of these matrices can be computed blockwise:%
\[
\left[
\begin{array}
[c]{cccc}%
D_{1} & 0 & \cdots & 0\\
0 & D_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & D_{n}%
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cccc}%
E_{1} & 0 & \cdots & 0\\
0 & E_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & E_{n}%
\end{array}
\right]  =\left[
\begin{array}
[c]{cccc}%
D_{1}E_{1} & 0 & \cdots & 0\\
0 & D_{2}E_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & D_{n}E_{n}%
\end{array}
\right]  .
\]

\end{proposition}

\begin{example}
Let us see what this says in the case when $n=2$ and all blocks $D_{1}%
,D_{2},E_{1},E_{2}$ are $2\times2$-matrices:%
\begin{align*}
&  \left(
\begin{array}
[c]{cccc}%
a_{1} & a_{2} & 0 & 0\\
a_{1}^{\prime} & a_{2}^{\prime} & 0 & 0\\
0 & 0 & b_{1} & b_{2}\\
0 & 0 & b_{1}^{\prime} & b_{2}^{\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{cccc}%
x_{1} & x_{2} & 0 & 0\\
x_{1}^{\prime} & x_{2}^{\prime} & 0 & 0\\
0 & 0 & y_{1} & y_{2}\\
0 & 0 & y_{1}^{\prime} & y_{2}^{\prime}%
\end{array}
\right)  \\
&  =\left(
\begin{array}
[c]{cccc}%
a_{1}x_{1}+a_{2}x_{1}^{\prime} & a_{1}x_{2}+a_{2}x_{2}^{\prime} & 0 & 0\\
a_{1}^{\prime}x_{1}+a_{2}^{\prime}x_{1}^{\prime} & a_{1}^{\prime}x_{2}%
+a_{2}^{\prime}x_{2}^{\prime} & 0 & 0\\
0 & 0 & b_{1}y_{1}+b_{2}y_{1}^{\prime} & b_{1}y_{2}+b_{2}y_{2}^{\prime}\\
0 & 0 & b_{1}^{\prime}y_{1}+b_{2}^{\prime}y_{1}^{\prime} & b_{1}^{\prime}%
y_{2}+b_{2}^{\prime}y_{2}^{\prime}%
\end{array}
\right)  .
\end{align*}

\end{example}

\begin{definition}
Let $D_{1},D_{2},\ldots,D_{n}$ be any $n$ square matrices (not necessarily of
the same size). Then, the block matrix%
\[
\left[
\begin{array}
[c]{cccc}%
D_{1} & \ast & \cdots & \ast\\
0 & D_{2} & \cdots & \ast\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & D_{n}%
\end{array}
\right]
\]
(where the $\ast$s are arbitrary matrices) is called a
\textbf{block-upper-triangular matrix} with diagonal blocks $D_{1}%
,D_{2},\ldots,D_{n}$.
\end{definition}

\begin{example}
Consider a block-upper-triangular matrix $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ with $A$ and $D$ being square matrices. Assume that $A$ and $D$ are
invertible. Is the whole matrix $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ invertible, too? What is its inverse?

Let $A$ be of size $n\times n$, and let $D$ be of size $m\times m$.

Let us first assume that $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ is invertible, and try to find its inverse. (Once we have a formula
for the inverse, we will then verify directly that it is indeed an inverse,
and thus our invertibility assumption will not be necessary anymore.)

Let the inverse of $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ be $\left[
\begin{array}
[c]{cc}%
X & Y\\
Z & W
\end{array}
\right]  $ (with $X$ being of size $n\times n$ and $W$ of size $m\times m$).
Thus,%
\[
\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cc}%
X & Y\\
Z & W
\end{array}
\right]  =I_{n+m}=\left[
\begin{array}
[c]{cc}%
I_{n} & 0\\
0 & I_{m}%
\end{array}
\right]  .
\]
Comparing this with%
\begin{align*}
\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cc}%
X & Y\\
Z & W
\end{array}
\right]   &  =\left[
\begin{array}
[c]{cc}%
AX+BZ & AY+BW\\
0X+DZ & 0Y+DW
\end{array}
\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem \ref{thm.block.2x2.mul}%
}\right) \\
&  =\left[
\begin{array}
[c]{cc}%
AX+BZ & AY+BW\\
DZ & DW
\end{array}
\right]  ,
\end{align*}
we obtain%
\[
\left[
\begin{array}
[c]{cc}%
AX+BZ & AY+BW\\
DZ & DW
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
I_{n} & 0\\
0 & I_{m}%
\end{array}
\right]  .
\]
Since the block matrices on both sides of this equality have the same
dimensions, we can rewrite this equality as the following system of equations:%
\begin{align*}
AX+BZ  &  =I_{n};\\
AY+BW  &  =0;\\
DZ  &  =0;\\
DW  &  =I_{m}.
\end{align*}
The fourth equation ($DW=I_{m}$) shows that $W$ is a right inverse of $D$, and
thus must be the inverse of $D$ (since a right inverse of a square matrix must
always be its inverse). That is, $W=D^{-1}$. Thus, from $DZ=0$, we can obtain
$Z=0$ (just compare $\underbrace{D^{-1}D}_{=I_{m}}Z=I_{m}Z=Z$ with
$D^{-1}\underbrace{DZ}_{=0}=D^{-1}0=0$). Thus, the first two of our above four
equations become%
\begin{align*}
AX  &  =I_{n};\\
AY+BD^{-1}  &  =0.
\end{align*}
Now, $AX=I_{n}$ entails that $X$ is a right inverse of $A$, and thus is the
inverse of $A$ (since a right inverse of a square matrix must always be its
inverse). Thus, $X=A^{-1}$. Hence, the equation $AY+BD^{-1}=0$ can be solved
for $Y$ (by multiplying with $A^{-1}$ on the left and bringing $A^{-1}BD^{-1}$
on the right hand side): It gives $Y=-A^{-1}BD^{-1}$.

(Be careful when solving these linear equations: Matrix multiplication is not
commutative, so $A^{-1}B$ is not the same as $BA^{-1}$, and you cannot write
$\dfrac{B}{A}$ for it.)

So now we know that $X=A^{-1}$, $Y=-A^{-1}BD^{-1}$, $Z=0$ and $W=D^{-1}$.
Hence, $\left[
\begin{array}
[c]{cc}%
X & Y\\
Z & W
\end{array}
\right]  =\left[
\begin{array}
[c]{cc}%
A^{-1} & -A^{-1}BD^{-1}\\
0 & D^{-1}%
\end{array}
\right]  $. That is, the putative inverse of $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ is $\left[
\begin{array}
[c]{cc}%
A^{-1} & -A^{-1}BD^{-1}\\
0 & D^{-1}%
\end{array}
\right]  $.

Let us now check that this is indeed the case:
\begin{align*}
\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cc}%
A^{-1} & -A^{-1}BD^{-1}\\
0 & D^{-1}%
\end{array}
\right]   &  =\left[
\begin{array}
[c]{cc}%
AA^{-1}+B0 & A\left(  -A^{-1}BD^{-1}\right)  +BD^{-1}\\
0A^{-1}+D0 & 0\left(  -A^{-1}BD^{-1}\right)  +DD^{-1}%
\end{array}
\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem \ref{thm.block.2x2.mul}%
}\right) \\
&  =\left[
\begin{array}
[c]{cc}%
I_{n} & 0\\
0 & I_{m}%
\end{array}
\right]  =I_{n+m}%
\end{align*}
and (by a similar computation)%
\[
\left[
\begin{array}
[c]{cc}%
A^{-1} & -A^{-1}BD^{-1}\\
0 & D^{-1}%
\end{array}
\right]  \cdot\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  =I_{n+m}.
\]
Thus, the matrix $\left[
\begin{array}
[c]{cc}%
A & B\\
0 & D
\end{array}
\right]  $ is indeed invertible and its inverse is $\left[
\begin{array}
[c]{cc}%
A^{-1} & -A^{-1}BD^{-1}\\
0 & D^{-1}%
\end{array}
\right]  $.
\end{example}

\textbf{Caution:} When multiplying two block matrices \textquotedblleft as if
the blocks were numbers\textquotedblright, make sure to keep the order of the
factors intact!%
\[
\left[
\begin{array}
[c]{cc}%
A & B
\end{array}
\right]  \left[
\begin{array}
[c]{c}%
X\\
Y
\end{array}
\right]  =AX+BY\text{ is not the same as }XA+BY
\]
(and $XA$ might not even be well-defined). In every product of blocks, the
factor that comes from the left matrix must come first (because matrix
multiplication is not commutative).

\section{Determinants}

Now, we will study determinants of (square) matrices. I will follow
\cite[Appendix B and \S 12]{Strickland}, which is the best introduction I know
to this subject.

\subsection{Motivation}

Back in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the
2019-10-16 class}, we have learned how to find the inverse of a square matrix
(if it exists). We can use this tactic to compute the inverse of an arbitrary
$2\times2$-matrix $\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $, with the caveat that we sometimes have to divide by certain
numbers that may be $0$. But if we assume that all these numbers are nonzero
(unless they simplify to $0$ for all $a,b,a^{\prime},b^{\prime}$), we get the
result $\left(
\begin{array}
[c]{cc}%
\dfrac{b^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{-b}{ab^{\prime
}-ba^{\prime}}\\
\dfrac{-a^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{a}{ab^{\prime
}-ba^{\prime}}%
\end{array}
\right)  $.

So the inverse of $\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ is the matrix $\left(
\begin{array}
[c]{cc}%
\dfrac{b^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{-b}{ab^{\prime
}-ba^{\prime}}\\
\dfrac{-a^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{a}{ab^{\prime
}-ba^{\prime}}%
\end{array}
\right)  $, as long as $ab^{\prime}-ba^{\prime}\neq0$. Each entry in this
matrix contains the denominator $ab^{\prime}-ba^{\prime}$. Moreover, (as you
can check -- it is not obvious) this denominator determines whether the matrix
has an inverse or not:

\begin{itemize}
\item If $ab^{\prime}-ba^{\prime}=0$, then $\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ has no inverse.

\item If $ab^{\prime}-ba^{\prime}\neq0$, then $\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ has an inverse, which is $\left(
\begin{array}
[c]{cc}%
\dfrac{b^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{-b}{ab^{\prime
}-ba^{\prime}}\\
\dfrac{-a^{\prime}}{ab^{\prime}-ba^{\prime}} & \dfrac{a}{ab^{\prime
}-ba^{\prime}}%
\end{array}
\right)  $.
\end{itemize}

This is nicer than one might expect.

Similarly, we can find the inverse of a $3\times3$-matrix:%
\[
\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  ^{-1}=\left(
\begin{array}
[c]{ccc}%
\dfrac{b^{\prime}c^{\prime\prime}-b^{\prime\prime}c^{\prime}}{D} &
\dfrac{cb^{\prime\prime}-bc^{\prime\prime}}{D} & \dfrac{bc^{\prime}%
-cb^{\prime}}{D}\\
\dfrac{a^{\prime\prime}c^{\prime}-a^{\prime}c^{\prime\prime}}{D} &
\dfrac{ac^{\prime\prime}-ca^{\prime\prime}}{D} & \dfrac{ca^{\prime}%
-ac^{\prime}}{D}\\
\dfrac{a^{\prime}b^{\prime\prime}-a^{\prime\prime}b^{\prime}}{D} &
\dfrac{ba^{\prime\prime}-ab^{\prime\prime}}{D} & \dfrac{ab^{\prime}%
-ba^{\prime}}{D}%
\end{array}
\right)
\]
where $D=ab^{\prime}c^{\prime\prime}+bc^{\prime}a^{\prime\prime}+ca^{\prime
}b^{\prime\prime}-ac^{\prime}b^{\prime\prime}-ba^{\prime}c^{\prime\prime
}-cb^{\prime}a^{\prime\prime}$. Again, all entries have the same denominator,
$D$. Again, $D$ determines whether the inverse exists: If $D=0$, then $\left(
%
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  $ has no inverse; otherwise, $D$ has an inverse, given by the above formula.

What is this number $D$ ? It is a sum of $6$ products, each with a $+$ or $-$
sign. Three of the products have a $+$ sign, and the other three have a $-$
sign. Each product contains exactly one entry from each row of the matrix, and
exactly one entry from each column of the matrix.

Wouldn't it be nice to have such a $D$ for all sizes of square matrices?

So here is our \textbf{wishlist:} We want to assign to each $n\times n$-matrix
$A$ a number $\det A$ (which would generalize the $D$ for $3\times3$-matrices,
and the $ab^{\prime}-ba^{\prime}$ for $2\times2$-matrices) with the following properties:

\begin{itemize}
\item The number $\det A$ is a sum of products of entries of $A$, some with
$-$ signs.

\item Each of these products has $n$ factors, with one from each row and one
from each column of the matrix.

\item The matrix $A$ is invertible if and only if $\det A\neq0$.
\end{itemize}

We have found such numbers for $2\times2$- and $3\times3$-matrices:%
\begin{align*}
\det\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)   &  =ab^{\prime}-ba^{\prime};\\
\det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)   &  =ab^{\prime}c^{\prime\prime}+bc^{\prime}a^{\prime\prime
}+ca^{\prime}b^{\prime\prime}-ac^{\prime}b^{\prime\prime}-ba^{\prime}%
c^{\prime\prime}-cb^{\prime}a^{\prime\prime}.
\end{align*}
Also, it is easy to check that%
\[
\det\left(
\begin{array}
[c]{c}%
a
\end{array}
\right)  =a.
\]


How do we define $\det A$ in general, when $A$ is an arbitrary $n\times n$-matrix?

\begin{itemize}
\item Ideally, $\det A$ should be a sum over all possible \textquotedblleft
generalized diagonals\textquotedblright\ of $A$, where a \textquotedblleft
generalized diagonal\textquotedblright\ is a selection of $n$ entries with one
taken from each row and one taken from each column. For example, the
generalized diagonals of $\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  $ are%
\begin{align*}
&  \left(  a,b^{\prime},c^{\prime\prime}\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
a,c^{\prime},b^{\prime\prime}\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
b,a^{\prime},c^{\prime\prime}\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
b,c^{\prime},a^{\prime\prime}\right)  ,\\
&  \left(  c,a^{\prime},b^{\prime\prime}\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
c,b^{\prime},a^{\prime\prime}\right)  .
\end{align*}
(The order doesn't matter: i.e., we don't distinguish between two
\textquotedblleft generalized diagonals\textquotedblright\ that select the
same entries in a different order. So $\left(  a,b^{\prime},c^{\prime\prime
}\right)  $ is considered the same generalized diagonal as $\left(  b^{\prime
},a,c^{\prime\prime}\right)  $. Thus, we can always list a \textquotedblleft
generalized diagonal\textquotedblright\ in the top-to-bottom order, starting
with the entry in row $1$, and moving down.)

\item Each of these \textquotedblleft generalized diagonals\textquotedblright%
\ is multiplied through and gets a sign ($+$ or $-$). What is the rule for
these signs? For example, here they are for our $3\times3$-matrix:%
\begin{align*}
+  &  \left(  a,b^{\prime},c^{\prime\prime}\right)
,\ \ \ \ \ \ \ \ \ \ -\left(  a,c^{\prime},b^{\prime\prime}\right)
,\ \ \ \ \ \ \ \ \ \ -\left(  b,a^{\prime},c^{\prime\prime}\right)
,\ \ \ \ \ \ \ \ \ \ +\left(  b,c^{\prime},a^{\prime\prime}\right)  ,\\
+  &  \left(  c,a^{\prime},b^{\prime\prime}\right)
,\ \ \ \ \ \ \ \ \ \ -\left(  c,b^{\prime},a^{\prime\prime}\right)  .
\end{align*}

\end{itemize}

\subsection{Permutations}

In order to formalize the \textquotedblleft generalized
diagonals\textquotedblright\ without even speaking of matrices, and
subsequently to define their signs, we will use \textbf{permutations}:

\begin{definition}
Let $n$ be a nonnegative integer. Let $\left[  n\right]  $ be the $n$-element
set $\left\{  1,2,\ldots,n\right\}  $.

A \textbf{permutation} of $\left[  n\right]  $ means a bijective map from
$\left[  n\right]  $ to $\left[  n\right]  $.
\end{definition}

Here, a map $f$ from a set $X$ to a set $Y$ is said to be

\begin{itemize}
\item \textbf{injective} (aka 1-to-1) if it sends distinct elements of $X$ to
distinct elements of $Y$ (that is, if $x_{1}\neq x_{2}$, then $f\left(
x_{1}\right)  \neq f\left(  x_{2}\right)  $);

\item \textbf{surjective} (aka onto) if every element of $Y$ is taken as a
value of $f$ (that is, for each $y\in Y$, there exists some $x\in X$ such that
$f\left(  x\right)  =y$);

\item \textbf{bijective} if it is both injective and surjective.
\end{itemize}

You can catch up on basic properties of maps (also known as functions) from
sources such as \cite[\S 4.4--4.5]{LeLeMe16}, \cite[\S 12.2]{Hammac15} or
\cite[\S 3.F]{Day-proofs}.

We can write a map $f:X\rightarrow Y$ in \textbf{two-line notation}, meaning
that we list the elements of $X$ as $x_{1},x_{2},\ldots,x_{k}$ (in some order)
and write $f=\left(
\begin{array}
[c]{cccc}%
x_{1} & x_{2} & \cdots & x_{k}\\
f\left(  x_{1}\right)  & f\left(  x_{2}\right)  & \cdots & f\left(
x_{k}\right)
\end{array}
\right)  $ (not a matrix, just a table of values of $f$). Using this notation,
the permutations of $\left[  3\right]  $ are%
\begin{align*}
&  \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 2 & 3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 3 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 1 & 3
\end{array}
\right)  ,\\
&  \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 3 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 1 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 2 & 1
\end{array}
\right)  .
\end{align*}


The permutations of $\left[  n\right]  $ will be used to index the products
that appear in $\det A$ when $A$ is an $n\times n$-matrix.

If $A$ is any $n\times n$-matrix, and $\sigma$ is a permutation of $\left[
n\right]  $, then we can obtain a \textquotedblleft generalized
diagonal\textquotedblright\ of $A$ by picking

\begin{itemize}
\item the $\sigma\left(  1\right)  $-st entry from the $1$-st row of $A$;

\item the $\sigma\left(  2\right)  $-nd entry from the $2$-nd row of $A$;

\item the $\sigma\left(  3\right)  $-rd entry from the $3$-rd row of $A$;

\item and so on
\end{itemize}

\noindent(i.e., we pick the $\sigma\left(  i\right)  $-th entry from row $i$
of $A$ for each $i\in\left\{  1,2,\ldots,n\right\}  $). The product of these
entries is%
\[
A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }\cdots
A_{n,\sigma\left(  n\right)  }.
\]
This product contains exactly one entry from each row (clearly), and
furthermore contains exactly one entry from each column (indeed, the
injectivity of $\sigma$ shows that it contains no two entries from the same
column, whereas the surjectivity of $\sigma$ shows that it contains at least
one entry from each column). Thus, the entries in this product form a
\textquotedblleft generalized diagonal\textquotedblright.

Thus, we have a guess which products should occur in $\det A$: namely, the
products%
\[
A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }\cdots
A_{n,\sigma\left(  n\right)  }\ \ \ \ \ \ \ \ \ \ \text{for }\sigma\text{
being a permutation of }\left[  n\right]  .
\]
But how do we decide what signs ($+$ or $-$) they get?

So we want to assign a sign to each permutation $\sigma$. Here is how we do this:

\begin{definition}
Let $\sigma$ be a permutation of $\left[  n\right]  $.

\textbf{(a)} An \textbf{inversion} of $\sigma$ means a pair $\left(
i,j\right)  $ of integers such that $1\leq i<j\leq n$ but $\sigma\left(
i\right)  >\sigma\left(  j\right)  $. (This is called a \textbf{reversal} of
$\sigma$ in \cite[Appendix B]{Strickland}.)

\textbf{(b)} We define $\ell\left(  \sigma\right)  $ as the number of
inversions of $\sigma$. (This is called the \textbf{Coxeter length }of
$\sigma$. It is denoted by $l\left(  \sigma\right)  $ in \cite[Appendix
B]{Strickland}.)

\textbf{(c)} We define the \textbf{sign} $\operatorname*{sign}\sigma$ of
$\sigma$ to be $\left(  -1\right)  ^{\ell\left(  \sigma\right)  }$. Thus,

\begin{itemize}
\item we have $\operatorname*{sign}\sigma=1$ if $\sigma$ has an even number of inversions;

\item we have $\operatorname*{sign}\sigma=-1$ if $\sigma$ has an odd number of inversions.
\end{itemize}

\noindent(Note that $\operatorname*{sign}\sigma$ is called
$\operatorname*{sgn}\left(  \sigma\right)  $ in \cite[Appendix B]{Strickland}.)
\end{definition}

\Needspace{20pc}

\begin{example}
Let us compute the inversions of the $6$ permutations of $\left[  3\right]  $:%
\[%
\begin{tabular}
[c]{|l|l|l|l|}\hline
permutation $\sigma$ & inversions & $\ell\left(  \sigma\right)  $ & sign
$\operatorname*{sign}\sigma$\\\hline\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 2 & 3
\end{array}
\right)  $ & none & $0$ & $\left(  -1\right)  ^{0}=1$\\\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
1 & 3 & 2
\end{array}
\right)  $ & $\left(  2,3\right)  $ & $1$ & $\left(  -1\right)  ^{1}%
=-1$\\\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 1 & 3
\end{array}
\right)  $ & $\left(  1,2\right)  $ & $1$ & $\left(  -1\right)  ^{1}%
=-1$\\\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 3 & 1
\end{array}
\right)  $ & $\left(  2,3\right)  $ and $\left(  1,3\right)  $ & $2$ &
$\left(  -1\right)  ^{2}=1$\\\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 1 & 2
\end{array}
\right)  $ & $\left(  1,2\right)  $ and $\left(  1,3\right)  $ & $2$ &
$\left(  -1\right)  ^{2}=1$\\\hline
$\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
3 & 2 & 1
\end{array}
\right)  $ & $\left(  1,2\right)  $ and $\left(  1,3\right)  $ and $\left(
2,3\right)  $ & $3$ & $\left(  -1\right)  ^{3}=-1$\\\hline
\end{tabular}
\ \
\]

\end{example}

Now, we can try to define $\det A$ as a sum of products of generalized
diagonals, one for each permutation $\sigma$ of $\left[  n\right]  $. These
products get multiplied by $\operatorname*{sign}\sigma$, and then get all
added together:

\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}\sigma\cdot A_{1,\sigma\left(  1\right)  }A_{2,\sigma
\left(  2\right)  }\cdots A_{n,\sigma\left(  n\right)  }.
\]

\end{definition}

Here, the $\sum$ sign is the
\textbf{\href{https://en.wikipedia.org/wiki/Summation}{\textbf{summation
sign}}}; thus, the determinant is defined as a big sum, with one addend for
each permutation of $\left[  n\right]  $.

\begin{example}
If $n=3$, then this becomes%
\begin{align*}
\det A  &  =1A_{1,1}A_{2,2}A_{3,3}+\left(  -1\right)  A_{1,1}A_{2,3}%
A_{3,2}+\left(  -1\right)  A_{1,2}A_{2,1}A_{3,3}\\
&  \ \ \ \ \ \ \ \ \ \ +1A_{1,2}A_{2,3}A_{3,1}+1A_{1,3}A_{2,1}A_{3,2}+\left(
-1\right)  A_{1,3}A_{2,2}A_{3,1}\\
&  =A_{1,1}A_{2,2}A_{3,3}+A_{1,2}A_{2,3}A_{3,1}+A_{1,3}A_{2,1}A_{3,2}\\
&  \ \ \ \ \ \ \ \ \ \ -A_{1,1}A_{2,3}A_{3,2}-A_{1,2}A_{2,1}A_{3,3}%
-A_{1,3}A_{2,2}A_{3,1}.
\end{align*}
This is exactly the formula $D=ab^{\prime}c^{\prime\prime}+bc^{\prime
}a^{\prime\prime}+ca^{\prime}b^{\prime\prime}-ac^{\prime}b^{\prime\prime
}-ba^{\prime}c^{\prime\prime}-cb^{\prime}a^{\prime\prime}$ when $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  $.
\end{example}

\begin{example}
If $n=2$, then the definition of $\det A$ becomes%
\[
\det A=1A_{1,1}A_{2,2}+\left(  -1\right)  A_{1,2}A_{2,1}=A_{1,1}%
A_{2,2}-A_{1,2}A_{2,1}.
\]
This is exactly $ab^{\prime}-ba^{\prime}$ if $A=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $.
\end{example}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[Day16]{Day-proofs}Martin V. Day, \textit{An Introduction to Proofs
and the Mathematical Vernacular}, 7 December 2016. \newline%
\url{https://web.archive.org/web/20180712152432/https://www.math.vt.edu/people/day/ProofsBook/IPaMV.pdf}
.

\bibitem[Hammac15]{Hammac15}Richard Hammack, \textit{Book of Proof}, 3rd
edition.\newline\url{https://www.people.vcu.edu/~rhammack/BookOfProof/}

\bibitem[Lay]{Lay}David C. Lay, Steven R. Lay, Judi J. McDonald,
\textit{Linear Algebra and its Applications}, 5th edition.

\bibitem[LeLeMe16]{LeLeMe16}Eric Lehman, F. Thomson Leighton, Albert R. Meyer,
\textit{Mathematics for Computer Science}, revised Tuesday 6th June 2018,
\newline\url{https://courses.csail.mit.edu/6.042/spring18/mcs.pdf} .

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