\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{tabu}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{hyperref}
%\usepackage{ytableau}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, October 11, 2015 20:25:58}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{TODO}
\newenvironment{todo}[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{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{obsolete}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{obsolete}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\ihead{Combinatorial proof of Chio Pivotal Condensation}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\author{Karthik Karnik, Anya Zhang \\
(advised by Darij Grinberg in PRIMES 2015)}
\title{Combinatorial proof of Chio Pivotal Condensation}
\date{25 May 2016}
\maketitle

In this note, we shall give a direct proof of the \textit{Chio pivotal condensation theorem}. This theorem is one of many that relate the determinant of a matrix to the determinant of a smaller matrix (and, in many cases, reduce the computation of the former to that of the latter -- thus ``condensing'' the determinant). It can be stated as follows:

\begin{theorem} \label{thm.chio}
Let $\mathbb{K}$ be a commutative ring with unity. Let $n \geq 2$ be an integer. Let $A = \left(a_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n} \in \mathbb{K}^{n\times n}$ be a matrix. Then,
\[
\det\left(  \left(  a_{i,j}a_{n,n}-a_{i,n}a_{n,j}\right)  _{1\leq i\leq
n-1,\ 1\leq j\leq n-1}\right)  =a_{n,n}^{n-2}\cdot\det\left(  \left(
a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}\right) .
\]
\end{theorem}

We refer to \cite{detnotes} for undefined notations used here (though they should all be standard).

Classically, Theorem~\ref{thm.chio} is proven using a trick. Namely, it is first proven under the assumption that $a_{n,n}$ be invertible (see, e.g., \cite[Exercise 6.19]{detnotes} and the reference therein); then, the ``universality of polynomial identities'' \cite{Conrad-UP1} shows that it holds in the general case as well (since it is an identity between two fixed polynomials in the $n^2$ variables $a_{1,1},a_{1,2},\ldots,a_{n,n}$).

In this note, we shall give a different proof of Theorem~\ref{thm.chio} which proceeds directly (and, to some extent, combinatorially, using bijections and sign-reversing involutions).

We fix $\mathbb{K}$, $n$, $A$ and $a_{i,j}$ as in Theorem~\ref{thm.chio}.

We start with a computation:

The definition of a determinant yields
\begin{align}
& \nonumber \det\left(  \left(  a_{i,j}a_{n,n}-a_{i,n}a_{n,j}\right)  _{1\leq i\leq
n-1,\ 1\leq j\leq n-1}\right) \\
& \nonumber = \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \left(a_{i,\sigma(i)}a_{n,n}-a_{i,n}a_{n,\sigma(i)}\right) \\
& \nonumber = \sum_{\sigma \in S_{n-1}} (-1)^\sigma \sum_{(p_1, p_2, \ldots, p_{n-1}) \in \{0,1\}^{n-1}} \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} \\
& \nonumber \qquad \qquad \left(\begin{array}{c} \text{since every } \sigma \in S_n \text{ satisfies } \\
\prod_{i=1}^{n-1} \left(a_{i,\sigma(i)}a_{n,n}-a_{i,n}a_{n,\sigma(i)}\right) = \sum_{(p_1, p_2, \ldots, p_{n-1}) \in \{0,1\}^{n-1}} \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} \end{array} \right) \\
& = \sum_{(p_1, p_2, \ldots, p_{n-1}) \in \{0,1\}^{n-1}} \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases}.
\label{eq.det1}
\end{align}

We shall need three further notations:
\begin{itemize}
\item For any $p = \left(p_1, p_2, \ldots, p_{n-1}\right) \in \left\{0,1\right\}^{n-1}$, set $\left|p\right| = p_1 + p_2 + \cdots + p_{n-1} \in \NN$. (Here and further below, $\NN$ means the set $\left\{0,1,2,\ldots\right\}$.)
\item We set $\left[m\right]=\left\{1,2,\ldots,m\right\}$ for every $m \in \mathbb{N}$.
\item For every $k \in \left[n\right]$, we set $T_{n,k} = \left\{\tau \in S_n \mid \tau\left(k\right) = n\right\}$. It is clear that the sets $T_{n,1}, T_{n,2}, \ldots, T_{n,n}$ are pairwise disjoint, and their union is $S_n$.
\end{itemize}

Now, we state a lemma:

\begin{lemma} \label{lem.p}
Let $p = \left(p_1, p_2, \ldots, p_{n-1}\right) \in \left\{0,1\right\}^{n-1}$.

\begin{enumerate}
\item[\textbf{(a)}] If $\left|p\right| = 0$, then
\[
\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases}
= a_{n,n}^{n-2} \sum_{\tau \in T_{n,n}} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)} .
\]

\item[\textbf{(b)}] If $\left|p\right| = 1$, then $p = \left(0, 0, \ldots, 0, 1, 0, 0, \ldots, 0\right)$ with the $1$ being at position $k$ for some $k \in \left[n-1\right]$. This $k$ further satisfies
\[
\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases}
= a_{n,n}^{n-2} \sum_{\tau \in T_{n,k}} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)} .
\]

\item[\textbf{(c)}] If $\left|p\right| > 1$, then
\[
\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} = 0 .
\]

\end{enumerate}
\end{lemma}

We shall prove Lemma~\ref{lem.p} further below; let us first see how we can derive Theorem~\ref{thm.chio} from it:

\begin{proof}[Proof of Theorem~\ref{thm.chio} using Lemma~\ref{lem.p}.]

Among all the $\left(n-1\right)$-tuples $p = \left(p_1, p_2, \ldots, p_{n-1}\right) \in \left\{0,1\right\}^{n-1}$, exactly one satisfies $\left|p\right| = 0$ (namely, $p = \left(0,0,\ldots,0\right)$), and exactly $n-1$ satisfy $\left|p\right| = 1$ (namely, the $\left(n-1\right)$-tuples $p = \left(0, 0, \ldots, 0, 1, 0, 0, \ldots, 0\right)$, with the $1$ being at position $k$ for some $k \in \left[n-1\right]$); all other $\left(n-1\right)$-tuples $p$ satisfy $\left|p\right| > 1$. Using this observation, and using Lemma~\ref{lem.p}, we may simplify the right hand side of (\ref{eq.det1}) as follows:
\begin{align*}
& \sum_{(p_1, p_2, \ldots, p_{n-1}) \in \{0,1\}^{n-1}} \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} \\
& = a_{n,n}^{n-2} \sum_{\tau \in T_{n,n}} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)} + \sum_{k=1}^{n-1} a_{n,n}^{n-2} \sum_{\tau \in T_{n,k}} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)} \\
& = \sum_{k=1}^n a_{n,n}^{n-2} \sum_{\tau \in T_{n,k} } \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)}
= a_{n,n}^{n-2} \sum_{k=1}^n \sum_{\tau \in T_{n,k} } \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)}.
\end{align*}
Since $T_{n,1},T_{n,2}, \ldots, T_{n,n}$ are pairwise disjoint and their union is $S_n$, this reduces to
\[
a_{n,n}^{n-2} \sum_{\tau \in S_n} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)}
 =a_{n,n}^{n-2}\cdot\det\left(  \left( a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}\right) .
\]
Thus, (\ref{eq.det1}) becomes
\[
\det\left(  \left(  a_{i,j}a_{n,n}-a_{i,n}a_{n,j}\right)  _{1\leq i\leq
n-1,\ 1\leq j\leq n-1}\right)
= a_{n,n}^{n-2}\cdot\det\left(  \left( a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}\right) .
\]
Hence, Theorem~\ref{thm.chio} is proven.
\end{proof}

It remains to prove Lemma \ref{lem.p}.

Before we do so, we shall introduce one further notation. Namely, for any $\sigma \in S_{n-1}$, we let $\widehat{\sigma}$ be the permutation of $[n]$ defined by
\[
\widehat{\sigma}(i) = \begin{cases} \sigma(i), & \text{if } i<n;\\ n, & \text{if } i=n \end{cases} \qquad \qquad \text{for every } i\in\{1,2,\ldots,n \}.
\]
It is well-known that the map $S_{n-1} \to T_{n,n}, \  \sigma \mapsto \widehat{\sigma}$ is well-defined (i.e., we have $\widehat{\sigma} \in T_{n,n}$ for every $\sigma \in S_{n-1}$) and a bijection.\footnote{See \cite[proof of Lemma 6.44]{detnotes} (where this map has been denoted by $\Phi$, and where $T_{n,n}$ has been denoted by $T$) for a proof.} Furthermore, it is well-known\footnote{See, for example, \cite[Section 6.6, (395)]{detnotes}.} that
\begin{align}
\left(-1\right)^{\widehat{\sigma}} = \left(-1\right)^{\sigma} \qquad \qquad \text{for every } \sigma \in S_n .
\label{eq.widehat.sign}
\end{align}

\begin{proof}[Proof of Lemma \ref{lem.p}.]
\textbf{(a)} Assume that $|p| = 0$. In other words, $p_1+p_2+\cdots +p_{n-1}=0$. Since $(p_1,p_2,\ldots,p_{n-1})\in \{0,1\}^{n-1}$, this yields $p_1=p_2=\cdots=p_{n-1}=0$.

Now,
\begin{align*}
& \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} \\
& =\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \left( a_{i,\sigma(i)}a_{n,n} \right)
\qquad \qquad \left(\text{since } p_i = 0 \right) \\
& = a_{n,n}^{n-1}\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1}  a_{i,\sigma(i)}
= a_{n,n}^{n-2} a_{n,n} \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1}  a_{i,\sigma(i)} \\
& = a_{n,n}^{n-2} \sum_{\sigma \in S_{n-1}} (-1)^\sigma a_{n,n} \prod_{i=1}^{n-1}  a_{i,\sigma(i)}
= a_{n,n}^{n-2} \sum_{\sigma \in S_{n-1}} (-1)^{\widehat{\sigma}} \prod_{i=1}^{n}  a_{i,\widehat{\sigma}(i)} \\
& \qquad \qquad \left(\begin{array}{c}
\text{since the definition of } \widehat{\sigma} \text{ shows that } 
a_{n,n} \prod_{i=1}^{n-1} a_{i,\sigma(i)} = \prod_{i=1}^{n}  a_{i,\widehat{\sigma}(i)}, \\
\text{and since (\ref{eq.widehat.sign}) shows that } 
\left(-1\right)^{\sigma} = \left(-1\right)^{\widehat{\sigma}}
\text{ for every } \sigma \in S_{n-1}
\end{array}\right) \\
& = a_{n,n}^{n-2} \sum_{\tau \in T_{n,n}} \left(-1\right)^\tau \prod_{i=1}^n a_{i,\tau\left(i\right)}
\end{align*}
(here, we have substituted $\tau$ for $\widehat{\sigma}$, since the map $S_{n-1} \to T_{n,n}, \  \sigma \mapsto \widehat{\sigma}$ is a bijection).
This proves Lemma \ref{lem.p} \textbf{(a)}.

\textbf{(b)} Assume that $|p| = 1$. In other words, $p_1+p_2+\cdots +p_{n-1}=1$. Since $(p_1,p_2,\ldots,p_{n-1})\in \{0,1\}^{n-1}$, this yields that exactly one of the $p_i$'s must be equal to $1$. In other words, $p_k = 1$ for a unique $k \in \left\{1,2,\ldots,n-1\right\}$. Consider this $k$.

Then we have
\begin{align}
& \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} \nonumber \\
& =\sum_{\sigma \in S_{n-1}} (-1)^\sigma (-a_{k,n}a_{n,\sigma(k)})\prod_{i\in [n-1]\setminus \{k\}} \left(a_{i,\sigma(i)}a_{n,n}\right) \nonumber \\
& = a_{n,n}^{n-2}\sum_{\sigma \in S_{n-1}} (-1)^\sigma (-a_{k,n}a_{n,\sigma(k)})\prod_{i\in [n-1]\setminus \{k\}}  a_{i,\sigma(i)} .
\label{pf.lem.p.b.1}
\end{align}

Now, let $t_{n,k} \in S_n$ be the transposition which switches $n$ with $k$ while leaving all other elements of $\left\{1,2,\ldots,n\right\}$ unchanged. Since $t_{n,k}$ is a transposition, we have $\left(-1\right)^{t_{n,k}} = -1$. Furthermore, it is easy to see that the map $T_{n,n} \to T_{n,k}, \  \tau \mapsto \tau \circ t_{n,k}$ is well-defined and a bijection\footnote{Its inverse is the map $T_{n,k} \to T_{n,n}, \  \tau \mapsto \tau \circ t_{n,k}$.}.

But recall that the map $S_{n-1} \to T_{n,n}, \  \sigma \mapsto \widehat{\sigma}$ is a bijection. Composing this bijection with the bijection $T_{n,n} \to T_{n,k}, \  \tau \mapsto \tau \circ t_{n,k}$, we obtain a bijection $S_{n-1} \to T_{n,k}, \  \sigma \mapsto \widehat{\sigma} \circ t_{n,k}$. This bijection satisfies
\begin{align}
\left(-1\right)^{\widehat{\sigma} \circ t_{n,k}}
= \underbrace{\left(-1\right)^{\widehat{\sigma}}}_{=\left(-1\right)^{\sigma}} \cdot \underbrace{\left(-1\right)^{t_{n,k}}}_{=-1}
&= - \left(-1\right)^{\sigma} \qquad \qquad \text{for every } \sigma \in S_{n-1} .
\label{eq.widehat-t.sign}
\end{align}
Moreover, for any $\sigma \in S_{n-1}$, it is easy to see that $\left(\widehat{\sigma} \circ t_{n,k}\right)\left(i\right) = \begin{cases} \sigma(i), & \text{if } i\not\in \left\{ k,n \right\}; \\ n, & \text{if }i = k; \\ \sigma(k), & \text{if }i=n \end{cases} $ for all $i \in [n]$. Thus, for any $\sigma \in S_{n-1}$, we have
\begin{align}
a_{k,n}a_{n,\sigma(k)}\prod_{i\in [n-1]\setminus \{k\}} a_{i,\sigma(i)}
&= \prod_{i=1}^{n} a_{i,\left(\widehat{\sigma} \circ t_{n,k}\right)(i)}.
\label{eq.widehat-t.prod}
\end{align}

Now, (\ref{pf.lem.p.b.1}) becomes
\begin{align*}
& \sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases}\\
& = a_{n,n}^{n-2}\sum_{\sigma \in S_{n-1}} (-1)^\sigma (-a_{k,n}a_{n,\sigma(k)})\prod_{i\in [n-1]\setminus \{k\}}  a_{i,\sigma(i)} \\
& = a_{n,n}^{n-2}\sum_{\sigma \in S_{n-1}} \underbrace{\left(-\left(-1\right)^\sigma\right)}_{\substack{= \left(-1\right)^{\widehat{\sigma} \circ t_{n,k}} \\ \text{(by (\ref{eq.widehat-t.sign}))}}} \underbrace{ a_{k,n}a_{n,\sigma(k)}\prod_{i\in [n-1]\setminus \{k\}}  a_{i,\sigma(i)}}_{\substack{= \prod_{i=1}^{n} a_{i,\left(\widehat{\sigma} \circ t_{n,k}\right)(i)} \\ \text{(by (\ref{eq.widehat-t.prod}))}}} \\
& = a_{n,n}^{n-2}\sum_{\sigma \in S_{n-1}} \left(-1\right)^{\widehat{\sigma} \circ t_{n,k}} \prod_{i=1}^{n} a_{i,\left(\widehat{\sigma} \circ t_{n,k}\right)(i)}
= a_{n,n}^{n-2} \sum_{\tau \in T_{n,k}} (-1)^\tau \prod_{i=1}^{n} a_{i,\tau(i)}
\end{align*}
(here, we have substituted $\tau$ for $\widehat{\sigma} \circ t_{n,k}$ in the sum, since the map $S_{n-1} \to T_{n,k}, \ \sigma \mapsto \widehat{\sigma} \circ t_{n,k}$ is a bijection).
This proves Lemma \ref{lem.p} \textbf{(b)}.

\textbf{(c)} Assume that $|p|>1$. In other words, $p_1+p_2+\cdots + p_{n-1}>1$. Thus there exist two distinct elements $u$ and $v$ of $\left[n-1\right]$ such that $p_u=p_v=1$ (since $\left(p_1,p_2,\ldots,p_{n-1}\right)\in\left\{0,1\right\}^{n-1}$). We choose such $u$ and $v$.

We now consider the sum
\begin{equation}
\sum_{\sigma \in S_{n-1}} (-1)^\sigma \prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases}
\label{pf.lem.p.c.sum}
\end{equation}
To show that this sum is equal to $0$, we use the following claim.

\begin{quote}
\emph{Claim 1:} For each $\sigma \in S_{n-1}$, we have
\begin{equation}
\prod_{i=1}^{n-1} \begin{cases} a_{i,\sigma(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,\sigma(i)}, & \text{if }p_i = 1 \end{cases} = \prod_{i=1}^{n-1} \begin{cases} a_{i,(\sigma \circ t_{u,v})(i)}a_{n,n}, & \text{if } p_i = 0; \\ -a_{i,n}a_{n,(\sigma \circ t_{u,v})(i)}, & \text{if }p_i = 1 \end{cases}
.
\label{pf.lem.p.c.claim1}
\end{equation}
\end{quote}

\emph{Proof of Claim 1:} Let $\sigma \in S_{n-1}$. We must prove the equation (\ref{pf.lem.p.c.claim1}).
We note that the products on the left and the right hand sides of this equation are identical for each factor except for the $u^\text{th}$ factor and the $v^\text{th}$ factor (because for any $i \in \left[n-1\right] \setminus \left\{u, v\right\}$, we have $(\sigma \circ t_{u,v})(i) = \sigma\left( \underbrace{t_{u,v}\left(i\right)}_{=i} \right) = \sigma\left(i\right)$). Thus it remains to show that
\[
(-a_{u,n}a_{n,\sigma(u)})(-a_{v,n}a_{n,\sigma(v)}) = (-a_{u,n}a_{n,(\sigma \circ t_{u,v})(u)})(-a_{v,n}a_{n,(\sigma \circ t_{u,v})(v)})
\]
(here we are using the fact that $p_u = p_v = 1$). But this follows from $(\sigma \circ t_{u,v})(u) = \sigma(v)$ and $(\sigma \circ t_{u,v})(v) = \sigma(u)$. Hence, Claim 1 is proven. \hfill $\blacksquare$

Let
\[
A_{n-1}=\left\{  \sigma\in S_{n-1}\ \mid\ \left(  -1\right)  ^{\sigma
}=1\right\}
\]
and
\[
C_{n-1}=\left\{  \sigma\in S_{n-1}\ \mid\ \left(  -1\right)  ^{\sigma
}=-1\right\}  .
\]
The sets $A_{n-1}$ and $C_{n-1}$ are disjoint, and satisfy $A_{n-1}\cup
C_{n-1}=S_{n-1}$. Furthermore, every $\sigma\in A_{n-1}$ satisfies $\left(
-1\right)  ^{\sigma\circ t_{u,v}}=\underbrace{\left(  -1\right)  ^{\sigma}
}_{\substack{=1\\\text{(since }\sigma\in A_{n-1}\text{)}}}\cdot
\underbrace{\left(  -1\right)  ^{t_{u,v}}}_{=-1}=-1$ and thus $\sigma\circ
t_{u,v}\in C_{n-1}$. Hence, the map $A_{n-1}\rightarrow C_{n-1},\ \sigma
\mapsto\sigma\circ t_{u,v}$ is well-defined. It is easy to see that this map
is also a bijection\footnote{Its inverse is the map $C_{n-1}\rightarrow
A_{n-1},\ \sigma\mapsto\sigma\circ t_{u,v}$.}. Now,
\begin{align*}
& \sum_{\sigma\in S_{n-1}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
\\
& =\sum_{\sigma\in A_{n-1}}\underbrace{\left(  -1\right)  ^{\sigma}
}_{\substack{=1\\\text{(since }\sigma\in A_{n-1}\text{)}}}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
\\
& \qquad\qquad+\sum_{\sigma\in C_{n-1}}\underbrace{\left(  -1\right)
^{\sigma}}_{\substack{=-1\\\text{(since }\sigma\in C_{n-1}\text{)}}
}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
\\
& =\sum_{\sigma\in A_{n-1}}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
-\sum_{\sigma\in C_{n-1}}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
\\
& =\sum_{\sigma\in A_{n-1}}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,\sigma(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,\sigma(i)}, & \text{if }p_{i}=1
\end{cases}
-\sum_{\sigma\in A_{n-1}}\prod_{i=1}^{n-1}
\begin{cases}
a_{i,(\sigma\circ t_{u,v})(i)}a_{n,n}, & \text{if }p_{i}=0;\\
-a_{i,n}a_{n,(\sigma\circ t_{u,v})(i)}, & \text{if }p_{i}=1
\end{cases}
\end{align*}
(here, we have substituted $\sigma\circ t_{u,v}$ for $\sigma$ in the second
sum, since the map $A_{n-1}\rightarrow C_{n-1},\ \sigma\mapsto\sigma\circ
t_{u,v}$ is a bijection). But Claim 1 shows that the two sums on the right
hand side of this equation are equal to each other term by term, and thus the
right hand side is $0$. Therefore, so is the left hand side.

This proves Lemma \ref{lem.p} \textbf{(c)} and completes the proof of Theorem \ref{thm.chio}.
\end{proof}

\section*{Acknowledgments}
We would like to thank the MIT PRIMES Program for providing us with the opportunity to participate in this reading group. We would also like to thank our mentor, Darij Grinberg, for his helpful guidance and instruction over the course of this year, and whose ideas provided the basis of this paper. 

\begin{thebibliography}{99999999}                                                                                         %


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

\bibitem[Conrad09]{Conrad-UP1}Keith Conrad, \textit{Universal Identities}, 12 October 2009.\newline
\url{http://www.math.uconn.edu/~kconrad/blurbs/linmultialg/univid.pdf}

\end{thebibliography}

\end{document}