Skip to content

Instantly share code, notes, and snippets.

@VincentTam

VincentTam/determinant-sildes.tex

Created May 1, 2025 20:57
Show Gist options
  • Save VincentTam/82f8e6e8b7e34c48af63973dac5720b9 to your computer and use it in GitHub Desktop.
Save VincentTam/82f8e6e8b7e34c48af63973dac5720b9 to your computer and use it in GitHub Desktop.
Download ZIP
Source code for the LaTeX beamer slides for my presentation on determinants for Simply Study Group
Raw
determinant-sildes.tex
\documentclass[dvipsnames]{beamer}
\usetheme{Madrid}
\usepackage{annotate-equations}
\renewcommand{\eqnhighlightshade}{30}
\usepackage{gensymb}
\usepackage{quiver} % for "swap pathways"
\usepackage{cancel}
\usetikzlibrary{graphs.standard, quotes} % for coins
\usepackage{wrapfig} % for coins
\usepackage{extpfeil} % for extensible arrows
\usepackage{stackrel}
\newcommand{\mathreflectbox}[1]{\text{\reflectbox{$#1$}}} % math mode reflect box
\newcommand{\xmapsfrom}[2]{\mathrel{\mathreflectbox{\xmapsto[\mathreflectbox{#1}]{\mathreflectbox{#2}}}}}
\def\towidthB#1#2#3{\hbox to#2{\hss$#1#3$\hss}}
\def\towidthA#1#2{\towidthB{#1}#2}
\def\towidth#1#2{\mathpalette\towidthA{{#1}{#2}}}
\newcommand{\mapstofrom}[1]{\mathrel{\begin{matrix} \xmapsto{\towidth{1cm}{#1}} \\[-5pt] \xmapsfrom{\towidth{1cm}{{#1}^{-1}}}{} \end{matrix}}}
\newcommand{\mapstofromA}[3]{\mathrel{\begin{matrix} \xmapsto{\towidth{#1}{#2}} \\[-5pt] \xmapsfrom{\towidth{#1}{{#3}}}{} \end{matrix}}}
\newcommand{\mapstofromZ}{\mathrel{\begin{smallmatrix} \xmapsto{\towidth{1cm}{}} \\[-3pt] \xmapsfrom{\towidth{1cm}{}}{} \end{smallmatrix}}}
\usepackage{pifont} % for cross mark, checkmark and solid heart
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\mathheart}{\text{\ding{170}}}
\tikzset{bolded/.style={line width=2pt}}
\tikzcdset{ampersand replacement=\&}
\usepackage{pgfplots}
\pgfplotsset{compat=1.18}
\usepgfplotslibrary{patchplots}
\usepackage{mathdots}
\usepackage{nccmath}
\usepackage{nicematrix}
\usetikzlibrary{fit,patterns,decorations} % for nicematrix hatched patterns
\usepackage[outline]{contour} % for coloured text in block header
\contourlength{0.2pt}
\usepackage{multirow} % for matrix inverse section Laplace expansion
\begin{document}
\title{Determinants through permutations}
\author{Vincent Tam}
\institute{Simple Study Group}
\date{2 Dec 2024}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}[plain]
\begin{definition}
Let $A \in {\cal M}_{n \times n}(\eqnmarkbox[black]{R}{R})$.
\vspace{2ex}
\begin{equation*}
\eqnmarkbox[blue]{detA}{\det A} =
\eqnmarkbox[red]{sumSigma}{\sum_{\sigma\in S_n}} \,
\eqnmarkbox[BurntOrange]{sgnSigma}{\mathsf{sgn}(\sigma)} \,
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}}
\end{equation*}
\annotate[yshift=3ex,xshift=1em]{below}{R}{any set closed under `$+$', `$-$' \\ and \textbf{commutative} `$\cdot$' $\xcancel{\text{division}}$}
\only<+->{\annotate[yshift=1em]{left}{detA}{determinant of $A$}}
\only<+->{\annotate[yshift=-0.7ex]{below,left}{sumSigma}{sum over all permutations in $S_n$}}
\only<+->{\annotate[yshift=-2.7ex]{below, label below}{sgnSigma}{sign of $\sigma$}}
\only<+->{\annotate[xshift=-1.5em,yshift=1em]{}{prodI}{product of ``{\color{red}row} {\color{blue}representative}s''}}
\vspace{1ex}
\end{definition}
\only<+>{
\begin{block}{Recall}
In ``$\sigma \in S_n$'',
\begin{itemize}
\item $\sigma$ is a \emph{permutation} of $\{1, \dots, n\}$
\item $S_n$ is called the \emph{symmetric group of degree $n$}
\item In $\sigma = \begin{pmatrix}
{\color{red}\mathheart} & \dots & {\color{red}\blacklozenge} \\
{\color{blue}\spadesuit} & \dots & {\color{blue}\clubsuit}
\end{pmatrix}$, ${\color{blue}\sigma(\mathheart)} = {\color{blue}\spadesuit}$, we can also write ${\color{blue}\sigma(\mathheart)}$ as ${\color{blue}\sigma_\mathheart}$.
\end{itemize}
\end{block}
}
\begin{block}<6->{Example ($n = 3$)}
\only<6>{
\begin{wrapfigure}{r}{0.2\textwidth}
\begin{tikzpicture}[
coin/.style={blue},
graphs/nodes={blue}
]
\node[draw, circle, fill=yellow, minimum size=1cm] at (0,0) {\textdollar 10};
\graph[counterclockwise, n=3] { 1, 2, 3 };
\end{tikzpicture}
\end{wrapfigure}
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}1} & {\color{blue}2} & {\color{blue}3} \end{pmatrix} = \mathsf{id},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{1}$
$\displaystyle A = \begin{pmatrix}
\eqnmarkbox[ForestGreen]{a11}{a_{{\color{red}1}{\color{blue}1}}} & a_{12} & a_{13} \\
a_{21} & \eqnmarkbox[ForestGreen]{a22}{a_{{\color{red}2}{\color{blue}2}}} & a_{23} \\
a_{31} & a_{32} & \eqnmarkbox[ForestGreen]{a33}{a_{{\color{red}3}{\color{blue}3}}}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a11}{a_{{\color{red}1}{\color{blue}1}}} \,
\eqnmarkbox[ForestGreen]{a22}{a_{{\color{red}2}{\color{blue}2}}} \,
\eqnmarkbox[ForestGreen]{a33}{a_{{\color{red}3}{\color{blue}3}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= \eqnmarkbox[BurntOrange]{sgnS2}{+} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}} \\
& \phantom{=}
\end{aligned}$
}
\only<7>{
\begin{wrapfigure}{r}{0.2\textwidth}
\begin{tikzpicture}[
coin/.style={xscale=-1},
graphs/nodes={xscale=-1, blue}
]
\node[draw, circle, fill=yellow, minimum size=1cm, coin] at (0,0) {\textdollar 10};
\graph[counterclockwise, n=3] { 1, 2, 3, 2 <-> [bend left, sloped, "flipped"'] 3 };
\end{tikzpicture}
\end{wrapfigure}
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}1} & {\color{blue}3} & {\color{blue}2} \end{pmatrix},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{-1}$ (${\color{blue}2} \leftrightarrow {\color{blue}3}$ swapped $1 \times$)
$\displaystyle A = \begin{pmatrix}
\eqnmarkbox[ForestGreen]{a11}{a_{{\color{red}1}{\color{blue}1}}} & a_{12} & a_{13} \\
a_{21} & a_{22} & \eqnmarkbox[ForestGreen]{a23}{a_{{\color{red}2}{\color{blue}3}}} \\
a_{31} & \eqnmarkbox[ForestGreen]{a32}{a_{{\color{red}3}{\color{blue}2}}} & a_{33}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a11}{a_{{\color{red}1}{\color{blue}1}}} \,
\eqnmarkbox[ForestGreen]{a23}{a_{{\color{red}2}{\color{blue}3}}} \,
\eqnmarkbox[ForestGreen]{a32}{a_{{\color{red}3}{\color{blue}2}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= +a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}
\eqnmarkbox[BurntOrange]{sgnS2}{-} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}2}}} \\
& \phantom{=}
\end{aligned}$
}
\only<8>{
\begin{wrapfigure}{r}{0.2\textwidth}
\begin{tikzpicture}[
coin/.style={rotate=120, xscale=-1},
graphs/nodes={rotate=120, xscale=-1, blue}
]
\node[draw, circle, fill=yellow, minimum size=1cm, coin] at (0,0) {\textdollar 10};
\graph[counterclockwise, n=3] { 1, 2, 3, 1 <-> [bend left, sloped, "flipped"] 2 };
\end{tikzpicture}
\end{wrapfigure}
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}2} & {\color{blue}1} & {\color{blue}3} \end{pmatrix},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{-1}$ (${\color{blue}1} \leftrightarrow {\color{blue}2}$ swapped $1 \times$)
$\displaystyle A = \begin{pmatrix}
a_{11} & \eqnmarkbox[ForestGreen]{a12}{a_{{\color{red}1}{\color{blue}2}}} & a_{13} \\
\eqnmarkbox[ForestGreen]{a21}{a_{{\color{red}2}{\color{blue}1}}} & a_{22} & a_{23} \\
a_{31} & a_{32} & \eqnmarkbox[ForestGreen]{a33}{a_{{\color{red}3}{\color{blue}3}}}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a12}{a_{{\color{red}1}{\color{blue}2}}} \,
\eqnmarkbox[ForestGreen]{a21}{a_{{\color{red}2}{\color{blue}1}}} \,
\eqnmarkbox[ForestGreen]{a33}{a_{{\color{red}3}{\color{blue}3}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= +a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}
- a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}2}}
\eqnmarkbox[BurntOrange]{sgnS2}{-} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}3}}} \\
& \phantom{=}
\end{aligned}$
}
\only<9>{
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}2} & {\color{blue}3} & {\color{blue}1} \end{pmatrix},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{1}$ (${\color{blue}1} \leftrightarrow {\color{blue}2}, {\color{blue}1} \leftrightarrow {\color{blue}3}$ swapped $2 \times$)
$\displaystyle A = \begin{pmatrix}
a_{11} & \eqnmarkbox[ForestGreen]{a12}{a_{{\color{red}1}{\color{blue}2}}} & a_{13} \\
a_{21} & a_{22} & \eqnmarkbox[ForestGreen]{a23}{a_{{\color{red}2}{\color{blue}3}}} \\
\eqnmarkbox[ForestGreen]{a31}{a_{{\color{red}3}{\color{blue}1}}} & a_{32} & a_{33}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a12}{a_{{\color{red}1}{\color{blue}2}}} \,
\eqnmarkbox[ForestGreen]{a23}{a_{{\color{red}2}{\color{blue}3}}} \,
\eqnmarkbox[ForestGreen]{a31}{a_{{\color{red}3}{\color{blue}1}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= +a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}
- a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}2}}
- a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}3}} \\
& \,\phantom{=} \eqnmarkbox[BurntOrange]{sgnS2}{+} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}1}}}
\end{aligned}$
}
\only<10>{
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}3} & {\color{blue}1} & {\color{blue}2} \end{pmatrix},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{1}$ (${\color{blue}2} \leftrightarrow {\color{blue}3}, {\color{blue}1} \leftrightarrow {\color{blue}3}$ swapped $2 \times$)
$\displaystyle A = \begin{pmatrix}
a_{11} & a_{12} & \eqnmarkbox[ForestGreen]{a13}{a_{{\color{red}1}{\color{blue}3}}} \\
\eqnmarkbox[ForestGreen]{a21}{a_{{\color{red}2}{\color{blue}1}}} & a_{22} & a_{23} \\
a_{31} & \eqnmarkbox[ForestGreen]{a32}{a_{{\color{red}3}{\color{blue}2}}} & a_{33}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a13}{a_{{\color{red}1}{\color{blue}3}}} \,
\eqnmarkbox[ForestGreen]{a21}{a_{{\color{red}2}{\color{blue}1}}} \,
\eqnmarkbox[ForestGreen]{a32}{a_{{\color{red}3}{\color{blue}2}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= +a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}
- a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}2}}
- a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}3}} \\
& \,\phantom{=} + a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}1}}
\eqnmarkbox[BurntOrange]{sgnS2}{+} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}3}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}2}}}
\end{aligned}$
}
\only<11>{
\begin{wrapfigure}{r}{0.2\textwidth}
\begin{tikzpicture}[
coin/.style={rotate=240, xscale=-1},
graphs/nodes={rotate=240, xscale=-1, blue}
]
\node[draw, circle, fill=yellow, minimum size=1cm, coin] at (0,0) {\textdollar 10};
\graph[counterclockwise, n=3] { 1, 2, 3, 1 <-> [bend right, sloped, "flipped"] 3 };
\end{tikzpicture}
\end{wrapfigure}
$\sigma = \begin{pmatrix} {\color{red}1} & {\color{red}2} & {\color{red}3} \\ {\color{blue}3} & {\color{blue}2} & {\color{blue}1} \end{pmatrix},
\eqnmarkbox[BurntOrange]{sgnS1}{\mathsf{sgn}(\sigma)} = \eqnmarkbox[BurntOrange]{sgnS2}{-1}$ (${\color{blue}1} \leftrightarrow {\color{blue}3}$ swapped $1 \times$)
$\displaystyle A = \begin{pmatrix}
a_{11} & a_{12} & \eqnmarkbox[ForestGreen]{a13}{a_{{\color{red}1}{\color{blue}3}}} \\
a_{21} & \eqnmarkbox[ForestGreen]{a22}{a_{{\color{red}2}{\color{blue}2}}} & a_{23} \\
\eqnmarkbox[ForestGreen]{a31}{a_{{\color{red}3}{\color{blue}1}}} & a_{32} & a_{33}
\end{pmatrix},
\eqnmarkbox[ForestGreen]{prodI}{\prod_{i=1}^n a_{{\color{red}i},{\color{blue}\sigma_i}}} =
\eqnmarkbox[ForestGreen]{a13}{a_{{\color{red}1}{\color{blue}3}}} \,
\eqnmarkbox[ForestGreen]{a22}{a_{{\color{red}2}{\color{blue}2}}} \,
\eqnmarkbox[ForestGreen]{a31}{a_{{\color{red}3}{\color{blue}1}}}$
$\begin{aligned}
\eqnmarkbox[blue]{detA2}{\det A} &= +a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}3}}
- a_{{\color{red}1}{\color{blue}1}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}2}}
- a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}3}} \\
& \,\phantom{=} + a_{{\color{red}1}{\color{blue}2}} a_{{\color{red}2}{\color{blue}3}} a_{{\color{red}3}{\color{blue}1}}
+ a_{{\color{red}1}{\color{blue}3}} a_{{\color{red}2}{\color{blue}1}} a_{{\color{red}3}{\color{blue}2}}
\eqnmarkbox[BurntOrange]{sgnS2}{-} \,
\eqnmarkbox[ForestGreen]{detA2}{a_{{\color{red}1}{\color{blue}3}} a_{{\color{red}2}{\color{blue}2}} a_{{\color{red}3}{\color{blue}1}}}
\end{aligned}$
}
\end{block}
\end{frame}
\begin{frame}{How to define $\mathsf{sgn}(\sigma)$?}
\begin{columns}
\begin{column}{0.7\textwidth}
\only<1-3>{
\begin{block}{Recall}
\begin{itemize}
\item swap: $(x \; y)$ is a specific example of
\item ($n$-)cycle: $(x, \sigma(x), \dots, \sigma^{n-1}(x))$
\end{itemize}
Example: $\rho = (1, 2, 3) = \left(\begin{smallmatrix}
1 & 2 & 3 \\ 2 & 3 & 1
\end{smallmatrix}\right)$
\end{block}
}
\only<4->{
\begin{block}{``Path independent'' solution}
Compute the \underline{number of inversions in } $\underline{\sigma} \in S_n$.
\vspace{-\topsep}
\begin{align*}
N(\sigma) &= \#\left\{({\color{red}s}, {\color{red}t}) \in \{{\color{red}1},\dots, {\color{red}n}\}^2 \:\middle|\: \begin{matrix} {\color{red}s} < {\color{red}t}\,\text{and} \\ {\color{blue}\sigma(s)} > {\color{blue}\sigma(t)} \end{matrix}\right\} \\
\mathsf{sgn}(\sigma) &:= (-1)^{N(\sigma)}
\end{align*}
\vspace{-\topsep}
Prove a technical lemma that
\vspace{1.5ex}
\begin{flalign*}
& \forall \sigma \in S_n, \eqnmarkbox[gray]{tau}{\forall \tau = ({\color{blue}p}, {\color{blue}q})}, & \\
& N(\tau\sigma) \equiv N(\sigma) \eqnmarkbox[gray]{tau2}{+ 1 \pmod{2}} &
\end{flalign*}
\annotate[yshift=.75em]{}{tau}{each swap ${\color{blue}p} \leftrightarrow {\color{blue}q}$}
\annotate[xshift=7em, yshift=-.75em]{below, left, label below}{tau2}{introduces an odd number of changes in $N$.}
\only<5->{
\vspace{-\topsep}
\begingroup
\addtolength{\jot}{-0.5em}
\begin{alignat*}{3}
N(\boldsymbol{\sigma}) &\equiv N(\boldsymbol{{\color{ForestGreen} \tau_k \cdots \tau_1} \mathsf{id}})
&&\equiv \cancelto{0}{N(\boldsymbol{\mathsf{id}})} + \boxed{\color{ForestGreen}k} && \pmod{2} \\
&\equiv N(\boldsymbol{{\color{DarkOrchid} \tau^\prime_{k^\prime} \cdots \tau^\prime_1} \mathsf{id}})
&&\equiv \cancelto{0}{N(\boldsymbol{\mathsf{id}})} + \boxed{\color{DarkOrchid}k^\prime} && \pmod{2}
\end{alignat*}
\endgroup
}
\end{block}
}
\only<1-4>{
\begin{itemize}
\item<1-> prev. e.g. → parity of no. of swaps
\item<2-> difficulty: ``swap pathway'' not unique
\vspace{1em}
\only<2-3>{
\begin{equation*}
\eqnmarkbox[NavyBlue]{rho}{(1, 2) (1, 3)} \mathrel{\tikzmarknode{eq}{=}}
\eqnmarkbox[Plum]{rho2a}{(1, 3) (1, 2)} \, \eqnmarkbox[Plum]{rho2b}{(1, 3) (1, 2)}
\end{equation*}
\annotate[yshift=1em]{}{eq}{$\curvearrowright 120\degree = \,\curvearrowleft 240\degree$}
\annotate[yshift=-1.5em]{below, left}{eq}{$\rho = \rho^{-2}$}
\annotate[xshift=-1em, yshift=-1em]{below, left, label below}{rho}{$\rho$}
\annotatetwo[yshift=-1em]{below, label below}{rho2a}{rho2b}{$\rho^{-1}$}
}
\end{itemize}
}
\end{column}
\begin{column}<3->{0.3\textwidth}
\begin{align*}
\sigma &= \color{ForestGreen}{\tau_k \tau_{k-1} \cdots \tau_1} \\
&= \color{DarkOrchid}{\tau^\prime_{k^\prime} \tau^\prime_{k^\prime-1} \cdots \tau^\prime_1} \\
{\color{ForestGreen}k} &\equiv {\color{DarkOrchid}k^\prime} \pmod{2} ???
\end{align*}
% https://q.uiver.app/#q=WzAsNCxbMSw0LCJcXHRleHR7aWR9Il0sWzAsMiwiXFx2ZG90cyIsWzI0MCw2MCw2MCwxXV0sWzEsMCwiXFxzaWdtYSJdLFsyLDIsIlxcdmRvdHMiLFswLDYwLDYwLDFdXSxbMCwxLCJcXGNvbG9ye2JsdWV9XFx0YXVfMSIsMCx7ImN1cnZlIjotMSwiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzEsMiwiXFxjb2xvcntibHVlfVxcdGF1X2siLDAseyJjdXJ2ZSI6LTEsImNvbG91ciI6WzI0MCw2MCw2MF19LFsyNDAsNjAsNjAsMV1dLFswLDMsIlxcY29sb3J7cmVkfVxcdGF1XlxccHJpbWVfMSIsMix7ImN1cnZlIjoxLCJjb2xvdXIiOlswLDYwLDYwXX0sWzAsNjAsNjAsMV1dLFszLDIsIlxcY29sb3J7cmVkfVxcdGF1XlxccHJpbWVfe2teXFxwcmltZX0iLDIseyJjdXJ2ZSI6MSwiY29sb3VyIjpbMCw2MCw2MF19LFswLDYwLDYwLDFdXV0=
\[\begin{tikzcd}[ampersand replacement=\&]
\& \boldsymbol{\sigma} \\
\textcolor{ForestGreen}{\vdots} \&\& \textcolor{DarkOrchid}{\vdots} \\
\& \boldsymbol{\mathsf{id}}
\arrow["{\color{ForestGreen}\tau_k}", color={ForestGreen}, curve={height=-6pt}, from=2-1, to=1-2]
\arrow["{\color{DarkOrchid}\tau^\prime_{k^\prime}}"', color={DarkOrchid}, curve={height=6pt}, from=2-3, to=1-2]
\arrow["{\color{ForestGreen}\tau_1}", color={ForestGreen}, curve={height=-6pt}, from=3-2, to=2-1]
\arrow["{\color{DarkOrchid}\tau^\prime_1}"', color={DarkOrchid}, curve={height=6pt}, from=3-2, to=2-3]
\end{tikzcd}\]
$\boldsymbol{\mathsf{id}} = \text{identity transform}$
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Proof of technical lemma: easy part}
\vspace{0.5em}
$$\tikzmarknode{p1}{(} \dots, \tikzmarknode{l}{\color{blue}{\clubsuit}}, \dots, \tikzmarknode{n1}{\color{blue}\boxed{\mathheart \mathstrut}}, \dots, \tikzmarknode{n2}{\color{blue}\boxed{\blacklozenge \mathstrut}}, \dots, \tikzmarknode{r}{\color{blue}{\spadesuit}}, \dots \tikzmarknode{p2}{)}$$
\annotatetwo[yshift=4em]{}{p1}{p2}{This is an $n$-tuple $({\color{blue}\sigma_1}, \dots, {\color{blue}\sigma_n})$, NOT an $n$-cycle.}
\annotatetwo[yshift=-1em]{below, label below}{l}{r}{
Every term ``outside $\color{blue}\boxed{\mathheart \mathstrut}$ and $\color{blue}\boxed{\blacklozenge \mathstrut}$'' that contributes to $N(\sigma)$,\\
i.e. $\begin{cases} {\color{blue}\clubsuit} > {\color{blue}\boxed{\mathheart \mathstrut}}\;\text{and/or}\;{\color{blue}\clubsuit} > {\color{blue}\boxed{\blacklozenge \mathstrut}} \\
{\color{blue}\boxed{\mathheart \mathstrut}} > {\color{blue}\spadesuit}\;\text{and/or}\;{\color{blue}\boxed{\blacklozenge \mathstrut}} > {\color{blue}\spadesuit}, \end{cases}$
}
\annotatetwo[yshift=1em]{}{n1}{n2}{\textbf{Before} swap $({\color{blue}\mathheart}, {\color{blue}\blacklozenge})$}
\onslide<2->{
\vspace{5em}
$$\tikzmarknode{pb1}{(} \dots, \tikzmarknode{lb}{\color{blue}{\clubsuit}}, \dots, \tikzmarknode{nb1}{\color{blue}\boxed{\blacklozenge \mathstrut}}, \dots, \tikzmarknode{nb2}{\color{blue}\boxed{\mathheart \mathstrut}}, \dots, \tikzmarknode{rb}{\color{blue}{\spadesuit}}, \dots \tikzmarknode{pb2}{)}$$
\annotatetwo[yshift=-4em]{below, label below}{pb1}{pb2}{This is an $n$-tuple $({\color{blue}(({\color{blue}\mathheart}, {\color{blue}\blacklozenge}) \sigma)_1}, \dots, {\color{blue}(({\color{blue}\mathheart}, {\color{blue}\blacklozenge}) \sigma)_n})$, NOT an $n$-cycle.}
\annotatetwo[yshift=1em]{}{lb}{rb}{
\underline{also} contributes to $N(({\color{blue}\mathheart}, {\color{blue}\blacklozenge}) \sigma)$, and \underline{\textit{vice versa}}.
}
\annotatetwo[yshift=-1em]{below, label below}{nb1}{nb2}{\textbf{After} swap $({\color{blue}\mathheart}, {\color{blue}\blacklozenge})$}
}
\end{frame}
\begin{frame}{Proof of technical lemma: tricky part case 1}
Consider terms ``inside $\color{blue}\boxed{\mathheart \mathstrut}$ and $\color{blue}\boxed{\blacklozenge \mathstrut}$''.
\begin{itemize}
\item $\tikz{\draw[thick] (0,0) -- (10pt, -10pt);}$: \cmark{} \textbf{inversion}
\item $\tikz{\draw[dashed] (0,0) -- (10pt, 10pt);}$: \xmark{} inversion
\end{itemize}
\begin{columns}
\begin{column}{0.5\textwidth}
Before swap $({\color{blue}\mathheart}, {\color{blue}\blacklozenge})$
% https://q.uiver.app/#q=WzAsNSxbMCwzLCJcXGJveGVke1xcaGVhcnRzIFxcbWF0aHN0cnV0fSIsWzI0MCw2MCw2MCwxXV0sWzQsMSwiXFxib3hlZHtcXGJsYWNrbG96ZW5nZSBcXG1hdGhzdHJ1dH0iLFsyNDAsNjAsNjAsMV1dLFsxLDQsIlxcY2x1YnMiLFsyNDAsNjAsNjAsMV1dLFszLDAsIlxcc3BhZGVzIixbMjQwLDYwLDYwLDFdXSxbMiwyLCJcXGJpZ3N0YXIiLFsyNDAsNjAsNjAsMV1dLFswLDIsIiIsMCx7InN0eWxlIjp7ImhlYWQiOnsibmFtZSI6Im5vbmUifX19XSxbMywxLCIiLDAseyJzdHlsZSI6eyJoZWFkIjp7Im5hbWUiOiJub25lIn19fV0sWzAsMywiIiwxLHsic3R5bGUiOnsiYm9keSI6eyJuYW1lIjoiZGFzaGVkIn0sImhlYWQiOnsibmFtZSI6Im5vbmUifX19XSxbMiwxLCIiLDEseyJzdHlsZSI6eyJib2R5Ijp7Im5hbWUiOiJkYXNoZWQifSwiaGVhZCI6eyJuYW1lIjoibm9uZSJ9fX1dLFswLDQsIiIsMSx7InN0eWxlIjp7ImJvZHkiOnsibmFtZSI6ImRhc2hlZCJ9LCJoZWFkIjp7Im5hbWUiOiJub25lIn19fV0sWzQsMSwiIiwxLHsic3R5bGUiOnsiYm9keSI6eyJuYW1lIjoiZGFzaGVkIn0sImhlYWQiOnsibmFtZSI6Im5vbmUifX19XV0=
\vspace{-\topsep}
\[\begin{tikzcd}[row sep=small,column sep=small]
\&\&\& \color{blue}{\spadesuit} \\
\&\&\&\& \color{blue}{\boxed{\blacklozenge \mathstrut}} \\
\&\& \color{blue}{\bigstar} \\
\color{blue}{\boxed{\mathheart \mathstrut}} \\
\& \color{blue}{\clubsuit}
\arrow[bolded, no head, from=1-4, to=2-5]
\arrow[dashed, no head, from=3-3, to=2-5]
\arrow[dashed, no head, from=4-1, to=1-4]
\arrow[dashed, no head, from=4-1, to=3-3]
\arrow[bolded, no head, from=4-1, to=5-2]
\arrow[dashed, no head, from=5-2, to=2-5]
\end{tikzcd}\]
\end{column}
\onslide<2->{
\begin{column}{0.5\textwidth}
After swap $({\color{blue}\mathheart}, {\color{blue}\blacklozenge})$
\vspace{-\topsep}
\[\begin{tikzcd}[row sep=small,column sep=small]
\&\&\& \color{blue}{\spadesuit} \\
\color{blue}{\boxed{\blacklozenge \mathstrut}} \\
\&\& \color{blue}{\bigstar} \\
\&\&\&\& \color{blue}{\boxed{\mathheart \mathstrut}} \\
\& \color{blue}{\clubsuit}
\arrow[bolded, no head, from=1-4, to=4-5]
\arrow[dashed, no head, from=2-1, to=1-4]
\arrow[bolded, no head, from=2-1, to=3-3]
\arrow[bolded, no head, from=2-1, to=5-2]
\arrow[bolded, no head, from=3-3, to=4-5]
\arrow[dashed, no head, from=5-2, to=4-5]
\end{tikzcd}\]
\end{column}
}
\end{columns}
\uncover<3->{Exercise: complete this proof}
\end{frame}
\begin{frame}{Example 1: triangular matrix}
\begin{definition}
An \textbf{upper triangular matrix} is a square matrix such that $u_{ij} = 0$ if $i > j$.
An \textbf{lower triangular matrix} is a square matrix such that $u_{ij} = 0$ if $i < j$.
\end{definition}
\only<1-2>{
\begin{columns}
\begin{column}{0.48\textwidth}
\begin{exampleblock}{Example upper triangular matrix}
$$A = \left( \begin{smallmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{smallmatrix} \right)$$
\end{exampleblock}
\end{column}
\begin{column}{0.48\textwidth}
\begin{exampleblock}{Example lower triangular matrix}
$$B = \left( \begin{smallmatrix} 1 & 0 & 0 \\ 2 & 3 & 0 \\ 4 & 5 & 6 \end{smallmatrix} \right)$$
\end{exampleblock}
\end{column}
\end{columns}
}
\begin{lemma}
The determinant of a triangular matrix $T$ is $\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} t_{{\color{red}i},{\color{blue}i}}$. \only<1>{(product of diagonal entries)}
Suppose that $T$ is \textbf{upper triangular}. \alt<1>{(the other case left as exercise)}{In the definiton of $\det(T)$,}
\vspace{-1.3\topsep}
$$\det(T) = \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} t_{{\color{red}i},{\color{blue}\sigma_i}}.$$
\vspace{-\topsep}
\only<2->{For any $\sigma \in S_n$, any row index ${\color{red}i^\prime} > {\color{blue}\sigma(i^\prime)}$ will zero the product $\prod_{\color{red}i}$,}
\only<3->{so focus on $\sigma$ such that for all $\color{red}i$, ${\color{red}i} \le {\color{blue}\sigma_i}$.}
\only<4-5>{``Dead end'': assume that $\sigma \ne \boldsymbol{\mathsf{id}}$ (identity transformation) and some row index ${\color{red}i^\prime} < {\color{blue}\sigma(i^{\prime})}$. Try to find some ${\color{red}i^{\prime\prime}} > {\color{blue}\sigma(i^{\prime\prime})}$.}
\only<5->{Discussion: the above way is a ``local'' way, but given conditions (bijection $\sigma$, sum (over $S_n$), product (over $\left\{{\color{red}1},\dots,{\color{red}n}\right\}$)) are all ``global''.}
\only<6->{Hint: Consider $\sum_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} \left( {\color{blue}\sigma_i} - {\color{red}i} \right)$.}
\end{lemma}
\end{frame}
\begin{frame}{Less direct but simpler proof}
For $n$ \textbf{distinct} numbers $x_1, \dots, x_n \in \mathbb{F}$, observe that
\vspace{-\topsep}
$$\mathsf{sgn}(\sigma) = \prod_{\substack{({\color{red}s}, {\color{red}t}) \in \{{\color{red}1}, \dots, {\color{red}n}\}^2 \\ {\color{red}s} < {\color{red}t}}} \frac{x_{\color{blue}\sigma(s)} - x_{\color{blue}\sigma(t)}}{x_{\color{red}s} - x_{\color{red}t}}
= \frac{\prod_{\substack{({\color{red}s}, {\color{red}t}) \in \{{\color{red}1}, \dots, {\color{red}n}\}^2 \\ {\color{red}s} < {\color{red}t}}} x_{\color{blue}\sigma(s)} - x_{\color{blue}\sigma(t)}}{\prod_{\substack{({\color{Orange}s^\prime}, {\color{Orange}t^\prime}) \in \{{\color{Orange}1}, \dots, {\color{Orange}n}\}^2 \\ {\color{Orange}s^\prime} < {\color{Orange}t^\prime}}} x_{\color{Orange}s^\prime} - x_{\color{Orange}t^\prime}}.$$
\only<1-3>{
\vspace{-\topsep}
\begin{itemize}
\item<1-> $({\color{red}s}, {\color{red}t}) \mapstofrom{\sigma} ({\color{blue}\sigma(s)}, {\color{blue}\sigma(t)})$ (abuse of notation)
\item<2-> denominator $x_{\color{red}s} - x_{\color{red}t} \mapstofrom{\sigma}$ numerator $x_{\color{blue}\sigma(s)} - x_{\color{blue}\sigma(t)}$
\item<3-> Choose ${\color{Orange}s^\prime} = \min({\color{blue}\sigma(s)}, {\color{blue}\sigma(t)})$ and ${\color{Orange}t^\prime} = \max({\color{blue}\sigma(s)}, {\color{blue}\sigma(t)})$, so that
$({\color{blue}\sigma(s)}, {\color{blue}\sigma(t)}) \mapstofromZ ({\color{Orange}s^\prime}, {\color{Orange}t^\prime})$ is another bijection.
$$\frac{x_{\color{blue}\sigma(s)} - x_{\color{blue}\sigma(t)}}{x_{\color{Orange}s^\prime} - x_{\color{Orange}t^\prime}}
= \begin{cases} 1 & \text{if}\; {\color{blue}\sigma(s)} < {\color{blue}\sigma(t)} \;\text{(\xmark\;inversion)} \\ \eqnmarkbox[BurntOrange]{pf1}{-1} & \text{if}\; {\color{blue}\sigma(s)} > {\color{blue}\sigma(t)} \;\text{(\cmark\;inversion)} \end{cases}$$
\annotate[yshift=-0.5em]{left, below, label below}{pf1}{each inversion gives a factor $-1$}
\end{itemize}
}
\only<4->{
\begin{columns}
\begin{column}{0.5\textwidth}
Use \textbf{Vandermonde polynomial} to simply our writing.
\begin{align*}
P(x_1,\dots,x_n) &= \prod _{\substack{(s,t) \in \{1,\dots,n\}^2 \\ s < t}}(x_s-x_t) \\
\mathsf{sgn}(\sigma) &= \frac{P(x_{\color{blue}\sigma(1)},\dots,x_{\color{blue}\sigma(n)})}{P(x_{\color{red}1},\dots,x_{\color{red}n})}
\end{align*}
\end{column}
\begin{column}{0.5\textwidth}
\only<5>{
\begin{block}{Exercise}
For each swap $\tau = ({\color{blue}p}, {\color{blue}q})$, $\mathsf{sgn}(\tau) = -1$.
Hint: Consider $$(x_i - x_p)(x_i - x_q),$$ in Vandermonde polynomial, and so on…
\end{block}
}
\only<6-8>{
\begin{lemma}
$\forall \sigma, \tau \in S_n$, $\mathsf{sgn}(\tau) = \frac{P(x_{\color{blue}\sigma(\tau(1))},\dots,x_{\color{blue}\sigma(\tau(n))})}{P(x_{\sigma(1)},\dots,x_{\sigma(n)})}$ \\
Why not $\frac{P(x_{\color{blue}\tau(\sigma(1))},\dots,x_{\color{blue}\tau(\sigma(n))})}{P(x_{\sigma(1)},\dots,x_{\sigma(n)})}$?
\only<6-7>{
\vspace{4ex}
Verbal ans: $\eqnmarkbox[red]{tau}{\tau} \quad \eqnmarkbox[orange]{sig}{\sigma(}\eqnmarkbox[red]{taua}{i}\eqnmarkbox[orange]{siga}{)}$
\tikzset{annotate equations/arrow/.style={->}}
\annotatetwo[yshift=0.5em]{}{tau}{taua}{\textbf{``acts on''}}
\only<7>{
\vspace{4ex}
\tikzset{annotate equations/arrow/.style={<->}}
\annotatetwo[yshift=-0.5em]{below, label below}{sig}{siga}{just a ``\emph{decoration}''}
}
}
\only<8->{
Symbolic ans: Let $y_i = x_{\sigma(i)}$. \\
$\mathsf{sgn}(\tau) = \frac{P(y_{\color{blue}\tau(1)},\dots,y_{\color{blue}\tau(n)})}{P(y_1,\dots,y_n)}$ \\
$y_{\tau(i)}$ means $i \stackrel{\tau}\mapsto \tau_i \stackrel{y}\mapsto y_{\tau(i)}$, and \\
$i \stackrel{\sigma}\mapsto \sigma(i) \stackrel{x}\mapsto y_i$, so $y = x \circ \sigma$. \\
$y \circ \tau = x \circ \sigma \circ \tau$
}
\end{lemma}
}
\only<9->{
\begin{lemma}
$\forall \sigma, \tau \in S_n, \mathsf{sgn}(\sigma \tau) = \mathsf{sgn}(\sigma)\,\mathsf{sgn}(\tau)$. \\
Direct consequence of ``$\mathsf{sgn}$'' as parity of no. of swaps\\
Another proof:
{\tiny\begin{align*}
&\mathrel{\phantom{=}} \mathsf{sgn}(\sigma \tau) \\
&= \frac{P(x_{\color{blue}(\sigma\tau)(1)},\dots,x_{\color{blue}(\sigma\tau)(n)})}{P(x_{\color{red}1},\dots,x_{\color{red}n})} \\
&= \underbrace{\frac{P(x_{\color{blue}\sigma(\tau(1))},\dots,x_{\color{blue}\sigma(\tau(n))})}{P(x_{\sigma(1)},\dots,x_{\sigma(n)})}}_{= \mathsf{sgn}(\tau)\,\text{by prev. lemma}} \, \underbrace{\frac{P(x_{\color{blue}\sigma(1)},\dots,x_{\color{blue}\sigma(n)})}{P(x_1,\dots,x_n)}}_{= \mathsf{sgn}(\sigma)\,\text{from observation}}
\end{align*}}
\end{lemma}
}
\end{column}
\end{columns}
}
\end{frame}
\begin{frame}[fragile]{Vandermonde matrix (from polynomial interpolation)}
\begin{columns}
\begin{column}{0.55\textwidth}
\vspace{-1.5\topsep}
\begin{align*}
A &= \left(t_i^{j-1}\right)_{ij} = \left(\begin{smallmatrix}
1 & t_1 & t_1^2 & \dots & t_1^{n-1} \\
1 & t_2 & t_2^2 & \dots & t_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & t_n & t_n^2 & \dots & t_n^{n-1} \\
\end{smallmatrix}\right) \\
\only<2->{\det(A)}
\only<2-4>{&= \sum_{\sigma\in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}\sigma_i}} \\}
\only<3->{&= \sum_{\sigma\in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} t_{{\color{red}i}}^{{\color{blue}\sigma_i}-1}}
\only<4>{
\intertext[0ex]{\small Easy proof: use factor theorem, but my goal = link between permutation $\sigma$ with determinants, so consider \colorbox{yellow}{Vandermonde} \colorbox{yellow}{polynomial} in previous proof.}
\mathsf{sgn}(\sigma) &= \colorbox{yellow}{$\displaystyle\prod_{\substack{({\color{red}s}, {\color{red}t}) \in \{{\color{red}1}, \dots, {\color{red}n}\}^2 \\ {\color{red}s} < {\color{red}t}}}$} \frac{x_{\color{blue}\sigma(s)} - x_{\color{blue}\sigma(t)}}{\colorbox{yellow}{$x_{\color{red}s} - x_{\color{red}t}$}}
}
\end{align*}
\vspace{-2\topsep}
\only<5->{
\begin{block}{Observation from small case ($n = 5$)}
$\begin{aligned}
\sigma &= ({\color{blue}2}, {\color{blue}4}) = \left(\begin{smallmatrix}
{\color{red}1} & {\color{red}2} & {\color{red}3} & {\color{red}4} & {\color{red}5} \\
{\color{blue}1} & {\color{blue}4} & {\color{blue}3} & {\color{blue}2} & {\color{blue}5}
\end{smallmatrix}\right), \\[7.5pt]
\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}5}} t_{{\color{red}i}}^{{\color{blue}\sigma_i}-1} &= \eqnmarkbox[black]{t1}{t_{\color{red}1}^{\color{blue}0}} t_{\color{red}2}^{\color{blue}3} t_{\color{red}3}^{\color{blue}2} t_{\color{red}4}^{\color{blue}1} \eqnmarkbox[black]{t5}{t_{\color{red}5}^{\color{blue}4}}
\end{aligned}$
\only<6->{
\vspace{5pt}
\annotate[yshift=0]{below}{t1}{pick as \textbf{few} $t_1$ as possible}
\annotate[xshift=2.5em,yshift=0.5em]{left}{t5}{pick as \textbf{much} $t_5$ as possible}
}
\only<7-8>{
\vspace{2em}
$(t_{\color{red}1}\eqnmarkbox[black]{pick1}{-t_{\color{red}2}})(\eqnmarkbox[black]{pick3}{t_{\color{red}2}}-t_{\color{red}3})(\eqnmarkbox[black]{pick4}{t_{\color{red}2}}-t_{\color{red}4})(t_{\color{red}2}\eqnmarkbox[black]{pick2}{-t_{\color{red}5}})$
\annotatetwo[yshift=0.5em]{}{pick1}{pick2}{try ${\color{red}i} = {\color{red}2}$, first picked}
\vspace{1em}
}
\only<8>{
\annotatetwo[yshift=-0.5em]{below, label below}{pick3}{pick4}{due to `${}^{\color{blue}3}$', two more $t_{\color{red}2}$ also picked}
}
\only<9->{
\vspace{0.5em}
$(t_{\eqnmarkbox[blue]{t21a}{\substack{{\color{red}1}\\{\color{blue}1}}}}-t_{\eqnmarkbox[blue]{t21}{\substack{{\color{red}2}\\{\color{blue}4}}}})(t_{\eqnmarkbox[blue]{t22}{\substack{{\color{red}2}\\{\color{blue}4}}}}-t_{\eqnmarkbox[blue]{t22a}{\substack{{\color{red}3}\\{\color{blue}3}}}})(t_{\eqnmarkbox[blue]{t23}{\substack{{\color{red}2}\\{\color{blue}4}}}}-t_{\eqnmarkbox[blue]{t23a}{\substack{{\color{red}4}\\{\color{blue}2}}}})(t_{\eqnmarkbox[blue]{t24}{\substack{{\color{red}2}\\{\color{blue}4}}}}-t_{\eqnmarkbox[blue]{t24a}{\substack{{\color{red}5}\\{\color{blue}5}}}})$
}
\only<10->{
\tikzset{annotate equations/arrow/.style={->}}
\annotatetwo[yshift=-0.5em]{below, label below}{t21}{t21a}{dominates}
\annotatetwo[yshift=-0.5em]{below, label below}{t22}{t22a}{dominates}
\annotatetwo[yshift=-0.5em]{below, label below}{t23}{t23a}{dominates}
\annotatetwo[yshift=-0.5em]{below, label below}{t24a}{t24}{dominates}
\only<10>{\vspace{2.5ex}}
}
\only<11->{
\vspace{1em}
The $t_{\color{red}erm}$ with a {\large larger $\color{blue}\sigma_i$} is chosen.
}
\end{block}
}
\end{column}
\begin{column}{0.45\textwidth}
Find min degree polynomial $p(t) = \sum_{k=0}^{n-1} {\color{orange!70!black}p_k} t^k$ passing through $(t_i, y_i)$ for each $i$.
\begin{tikzpicture}[scale=0.6]
\begin{axis}[
xlabel=$t$,
ylabel=$y$,
xmin=-3,
xmax=5,
ymin=-3,
ymax=5,
axis lines=center,
nodes near coords,
xticklabel=\empty,
yticklabel=\empty,
]
\addplot[
patch,
patch type=cubic spline,
smooth,
orange!70!black,
dashed,
mark=*,
coordinate style/.from={anchor=\thisrow{anchor}},
point meta=explicit symbolic,
every node near coord/.style={color=black},
thick,
] table [meta=label] {
x y label anchor
-2 1 $(t_1,y_1)$ 330
-1.4 2.1 $(t_2,y_2)$ 270
-0.8 -1.4 $(t_3,y_3)$ 90
0.7 0.2 $(t_4,y_4)$ 240
};
\addplot[orange!70!black,nodes near coords=$\boldsymbol{\iddots}$,thick] coordinates {(1,1)};
\addplot[
patch,
patch type=cubic spline,
smooth,
orange!70!black,
dashed,
mark=*,
coordinate style/.from={anchor=\thisrow{anchor}},
point meta=explicit symbolic,
every node near coord/.style={color=black},
thick,
] table [meta=label] {
x y label anchor
1.7 2.5 $(t_{n-2},y_{n-2})$ 270
2.6 1.4 $(t_{n-1},y_{n-1})$ 200
3.1 -1.2 $(t_n,y_n)$ 90
};
\end{axis}
\end{tikzpicture}
\vspace{-\topsep}
\begin{align*}
\underbrace{{\color{orange!70!black}p_0} + {\color{orange!70!black}p_1} {\color{gray}t_i} + \dots + {\color{orange!70!black}p_{n-1}} {\color{gray}t_i^{n-1}}}_{=p(t_i)} &= y_i \\
\left(\begin{smallmatrix}
{\color{gray}1} & {\color{gray}t_1} & {\color{gray}\dots} & {\color{gray}t_1^{n-1}} \\
{\color{gray}1} & {\color{gray}t_2} & {\color{gray}\dots} & {\color{gray}t_2^{n-1}} \\
{\color{gray}\vdots} & {\color{gray}\vdots} & {\color{gray}\ddots} & {\color{gray}\vdots} \\
{\color{gray}1} & {\color{gray}t_n} & {\color{gray}\dots} & {\color{gray}t_n^{n-1}} \\
\end{smallmatrix}\right)
\left(\begin{smallmatrix} {\color{orange!70!black}p_0} \\ {\color{orange!70!black}p_1} \\ \vdots \\ {\color{orange!70!black}p_{n-1}} \end{smallmatrix}\right)
&= \left(\begin{smallmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{smallmatrix}\right)
\end{align*}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Vandermonde matrix (from polynomial interpolation)}
\vspace{-1.6ex}
{\scriptsize\begin{equation*}
A = \left(t_i^{j-1}\right)_{ij},
\det(A) = \sum_{\sigma\in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} t_{{\color{red}i}}^{{\color{blue}\sigma_i}-1}
\end{equation*}}
\vspace{-2ex}
\begin{block}{Abstraction from small case}
\only<1>{
\begin{itemize}
\item Replace ``${\color{red}2} \mapsto {\color{blue}4}$'' with ``${\color{red}i} \mapsto {\color{blue}\sigma(i)}$''.
\item Replace ``${\color{red}1} \mapsto {\color{blue}1}$'' with ``${\color{red}i^\prime} \mapsto {\color{blue}\sigma(i^\prime)}$'', note that ${\color{blue}\sigma(i)} > {\color{blue}\sigma(i^\prime)}$.
\item Replace ``${\color{red}3} \mapsto {\color{blue}3}$'' with ``${\color{red}i^{\prime\prime}} \mapsto {\color{blue}\sigma(i^{\prime\prime})}$'', note that ${\color{blue}\sigma(i)} > {\color{blue}\sigma(i^{\prime\prime})}$.
\end{itemize}
}
\vspace{0.5ex}
\only<2->{\vspace{1.9ex}}
\begin{equation*}
\sigma = \begin{pmatrix}
\pgfsetfillopacity{0.2}{\color{red}1} & \pgfsetfillopacity{1}\cdots & \tikzmarknode{ip}{\color{red}i^\prime} & \cdots & \eqnmarkbox[red]{i}{\color{red}i} & \cdots & \tikzmarknode{ipp}{\color{red}i^{\prime\prime}} & \cdots & \pgfsetfillopacity{0.2}{\color{red}n} \\
{\color{blue}\sigma(1)} & \pgfsetfillopacity{1}\cdots & \tikzmarknode{sigip}{\color{blue}\sigma(i^\prime)} & \cdots & \tikzmarknode{sigi}{\color{blue}\sigma(i)} & \cdots & \tikzmarknode{sigipp}{\color{blue}\sigma(i^{\prime\prime})} & \dots & \pgfsetfillopacity{0.2}{\color{blue}\sigma(n)}\pgfsetfillopacity{1}
\end{pmatrix}
\end{equation*}
\annotatetwo[xshift=-0.7em,yshift=0.5em]{}{i}{ip}{\xmark{} inversion $({\color{red}i^\prime}, {\color{red}i})$}
\annotatetwo[xshift=0.7em,yshift=0.5em]{}{ipp}{i}{\cmark{} inversion $({\color{red}i}, {\color{red}i^{\prime\prime}})$}
\vspace{-2ex}
{\small\begin{tabular}{l|l|l}
\textcolor{red}{index} & $\color{red}i^\prime$ & $\color{red}i^{\prime\prime}$ \\ \hline
$<$/$>$ & ${\color{red}i^\prime} < {\color{red}i}$ & ${\color{red}i^{\prime\prime}} > {\color{red}i}$ \\
factor in $P(t_{\color{red}1},\dots,t_{\color{red}n})$ & $t_{\color{red}i^\prime} \eqnmarkbox[blue]{ti1}{\mathrel{-} t_{\color{red}i}}$ & $\eqnmarkbox[blue]{ti2}{t_{\color{red}i}} - t_{\color{red}i^{\prime\prime}}$ \\
no. of `$\eqnmarkbox[blue]{m}{-}$' & $\colorbox{yellow}{$\#\{({\color{red}i^\prime}, {\color{red}i}) \mid {\color{red}i^\prime} < {\color{red}i}\;\text{and}\;{\color{blue}\sigma(i^\prime)} < {\color{blue}\sigma(i)} \}$}$ & 0
\end{tabular}}
\only<2->{
\vspace{-2ex}
{\footnotesize
\begingroup
\addtolength{\jot}{-2.7ex}
\begin{align*}
\sum_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} \colorbox{yellow}{$\#\{({\color{red}i^\prime}, {\color{red}i}) \mid {\color{red}i^\prime} < {\color{red}i}\;\text{and}\;{\color{blue}\sigma(i^\prime)} < {\color{blue}\sigma(i)} \}$}
&= \text{no. of non inversions in}\;\sigma = \binom{n}{2} - N(\sigma) \\
\onslide<3->{P(t_{\color{red}1},\dots,t_{\color{red}n}) = \prod_{\substack{({\color{red}p}, {\color{red}q}) \in \{{\color{red}1}, \dots, {\color{red}n}\}^2 \\ {\color{red}p} < {\color{red}q}}} (t_{\color{red}p} - t_{\color{red}q}) &= \sum_{\sigma \in S_n} (-1)^{\binom{n}{2} - N(\sigma)} \prod_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} t_{{\color{red}i}}^{{\color{blue}\sigma_i}-1} \\}
\onslide<4->{\prod_{\substack{({\color{red}p}, {\color{red}q}) \in \{{\color{red}1}, \dots, {\color{red}n}\}^2 \\ {\color{red}p} > {\color{red}q}}} (t_{\color{red}p} - t_{\color{red}q}) &= \sum_{\sigma \in S_n} \underbrace{(-1)^{N(\sigma)}}_{\mathsf{sgn}(\sigma)} \prod_{{\color{red}i}={\color{red}1}}^{{\color{red}n}} t_{{\color{red}i}}^{{\color{blue}\sigma_i}-1} = \det(A)}
\end{align*}
\endgroup
}
}
\end{block}
\end{frame}
\begin{frame}{Basic fact 1: $\det(A) = \det\left( A^\intercal \right)$}
\only<6->{\vspace{-1ex}}
\begin{lemma}
\begin{equation*}
\forall \rho \in S_n, \det (A) = \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{\eqnmarkbox[black]{rhoi}{\color{red}\rho_i},\eqnmarkbox[black]{rhosigi}{\color{blue}(\sigma\rho)_i}}
\end{equation*}
\only<2>{
Proof: $\rho$ permutes the key-value pairs $\{\xcancel{{\color{red}i} \stackrel{\sigma}{\mapsto} \; {\color{blue}\sigma_i}} ({\color{red}i}, {\color{blue}\sigma_i}) \mid {\color{red}i} \in \{ {\color{red}1}, \dots, {\color{red}n} \} \}$,
so ``$\prod_{\color{red}i}$'' on the right is invariant under $\rho$.
}
\end{lemma}
\only<6->{\vspace{-1ex}}
\only<3->{
\begin{block}{Proposition}
$\det(A) = \det(A^\intercal)$
Proof:
\vspace{-\topsep}
\begin{equation*}
\begin{aligned}
\det(A^\intercal) &=
\only<3>{\sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} \eqnmarkbox[gray]{ATij}{\left( A^\intercal \right)_{{\color{red}i},{\color{blue}\sigma_i}}}}
\only<4->{\sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}\sigma_i},{\color{blue}i}}}
\\[1ex]
\only<5->{&= \sum_{\sigma \in S_n} \eqnmarkbox[gray]{sgnsig}{\mathsf{sgn}(\sigma)} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{\eqnmarkbox[black]{detATpf1}{\color{red}i},\eqnmarkbox[black]{detATpf2}{\color{blue}(\sigma^{-1})(i)}} \\[4.7ex]}
\only<6->{&= \sum_{\sigma \in S_n} \mathsf{sgn}(\eqnmarkbox[gray]{sigm1a}{\sigma^{-1}}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}(\eqnmarkbox[gray]{sigm1b}{\sigma^{-1}})_i}}}
\only<7->{&= \det(A)}
\end{aligned}
\end{equation*}
\only<3>{\annotate[yshift=1.5ex]{}{ATij}{$\left( A^\intercal \right)_{ij} = a_{ji}$, so \dots}}
\only<5->{
\vspace{2ex}
\annotate[yshift=1.5ex]{}{sgnsig}{$=\mathsf{sgn}(\sigma^{-1})$}
\annotatetwo[yshift=-1.1ex]{below, label below}{detATpf1}{detATpf2}{${\color{red}\text{index}} \stackrel{\sigma^{-1}}{\mapsto} {\color{blue}\text{``row representative''}}$}
}
\only<6->{\annotatetwo[yshift=1.9ex]{}{sigm1a}{sigm1b}{$\sigma^{-1}$ runs through $S_n$}}
\end{block}
}
\end{frame}
\begin{frame}{Basic fact 2: swapping row/col changes sign of det}
\begin{lemma}
$\forall \tau \in S_n,$
\only<3->{\vspace{-\topsep}}
\begin{equation*}
\begin{aligned}
\det (A) &= \sum_{\sigma \in S_n} \mathsf{sgn}(\eqnmarkbox[BurntOrange]{tausig1}{\tau\sigma}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}(\eqnmarkbox[BurntOrange]{tausig2}{\tau\sigma})_i}} \only<1-2>{\\}
&= \sum_{\sigma \in S_n} \mathsf{sgn}(\eqnmarkbox[BurntOrange]{sigtau1}{\sigma\tau}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}(\eqnmarkbox[BurntOrange]{sigtau2}{\sigma\tau})_i}}
\end{aligned}
\end{equation*}
\only<2>{
\vspace{1ex}
\annotatetwo[yshift=2.1ex]{}{tausig1}{tausig2}{also runs through $S_n$}
\annotatetwo[yshift=-2.1ex]{below, label below}{sigtau1}{sigtau2}{also runs through $S_n$}
}
\end{lemma}
\only<3->{
\begin{block}{Proposition}
Let $\tau = ({\color{red}p}, {\color{red}q})$ and $M = \left(\eqnmarkbox[BurntOrange]{deltatauij}{\delta_{\tau_i, j}}\right)_{ij}$.
Then $\det(\eqnmarkbox{MA}{MA}) = -\det(A)$
\only<3>{
\vspace{3ex}
\annotate[yshift=-1.5ex]{below,left}{deltatauij}{so that $m_{\color{red}qp} = \delta_{\tau_{\color{red}q},{\color{red}p}} = \delta_{\color{red}pp} = 1,\dots$}
\annotate[yshift=-1.5ex]{below}{MA}{$A$ with rows swapped $R_{\color{red}p} \leftrightarrow R_{\color{red}q}$}
}
\only<4-8>{
Proof:
\vspace{-\topsep}
\begingroup
\addtolength{\jot}{-1ex}
\begin{equation*}
\begin{aligned}
\det(MA) &= \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}}
\temporal<4>{}{
\eqnmarkbox[gray]{MAij}{(MA)_{{\color{red}i},{\color{blue}\sigma_i}}}
}{
a_{{\color{red}\tau_i},{\color{blue}\sigma_i}}
}
\\
\uncover<6->{&= \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{\eqnmarkbox[black]{fact2pf1}{\color{red}i},\eqnmarkbox[black]{fact2pf2}{\color{blue}(\sigma\tau)_i}} \\}
\uncover<7->{&= \eqnmarkbox[black]{fact2pfm}{-} \sum_{\sigma \in S_n} \eqnmarkbox[black]{fact2pfsgn}{\mathsf{sgn}(\sigma\tau)} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}(\sigma\tau)_i}}}
\uncover<8->{\mathrel{\tikzmarknode[outer ysep=5pt]{fact2pf9}{=}} -\det(A)}
\end{aligned}
\end{equation*}
\endgroup
\only<4>{\annotate[yshift=-1.5ex]{below}{MAij}{$\left(MA\right)_{ij} = a_{\tau_i,j}$}}
\uncover<6->{\annotatetwo[yshift=1ex,xshift=4.5em]{}{fact2pf1}{fact2pf2}{prev. prev. lemma with $\rho = \tau$}}
\uncover<7->{\annotatetwo[yshift=1.8ex,xshift=-8em]{below}{fact2pfm}{fact2pfsgn}{$\text{sign of swap} = -1$ \\ $\mathsf{sgn}(\sigma\tau) = \mathsf{sgn}(\sigma) \mathsf{sgn}(\tau)$}}
\uncover<8->{\annotate[yshift=-0.5ex]{below}{fact2pf9}{prev. lemma}}
}
\end{block}
}
\only<9->{
\begin{corollary}
The determinant of a matrix with two identitical rows (or columns) is zero.
\end{corollary}
}
\end{frame}
\begin{frame}{Basic fact 3: $\det(AB) = \det(A) \det(B)$}
\vspace{-\topsep}
\begin{align*}
\det(AB) &= \sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}}
\alt<1>{(AB)_{{\color{red}i},{\color{blue}\varepsilon_i}}}{\sum_{k=1}^n a_{{\color{red}i},k} b_{k,{\color{blue}\varepsilon_i}}} \\
\uncover<2->{&= \sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \sum_{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}}} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,{\color{blue}\varepsilon_i}} \\}
\only<15->{&= \sum_{\varepsilon \in S_n} \sum_{\sigma \in S_n} \mathsf{sgn}(\varepsilon) \left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},\sigma_i} \right) \left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} b_{\sigma_i,{\color{blue}\varepsilon_i}} \right) \tag{$\vec{v}$ renamed as $\sigma$} \\}
\only<16->{
&= \sum_{\sigma \in S_n} \sum_{\varepsilon \in S_n}
\alt<18->{\mathsf{sgn}(\sigma) \mathsf{sgn}\left( \varepsilon \sigma^{-1} \right)}{\mathsf{sgn}(\varepsilon)}
\left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},\sigma_i}\right)
\left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} \temporal<17>{b_{\sigma_i,{\color{blue}\varepsilon_i}}}{b_{\sigma\left(\sigma^{-1}(i)\right),{\color{blue}\varepsilon\left(\sigma^{-1}(i)\right)}}}{b_{i,{\color{blue}\left(\varepsilon\sigma^{-1}\right)_i}}}\right)
\only<16-18>{\tag{\temporal<17>{summation order swapped}{product permuted by $\sigma^{-1}$}{$\mathsf{sgn}(\varepsilon)$ split}}} \\
}
\only<19->{
&= \uncover<21->{\left[}\sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},\sigma_i}\right) \uncover<21->{\right]}
\uncover<21->{\left[}\sum_{\varepsilon \in S_n} \mathsf{sgn}\left( \alt<20->{\varepsilon}{\tikzmarknode{fact3pfz1}{\varepsilon \sigma^{-1}}} \right) \left( \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} b_{i,{\color{blue}\alt<20->{\varepsilon}{\tikzmarknode{fact3pfz2}{\left( \varepsilon\sigma^{-1} \right)}}_i}} \right) \uncover<21->{\right]} \\
}
\only<22>{&= \det(A) \det(B)}
\end{align*}
\only<19>{\annotatetwo[yshift=-3.5ex,xshift=-3em]{below, label below}{fact3pfz1}{fact3pfz2}{apply prev. prev. lemma with $\tau \leftarrow \sigma^{-1}$ and $\sigma \leftarrow \varepsilon$}}
\only<2>{
\vspace{-3\topsep}
\begin{block}{Fact (Product of sums as sum of products)}
\vspace{-1.2\topsep}
\begin{columns}
\begin{column}{0.6\textwidth}
{\small\begin{gather*}
\prod_{i = 1}^m \sum_{j=1}^n a_{ij} = \sum_{\vec{j} \in \{1,\dots,n\}^m} \prod_{i=1}^m a_{i,j_i} \\
\left(a_{11} + \boxed{a_{12}} + a_{13} + a_{14} + a_{15}\right) \to \sum\nolimits_{j=1}^5 a_{1j} \\
\left(a_{21} + a_{22} + a_{23} + \boxed{a_{24}} + a_{25}\right) \to \sum\nolimits_{j=1}^5 a_{2j} \\
\left(\boxed{a_{31}} + a_{32} + a_{33} + a_{34} + a_{35}\right) \to \sum\nolimits_{j=1}^5 a_{3j} \\
\left(a_{41} + \boxed{a_{42}} + a_{43} + a_{44} + a_{45}\right) \to \sum\nolimits_{j=1}^5 a_{4j} \\
\end{gather*}}
\end{column}
\begin{column}{0.4\textwidth}
{\small$\vec{j}$ as a choice function: \\ row index $\mapsto$ {\color{RawSienna}column index}
\vspace{-\topsep}
\begin{gather*}
m = 4, n = 5, \\
\vec{j} = \begin{pmatrix} {\color{RawSienna}2} \\ {\color{RawSienna}4} \\ {\color{RawSienna}1} \\ {\color{RawSienna}2} \end{pmatrix} \\
\prod_{i = 1}^m \boxed{a_{i,{\color{RawSienna}j_i}}} = \boxed{a_{1{\color{RawSienna}2}} a_{2{\color{RawSienna}4}} a_{3{\color{RawSienna}1}} a_{4{\color{RawSienna}2}}}
\end{gather*}}
\end{column}
\end{columns}
\end{block}
}
\only<3-14>{
\vspace{-3\topsep}
\begin{lemma}
\vspace{-0.3ex}
\begin{equation*}
\sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,{\color{blue}\varepsilon_i}} = 0
\end{equation*}
\begingroup
\small
\vspace{-0.5ex}
\begin{columns}
\begin{column}{0.35\textwidth}
\uncover<4->{
\begin{tabular}{c|c}
before \alt<1-9>{\color{blue}\underline{swap}}{\color{red}\underline{swap}} & after \alt<1-9>{\color{blue}\underline{swap}}{\color{red}\underline{swap}} \\ \hline
\alt<1-9>{$a_{{\color{red}1}5} b_{5{\color{blue}\underline{3}}}$}{$a_{{\color{red}1}\underline{5}} b_{5{\color{blue}3}}$} & \alt<1-9>{$a_{{\color{red}1}5} b_{5{\color{blue}\underline{4}}}$}{$a_{{\color{red}\underline{2}}5} b_{5{\color{blue}3}}$} \\
\alt<1-9>{$a_{{\color{red}2}5} b_{5{\color{blue}\underline{4}}}$}{$a_{{\color{red}2}\underline{5}} b_{5{\color{blue}4}}$} & \alt<1-9>{$a_{{\color{red}2}5} b_{5{\color{blue}\underline{3}}}$}{$a_{{\color{red}\underline{1}}5} b_{5{\color{blue}4}}$} \\
$a_{{\color{red}3}\spadesuit} b_{\spadesuit{\color{blue}5}}$ & $a_{{\color{red}3}\spadesuit} b_{\spadesuit{\color{blue}5}}$ \\
$a_{{\color{red}4}\blacklozenge} b_{\blacklozenge{\color{blue}1}}$ & $a_{{\color{red}4}\blacklozenge} b_{\blacklozenge{\color{blue}1}}$ \\
$a_{{\color{red}5}\clubsuit} b_{\clubsuit{\color{blue}2}}$ & $a_{{\color{red}5}\clubsuit} b_{\clubsuit{\color{blue}2}}$
\end{tabular}
}
\end{column}
\begin{column}{0.65\textwidth}
\uncover<5->{
If $v(i^\prime) = v(i^{\prime\prime})$, apply swap \alt<1-9>{$\tau := ({\color{blue}\varepsilon(i^\prime)}, {\color{blue}\varepsilon(i^{\prime\prime})})$ to $\varepsilon$}{$\rho := ({\color{red}i^\prime},{\color{red}i^{\prime\prime}})$ to $\color{red}i$, then for all $\color{red}i$, $v(\rho(i)) = v_i$, and LHS is}
\only<5-6>{
\vspace{0.7ex}
\begin{equation*}
\text{LHS} = \eqnmark[green!75!black]{fact3xs1}{\sum_{\varepsilon \in S_n}} \mathsf{sgn}(\eqnmarkbox[red]{fact3xtau}{\tau}\varepsilon) \eqnmark[green!75!black]{fact3xs2}{\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}}} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,{\color{blue}(\tau\varepsilon)_i}}
\end{equation*}
\annotate[yshift=-3.2ex]{below}{fact3xtau}{\footnotesize WRONG: $\tau$ depends on $\vec{v}$}
\only<6>{\annotatetwo[yshift=1ex,xshift=1.5em]{}{fact3xs1}{fact3xs2}{\footnotesize swap them first before applying $\tau$ to $\varepsilon$}}
}
\only<7>{
\vspace{1.5ex}
\begin{equation*}
\text{LHS} = \eqnmark[green!75!black]{fact3xs3}{\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}}} \eqnmark[green!75!black]{fact3xs4}{\sum_{\varepsilon \in S_n}} \mathsf{sgn}(\varepsilon) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,\eqnmark[blue]{fact3xeps}{\varepsilon_i}}
\annotatetwo[yshift=1ex]{}{fact3xs3}{fact3xs4}{\footnotesize two $\sum$ swapped}
\annotate[yshift=-1ex]{below,left}{fact3xeps}{\footnotesize $\tau$ not yet applied to $\varepsilon$}
\end{equation*}
}
\only<8>{
\begin{equation*}
\text{LHS} = \sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,{\color{blue}(\tau\varepsilon)_i}}
\end{equation*}
}
\only<9>{
\vspace{-1.7ex}
\begin{equation*}
\text{LHS} = -\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \eqnmarkbox[BurntOrange]{fact3xtaueps}{\sum_{\varepsilon \in S_n} \mathsf{sgn}(\tau\varepsilon) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},v_i} b_{v_i,{\color{blue}(\tau\varepsilon)_i}}}
\end{equation*}
\vspace{2.5ex}
\annotate[yshift=-1ex]{below,left}{fact3xtaueps}{\footnotesize prev. lemma can't be applied \\ since $\tau$ also depends on $\varepsilon$}
}
\only<10>{
\vspace{0.7ex}
\begin{equation*}
\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \left(\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i}, v_i} \right) \hspace{-0.5em} \left(\eqnmark[gray]{fact3prod2}{\prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}}} b_{\eqnmark[orange]{fact3vrho}{v(\rho(i))}\!\!,{\color{blue}\varepsilon(\rho(i))}} \right)
\end{equation*}
\annotate[yshift=1ex]{left}{fact3prod2}{\footnotesize invariant under $\rho$}
\annotate[yshift=-1ex]{left,below}{fact3vrho}{\footnotesize $v(\rho(i)) = v_i$}
}
\only<11>{
\begin{equation*}
\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \sum_{\varepsilon \in S_n} \mathsf{sgn}(\varepsilon) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i}, v_i} b_{v_i,{\color{blue}\varepsilon(\rho(i))}}
\end{equation*}
}
\only<12>{
\begin{equation*}
-\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}} \eqnmark[orange!70!black]{fact3sum1}{\sum_{\varepsilon \in S_n}} \mathsf{sgn}(\eqnmark[orange!70!black]{fact3sum2}{\varepsilon\rho}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i}, v_i} b_{v_i,\eqnmarkbox[orange!70!black]{fact3sum3}{\color{blue}(\varepsilon\rho)_i}}
\end{equation*}
\annotatetwo[yshift=1ex]{}{fact3sum1}{fact3sum2}{\footnotesize $\varepsilon\rho$ also runs through $S_n$}
}
\only<13-14>{
\begin{equation*}
-\tikzmarknode{fact3sumz1}{\sum_{\substack{\vec{v} \in \{1,\dots,n\}^{{\color{red}n}} \\ \vec{v}\;\text{not bijective}}}} \tikzmarknode{fact3sumz2}{\sum_{\varepsilon \in S_n}} \mathsf{sgn}(\eqnmark[orange!70!black]{fact3epsrho1}{\varepsilon}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i}, v_i} b_{v_i,\eqnmarkbox[orange!70!black]{fact3epsrho2}{\color{blue}\varepsilon_i}}
\end{equation*}
\annotatetwo[yshift=-2ex]{below,label below}{fact3epsrho1}{fact3epsrho2}{\footnotesize $\varepsilon\rho$ replaced with $\varepsilon$}
\only<14>{
\annotatetwo[yshift=1ex]{}{fact3sumz1}{fact3sumz2}{swap them, then $\text{LHS} = -\text{LHS}$}
}
}
}
\end{column}
\end{columns}
\endgroup
\end{lemma}
}
\end{frame}
\begin{frame}{Recover book's definition (Laplace expansion)}
\only<1-5>{
\vspace{-0.7ex}
\begin{exampleblock}{Observation from $n = 3$}
\vspace{2.5ex}
\begin{align*}
\begin{vmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} & a_{33}
\end{vmatrix} &
\uncover<2->{
=\begin{NiceMatrix}
a_{11} & & \\
& a_{22} & a_{23} \\
& a_{32} & a_{33}
\CodeAfter
\tikz \draw (1-1) circle (3mm) ;
\SubMatrix|{2-2}{3-3}|
\end{NiceMatrix}
}
\uncover<3->{
\mathrel{\tikzmarknode[outer sep=5pt]{lapobs1}{-}} \begin{NiceMatrix}
& a_{12} & \\
a_{21} & & a_{23} \\
a_{31} & & a_{33}
\CodeAfter
\tikz \draw (1-2) circle (3mm) ;
\SubMatrix|{2-1}{3-3}|
\end{NiceMatrix}
}
\uncover<4->{
\mathrel{\tikzmarknode[outer sep=5pt]{lapobs2}{+}} \begin{NiceMatrix}
& & a_{13} \\
a_{21} & a_{22} & \\
a_{31} & a_{32} &
\CodeAfter
\tikz \draw (1-3) circle (3mm) ;
\SubMatrix|{2-1}{3-2}|
\end{NiceMatrix}
} \\
\uncover<5->{
&= -\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{21}$};} \begin{vmatrix} & a_{12} & a_{13} \\ & & \\ & a_{32} & a_{33} \end{vmatrix}
+\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{22}$};} \begin{vmatrix} a_{11} & & a_{13} \\ & & \\ a_{31} & & a_{33} \end{vmatrix}
-\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{23}$};} \begin{vmatrix} a_{11} & a_{12} & \\ & & \\ a_{31} & a_{32} & \end{vmatrix}
}
\end{align*}
\hspace{-10ex}
\uncover<4->{\annotatetwo[yshift=3ex]{}{lapobs1}{lapobs2}{alternating signs}}
\end{exampleblock}
}
\only<5-6>{
\begin{exampleblock}{Notation}
For any $A \in {\cal M}_{n \times n}(R)$, denote $\tilde{A}_{ij}$ as the matrix with $i$-th row and $j$-column removed.
\only<5>{Using this notation, the above determinant would become $$-\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{21}$};}\det(\tilde{A}_{21})+\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{22}$};}\det(\tilde{A}_{22})-\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{23}$};}\det(\tilde{A}_{23}).$$}
\end{exampleblock}
}
\only<6-7>{
\only<6>{Recall that the definition of determinant contains $\mathsf{sgn}(\sigma) := (-1)^{N(\sigma)}$ (i.e. parity of no. of inversions)}
\begin{block}{Effect of $\bigstar$-deletion on no. of inversions}
\begin{tabular}{lcc}
{\footnotesize \rule{0.2cm}{0.7pt} $\bigstar$-deletion} & matrix & $\color{blue}\sigma$-$\color{red}i$ graph ($\curvearrowleft 90\degree$) \\[3ex]
before & $\tikzmarknode[outer sep=5pt]{matA}{A} = \begin{NiceArrayWithDelims}{\downarrow}{.}{>{\strut}cccc}[small,first-col,last-col,margin]
& & & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & & \\
& & \Block[fill=blue]{}{\color{yellow}\bigstar} & & & \boldsymbol{\gets\,{\color{red} i_0}} \\
{\color{red}\boldsymbol{i} \hspace{3mm}} & & & & \Block[fill=blue]{}{\phantom{\bigstar}} & \\
\CodeAfter
\SubMatrix[{1-1}{4-4}]
\tikz \draw[->] ([yshift=2mm]1-|1) -- ([yshift=2mm]1-|last) node[right, blue]{$\boldsymbol{\sigma_i}$};
\end{NiceArrayWithDelims}$ &
$\begin{NiceArray}{>{\strut}cccc}[small,first-col,code-for-first-col=\color{blue},last-row,margin]
& & & & \Block[fill=blue]{}{\phantom{\bigstar}} \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & \\
\boldsymbol{j_0 = \sigma_{i_0}} \to & & & \Block[fill=blue]{}{\color{yellow}\bigstar} & \\
& & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& & & \boldsymbol{\begin{array}{c} \\[2pt] \uparrow \\[2pt] {\color{red}i_0} \end{array}} &
\CodeAfter
\tikz [<->] \draw ([xshift=-2mm, yshift=1mm]1-|1) |- ([xshift=1mm, yshift=-2mm]last-|last)
node[pos=0, above, blue]{$\boldsymbol{\sigma_i}$} node[pos=1, right, red]{$\boldsymbol{i}$};
\end{NiceArray}$ \\
\only<7>{& & \\ after &
$\tikzmarknode[outer sep=2pt]{matAtd}{\tilde{A}}_{\eqnmark[red]{i0}{i_0},\sigma_{i_0}} = \begin{NiceArrayWithDelims}{\downarrow}{.}{cccc}[small,first-col,last-col,margin]
& & \Block[tikz={pattern = north west lines,pattern color=gray}]{*-1}{} & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & & \\
& \Block[tikz={pattern = north east lines,pattern color=gray}]{1-*}{} & \tikz{\node[fill=blue,text=yellow,inner sep=0,opacity=0.3]{$\star$};} & & & \boldsymbol{\gets\,{\color{red} i_0}}\text{-th} \\
{\color{red}\boldsymbol{i} \hspace{3mm}} & & & & \Block[fill=blue]{}{\phantom{\bigstar}} & \text{row deleted} \\
\CodeAfter
\SubMatrix[{1-1}{4-4}]
\tikz[->] {
\draw ([yshift=2mm]1-|1) -- ([yshift=2mm]1-|last) node[right, blue]{$\boldsymbol{\tilde{\sigma}_i}$};
}
\end{NiceArrayWithDelims}$ &
$\begin{NiceArray}{cccc}[small,first-col,code-for-first-col=\color{blue},last-row,margin]
& & & \Block[tikz={pattern = north west lines,pattern color=gray}]{*-1}{} & \Block[fill=blue]{}{\phantom{\bigstar}} \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & \\
\boldsymbol{j_0 = \sigma_{i_0}} \to & \Block[tikz={pattern = north east lines,pattern color=gray}]{1-*}{} & & \tikz{\node[fill=blue,text=yellow,inner sep=0,opacity=0.3]{$\star$};} & \\
& & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& & & \boldsymbol{\begin{array}{c} \\[2pt] \uparrow \\[2pt] {\color{red}i_0} \end{array}} &
\CodeAfter
\tikz{
\draw[<->] ([xshift=-2mm, yshift=1mm]1-|1) |- ([xshift=1mm, yshift=-2mm]last-|last)
node[pos=0, above, blue]{$\boldsymbol{\tilde{\sigma}_i}$}
node[pos=1, right, red]{$\boldsymbol{i}$};
\draw[thick,line width=2.5pt,dash=on 10pt off 5pt phase 0pt,gray!60!black,-latex] ([xshift=-4mm,yshift=1pt]4-|1) -- ([xshift=4mm,yshift=1pt]4-|last);
\draw[thick,line width=2.5pt,dash=on 10pt off 5pt phase 0pt,gray!60!black,-latex] ([xshift=1pt,yshift=-4mm]last-|3) -- ([xshift=1pt,yshift=4mm]1-|3);
}
\end{NiceArray}$}
\end{tabular}
\annotate[yshift=-1ex]{below, left}{matA}{\scriptsize $n \times n$-matrix}
\only<7>{
\annotate[yshift=-2.5ex, xshift=2em]{below, left, label below}{matAtd}{\scriptsize $(n-1) \times (n-1)$-matrix}
\annotate[yshift=3.5ex, xshift=1em]{left}{i0}{\scriptsize fixed \textcolor{red}{row index} independent of $\sigma$}
}
\end{block}
}
\only<8-11>{
\begin{block}{Effect of $\bigstar$-deletion on no. of inversions}
\begin{columns}[T]
\begin{column}{0.5\textwidth}
\vspace{5pt}
\begin{tabular}{lc}
{\footnotesize \rule{0.2cm}{0.7pt} $\bigstar$-deletion} & $\color{blue}\sigma$-$\color{red}i$ graph ($\curvearrowleft 90\degree$) \\[3ex]
before &
$\begin{NiceArray}{>{\strut}cccc}[small,first-col,code-for-first-col=\color{blue},last-row,margin]
& & & & \Block[fill=blue]{}{\phantom{\bigstar}} \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & \\
\boldsymbol{j_0 = \sigma_{i_0}} \to & & & \Block[fill=blue]{}{\color{yellow}\bigstar} & \\
& & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& & & \boldsymbol{\begin{array}{c} \\[2pt] \uparrow \\[2pt] {\color{red}i_0} \end{array}} &
\CodeAfter
\tikz [<->] \draw ([xshift=-2mm, yshift=1mm]1-|1) |- ([xshift=1mm, yshift=-2mm]last-|last)
node[pos=0, above, blue]{$\boldsymbol{\sigma_i}$} node[pos=1, right, red]{$\boldsymbol{i}$};
\end{NiceArray}$ \\
& \\ after &
$\begin{NiceArray}{cccc}[small,first-col,code-for-first-col=\color{blue},last-row,margin]
& & & \Block[tikz={pattern = north west lines,pattern color=gray}]{*-1}{} & \Block[fill=blue]{}{\phantom{\bigstar}} \\
& \Block[fill=blue]{}{\phantom{\bigstar}} & & & \\
\boldsymbol{j_0 = \sigma_{i_0}} \to & \Block[tikz={pattern = north east lines,pattern color=gray}]{1-*}{} & & \tikz{\node[fill=blue,text=yellow,inner sep=0,opacity=0.3]{$\star$};} & \\
& & \Block[fill=blue]{}{\phantom{\bigstar}} & & \\
& & & \boldsymbol{\begin{array}{c} \\[2pt] \uparrow \\[2pt] {\color{red}i_0} \end{array}} &
\CodeAfter
\tikz{
\draw[<->] ([xshift=-2mm, yshift=1mm]1-|1) |- ([xshift=1mm, yshift=-2mm]last-|last)
node[pos=0, above, blue]{$\boldsymbol{\tilde{\sigma}_i}$}
node[pos=1, right, red]{$\boldsymbol{i}$};
\draw[thick,line width=2.5pt,dash=on 10pt off 5pt phase 0pt,gray!60!black,-latex] ([xshift=-4mm,yshift=1pt]4-|1) -- ([xshift=4mm,yshift=1pt]4-|last);
\draw[thick,line width=2.5pt,dash=on 10pt off 5pt phase 0pt,gray!60!black,-latex] ([xshift=1pt,yshift=-4mm]last-|3) -- ([xshift=1pt,yshift=4mm]1-|3);
}
\end{NiceArray}$
\end{tabular}
\end{column}
\begin{column}{0.5\textwidth}
\vspace{5pt}
Observations:
\begin{itemize}
\item $\tilde{\sigma}$ is a bijection \only<9>{(passes both vertical line \& horizontal line tests)}
\item<9-> no. of $\underbrace{\begin{smallmatrix} {\color{blue}\blacksquare} & & \\ & \searrow & \\ & & {\color{blue}\blacksquare} \end{smallmatrix}}_{\text{inversions}}$ and $\underbrace{\begin{smallmatrix} & & {\color{blue}\blacksquare} \\ & \nearrow & \\ {\color{blue}\blacksquare} & & \end{smallmatrix}}_{\text{non-inversions}}$ involving $\color{blue}\blacksquare$ (without $\bigstar$) don't change after we've removed $\tikz[baseline=-0.5ex]{\node[fill=blue,text=yellow,inner sep=1pt]{$\bigstar$};}$
\only<10>{\color{gray!60!black} since \raisebox{-1ex}{shifting} caused by
\begingroup
\contourlength{1.5pt}
$\tikz[baseline=-0.5ex]{\node[pattern=north west lines,pattern color=gray]{\contour{white}{$\bigstar$-deletion}};}$
\endgroup
doesn't move $\color{blue}\blacksquare$ across \contour{black}{$\boldsymbol{\dashrightarrow}$} and \rotatebox{90}{\contour{black}{$\boldsymbol{\dasharrow}$}}}
\only<11>{
\item so to compare $N(\sigma)$ and $N(\tilde{\sigma})$, only focus on
\begingroup
\setlength{\arraycolsep}{0.5pt}
$$\underbrace{\begin{NiceArray}{*3{W{c}{1.15em}}c!{\hspace{0.75em}}c!{\hspace{0.75em}}*3{W{c}{1.15em}}}
\CodeBefore
\cellcolor{blue}{1-1,1-6,3-3,3-8}
\Body
{\color{yellow}\bigstar} & & & & & & & \\
& \searrow & & & \text{and} & & \searrow & \\
& & & & & & & {\color{yellow}\bigstar} \\
\end{NiceArray}}_{\text{inversions involving}\;\tikz[baseline=-0.5ex]{\node[fill=blue,text=yellow,inner sep=1pt]{$\bigstar$};}\;\text{in}\,\sigma \in S_n}$$
\endgroup
}
\end{itemize}
\end{column}
\end{columns}
\end{block}
}
\only<12-16>{
\begin{block}{Effect of $\bigstar$-deletion on no. of inversions}
\vspace{3ex}
\begingroup
\setlength{\tabcolsep}{0pt}
\begin{NiceTabular}{r!{\hspace{1em}}*{3}{W{c}{3em}}c!{\hspace{1pt}}c!{\hspace{1pt}}*{3}{W{c}{3em}}c!{\hspace{1.5em}}l}
\CodeBefore
\cellcolor{blue}{4-5,4-6}
\Body
& \Block[fill=yellow]{3-3}<\Large>{$k\,{\color{blue}\blacksquare}$-cell} & & & & & \Block{3-3}{$n-{\color{blue}\sigma_{i_0}}-k$ \\ ${\color{blue}\blacksquare}$-cell} & & & & \Block{3-1}{$n-{\color{blue}\sigma_{i_0}}$ \\ $\color{blue}\blacksquare$-cell above} \\
& & & & & & & & & & \\
& & & & & & & & & & \\
${\color{blue}j_0} = {\color{blue}\sigma_{i_0}}$ & & & & & $\color{yellow}\bigstar$ & & & & & \\
& \Block[c]{3-3}{${\color{red}i_0} - 1 - k$ \\ ${\color{blue}\blacksquare}$-cell} & & & & & \Block[fill=yellow]{3-3}<\Large>{${\color{blue}\sigma_{i_0}}-{\color{red}i_0}+k$ \\ ${\color{blue}\blacksquare}$-cell} & & & & \Block{3-1}{${\color{blue}\sigma_{i_0}}-1$ \\ $\color{blue}\blacksquare$-cell below} \\
& & & & & & & & & & \\
& & & & & & & & & & \\
& & & & & & & & & & \\
total & \Block[c]{1-3}{${\color{red}i_0}-1\,{\color{blue}\blacksquare}$-cell \\ on the left} & & & & $\color{red}i_0$ & \Block[c]{1-3}{$n-{\color{red}i_0}\,{\color{blue}\blacksquare}$-cell \\ on the right} & & & & \\
\CodeAfter
\tikz {
\draw[<->,line width=0.7pt] ([yshift=2mm]1-|2) |- ([xshift=2mm]8-|10)
node[pos=0, above, blue]{$\sigma_i$}
node[pos=1, right, red]{$i$};
\draw[dashed,line width=0.3pt] (4-|2) -- (4-|11.5);
\draw[-latex,dashed,line width=1.5pt,gray!60!black] (5-|2) -- (5-|11.5);
\draw[-latex,dashed,line width=1.5pt,gray!60!black] (9-|5) -- (1-|5);
\draw[dashed,line width=0.3pt] (9-|7) -- (1-|7);
}
\end{NiceTabular}
\endgroup
\vspace{-1.5ex}
{\small\begin{align*}
\uncover<13->{N(\sigma) - N(\tilde{\sigma}) &= \colorbox{yellow}{$k$} + \colorbox{yellow}{${\color{blue}\sigma_{i_0}}-{\color{red}i_0}+k$} \\}
\temporal<14>{}{N(\sigma) - N(\tilde{\sigma}) &\equiv {\color{red}i_0} + {\color{blue}\sigma_{i_0}} \pmod2 \\}
{N(\sigma) &\equiv {\color{red}i_0} + {\color{blue}\sigma_{i_0}} + N(\tilde{\sigma}) \pmod2 \\}
\uncover<16->{\mathsf{sgn}(\sigma) &= (-1)^{{\color{red}i_0} + {\color{blue}\sigma_{i_0}}} \mathsf{sgn}(\tilde{\sigma})}
\end{align*}}
\end{block}
}
\only<17->{
\begin{exampleblock}{
\begingroup
\contourlength{0.5pt}
Observation from $n=3$ with $\text{\contour{white}{$\color{red}i_0$}} = \text{\contour{white}{\color{red}2}}$ (recall)
\endgroup
}
\only<17-19>{$$\det(A) = -\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{red}2}1}$};}\det(\tilde{A}_{{\color{red}2}1})+\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{red}2}2}$};}\det(\tilde{A}_{{\color{red}2}2})-\tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{red}2}3}$};}\det(\tilde{A}_{{\color{red}2}3}).$$}
Goal: for each ${\color{red}i_0} \in \{{\color{red}1},\dots,{\color{red}n}\}$,
$\det(A) = \sum\limits_{j=1}^n (-1)^{{\color{red}i_0}+j} \tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{red}i_0},j}$};} \det\left(\tilde{A}_{{\color{red}i_0},j}\right).$
\end{exampleblock}
\only<17-21>{
\begin{block}{Effect of $\bigstar$-deletion on $\mathsf{sgn}(\sigma)$}
\[
\forall {\color{red}i_0} \in \{{\color{red}1},\dots,{\color{red}n}\}, \forall \sigma \in S_n,
\mathsf{sgn}(\sigma) = (-1)^{{\color{red}i_0} + {\color{blue}\sigma_{i_0}}} \mathsf{sgn}(\tilde{\sigma}) \tag{$\bigstar$}
\]
\end{block}
}
\alt<29->{\vspace{-1.5\topsep}}{\alt<22-24>{\vspace{0.5ex}}{}}
\begin{align*}
\det(A)
\only<17-18>{&= \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}\sigma_i}} \\}
\only<18-19>{&= \sum_{\sigma \in S_n} \mathsf{sgn}(\sigma) a_{{\color{red}i_0},{\color{blue}\sigma_{i_0}}} \prod_{\substack{{\color{red}i} = {\color{red}1} \\ {\color{red}i} \ne {\color{red}i_0}}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}\sigma_i}} \tag{$a_{{\color{red}i_0},{\color{blue}\sigma_{i_0}}}$ extracted} \\}
\only<19-20>{&= \sum_{\sigma \in S_n} (-1)^{{\color{red}i_0}+{\color{blue}\sigma_{i_0}}}\,\mathsf{sgn}(\tilde{\sigma}) a_{{\color{red}i_0},{\color{blue}\sigma_{i_0}}} \prod_{\substack{{\color{red}i} = {\color{red}1} \\ {\color{red}i} \ne {\color{red}i_0}}}^{{\color{red}n}} a_{{\color{red}i},{\color{blue}\sigma_i}} \tag{$\bigstar$ applied} \\}
\only<20-29>{&= \tikzmarknode{lapSum}{\sum_{\sigma \in S_n}} \eqnmarkbox[gray]{lapSum1}{(-1)^{{\color{red}i_0}+{\color{blue}\sigma_{i_0}}}}\,\mathsf{sgn}(\tilde{\sigma}) \eqnmarkbox[gray]{lapSum2}{a_{{\color{red}i_0},{\color{blue}\sigma_{i_0}}}} \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n-1}} a_{{\color{red}i},{\color{blue}\tilde{\sigma}_i}} \tag{$\bigstar$-deletion} \\}
\only<29-30>{&= \sum_{{\color{orange!60!black}j_0}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{i_0+{\color{orange!60!black}j_0}} a_{i_0,{\color{orange!60!black}j_0}} {\color{purple}\sum_{\sigma \in S_n}} {\color{purple}\delta}_{{\color{blue}\sigma_{i_0}},{\color{orange!60!black}j_0}} \mathsf{sgn}(\tilde{\sigma}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n-1}} a_{{\color{red}i},{\color{blue}\tilde{\sigma}_i}} \\}
\only<30-33>{&= \sum_{{\color{orange!60!black}j_0}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{i_0+{\color{orange!60!black}j_0}} a_{i_0,{\color{orange!60!black}j_0}} {\color{purple}\sum_{\substack{\sigma \in S_n \\ {\color{blue}\sigma_{i_0}} = {\color{orange!60!black}j_0}}}} \mathsf{sgn}(\tilde{\sigma}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n-1}} a_{{\color{red}i},{\color{blue}\tilde{\sigma}_i}}}
\only<31-33>{\intertext{Remember that $\sigma \in S_n, {\color{blue}\sigma_{i_0}} = {\color{orange!60!black}j_0} \mapstofromA{6em}{\bigstar\text{-deletion}}{\bigstar\text{-insertion}} \tilde{\sigma} \in S_{n-1}$}}
\only<32-33>{&= \sum_{{\color{orange!60!black}j_0}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{i_0+{\color{orange!60!black}j_0}} a_{i_0,{\color{orange!60!black}j_0}} \underbrace{\sum_{\tilde{\sigma} \in S_{n-1}} \mathsf{sgn}(\tilde{\sigma}) \prod_{{\color{red}i} = {\color{red}1}}^{{\color{red}n-1}} a_{{\color{red}i},{\color{blue}\tilde{\sigma}_i}}}_{\det\left(\tilde{A}_{i_0,{\color{orange!60!black}j_0}}\right)}}
\only<34>{&= \sum_{{\color{orange!60!black}j_0}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{i_0+{\color{orange!60!black}j_0}} a_{i_0,{\color{orange!60!black}j_0}} \det\left(\tilde{A}_{i_0,{\color{orange!60!black}j_0}}\right) \tag{simplify by dropping subscript `${}_0$'}}
\only<35-36>{&= \underbrace{\sum_{\eqnmark[orange!60!black]{lapExp1j}{j}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{{\color{red}i}+{\color{orange!60!black}j}} \tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{red}i},{\color{orange!60!black}j}}$};} \det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)}_{\text{expansion along $i$-th row}} \quad \forall \eqnmark[red]{lapExp1i}{i} \in \{{\color{red}1},\dots,{\color{red}n}\} \\}
\only<36>{
&= \underbrace{\sum_{\eqnmark[orange!60!black]{lapExp2i}{i}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}} (-1)^{{\color{orange!60!black}i}+{\color{red}j}} \tikz[baseline=-0.5ex]{\node[draw,circle,radius=3mm,inner sep=0]{$a_{{\color{orange!60!black}i},{\color{red}j}}$};} \det\left(\tilde{A}_{{\color{orange!60!black}i},{\color{red}j}}\right)}_{\text{expansion along $j$-th column}} \quad \forall \eqnmark[red]{lapExp2j}{j} \in \{{\color{red}1},\dots,{\color{red}n}\}
\tag{Apply fact 1: $\det(A) = \underbrace{\det(A^\intercal)}_{i, j\;\text{interchanged}}$}
}
\end{align*}
\only<21-24>{
\begingroup
\tikzset{annotate equations/arrow/.style={->}}
\annotatetwo[yshift=1ex]{}{lapSum1}{lapSum}{want to move to the left of summation sign}
\annotatetwo[yshift=-0.3ex]{below}{lapSum2}{lapSum}{but depends on}
\endgroup
}
\only<35-36>{
\annotate[yshift=-0.3ex,xshift=0.5em]{below}{lapExp1i}{$i$ fixed}
\annotate[yshift=-0.3ex,xshift=-1em]{below,left}{lapExp1j}{$j$ moving}
}
\only<36>{
\annotate[yshift=-0.3ex,xshift=-1em]{below,left}{lapExp2i}{$i$ moving}
\annotate[yshift=-0.3ex,xshift=0.5em]{below}{lapExp2j}{$j$ fixed}
}
\only<22-23>{
\vspace{-2\topsep}
\begin{block}{
\begingroup
\contourlength{0.5pt}
Sum by \contour{white}{\color{green!80!black}sorting} and \contour{white}{\color{purple}counting}
\endgroup
}
Suppose that $f: D \to R$ is defined on a finite set $D$ and it has range $R$ closed under `$+$', `$-$' and \textbf{commutative} `$\cdot$' $\xcancel{\text{division}}$. Then
\vspace{-\topsep}
$$\eqnmark[orange!60!black]{sumsumL}{\sum_{x \in D} f(x)} = \eqnmark[green!80!black]{sumsumR1}{\sum_{y \in R} y} \eqnmark[purple]{sumsumR2}{\sum_{x \in D} 1_{f(x) = y}(x,y)}.$$
\uncover<23>{
\vspace{2ex}
\annotate[yshift=0ex,xshift=-0.5em]{left, below}{sumsumL}{\scriptsize sum of all function values \\[-0.5ex] \scriptsize with double count allowed}
\annotate[yshift=-1ex,xshift=2em]{below,left,label below}{sumsumR1}{\scriptsize sort into different \\[-0.5ex] \scriptsize output values}
\annotate[yshift=1.8ex]{below}{sumsumR2}{count how many input $x$ \\ gives that output $y$}
}
\end{block}
}
\only<24-28>{
\alt<24>{\vspace{-2\topsep}}{\vspace{-4\topsep}}
\begin{lemma}
Suppose that $f$ and $g$ are functions defined on the same finite set $D$ and they have range $R_f$ and $R_g$ respectively, such that they are both contained inside a larger set closed under `$+$', `$-$' and \textbf{commutative} `$\cdot$' $\xcancel{\text{division}}$. Then
\vspace{-\topsep}
\begingroup
\small
\begin{equation*}
\sum_{x \in D} f(x) g(x) = \only<24>{\sum_{x \in D} \underbrace{\left( \sum_{y \in R_f} {\color{purple}1_{f(x) = y}}(x,y) \right)}_{x\;\text{fixed, unique output}\;f(x)} {\color{green!80!black}f(x)} g(x)}
\only<25-26>{{\color{green!80!black}\sum_{y \in R_f}} {\color{purple}\sum_{x \in D}} \eqnmark[purple]{sumLem1a}{1_{f(x) = y}(x,y)} \eqnmark[green!80!black]{sumLem1b}{f(x)} g(x) \tag{order of `$\sum$' swapped}}
\only<27>{{\color{green!80!black}\sum_{y \in R_f}} {\color{purple}\sum_{x \in D} 1_{f(x) = y}(x,y)} \eqnmark[green!80!black]{sumLemY}{y} g(x)}
\only<28->{\eqnmark[green!80!black]{sumLemSort}{\sum_{y \in R_f} y} {\color{purple}\sum_{x \in D}} \eqnmark[purple]{sumLemFltr}{1_{f(x) = y}(x,y)} g(x)}
\end{equation*}
\only<26>{\annotatetwo[yshift=-1.7ex,xshift=1em]{below, label below}{sumLem1a}{sumLem1b}{\scriptsize if $f(x) \ne y$, then `$1_{f(x) = y}(x, y)$' in front will ``kill'' this term}}
\only<27>{\annotate[yshift=-1ex]{below}{sumLemY}{\scriptsize move to the left of 2nd `$\sum$'}}
\only<28->{
\annotate[yshift=0.7ex]{below,left}{sumLemSort}{\scriptsize ``sorting'' output of $f$}
\annotate[yshift=-1.5ex,xshift=-2em]{below,label below}{sumLemFltr}{\scriptsize \text{``filter''}\;y\;\text{to match specific output}\;f(x)}
}
\endgroup
\end{lemma}
}
}
\end{frame}
\begin{frame}[fragile]{Matrix inverse by determinant}
\vspace{-\topsep}
$$
\forall i \in \{{\color{red}1},\dots,{\color{red}n}\}, \quad
\det(A) =
\temporal<2>{
\sum_{{\color{orange!60!black}j}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}}
(-1)^{{\color{red}i}+{\color{orange!60!black}j}}
\tikz[baseline=(a.base)]{\node[draw,circle,radius=3mm,inner sep=1pt](a){$a_{{\color{red}i},{\color{orange!60!black}j}}$};}
\det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)
}{
\sum_{{\color{orange!60!black}j}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}}
\tikz[baseline=(a.base)]{\node[draw,circle,radius=3mm,inner sep=1pt](a){$a_{{\color{red}i},{\color{orange!60!black}j}}$};}
(-1)^{{\color{red}i}+{\color{orange!60!black}j}}
\det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)
}{
\sum_{{\color{orange!60!black}j}={\color{orange!60!black}1}}^{{\color{orange!60!black}n}}
\tikz[baseline=(a.base)]{\node[draw,circle,radius=3mm,inner sep=1pt](a){$a_{{\color{red}i},{\color{orange!60!black}j}}$};}\;
\boxed{
\tikzmarknode[outer sep=10pt]{cofAij}{(-1)^{{\color{red}i}+{\color{orange!60!black}j}}}
\eqnmarkbox[Sepia]{mnrA}{\det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)}
}
}
$$
\only<3>{
$\eqnmark[LimeGreen!50!black]{cofA}{C} := (C_{{\color{red}i},{\color{orange!60!black}j}})_{{\color{red}i},{\color{orange!60!black}j}}$
\annotate[yshift=-1ex]{below}{cofA}{cofactor matrix of $A$}
\annotate[yshift=-2ex]{below,label below}{mnrA}{$({\color{red}i},{\color{orange!60!black}j})$ minor of $A$, \\ denoted as $M_{{\color{red}i},{\color{orange!60!black}j}}$}
\annotate[yshift=-2ex,xshift=-5em]{below,label below,left}{cofAij}{$({\color{red}i},{\color{orange!60!black}j})$ cofactor of $A$, \\ denoted as $C_{{\color{red}i},{\color{orange!60!black}j}}$}
\vspace{-2ex}
}
\begingroup
\tikzset{highlight/.style={rectangle,
fill=red!25,
rounded corners = 0.5 mm,
inner sep=5pt,
fit=#1}}
\[\begin{NiceArray}{W{r}{4em}@{\hspace{0.5cm}}W{c}{1.5em}W{c}{1em}W{c}{1.5em}W{c}{1em}W{c}{1.5em}@{\hspace{8mm}}W{c}{1.5em}W{c}{1em}cW{c}{1em}W{c}{1.5em}@{\hspace{0.5cm}}W{l}{6em}}[nullify-dots,last-row,small]
\CodeBefore [create-cell-nodes]
\SubMatrix({2-7}{6-11})
\SubMatrix({7-2}{11-6})
\SubMatrix({7-7}{11-11})
\begin{tikzpicture}
\node [highlight = (9-2) (9-6)] { } ;
\node [highlight = (2-9) (6-9)] { } ;
\end{tikzpicture}
\Body
& & & & & & & & \color{red}\Block{1-1}<\scriptsize>{i\text{-th column of}\,C^\intercal} \\[2pt]
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{1,1} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & {\scriptstyle(-1)^{i+1} \det\left(\tilde{A}_{i,1}\right)} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{n,1} $};} \\
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} \\
& & & & & & & & {\scriptstyle(-1)^{i+j} \det\left(\tilde{A}_{i,j}\right)} & & & \scriptstyle \color{orange!60!black}\Block{1-1}<\scriptsize>{j\text{-th row} \\ \text{of}\,C^\intercal} \\
& & & & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} \\
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{1,n} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & {\scriptstyle(-1)^{i+n} \det\left(\tilde{A}_{i,n}\right)} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{n,n} $};} \\[3mm]
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{11} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{1n} $};} & {\det(A)} \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & {\Ddots} & \Vdots\\
\color{red} \Block{1-1}<\scriptsize>{i\text{-th row} \\ \text{of}\,A}
& a_{i1} & \Cdots & a_{ij} & \Cdots & a_{in} & \Cdots & & \det(A) \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & {\Ddots} \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{n1} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{nn} $};} & & & & & {\det(A)} \\
& & & \scriptstyle \color{orange!60!black}\overset{\uparrow}{j\text{-th column of}\;A}
\CodeAfter
\tikz \draw [gray,shorten > = 3mm, shorten < = 3mm,line width=1pt] (9-4.north) to [bend left] (4-9.west) ;
\tikz \draw (9-2) circle (3mm);
\tikz \draw (9-4) circle (3mm);
\tikz \draw (9-6) circle (3mm);
\end{NiceArray}\]
\endgroup
\end{frame}
\begin{frame}[fragile,b]{Matrix inverse by determinant}
\temporal<2>{
An \colorbox{yellow}{off diagonal entry} of $AC$ is \colorbox{yellow}{$0$}.
}{
\vspace{-1.5ex}
\begin{equation*}
\forall {\color{red}i} \in \{{\color{red}1},\dots,{\color{red}n}\},
\forall {\color{blue}i^\prime} \in \{{\color{blue}1},\dots,{\color{blue}n}\} \setminus \{{\color{red}i}\},
\sum_{{\color{orange!60!black}j} = {\color{orange!60!black}1}}^{{\color{orange!60!black}n}}
\tikz[baseline=(a.base)]{\node[draw,circle,radius=3mm,inner sep=1pt,fill=blue!25](a){$a_{{\color{blue}i^\prime},{\color{orange!60!black}j}}$};} \;
\tikz[baseline=(a.base)]{\node[fill=red!25](a){$(-1)^{{\color{red}i}+{\color{orange!60!black}j}} \det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)$};}
\end{equation*}
\vspace{-1ex}
}{}
\only<4>{
Conclusion: \colorbox{yellow}{$\boxed{AC^\intercal = \det(A)I}$} $\in {\cal M}_{n \times n}(R)$ ($R$ might not contain `$1$', and it might not have division.)
}
\begingroup
\tikzset{highlight/.style={rectangle,
fill=red!25,
rounded corners = 0.5 mm,
inner sep=5pt,
fit=#1},
highlightA/.style={rectangle,
fill=blue!25,
rounded corners = 0.5 mm,
inner sep=5pt,
fit=#1}}
\[\begin{NiceArray}{W{r}{4em}@{\hspace{0.5cm}}W{c}{1.5em}W{c}{1em}W{c}{1.5em}W{c}{1em}W{c}{1.5em}@{\hspace{8mm}}W{c}{1.5em}W{c}{1em}cW{c}{1em}W{c}{1.5em}@{\hspace{0.5cm}}W{l}{6em}}[nullify-dots,last-row,small]
\CodeBefore [create-cell-nodes]
\SubMatrix({2-7}{6-11})
\SubMatrix({7-2}{13-6})
\SubMatrix({7-7}{13-11})
\begin{tikzpicture}
\node [highlightA = (11-2) (11-6)] { } ;
\node [highlight = (2-9) (6-9)] { } ;
\end{tikzpicture}
\cellcolor{yellow}{11-9}
\Body
& & & & & & & & \color{red}\Block{1-1}<\scriptsize>{i\text{-th column of}\,C^\intercal} \\[2mm]
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{1,1} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & {\scriptstyle(-1)^{i+1} \det\left(\tilde{A}_{i,1}\right)} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{n,1} $};} \\
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} \\
& & & & & & & & {\scriptstyle(-1)^{i+j} \det\left(\tilde{A}_{i,j}\right)} & & & \scriptstyle \color{orange!60!black}\Block{1-1}<\scriptsize>{j\text{-th row} \\ \text{of}\,C^\intercal} \\
& & & & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} \\
& & & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{1,n} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & {\scriptstyle(-1)^{i+n} \det\left(\tilde{A}_{i,n}\right)} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ C_{n,n} $};} \\[3mm]
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{11} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{1n} $};} & {\det(A)} \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & {\Ddots} & \Vdots\\
\color{red} \Block{1-1}<\scriptsize>{i\text{-th row} \\ \text{of}\,A}
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{i1} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{in} $};} & \Cdots & & \det(A) \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & \Vdots \\
\color{blue} \Block{1-1}<\scriptsize>{i^\prime\text{-th row} \\ \text{of}\,A}
& a_{i^\prime 1} & \Cdots & a_{i^\prime j} & \Cdots & a_{i^\prime n} & \Cdots & & 0 \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} & & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Vdots $};} \\
& \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{n1} $};} & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ \Cdots $};} & & & \tikz[baseline=(a.base)]{\node[opacity=0.4](a){$ a_{nn} $};} & & & & & {\det(A)} \\
& & & \scriptstyle \color{orange!60!black}\overset{\text{\contour{orange!60!black}{$\uparrow$}}}{j\text{-th column of}\;A}
\CodeAfter
\tikz \draw [gray,shorten > = 3mm, shorten < = 3mm,line width=1pt] (11-4.north) to [bend left] (4-9.west) ;
\tikz \draw (11-2) circle (3mm);
\tikz \draw (11-4) circle (3mm);
\tikz \draw (11-6) circle (3mm);
\only<3>{
\tikz \node[align=left, anchor=north west, yshift=6ex, font=\scriptsize] at (1-|1) {
$\forall {\color{red}i} \in \{{\color{red}1},\dots,{\color{red}n}\}$,
$\forall {\color{blue}i^\prime} \in \{{\color{blue}1},\dots,{\color{blue}n}\} \setminus \{{\color{red}i}\}$, \\
$\mathrel{\phantom{=}} \sum\limits_{{\color{orange!60!black}j} = {\color{orange!60!black}1}}^{{\color{orange!60!black}n}} \;\;
\tikz[baseline=(a.base)]{
\node[draw,circle,radius=3mm,inner sep=2pt,fill=blue!25](a){$a_{{\color{blue}i^\prime},{\color{orange!60!black}j}}$};
\node[fill=red!25, xshift=2.2em, yshift=1ex]{$(-1)^{{\color{red}i}+{\color{orange!60!black}j}} \det\left(\tilde{A}_{{\color{red}i},{\color{orange!60!black}j}}\right)$};
}
$ \\[3pt]
$= \begin{array}{|ccccc|l}
a_{11} & \cdots & a_{1j} & \cdots & a_{1n} & \\
\vdots & \ddots & \cdots & \cdots & \vdots &
\multirow{3}*{
\hspace{-5pt} $\gets \begin{array}{|l|}
\hline \rlap{\phantom{T}} \scriptstyle \color{red} i\text{-th row of}\, A \\
\scriptstyle \text{replaced by} \\
\scriptstyle \text{entries from} \\
\scriptstyle \color{blue} i^\prime\text{-th of}\, A \\\hline
\end{array}$
} \\
\tikz[baseline=(a.base)]{
\node[draw,circle,inner sep=-1pt,fill=blue!25,xshift=-0.6em,font=\scriptsize] (a) {
$\,a_{{\color{blue}i^\prime},{\color{orange!60!black}1}}$
};
} &
\cdots &
\tikz[baseline=(a.base)]{
\node[draw,circle,inner sep=-1pt,fill=blue!25,xshift=-0.8em,font=\scriptsize] (a) {
$\,a_{{\color{blue}i^\prime},{\color{orange!60!black}j}}$
};
} & \cdots &
\tikz[baseline=(a.base)]{
\node[draw,circle,inner sep=-1pt,fill=blue!25,xshift=-1em,font=\scriptsize] (a) {
$\,a_{{\color{blue}i^\prime},{\color{orange!60!black}n}}$
};
} & \\
\vdots & \ddots & \cdots & \cdots & \vdots & \\
a_{i^\prime 1} & \cdots & a_{i^\prime j} & \cdots & a_{i^\prime n} & \scriptstyle \gets \color{blue} i^\prime\text{-th row of}\, A \\
\vdots & \ddots & \cdots & \cdots & \vdots & \\
a_{n1} & \cdots & a_{nj} & \cdots & a_{nn} & \\
\end{array}$
};
}
\end{NiceArray}\]
\endgroup
\end{frame}
\begin{frame}[t]{Food for thoughts / Exercises}
The questions below are here to test your understanding of the ideas presented in this presentation.
\begin{enumerate}[<+->]
\item Complete the previous section by stating the formula of $A^{-1}$, which involves $\det(A)$.
\item Prove the multilinearity of determinant. That's an important property of determinant that I'm hiding throughout this presentation.
\item Hence, prove \textbf{Cramer's Rule}.
\item Find an alternative proof for Basic Fact 3 ($\det(AB) = \det(A) \det(B)$)
\begin{enumerate}
\item by applying the Technical Lemma that a swap alters the sign of a permutation
\item and swapping $\tikz[baseline=-0.5ex]{\node[fill=blue,text=yellow,inner sep=1pt]{$\bigstar$};}$ with adjacent entries until it reaches the bottom right corner.
\end{enumerate}
\end{enumerate}
\end{frame}
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment