\documentclass
[numbers=enddot,12pt,final,onecolumn,notitlepage,english]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, December 02, 2023 21:09:18}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Problem}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newtheorem{aufg}[exer]{Problem}
\newenvironment{aufgabe}[1][]
{\begin{aufg}[#1]\begin{leftbar}}
{\end{leftbar}\end{aufg}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{aufgabe}[1][Aufgabe]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{84th Putnam contest 2023 problem B6}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{84th Putnam contest 2023 problem B6 with solution}
\author{Darij Grinberg}
\date{\today}
\maketitle

\subsection{Problem B6}

The following is Problem B6 on the 84th Putnam contest 2023 in the form I
proposed it (which is slightly easier than what made it on the contest,
because the answer is provided).

\begin{exercise}
\label{exe.put2023b6}Let $m$ be a positive integer. Let $n$ be either $2m$ or
$2m-1$.

Let $A$ be the $n\times n$-matrix $\left(  a_{i,j}\right)  _{1\leq i\leq
n,\ 1\leq j\leq n}$, where $a_{i,j}$ is the number of all pairs $\left(
x,y\right)  $ of nonnegative integers satisfying $xi+yj=n$.

Prove that $\det A=\left(  -1\right)  ^{m-1}\cdot2m$.

(For instance, for $m=3$ and $n=5$, we have $A=\left(
\begin{array}
[c]{rrrrr}%
6 & 3 & 2 & 2 & 2\\
3 & 0 & 1 & 0 & 1\\
2 & 1 & 0 & 0 & 1\\
2 & 0 & 0 & 0 & 1\\
2 & 1 & 1 & 1 & 2
\end{array}
\right)  $.)
\end{exercise}

\begin{remark}
This is likely connected to gcd-matrices and M\"{o}bius inversion.
\end{remark}

\begin{proof}
[Solution to Problem \ref{exe.put2023b6}.]By assumption, $n$ is
either $2m$ or $2m-1$. Hence, $m$ is either $n/2$ or $\left(  n+1\right)  /2$.
Thus, it easily follows that $0\leq m\leq n$ and $m-1<n/2$.

We shall use the \emph{Iverson bracket notation}: If $\mathcal{A}$ is a
logical statement, then $\left[  \mathcal{A}\right]  $ shall mean $%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true;}\\
0, & \text{if }\mathcal{A}\text{ is false.}%
\end{cases}
$

We set $\left[  n\right]  :=\left\{  1,2,\ldots,n\right\}  $ and $\left[
0,n\right]  :=\left\{  0,1,\ldots,n\right\}  $.

If $M$ is any matrix, then we will use the notation $M_{i,j}$ for the entry of
$M$ in the $i$-th row and the $j$-th column. Thus, in particular, the entries
of our matrix $A$ are $A_{i,j}=a_{i,j}$ for all $i,j\in\left[  n\right]  $.

We shall consider $n\times\left(  n+1\right)  $-matrices whose rows are
indexed by $1,2,\ldots,n$ and whose columns are indexed by $0,1,\ldots,n$.
Likewise, we shall consider $\left(  n+1\right)  \times n$-matrices whose rows
are indexed by $0,1,\ldots,n$ and whose columns are indexed by $1,2,\ldots,n$.

If $M$ is an $n\times\left(  n+1\right)  $-matrix, and $j\in\left[
0,n\right]  $, then $M^{\sim j}$ shall denote the $n\times n$-matrix obtained
from $M$ by removing the $j$-th column. Likewise, if $N$ is an $\left(
n+1\right)  \times n$-matrix, and $i\in\left[  0,n\right]  $, then $N_{\sim
i}$ shall denote the $n\times n$-matrix obtained from $N$ by removing the
$i$-th column. The Cauchy--Binet formula (or, more precisely, a particular
case thereof) says that if $M$ is an $n\times\left(  n+1\right)  $-matrix and
$N$ is an $\left(  n+1\right)  \times n$-matrix, then%
\begin{equation}
\det\left(  MN\right)  =\sum_{k=0}^{n}\det\left(  M^{\sim k}\right)  \cdot
\det\left(  N_{\sim k}\right)  .\label{sol.put2023b6.cb}%
\end{equation}


Now, let $M$ be the $n\times\left(  n+1\right)  $-matrix $\left(  \left[
i\mid j\right]  \right)  _{i\in\left[  n\right]  ,\ j\in\left[  0,n\right]  }$
(so that its $\left(  i,j\right)  $-entry is $1$ if $i\mid j$ and $0$
otherwise). Let $N$ be the $\left(  n+1\right)  \times n$-matrix $\left(
\left[  j\mid n-i\right]  \right)  _{i\in\left[  0,n\right]  ,\ j\in\left[
n\right]  }$. For example, for $n=8$, we have
\[
M=\left(
\begin{array}
[c]{cccccccccc}
& j=0 & j=1 & j=2 & j=3 & j=4 & j=5 & j=6 & j=7 & j=8\\
i=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
i=2 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
i=3 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\
i=4 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\
i=5 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
i=6 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
i=7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
i=8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{array}
\right)
\]
and%
\[
N=\left(
\begin{array}
[c]{ccccccccc}
& j=1 & j=2 & j=3 & j=4 & j=5 & j=6 & j=7 & j=8\\
i=0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\
i=1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
i=2 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0\\
i=3 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
i=4 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\
i=5 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
i=6 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
i=7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
i=8 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{array}
\right)  ..
\]


Now, it is easy to see that
\begin{equation}
A=MN.\label{sol.put2023b6.A=MN}%
\end{equation}
(Indeed, for each $i,j\in\left[  n\right]  $, we have%
\begin{align*}
\left(  MN\right)  _{i,j} &  =\sum_{k=0}^{n}M_{i,k}N_{k,j}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of matrix multiplication}%
\right)  \\
&  =\sum_{k=0}^{n}\underbrace{\left[  i\mid k\right]  \left[  j\mid
n-k\right]  }_{=\left[  i\mid k\text{ and }j\mid n-k\right]  }%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definitions of }M\text{ and
}N\right)  \\
&  =\sum_{k=0}^{n}\left[  i\mid k\text{ and }j\mid n-k\right]  \\
&  =\left(  \text{number of }k\in\left[  0,n\right]  \text{ satisfying }i\mid
k\text{ and }j\mid n-k\right)  \\
&  =\left(  \text{number of pairs }\left(  x,y\right)  \text{ of nonnegative
integers satisfying }xi+yj=n\right)  \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by a simple bijection, explained in}\\
\text{the footnote following this computation}%
\end{array}
\right)  \\
&  =a_{i,j}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }%
a_{i,j}\right)  \\
&  =A_{i,j}.
\end{align*}
\footnote{Let me justify the equality%
\begin{align*}
&  \left(  \text{number of }k\in\left[  0,n\right]  \text{ satisfying }i\mid
k\text{ and }j\mid n-k\right)  \\
&  =\left(  \text{number of pairs }\left(  x,y\right)  \text{ of nonnegative
integers satisfying }xi+yj=n\right)
\end{align*}
that was used above. Clearly, it suffices to find a bijection%
\begin{align*}
\text{from the set }\mathfrak{A} &  :=\left\{  k\in\left[  0,n\right]  \text{
satisfying }i\mid k\text{ and }j\mid n-k\right\}  \\
\text{to the set }\mathfrak{B} &  :=\left\{  \text{pairs }\left(  x,y\right)
\text{ of nonnegative integers satisfying }xi+yj=n\right\}  .
\end{align*}
We can construct such a bijection as follows:
\par
\begin{itemize}
\item For each $k\in\mathfrak{A}$, we have $\left(  k/i,\ \left(  n-k\right)
/j\right)  \in\mathfrak{B}$ (since $k\in\mathfrak{A}$ entails $k\in\left[
0,n\right]  $ and $i\mid k$ and $j\mid n-k$ and therefore $k/i\in\mathbb{N}$
and $\left(  n-k\right)  /j\in\mathbb{N}$, and of course we have $\left(
k/i\right)  i+\left(  \left(  n-k\right)  /j\right)  j=k+\left(  n-k\right)
=n$). Thus, we can define a map%
\begin{align*}
\phi:\mathfrak{A} &  \rightarrow\mathfrak{B},\\
k &  \mapsto\left(  k/i,\ \left(  n-k\right)  /j\right)  .
\end{align*}
\par
\item For each $\left(  x,y\right)  \in\mathfrak{B}$, we have $xi\in
\mathfrak{A}$ (in fact, $\left(  x,y\right)  \in\mathfrak{B}$ entails
$x,y\in\mathbb{N}$ and $xi+yj=n$; now we clearly have $i\mid xi$ and $j\mid
yj=\underbrace{xi+yj}_{=n}-\,xi=n-xi$ and finally $xi\in\left[  0,n\right]  $
(since $xi\geq0$ and $xi\leq xi+yj=n$); but these three facts combined yield
$xi\in\mathfrak{A}$). Thus, we can define a map%
\begin{align*}
\psi:\mathfrak{B} &  \rightarrow\mathfrak{A},\\
\left(  x,y\right)   &  \mapsto xi.
\end{align*}
\par
\item The maps $\phi$ and $\psi$ are easily seen to be mutually inverse
(indeed, $\psi\circ\phi=\operatorname*{id}$ is obvious; and $\phi\circ
\psi=\operatorname*{id}$ can be proved as follows: if $\left(  x,y\right)
\in\mathfrak{B}$, then $xi+yj=n$ and thus $n-xi=yj$, so that $\phi\left(
\psi\left(  \left(  x,y\right)  \right)  \right)  =\phi\left(  xi\right)
=\left(  xi/i,\ \underbrace{\left(  n-xi\right)  }_{=yj}/j\right)  =\left(
xi/i,\ yj/j\right)  =\left(  x,y\right)  $, so that $\phi\circ\psi
=\operatorname*{id}$ is proved). Thus, $\phi:\mathfrak{A}\rightarrow
\mathfrak{B}$ is a bijection. This is exactly the bijection we need.
\end{itemize}
} Thus, $MN=A$, so that $A=MN$.)

Now, from (\ref{sol.put2023b6.A=MN}), we obtain%
\begin{equation}
\det A=\det\left(  MN\right)  =\sum_{k=0}^{n}\det\left(  M^{\sim k}\right)
\cdot\det\left(  N_{\sim k}\right)  \label{sol.put2023b6.detA=sum}%
\end{equation}
(by (\ref{sol.put2023b6.cb})). It remains to manage the right hand side. We
will need several claims:

\begin{statement}
\textit{Claim 1:} Let $k\in\left[  0,n\right]  $ satisfy $k>\dfrac{n}{2}$.
Then,
\[
\det\left(  M^{\sim k}\right)  =\left(  -1\right)  ^{k+1}.
\]

\end{statement}

\begin{proof}
[Proof of Claim 1.]We have $k>\dfrac{n}{2}$, so that $2k>n$. Hence, the only
multiples of $k$ in the set $\left[  0,n\right]  $ are $0$ and $k$. In other
words, we have $\left[  k\mid j\right]  =0$ for all $j\in\left[  0,n\right]  $
other than $0$ and $k$, whereas $\left[  k\mid j\right]  =1$ holds for $j=0$
and for $j=k$.

Thus, the $k$-th row of the matrix $M$ has only two entries distinct from $0$:
namely, a $1$ in the $0$-st column, and a $1$ in the $k$-th column.
Therefore\textsl{, }the $k$-th row of the matrix $M^{\sim k}$ is $\left(
1,0,0,\ldots,0\right)  $ (since the $1$ in the $k$-th column disappears when
we remove this column). Expanding $\det\left(  M^{\sim k}\right)  $ along this
row, we thus obtain $\det\left(  M^{\sim k}\right)  =\left(  -1\right)
^{k+1}\cdot\det Q$, where $Q$ is the result of removing the $0$-th column and
the $k$-th row from $M^{\sim k}$. But it is easy to see that the matrix $Q$ is
upper-triangular with its diagonal entries all being equal to $1$ (since
$\left[  i\mid j\right]  =0$ if $i>j$, and since $\left[  i\mid j\right]  =1$
if $i=j$). Therefore, its determinant is $\det Q=1$. Thus, $\det\left(
M^{\sim k}\right)  =\left(  -1\right)  ^{k+1}\cdot\underbrace{\det Q}%
_{=1}=\left(  -1\right)  ^{k+1}$. This proves Claim 1.
\end{proof}

\begin{statement}
\textit{Claim 2:} Assume that $n=2m$. Then,%
\[
\det\left(  M^{\sim\left(  n/2\right)  }\right)  =0.
\]

\end{statement}

\begin{proof}
[Proof of Claim 2.]From $n=2m$, we see that $n$ is even. Thus, $n/2\in\left[
n\right]  $ (since $n/2=m>0$), so that the matrix $M$ has an $\left(
n/2\right)  $-th row. Moreover, this $\left(  n/2\right)  $-th row is not the
$n$-th row (since $n=2m>0$ and thus $n/2<n$).

Now, it is easy to see that the $\left(  n/2\right)  $-th row and the $n$-th
row of $M$ agree in all their entries except for the ones in the $\left(
n/2\right)  $-th column (since any $j\in\left[  0,n\right]  $ satisfies
$\left[  n/2\mid j\right]  =%
\begin{cases}
1, & \text{if }j\in\left\{  0,n/2,n\right\}  ;\\
0, & \text{otherwise}%
\end{cases}
$ and $\left[  n\mid j\right]  =%
\begin{cases}
1, & \text{if }j\in\left\{  0,n\right\}  ;\\
0, & \text{otherwise,}%
\end{cases}
$\ \ and these two values disagree only for $j=n/2$). Since the $\left(
n/2\right)  $-th column is removed in $M^{\sim\left(  n/2\right)  }$, this
entails that the $\left(  n/2\right)  $-th row and the $n$-th row of the
matrix $M^{\sim\left(  n/2\right)  }$ completely agree. Hence, the matrix
$M^{\sim\left(  n/2\right)  }$ has two equal rows, and therefore its
determinant is $0$. In other words, $\det\left(  M^{\sim\left(  n/2\right)
}\right)  =0$. This proves Claim 2.
\end{proof}

\begin{statement}
\textit{Claim 3:} Let $k\in\left[  0,n\right]  $. Then, $\det\left(  N_{\sim
k}\right)  =\left(  -1\right)  ^{n\left(  n-1\right)  /2}\cdot\det\left(
M^{\sim\left(  n-k\right)  }\right)  $.
\end{statement}

\begin{proof}
[Proof of Claim 3.]From $M=\left(  \left[  i\mid j\right]  \right)
_{i\in\left[  n\right]  ,\ j\in\left[  0,n\right]  }$, we see that the
transpose $M^{T}$ of the matrix $M$ is given by $M^{T}=\left(  \left[  j\mid
i\right]  \right)  _{i\in\left[  0,n\right]  ,\ j\in\left[  n\right]  }$.
Comparing this with $N=\left(  \left[  j\mid n-i\right]  \right)
_{i\in\left[  0,n\right]  ,\ j\in\left[  n\right]  }$, we observe that the
matrix $N$ can be obtained from the matrix $M^{T}$ by reversing the order of
the rows, i.e., by permuting the rows using the permutation
\begin{align*}
\left[  0,n\right]   &  \rightarrow\left[  0,n\right]  ,\\
i &  \mapsto n-i.
\end{align*}
Hence, the matrix $N_{\sim k}$ is obtained from the matrix $\left(
M^{T}\right)  _{\sim\left(  n-k\right)  }$ in the exact same way (i.e., by
reversing the order of the rows). Therefore,%
\[
\det\left(  N_{\sim k}\right)  =\left(  -1\right)  ^{\sigma}\cdot\det\left(
\left(  M^{T}\right)  _{\sim\left(  n-k\right)  }\right)  ,
\]
where $\sigma$ is a permutation of an $n$-element set that reverses the order
of its elements. Basic combinatorics shows that the sign $\left(  -1\right)
^{\sigma}$ of this latter permutation equals $\left(  -1\right)  ^{\sigma
}=\left(  -1\right)  ^{n\left(  n-1\right)  /2}$ (for example, because this
permutations has $n\left(  n-1\right)  /2$ inversions). Thus, we obtain%
\begin{align*}
\det\left(  N_{\sim k}\right)   &  =\underbrace{\left(  -1\right)  ^{\sigma}%
}_{=\left(  -1\right)  ^{n\left(  n-1\right)  /2}}\cdot\det\left(
\underbrace{\left(  M^{T}\right)  _{\sim\left(  n-k\right)  }}_{=\left(
M^{\sim\left(  n-k\right)  }\right)  ^{T}}\right)  \\
&  =\left(  -1\right)  ^{n\left(  n-1\right)  /2}\cdot\underbrace{\det\left(
\left(  M^{\sim\left(  n-k\right)  }\right)  ^{T}\right)  }_{\substack{=\det
\left(  M^{\sim\left(  n-k\right)  }\right)  \\\text{(since }\det\left(
U^{T}\right)  =\det U\\\text{for any matrix }U\text{)}}}=\left(  -1\right)
^{n\left(  n-1\right)  /2}\cdot\det\left(  M^{\sim\left(  n-k\right)
}\right)  .
\end{align*}
This proves Claim 3.
\end{proof}

\begin{statement}
\textit{Claim 4:} We have%
\[
\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  =m.
\]

\end{statement}

\begin{proof}
[Proof of Claim 4.]Let $M^{\prime}$ be the $\left(  n+1\right)  \times\left(
n+1\right)  $-matrix obtained from $M$ by attaching an extra row $\left(
1,1,\ldots,1\right)  $ at the very top of the matrix. Then, the topmost two
rows of the matrix $M^{\prime}$ are equal (since the top row of $M$ already is
$\left(  1,1,\ldots,1\right)  $), so that $\det\left(  M^{\prime}\right)  =0$.
On the other hand, expanding the determinant of $M^{\prime}$ along the topmost
row, we obtain%
\begin{align}
\det\left(  M^{\prime}\right)   &  =\sum_{k=0}^{n}\left(  -1\right)
^{k}1\cdot\det\left(  M^{\sim k}\right)  =\sum_{k=0}^{n}\left(  -1\right)
^{k}\det\left(  M^{\sim k}\right)  \nonumber\\
&  =\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)
+\sum_{k=m}^{n}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)
\label{sol.put2023b6.c4.pf.1}%
\end{align}
(since $0\leq m\leq n$). However, it is not hard to see that%
\begin{equation}
\sum_{k=m}^{n}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)
=-m,\label{sol.put2023b6.c4.pf.2}%
\end{equation}
for example by distinguishing between two cases:

\begin{itemize}
\item If $n=2m$, then $m=n/2$ and thus%
\begin{align*}
& \sum_{k=m}^{n}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  \\
& =\sum_{k=n/2}^{n}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  \\
& =\left(  -1\right)  ^{n/2}\underbrace{\det\left(  M^{\sim\left(  n/2\right)
}\right)  }_{\substack{=0\\\text{(by Claim 2)}}}+\sum_{k=n/2+1}^{n}\left(
-1\right)  ^{k}\underbrace{\det\left(  M^{\sim k}\right)  }%
_{\substack{=\left(  -1\right)  ^{k+1}\\\text{(by Claim 1)}}}\\
& =\underbrace{\left(  -1\right)  ^{n/2}0}_{=0}+\sum_{k=n/2+1}^{n}%
\underbrace{\left(  -1\right)  ^{k}\left(  -1\right)  ^{k+1}}_{=-1}%
=\sum_{k=n/2+1}^{n}\left(  -1\right)  =\left(  n-n/2\right)  \left(
-1\right)  \\
& =-n/2=-m\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m=n/2\right)  .
\end{align*}


\item If $n\neq2m$, then $n=2m-1$ (since $n$ is either $2m$ or $2m-1$) and
thus $m=\left(  n+1\right)  /2$ and therefore%
\begin{align*}
& \sum_{k=m}^{n}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  \\
& =\sum_{k=\left(  n+1\right)  /2}^{n}\left(  -1\right)  ^{k}\underbrace{\det
\left(  M^{\sim k}\right)  }_{\substack{=\left(  -1\right)  ^{k+1}\\\text{(by
Claim 1,}\\\text{since }k\geq\left(  n+1\right)  /2>n/2\text{)}}}\\
& =\sum_{k=\left(  n+1\right)  /2}^{n}\underbrace{\left(  -1\right)
^{k}\left(  -1\right)  ^{k+1}}_{=-1}=\left(  n-\left(  n+1\right)
/2+1\right)  \left(  -1\right)  \\
& =-\left(  n+1\right)  /2=-m\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}m=\left(  n+1\right)  /2\right)  .
\end{align*}

\end{itemize}

In either case, we have proved (\ref{sol.put2023b6.c4.pf.2}). Now,
(\ref{sol.put2023b6.c4.pf.1}) becomes
\begin{align*}
\det\left(  M^{\prime}\right)   &  =\sum_{k=0}^{m-1}\left(  -1\right)
^{k}\det\left(  M^{\sim k}\right)  +\underbrace{\sum_{k=m}^{n}\left(
-1\right)  ^{k}\det\left(  M^{\sim k}\right)  }_{\substack{=-m\\\text{(by
(\ref{sol.put2023b6.c4.pf.2}))}}}\\
&  =\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  -m.
\end{align*}
Hence,%
\[
\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)
-m=\det\left(  M^{\prime}\right)  =0,
\]
so that%
\[
\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\det\left(  M^{\sim k}\right)  =m.
\]
This proves Claim 4.
\end{proof}

Now, (\ref{sol.put2023b6.detA=sum}) becomes%
\begin{align}
\det A &  =\sum_{k=0}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(
N_{\sim k}\right)  \nonumber\\
&  =\sum_{k=0}^{m-1}\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim
k}\right)  +\sum_{k=m}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(
N_{\sim k}\right)  \label{sol.put2023b6.detA=sum2}%
\end{align}
(since $0\leq m\leq n$). However, it is easy to see that%
\begin{equation}
\sum_{k=m}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim
k}\right)  =\sum_{k=n-m+1}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(
N_{\sim k}\right)  ,\label{sol.put2023b6.n-m+14}%
\end{equation}
for instance by distinguishing between two cases:

\begin{itemize}
\item If $n=2m$, then $m=n/2$ and thus%
\begin{align*}
& \sum_{k=m}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim
k}\right)  \\
& =\sum_{k=n/2}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim
k}\right)  \\
& =\underbrace{\det\left(  M^{\sim\left(  n/2\right)  }\right)  }%
_{\substack{=0\\\text{(by Claim 2)}}}\cdot\,\det\left(  N_{\sim\left(
n/2\right)  }\right)  +\sum_{k=n/2+1}^{n}\det\left(  M^{\sim k}\right)
\cdot\det\left(  N_{\sim k}\right)  \\
& =\sum_{k=n/2+1}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim
k}\right)  =\sum_{k=n-m+1}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(
N_{\sim k}\right)
\end{align*}
(since $n/2=n-m$ (because $n-\underbrace{m}_{=n/2}=n-n/2=n/2$)), so that
(\ref{sol.put2023b6.n-m+14}) holds.

\item If $n\neq2m$, then $n=2m-1$ (since $n$ is either $2m$ or $2m-1$) and
thus $m=n-m+1$, so that (\ref{sol.put2023b6.n-m+14}) holds tautologically
(since the summation bounds on both sides are equal).
\end{itemize}

In either case, we have proved (\ref{sol.put2023b6.n-m+14}). Now,
(\ref{sol.put2023b6.detA=sum2}) becomes%
\begin{align*}
\det A &  =\sum_{k=0}^{m-1}\det\left(  M^{\sim k}\right)  \cdot\det\left(
N_{\sim k}\right)  +\underbrace{\sum_{k=m}^{n}\det\left(  M^{\sim k}\right)
\cdot\det\left(  N_{\sim k}\right)  }_{\substack{=\sum_{k=n-m+1}^{n}%
\det\left(  M^{\sim k}\right)  \cdot\det\left(  N_{\sim k}\right)  \\\text{(by
(\ref{sol.put2023b6.n-m+14}))}}}\\
&  =\sum_{k=0}^{m-1}\det\left(  M^{\sim k}\right)  \cdot\underbrace{\det
\left(  N_{\sim k}\right)  }_{\substack{=\left(  -1\right)  ^{n\left(
n-1\right)  /2}\cdot\det\left(  M^{\sim\left(  n-k\right)  }\right)
\\\text{(by Claim 3)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\sum_{k=n-m+1}^{n}\det\left(  M^{\sim k}\right)
\cdot\underbrace{\det\left(  N_{\sim k}\right)  }_{\substack{=\left(
-1\right)  ^{n\left(  n-1\right)  /2}\cdot\det\left(  M^{\sim\left(
n-k\right)  }\right)  \\\text{(by Claim 3)}}}\\
&  =\left(  -1\right)  ^{n\left(  n-1\right)  /2}\sum_{k=0}^{m-1}\det\left(
M^{\sim k}\right)  \cdot\det\left(  M^{\sim\left(  n-k\right)  }\right)  \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{n\left(  n-1\right)  /2}%
\sum_{k=n-m+1}^{n}\det\left(  M^{\sim k}\right)  \cdot\det\left(
M^{\sim\left(  n-k\right)  }\right)  \\
&  =\left(  -1\right)  ^{n\left(  n-1\right)  /2}\sum_{k=0}^{m-1}\det\left(
M^{\sim k}\right)  \cdot\det\left(  M^{\sim\left(  n-k\right)  }\right)  \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{n\left(  n-1\right)  /2}%
\sum_{k=0}^{m-1}\det\left(  M^{\sim\left(  n-k\right)  }\right)  \cdot
\det\left(  M^{\sim k}\right)  \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have
substituted }n-k\text{ for }k\text{ in the second sum}\right)  \\
&  =\left(  -1\right)  ^{n\left(  n-1\right)  /2}\sum_{k=0}^{m-1}\det\left(
M^{\sim k}\right)  \cdot\det\left(  M^{\sim\left(  n-k\right)  }\right)  \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  -1\right)  ^{n\left(  n-1\right)  /2}%
\sum_{k=0}^{m-1}\det\left(  M^{\sim k}\right)  \cdot\det\left(  M^{\sim\left(
n-k\right)  }\right)  \\
&  =2\cdot\left(  -1\right)  ^{n\left(  n-1\right)  /2}\sum_{k=0}^{m-1}%
\det\left(  M^{\sim k}\right)  \cdot\underbrace{\det\left(  M^{\sim\left(
n-k\right)  }\right)  }_{\substack{=\left(  -1\right)  ^{\left(  n-k\right)
+1}\\\text{(by Claim 1, applied to }n-k\text{ instead of }k\\\text{(since
}k\leq m-1<n/2\text{ and thus }n-k>n-n/2=n/2\text{))}}}\\
&  =2\cdot\left(  -1\right)  ^{n\left(  n-1\right)  /2}\sum_{k=0}^{m-1}%
\det\left(  M^{\sim k}\right)  \cdot\underbrace{\left(  -1\right)  ^{\left(
n-k\right)  +1}}_{=\left(  -1\right)  ^{n+1}\left(  -1\right)  ^{k}}%
\end{align*}%
\begin{align*}
&  =2\cdot\underbrace{\left(  -1\right)  ^{n\left(  n-1\right)  /2}\left(
-1\right)  ^{n+1}}_{\substack{=\left(  -1\right)  ^{n\left(  n-1\right)
/2+\left(  n+1\right)  }\\=\left(  -1\right)  ^{m-1}\\\text{(by easy
modulo-}2\\\text{computations)}}}\underbrace{\sum_{k=0}^{m-1}\left(
-1\right)  ^{k}\det\left(  M^{\sim k}\right)  }_{\substack{=m\\\text{(by Claim
4)}}}\\
&  =2\cdot\left(  -1\right)  ^{m-1}\cdot m=\left(  -1\right)  ^{m-1}\cdot2m.
\end{align*}
This solves the problem.
\end{proof}


\end{document}