\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=Monday, November 18, 2019 23:26:22}
%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-23}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Determinants}

\subsection{Definition of a determinant}

Fix a nonnegative integer $n$.

Last time, we defined:

\begin{itemize}
\item $\left[  n\right]  $ to be the set $\left\{  1,2,\ldots,n\right\}  $.

\item a \textbf{permutation} of $\left[  n\right]  $ to be a bijective map
from $\left[  n\right]  $ to $\left[  n\right]  $.

\item an \textbf{inversion} of a permutation $\sigma$ of $\left[  n\right]  $
to be a pair $\left(  i,j\right)  $ of two integers such that $1\leq i<j\leq
n$ and $\sigma\left(  i\right)  >\sigma\left(  j\right)  $.

\item the \textbf{Coxeter length} $\ell\left(  \sigma\right)  $ of a
permutation $\sigma$ of $\left[  n\right]  $ to be the number of its inversions.

\item the \textbf{sign} $\operatorname*{sign}\left(  \sigma\right)  $ of a
permutation $\sigma$ of $\left[  n\right]  $ to be $\left(  -1\right)
^{\ell\left(  \sigma\right)  }$.
\end{itemize}

Thus, $\operatorname*{sign}\left(  \sigma\right)  $ is $1$ is $\sigma$ has an
even number of inversions, and is $-1$ if $\sigma$ has an odd number of inversions.

[\textbf{Warning:} Some books define permutations rather differently! Also,
the sign of $\sigma$ is also known as the \textbf{signum} or the
\textbf{signature} of $\sigma$, and is often denoted by $\left(  -1\right)
^{\sigma}$ or $\operatorname*{sgn}\left(  \sigma\right)  $ or $\varepsilon
\left(  \sigma\right)  $ or whatever else the author's creativity gives birth
to. Really, you should not expect any two texts on this subject to use the
same notations -- not even if they are written by the same author.]

Now, recall the definition of a determinant:

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

\begin{example}%
\[
\det\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  =ab^{\prime}-ba^{\prime}.
\]

\end{example}

[\textbf{Note:} Different authors define determinants in different ways (in
particular, Lay defines them differently in \cite{Lay}); but the definitions
are all equivalent.]

What can we say about determinants?

First, we will have to understand permutations and their signs better.

\subsection{More about permutations and their signs}

Let $\beta:X\rightarrow Y$ and $\alpha:Y\rightarrow Z$ be two maps. Then,
$\alpha\circ\beta$ (this is called \textquotedblleft$\alpha$ \textbf{after}
$\beta$\textquotedblright\ or \textquotedblleft$\alpha$ \textbf{composed with}
$\beta$\textquotedblright\ or \textquotedblleft the \textbf{composition} of
$\alpha$ and $\beta$\textquotedblright) denotes the map from $X$ to $Z$ that
first applies $\beta$ and then applies $\alpha$ to the result; in other words,%
\[
\left(  \alpha\circ\beta\right)  \left(  x\right)  =\alpha\left(  \beta\left(
x\right)  \right)  .
\]


\begin{proposition}
Let $\alpha$ and $\beta$ be two permutations of $\left[  n\right]  $. Then,
$\alpha\circ\beta$ is a permutation of $\left[  n\right]  $.
\end{proposition}

Recall:

\begin{itemize}
\item If $Z$ is a set, then the \textbf{identity map} of $Z$ means the map
from $Z$ to $Z$ that sends each $z\in Z$ to $z$ itself. (In other words, it
leaves every element unchanged.) It is denoted by $\operatorname*{id}%
\nolimits_{Z}$. If $Z$ is clear from the context, we can just call it
$\operatorname*{id}$ (omitting the subscript $Z$).

\item Two maps $\alpha:X\rightarrow Y$ and $\beta:Y\rightarrow X$ are said to
be \textbf{(mutually) inverse} if
\[
\alpha\circ\beta=\operatorname*{id}\nolimits_{Y}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \beta\circ\alpha=\operatorname*{id}\nolimits_{X}.
\]
Roughly speaking, $\alpha$ and $\beta$ are inverse if each of them undoes the
other. If $\alpha$ and $\beta$ are inverse, then $\beta$ is said to be the
\textbf{inverse} of $\alpha$ and is denoted by $\alpha^{-1}$. (It is easy to
see that a map has at most one inverse\footnote{The argument is exactly the
same as for the fact that each matrix has at most one inverse!}.)
\end{itemize}

Note that the identity map $\operatorname*{id}\nolimits_{\left[  n\right]
}:\left[  n\right]  \rightarrow\left[  n\right]  $ is clearly a permutation of
$\left[  n\right]  $, and thus is also known as the \textbf{identity
permutation}, or simply as the \textbf{identity}. This permutation
$\operatorname*{id}$ has no inversions (since $\operatorname*{id}\left(
k\right)  =k$ for each $k$, and thus it is impossible that $i<j$ but
$\operatorname*{id}\left(  i\right)  >\operatorname*{id}\left(  j\right)  $).
Thus, it has Coxeter length $\ell\left(  \operatorname*{id}\right)  =0$ and
sign $\operatorname*{sign}\left(  \operatorname*{id}\right)  =\left(
-1\right)  ^{\ell\left(  \operatorname*{id}\right)  }=\left(  -1\right)
^{0}=1$.

\begin{proposition}
Let $\alpha$ be a permutation of $\left[  n\right]  $. Then, $\alpha$ has an
inverse $\alpha^{-1}$, and this inverse $\alpha^{-1}$ is also a permutation of
$\left[  n\right]  $.
\end{proposition}

Better yet: A map from $\left[  n\right]  $ to $\left[  n\right]  $ has an
inverse if and only if it is a permutation.

So the permutations of $\left[  n\right]  $ form a set with some extra
structure: You can compose them and invert them, and the results will always
be permutations of $\left[  n\right]  $. Once you get to abstract algebra, you
will recognize that this means that the permutations of $\left[  n\right]  $
form a group, called the $n$-th \textbf{symmetric group}.

\begin{theorem}
\label{thm.det.triang}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}.
\]

\end{theorem}

\begin{example}
For $n=3$, this means%
\[
\det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
0 & b^{\prime} & c^{\prime}\\
0 & 0 & c^{\prime\prime}%
\end{array}
\right)  =ab^{\prime}c^{\prime\prime}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \det\left(
\begin{array}
[c]{ccc}%
a & 0 & 0\\
a^{\prime} & b^{\prime} & 0\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  =ab^{\prime}c^{\prime\prime}.
\]

\end{example}

In particular, the theorem says that the determinant of a diagonal matrix is
the product of its diagonal entries.

\begin{proof}
[Proof of Theorem \ref{thm.det.triang}.]Assume that $A$ is upper-triangular.
(The lower-triangular case is similar.)

Now, the definition of $\det A$ yields
\[
\det A=\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)  }.
\]
In this sum, one addend corresponds to $\sigma=\operatorname*{id}$, the
identity permutation (which sends each number to itself). This addend is%
\[
\underbrace{\operatorname*{sign}\left(  \operatorname*{id}\right)
}_{\substack{=1\\\text{(since }\operatorname*{id}\text{ has no inversions)}%
}}\cdot\underbrace{A_{1,\operatorname*{id}\left(  1\right)  }%
A_{2,\operatorname*{id}\left(  2\right)  }\cdots A_{n,\operatorname*{id}%
\left(  n\right)  }}_{\substack{=A_{1,1}A_{2,2}\cdots A_{n,n}\\\text{(since
}\operatorname*{id}\left(  k\right)  =k\text{ for each }k\text{)}}%
}=A_{1,1}A_{2,2}\cdots A_{n,n}.
\]
This is good! Now we need to prove that all the other addends are $0$.

In other words, we need to prove that if $\sigma$ is a permutation of $\left[
n\right]  $ that is \textbf{not} the identity, then $\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)  }=0$.

So let $\sigma$ be a permutation of $\left[  n\right]  $ that is \textbf{not}
the identity. We must prove that $\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)  }=0$. In other words, we must prove that
\newline$A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }\cdots
A_{n,\sigma\left(  n\right)  }=0$. In other words, we must prove that at least
one of the entries $A_{1,\sigma\left(  1\right)  },A_{2,\sigma\left(
2\right)  },\ldots,A_{n,\sigma\left(  n\right)  }$ is $0$. It will clearly
suffice to show that at least one of these entries lies below the diagonal of
$A$ (because $A$ is upper-triangular, so all its entries below the diagonal
are $0$). In other words, it will suffice to show that at least one
$i\in\left\{  1,2,\ldots,n\right\}  $ satisfies $i>\sigma\left(  i\right)  $
(because then, $A_{i,\sigma\left(  i\right)  }$ will be an entry of $A$ below
the diagonal, and thus will be $0$).

We will prove this by contradiction: Assume the contrary. Thus, no
$i\in\left\{  1,2,\ldots,n\right\}  $ satisfies $i>\sigma\left(  i\right)  $.
In other words, each $i\in\left\{  1,2,\ldots,n\right\}  $ satisfies
$i\leq\sigma\left(  i\right)  $. Hence:

\begin{itemize}
\item we have $n\leq\sigma\left(  n\right)  $, and thus $\sigma\left(
n\right)  =n$ (since $\sigma\left(  n\right)  $ must be in $\left[  n\right]
$);

\item we have $n-1\leq\sigma\left(  n-1\right)  $, and thus $\sigma\left(
n-1\right)  =n-1$ (since $\sigma\left(  n-1\right)  $ must be in $\left[
n\right]  $, but $n$ is already taken as a value of $\sigma$);

\item we have $n-2\leq\sigma\left(  n-2\right)  $, and thus $\sigma\left(
n-2\right)  =n-2$ (since $\sigma\left(  n-2\right)  $ must be in $\left[
n\right]  $, but $n$ and $n-1$ are already taken as values of $\sigma$);

\item and so on.
\end{itemize}

\noindent Thus, $\sigma\left(  i\right)  =i$ for all $i$. In other words,
$\sigma$ is the identity permutation. This contradicts the fact that $\sigma$
is not the identity permutation.

This contradiction completes our proof.
\end{proof}

Recall that we have used the elementary matrices as \textquotedblleft building
blocks\textquotedblright\ for matrices. In a similar way, the transpositions
(which we will now define) serve as \textquotedblleft building
blocks\textquotedblright\ for permutations:

\begin{definition}
Let $p$ and $q$ be two distinct elements of $\left[  n\right]  $. Then, the
\textbf{transposition} $t_{p,q}$ denotes the permutation of $\left[  n\right]
$ that interchanges $p$ with $q$ and leaves all other elements of $\left[
n\right]  $ unchanged.
\end{definition}

Thus, if $n=7$, then
\[
t_{2,4}=\left(
\begin{array}
[c]{ccccccc}%
1 & 2 & 3 & 4 & 5 & 6 & 7\\
1 & 4 & 3 & 2 & 5 & 6 & 7
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{in two-line notation}\right)  .
\]


\begin{example}
Let $n=7$. Consider a permutation $\sigma$ of $\left[  7\right]  $, written in
two-line notation as follows:%
\[
\sigma=\left(
\begin{array}
[c]{ccccccc}%
1 & 2 & 3 & 4 & 5 & 6 & 7\\
\sigma\left(  1\right)  & \sigma\left(  2\right)  & \sigma\left(  3\right)  &
\sigma\left(  4\right)  & \sigma\left(  5\right)  & \sigma\left(  6\right)  &
\sigma\left(  7\right)
\end{array}
\right)  .
\]


\textbf{(a)} The two-line notation of $\sigma\circ t_{2,4}$ is%
\[
\sigma\circ t_{2,4}=\left(
\begin{array}
[c]{ccccccc}%
1 & 2 & 3 & 4 & 5 & 6 & 7\\
\sigma\left(  1\right)  & \sigma\left(  4\right)  & \sigma\left(  3\right)  &
\sigma\left(  2\right)  & \sigma\left(  5\right)  & \sigma\left(  6\right)  &
\sigma\left(  7\right)
\end{array}
\right)
\]
or, equivalently,%
\[
\sigma\circ t_{2,4}=\left(
\begin{array}
[c]{ccccccc}%
1 & 4 & 3 & 2 & 5 & 6 & 7\\
\sigma\left(  1\right)  & \sigma\left(  2\right)  & \sigma\left(  3\right)  &
\sigma\left(  4\right)  & \sigma\left(  5\right)  & \sigma\left(  6\right)  &
\sigma\left(  7\right)
\end{array}
\right)  .
\]
In other words, the two-line notation of $\sigma\circ t_{2,4}$ is obtained
from $\sigma$ by swapping $2$ with $4$ in the top line.

\textbf{(b)} The two-line notation of $t_{2,4}\circ\sigma$ is obtained from
$\sigma$ by swapping $2$ with $4$ in the bottom line.
\end{example}

More generally:

\begin{proposition}
\label{prop.perm.sig-tpq-tln}Let $\sigma$ be any permutation of $\left[
n\right]  $. Let $p$ and $q$ be two distinct elements of $\left[  n\right]  $. Then:

\textbf{(a)} The two-line notation of $\sigma\circ t_{p,q}$ is obtained from
the two-line notation of $\sigma$ by swapping $p$ with $q$ in the top line.

\textbf{(b)} The two-line notation of $t_{p,q}\circ\sigma$ is obtained from
the two-line notation of $\sigma$ by swapping $p$ with $q$ in the bottom line.
\end{proposition}

You can easily convince yourself that $\sigma\circ t_{p,q}$ and $t_{p,q}%
\circ\sigma$ are two different permutations in general. (For example,
$t_{1,2}\circ t_{2,3}\neq t_{2,3}\circ t_{1,2}$.)

Recall: The composition of two maps $\alpha$ and $\beta$ is $\alpha\circ\beta
$. We can also define the composition $\alpha_{1}\circ\alpha_{2}\circ
\cdots\circ\alpha_{k}$ of $k$ maps $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$.
(This will be the map that applies $\alpha_{k}$ first, then $\alpha_{k-1}$,
then $\alpha_{k-2}$, and so on.\footnote{Of course, $\alpha_{1}\circ\alpha
_{2}\circ\cdots\circ\alpha_{k}=\alpha_{1}\circ\left(  \alpha_{2}\circ
\alpha_{3}\circ\cdots\circ\alpha_{k}\right)  =\left(  \alpha_{1}\circ
\alpha_{2}\circ\cdots\circ\alpha_{k-1}\right)  \circ\alpha_{k}$, so you can
view a composition of $k$ maps as a result of repeatedly composing them in
pairs.}) A composition of $0$ maps is understood to mean the identity map.

We won't directly use the following theorem, but it explains the role of
transpositions as \textquotedblleft building blocks\textquotedblright\ for
arbitrary permutations:

\begin{theorem}
Any permutation of $\left[  n\right]  $ is a composition of some transpositions.

In other words, if $\sigma$ is a permutation of $\left[  n\right]  $, then we
can write $\sigma$ in the form%
\[
\sigma=t_{p_{1},q_{1}}\circ t_{p_{2},q_{2}}\circ\cdots\circ t_{p_{k},q_{k}%
}\ \ \ \ \ \ \ \ \ \ \text{for some }p_{1},q_{1},p_{2},q_{2},\ldots
,p_{k},q_{k}\in\left[  n\right]  .
\]
(It is possible that $k=0$ here, in which case the right hand side of this
equation should be understood to be a composition of $0$ maps, i.e., the
identity permutation of $\left[  n\right]  $.)
\end{theorem}

\begin{proof}
[Proof idea.]We can rewrite
\[
\sigma=t_{p_{1},q_{1}}\circ t_{p_{2},q_{2}}\circ\cdots\circ t_{p_{k},q_{k}}%
\]
as%
\[
\sigma=t_{p_{1},q_{1}}\circ t_{p_{2},q_{2}}\circ\cdots\circ t_{p_{k},q_{k}%
}\circ\operatorname*{id}.
\]
But this can be restated as \textquotedblleft$\sigma$ is obtained from
$\operatorname*{id}$ by a sequence of swaps of entries in the bottom row (of
the two-line notation)\textquotedblright\ (because of Proposition
\ref{prop.perm.sig-tpq-tln} \textbf{(b)}).

For example, let $n=5$ and $\sigma=\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
2 & 5 & 4 & 1 & 3
\end{array}
\right)  $. Then, let us perform some swaps of entries in the bottom row to
turn $\sigma$ into $\operatorname*{id}$:%
\begin{align*}
\sigma &  =\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
2 & 5 & 4 & 1 & 3
\end{array}
\right) \\
&  \overset{\text{swap }1\text{ with }2}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
1 & 5 & 4 & 2 & 3
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we have done this swap}\\
\text{in order to put }1\text{ in its place}%
\end{array}
\right) \\
&  \overset{\text{swap }2\text{ with }5}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
1 & 2 & 4 & 5 & 3
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we have done this swap}\\
\text{in order to put }2\text{ in its place}%
\end{array}
\right) \\
&  \overset{\text{swap }3\text{ with }4}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
1 & 2 & 3 & 5 & 4
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we have done this swap}\\
\text{in order to put }3\text{ in its place}%
\end{array}
\right) \\
&  \overset{\text{swap }4\text{ with }5}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & 4 & 5\\
1 & 2 & 3 & 4 & 5
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we have done this swap}\\
\text{in order to put }4\text{ in its place}%
\end{array}
\right) \\
&  =\operatorname*{id}.
\end{align*}
This means that
\[
\sigma=t_{1,2}\circ t_{2,5}\circ t_{3,4}\circ t_{4,5}\circ\operatorname*{id}%
=t_{1,2}\circ t_{2,5}\circ t_{3,4}\circ t_{4,5}.
\]


The same logic works in the general case: We just need to find a way to
transform the bottom row of $\sigma$ into $\left(  1,2,3,\ldots,n\right)  $ by
a sequence of swaps. One way to do this is by repeatedly swapping elements
that are in wrong places to bring at least one element into its right place in
each swap.\footnote{This method is called
\href{https://en.wikipedia.org/wiki/Selection_sort}{\textquotedblleft
insertion sort\textquotedblright}.} Another way to do this is by repeatedly
picking an inversion (i.e., a bigger element that is placed left of a smaller
element) and swapping them.\footnote{This method (or one specific
implementation of it) is known as
\href{https://en.wikipedia.org/wiki/Bubble_sort}{\textquotedblleft bubble
sort\textquotedblright}.}
\end{proof}

Now we shall compute the sign of a transposition (\cite[Example B.6]%
{Strickland}):

\begin{proposition}
\label{prop.perm.sigtpq}Let $p$ and $q$ be two distinct elements of $\left[
n\right]  $. Then, $\operatorname*{sign}\left(  t_{p,q}\right)  =-1$.
\end{proposition}

\begin{proof}
Notice that $t_{p,q}=t_{q,p}$. Therefore, we can WLOG assume that $p<q$ (since
otherwise, we can do the same argument with $p$ and $q$ interchanged). Assume
this, and observe that the inversions of $t_{p,q}$ are:

\begin{itemize}
\item $\left(  p,q\right)  $;

\item $\left(  p,i\right)  $ is an inversion for each $i\in\left\{
p+1,p+2,\ldots,q-1\right\}  $;

\item $\left(  i,q\right)  $ is an inversion for each $i\in\left\{
p+1,p+2,\ldots,q-1\right\}  $.
\end{itemize}

Thus, the total number of inversions of $t_{p,q}$ is $1+\left(  q-p-1\right)
+\left(  q-p-1\right)  =2\left(  q-p\right)  -1$, which is clearly odd. In
other words, $\ell\left(  t_{p,q}\right)  $ is odd. Hence,
$\operatorname*{sign}\left(  t_{p,q}\right)  =\left(  -1\right)  ^{\ell\left(
t_{p,q}\right)  }=\left(  -1\right)  ^{\text{something odd}}=-1$.
\end{proof}

The following fact (\cite[Proposition B.13]{Strickland}) is the most important
property of signs of permutations:

\begin{theorem}
\label{thm.perm.sigst}Let $\sigma$ and $\tau$ be two permutations of $\left[
n\right]  $. Then,%
\[
\operatorname*{sign}\left(  \sigma\circ\tau\right)  =\operatorname*{sign}%
\left(  \sigma\right)  \cdot\operatorname*{sign}\left(  \tau\right)  .
\]

\end{theorem}

\begin{proof}
[Proof idea.]The definition of signs yields $\operatorname*{sign}\left(
\sigma\circ\tau\right)  =\left(  -1\right)  ^{\ell\left(  \sigma\circ
\tau\right)  }$ and $\operatorname*{sign}\left(  \sigma\right)  \cdot
\operatorname*{sign}\left(  \tau\right)  =\left(  -1\right)  ^{\ell\left(
\sigma\right)  }\cdot\left(  -1\right)  ^{\ell\left(  \tau\right)  }=\left(
-1\right)  ^{\ell\left(  \sigma\right)  +\ell\left(  \tau\right)  }$. Hence,
it suffices to prove that $\ell\left(  \sigma\circ\tau\right)  $ and
$\ell\left(  \sigma\right)  +\ell\left(  \tau\right)  $ differ by a multiple
of $2$. This is not obvious!\footnote{It is not true that $\ell\left(
\sigma\circ\tau\right)  =\ell\left(  \sigma\right)  +\ell\left(  \tau\right)
$.}

I've shown a \textquotedblleft proof\textquotedblright\ using braids on the
whiteboard. For a formal proof, see \cite[Proposition B.13]{Strickland}.
\end{proof}

\begin{corollary}
\label{cor.perm.sigstpq}Let $\sigma$ be a permutation of $\left[  n\right]  $.
Let $p$ and $q$ be two distinct elements of $\left[  n\right]  $. Then,%
\[
\operatorname*{sign}\left(  \sigma\circ t_{p,q}\right)  =-\operatorname*{sign}%
\left(  \sigma\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \operatorname*{sign}\left(  t_{p,q}\circ\sigma\right)
=-\operatorname*{sign}\left(  \sigma\right)  .
\]

\end{corollary}

\begin{proof}
Applying Theorem \ref{thm.perm.sigst} to $\tau=t_{p,q}$, we find%
\[
\operatorname*{sign}\left(  \sigma\circ t_{p,q}\right)  =\operatorname*{sign}%
\left(  \sigma\right)  \cdot\underbrace{\operatorname*{sign}\left(
t_{p,q}\right)  }_{\substack{=-1\\\text{(by Proposition \ref{prop.perm.sigtpq}%
)}}}=-\operatorname*{sign}\left(  \sigma\right)  .
\]
This proves the first equality. Similarly we can prove the second equality.
\end{proof}

[Note the connection to the \textquotedblleft$15$-game\textquotedblright: see
\url{http://migo.sixbit.org/puzzles/fifteen/} and various other sources.]

\begin{proposition}
\label{prop.perm.siginv}Let $\sigma$ be a permutation of $\left[  n\right]  $.
Then, $\operatorname*{sign}\left(  \sigma^{-1}\right)  =\operatorname*{sign}%
\left(  \sigma\right)  $.
\end{proposition}

\begin{proof}
Apply Theorem \ref{thm.perm.sigst} to $\tau=\sigma^{-1}$. This results in%
\[
\operatorname*{sign}\left(  \sigma\circ\sigma^{-1}\right)
=\operatorname*{sign}\left(  \sigma\right)  \cdot\operatorname*{sign}\left(
\sigma^{-1}\right)  .
\]
But $\operatorname*{sign}\left(  \underbrace{\sigma\circ\sigma^{-1}%
}_{=\operatorname*{id}}\right)  =\operatorname*{sign}\left(
\operatorname*{id}\right)  =1$. So we get $1=\operatorname*{sign}\left(
\sigma\right)  \cdot\operatorname*{sign}\left(  \sigma^{-1}\right)  $. Thus,
$\operatorname*{sign}\left(  \sigma^{-1}\right)  =1/\operatorname*{sign}%
\left(  \sigma\right)  =\operatorname*{sign}\left(  \sigma\right)  $ (since
$\operatorname*{sign}\left(  \sigma\right)  $ is either $1$ or $-1$).
\end{proof}

This all is not really linear algebra; we have rather been doing some basic
combinatorics of permutations that will be used in linear algebra. If you like
this kind of combinatorics, check out \cite{Mulhol16}, \cite{Bump02} and
\cite{Joyner08}.

\subsection{Some determinant identities}

Let us see what all these properties of signs imply for matrices.

\begin{theorem}
\label{thm.det.transpose}If $A$ is any $n\times n$-matrix, then $\det\left(
A^{T}\right)  =\det A$.
\end{theorem}

\begin{example}
For $n=3$, this theorem says that%
\[
\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)  =\det\left(
\begin{array}
[c]{ccc}%
a & a^{\prime} & a^{\prime\prime}\\
b & b^{\prime} & b^{\prime\prime}\\
c & c^{\prime} & c^{\prime\prime}%
\end{array}
\right)  .
\]

\end{example}

\begin{proof}
[Proof of Theorem \ref{thm.det.transpose}.]The definition of the determinant
yields%
\[
\det A=\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)  }%
\]
and%
\begin{align*}
&  \det\left(  A^{T}\right)  \\
&  =\sum_{\sigma\text{ is a permutation of }\left[  n\right]  }%
\underbrace{\operatorname*{sign}\left(  \sigma\right)  }%
_{\substack{=\operatorname*{sign}\left(  \sigma^{-1}\right)  \\\text{(by
Proposition \ref{prop.perm.siginv})}}}\cdot\underbrace{\left(  A^{T}\right)
_{1,\sigma\left(  1\right)  }\left(  A^{T}\right)  _{2,\sigma\left(  2\right)
}\cdots\left(  A^{T}\right)  _{n,\sigma\left(  n\right)  }}%
_{\substack{=A_{\sigma\left(  1\right)  ,1}A_{\sigma\left(  2\right)
,2}\cdots A_{\sigma\left(  n\right)  ,n}\\=A_{1,\sigma^{-1}\left(  1\right)
}A_{2,\sigma^{-1}\left(  2\right)  }\cdots A_{n,\sigma^{-1}\left(  n\right)
}\\\text{(indeed, the numbers }A_{1,\sigma^{-1}\left(  1\right)  }%
,A_{2,\sigma^{-1}\left(  2\right)  },\ldots,A_{n,\sigma^{-1}\left(  n\right)
}\\\text{are the same as the numbers }A_{\sigma\left(  1\right)  ,1}%
,A_{\sigma\left(  2\right)  ,2},\ldots,A_{\sigma\left(  n\right)  ,n}%
\text{,}\\\text{except they are listed in a different order)}}}\\
&  =\sum_{\sigma\text{ is a permutation of }\left[  n\right]  }%
\operatorname*{sign}\left(  \sigma^{-1}\right)  \cdot A_{1,\sigma^{-1}\left(
1\right)  }A_{2,\sigma^{-1}\left(  2\right)  }\cdots A_{n,\sigma^{-1}\left(
n\right)  }.
\end{align*}
The right hand sides of these two equalities are actually the same sum, except
that the addends are in a different order. Indeed, the inverses of all
permutations of $\left[  n\right]  $ are precisely the permutations of
$\left[  n\right]  $. Thus, the right hand sides are equal. Hence, the left
hand sides are equal, i.e., we have $\det A=\det\left(  A^{T}\right)  $.
\end{proof}

\begin{theorem}
\label{thm.det.equal-rows}If an $n\times n$-matrix $A$ has two equal rows,
then $\det A=0$.
\end{theorem}

\begin{example}
Let us check this for a $3\times3$-matrix whose first two rows are equal:%
\[
\det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  =abc^{\prime}+bca^{\prime}+cab^{\prime}-acb^{\prime}-bac^{\prime
}-cba^{\prime}=0,
\]
since the addends cancel each other in pairs.
\end{example}

\begin{proof}
[Proof of Theorem \ref{thm.det.equal-rows} (sketched).]Let us assume that the
$p$-th and the $q$-th row of $A$ are equal, where $p$ and $q$ are two elements
of $\left[  n\right]  $ with $p<q$. Now, the definition of the determinant
says%
\begin{align*}
\det A  &  =\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)  }\\
&  =\sum_{\substack{\sigma\text{ is a permutation of }\left[  n\right]
;\\\operatorname*{sign}\left(  \sigma\right)  =1}}A_{1,\sigma\left(  1\right)
}A_{2,\sigma\left(  2\right)  }\cdots A_{n,\sigma\left(  n\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ -\sum_{\substack{\sigma\text{ is a permutation of
}\left[  n\right]  ;\\\operatorname*{sign}\left(  \sigma\right)
=-1}}A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }\cdots
A_{n,\sigma\left(  n\right)  }%
\end{align*}
(because each permutation $\sigma$ of $\left[  n\right]  $ must satisfy
$\operatorname*{sign}\left(  \sigma\right)  =1$ or $\operatorname*{sign}%
\left(  \sigma\right)  =-1$, and thus we can split the sum up into the part
containing all addends with $\operatorname*{sign}\left(  \sigma\right)  =1$
and the part containing all addends with $\operatorname*{sign}\left(
\sigma\right)  =-1$).

We want to show that each addend of the first sum on the right hand side
equals some addend of the second sum, and actually there is a 1-to-1
correspondence that makes all addends cancel each other.

Recall Corollary \ref{cor.perm.sigstpq}, which stated that
$\operatorname*{sign}\left(  \sigma\circ t_{p,q}\right)
=-\operatorname*{sign}\left(  \sigma\right)  $ for each permutation $\sigma$
of $\left[  n\right]  $. Thus, if $\sigma$ is any permutation of $\left[
n\right]  $, then the two permutations $\sigma$ and $\sigma\circ t_{p,q}$ have
opposite signs. Hence, if the first sum has an addend corresponding to some
$\sigma$, then the second sum has an addend corresponding to $\sigma\circ
t_{p,q}$ (and vice versa). We claim that these two addends will cancel each
other. Why?

Consider a permutation $\sigma$ of $\left[  n\right]  $, and the corresponding
product%
\[
A_{1,\sigma\left(  1\right)  }A_{2,\sigma\left(  2\right)  }\cdots
A_{n,\sigma\left(  n\right)  }.
\]
For the permutation $\sigma\circ t_{p,q}$, the corresponding product will be
the same, except that the factors $A_{p,\sigma\left(  p\right)  }$ and
$A_{q,\sigma\left(  q\right)  }$ get replaced by $A_{p,\sigma\left(  q\right)
}$ and $A_{q,\sigma\left(  p\right)  }$. But this replacement does not change
the product, because%
\[
\underbrace{A_{p,\sigma\left(  p\right)  }}_{\substack{=A_{q,\sigma\left(
p\right)  }\\\text{(since the }p\text{-th}\\\text{and }q\text{-th
rows}\\\text{of }A\text{ are equal)}}}\cdot\underbrace{A_{q,\sigma\left(
q\right)  }}_{\substack{=A_{p,\sigma\left(  q\right)  }\\\text{(since the
}q\text{-th}\\\text{and }p\text{-th rows}\\\text{of }A\text{ are equal)}%
}}=A_{q,\sigma\left(  p\right)  }\cdot A_{p,\sigma\left(  q\right)
}=A_{p,\sigma\left(  q\right)  }\cdot A_{q,\sigma\left(  p\right)  }.
\]
Thus, the products corresponding to $\sigma$ and to $\sigma\circ t_{p,q}$ are
the same. But these products belong to different sums, and thus cancel each
other. This cancellation kills all addends of both sums. Thus, the result will
be $0$. In other words, $\det A=0$.
\end{proof}

\begin{theorem}
\label{thm.det.scale-row}If we scale a row of an $n\times n$-matrix $A$ by a
number $\lambda$, then $\det A$ gets multiplied by $\lambda$.
\end{theorem}

\begin{example}
Let us scale the $2$-nd row of a $3\times3$-matrix by $\lambda$, and see what
happens to its determinant:%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
\lambda a^{\prime} & \lambda b^{\prime} & \lambda c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right) \\
&  =a\left(  \lambda b^{\prime}\right)  c^{\prime\prime}+b\left(  \lambda
c^{\prime}\right)  a^{\prime\prime}+c\left(  \lambda a^{\prime}\right)
b^{\prime\prime}-a\left(  \lambda c^{\prime}\right)  b^{\prime\prime}-b\left(
\lambda a^{\prime}\right)  c^{\prime\prime}-c\left(  \lambda b^{\prime
}\right)  a^{\prime\prime}\\
&  =\lambda\underbrace{\left(  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}\right)  }%
_{=\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)  }\\
&  =\lambda\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)  .
\end{align*}

\end{example}

\begin{proof}
[Proof of Theorem \ref{thm.det.scale-row} (sketched).]The same idea as in the
example works in the general case: Scale a row of $A$ by $\lambda$, and write
the determinant of the resulting matrix as a sum over all permutations of
$\left[  n\right]  $ (as in the definition of a determinant). Each addend of
this sum will contain exactly one copy of $\lambda$, because it will contain
exactly one factor from the row that has been scaled by $\lambda$. Thus, a
$\lambda$ factors out from the determinant, and what remains is the
determinant of the original matrix.
\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[Bump02]{Bump02}Daniel Bump, \textit{Mathematics of the Rubik's Cube},
lecture notes (in 2 versions).\newline\url{http://sporadic.stanford.edu/bump/match/rubik.html}

\bibitem[Joyner08]{Joyner08}W. D. Joyner, \textit{Mathematics of the Rubik's
cube}, 19 August 2008.\newline%
\url{https://web.archive.org/web/20160304122348/http://www.permutationpuzzles.org/rubik/webnotes/}
(link to the PDF at the bottom).

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

\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}

\bibitem[Mulhol16]{Mulhol16}Jamie Mulholland, \textit{Permutation Puzzles: A
Mathematical Perspective},\newline\url{http://www.sfu.ca/~jtmulhol/math302/}

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