\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{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=Friday, March 30, 2018 20:45:40}
%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
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\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]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newtheorem{exetwo}[exera]{Additional exercise}
\newenvironment{addexercise}[1][]
{\begin{exetwo}[#1]\begin{leftbar}}
{\end{leftbar}\end{exetwo}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\ihead{An exercise on determinant-like sums}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{An exercise on determinant-like sums}
\author{Darij Grinberg}
\date{
%TCIMACRO{\TeXButton{today}{\today}}%
%BeginExpansion
\today
%EndExpansion
}
\maketitle

The following exercise is inspired by Gabriel Dospinescu's \cite[Exercise
12.9]{AndDos}:

\begin{exercise}
\label{exe.powerdet}Let $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $. Let
$n\in\mathbb{N}$ and $r\in\mathbb{N}$ with $r>0$. The \textit{sum} of a matrix
shall mean the sum of its entries. If $A$ is any matrix and $i$ and $j$ are
two positive integers, then the $\left(  i,j\right)  $-th entry of $A$ will be
denoted by $A_{i,j}$. Let $S_{n}$ denote the set of all permutations of
$\left\{  1,2,\ldots,n\right\}  $. If $\sigma\in S_{n}$ is a permutation, then
$\left(  -1\right)  ^{\sigma}$ shall denote the sign of $\sigma$.

Let $m$ be the minimum sum of an $r\times n$-matrix $M\in\mathbb{N}^{r\times
n}$ that has no two equal columns. (Explicitly, $m$ can be computed as
follows: Let $s$ be the smallest nonnegative integer satisfying $\sum
_{t=0}^{s-1}\dbinom{r+t-1}{t}\leq n$, and write $n$ in the form $n=\sum
_{t=0}^{s-1}\dbinom{r+t-1}{t}+w$. Then, $m=\sum_{t=0}^{s-1}t\dbinom{r+t-1}%
{t}+sw$.)

\textbf{(a)} Let $A\in\mathbb{K}^{n\times n}$ be an $n\times n$-matrix of rank
$\leq r$ over a field $\mathbb{K}$. Prove that%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{k}=0
\]
for each $k\in\left\{  0,1,\ldots,m-1\right\}  $.

\textbf{(b)} Let $\mathbb{K}$ be a field of characteristic $0$. Prove that $m$
is the smallest $k\in\mathbb{N}$ such that there exists an $n\times n$-matrix
$A\in\mathbb{K}^{n\times n}$ of rank $\leq r$ satisfying%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{k}\neq0.
\]

\end{exercise}

\begin{remark}
The \textquotedblleft characteristic $0$\textquotedblright\ condition in
Exercise \ref{exe.powerdet} \textbf{(b)} is important; if $\mathbb{K}$ has
positive characteristic, then the smallest $k$ can be larger than $m$.
\end{remark}

\begin{remark}
Exercise \ref{exe.powerdet} can be significantly shortened if we restrict
ourselves to the case of fields of characteristic $0$. In fact, in this case,
part \textbf{(a)} can be removed, as its claim is contained in part
\textbf{(b)}. We can shorten the exercise further if we let the reader figure
out the value of $m$, i.e., if we pose it as follows:

\textquotedblleft Let $n$ and $r$ be integers with $n\geq0$ and $r>0$. Let
$\mathbb{K}$ be a field of characteristic $0$. Let $S_{n}$ denote the set of
all permutations of $\left\{  1,2,\ldots,n\right\}  $. If $\sigma\in S_{n}$ is
a permutation, then $\left(  -1\right)  ^{\sigma}$ shall denote the sign of
$\sigma$. Find the smallest integer $k\geq0$ such that there exists an
$n\times n$-matrix $\left(  A_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq
n}\in\mathbb{K}^{n\times n}$ of rank $\leq r$ satisfying%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{k}\neq0.
\]
\textquotedblright
\end{remark}

\begin{remark}
The case $r=n$ of Exercise \ref{exe.powerdet} is contained in \cite[Exercise
6.54]{Grinbe15}, whereas the case $r=1$ of Exercise \ref{exe.powerdet} is
contained in \cite[Exercise 6.55]{Grinbe15} (since an $n\times m$-matrix of
rank $\leq1$ can always be written in the form $\left(  a_{i}b_{j}\right)
_{1\leq i\leq n,\ 1\leq j\leq m}$ for some $a_{1},a_{2},\ldots,a_{n}%
\in\mathbb{K}$ and $b_{1},b_{2},\ldots,b_{m}\in\mathbb{K}$). Both of these
cases allow for explicit formulas for $\sum_{\sigma\in S_{n}}\left(
-1\right)  ^{\sigma}\left(  \sum_{i=1}^{n}A_{i,\sigma\left(  i\right)
}\right)  ^{k}$ when $k=m$; it is unclear whether such formulas exist for
other values of $r$.
\end{remark}

\begin{proof}
[Solution sketch to Exercise \ref{exe.powerdet}.]If $M\in\mathbb{N}^{r\times
n}$ is any matrix, then $\Sigma M$ shall denote the sum of $M$; in other
words, $\Sigma M=\sum_{i=1}^{n}\sum_{h=1}^{r}M_{h,i}=M_{1,1}+M_{1,2}%
+\cdots+M_{r,n}$.

Furthermore, if $M\in\mathbb{N}^{r\times n}$ is any matrix, then
$\mathbf{m}\left(  M\right)  $ shall denote the multinomial coefficient
\[
\dbinom{M_{1,1}+M_{1,2}+\cdots+M_{r,n}}{M_{1,1},M_{1,2},\ldots,M_{r,n}}%
=\dfrac{\left(  \sum_{i=1}^{n}\sum_{h=1}^{r}M_{h,i}\right)  !}{\prod_{i=1}%
^{n}\prod_{h=1}^{r}M_{h,i}!}\in\mathbb{N}.
\]


The multinomial formula shows that any $r\times n$-matrix $D\in\mathbb{K}%
^{r\times n}$ satisfies%
\begin{equation}
\left(  \sum_{i=1}^{n}\sum_{h=1}^{r}D_{h,i}\right)  ^{k}=\sum_{\substack{M\in
\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(  M\right)  \prod
_{i=1}^{n}\prod_{h=1}^{r}D_{h,i}^{M_{h,i}}. \label{sol.powerdet.multinom}%
\end{equation}


\textbf{(a)} Let $k\in\mathbb{N}$ be arbitrary.

The matrix $A$ has rank $\leq r$. Hence, it can be written in the form $A=BC$
for some $n\times r$-matrix $B\in\mathbb{K}^{n\times r}$ and some $r\times
n$-matrix $C\in\mathbb{K}^{r\times n}$\ \ \ \ \footnote{This is a well-known
fact from linear algebra: see
\url{https://en.wikipedia.org/wiki/Rank_factorization} .}. The equality $A=BC$
leads to%
\begin{equation}
A_{i,j}=\sum_{h=1}^{r}B_{i,h}C_{h,j} \label{sol.powerdet.a.a=bc}%
\end{equation}
for each $\left(  i,j\right)  \in\left\{  1,2,\ldots,n\right\}  ^{2}$. Hence,%
\begin{align}
&  \sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}\underbrace{A_{i,\sigma\left(  i\right)  }}_{\substack{=\sum_{h=1}%
^{r}B_{i,h}C_{h,\sigma\left(  i\right)  }\\\text{(by
(\ref{sol.powerdet.a.a=bc}))}}}\right)  ^{k}\nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\underbrace{\left(
\sum_{i=1}^{n}\sum_{h=1}^{r}B_{i,h}C_{h,\sigma\left(  i\right)  }\right)
^{k}}_{\substack{=\sum_{\substack{M\in\mathbb{N}^{r\times n};\\\Sigma
M=k}}\mathbf{m}\left(  M\right)  \prod_{i=1}^{n}\prod_{h=1}^{r}\left(
B_{i,h}C_{h,\sigma\left(  i\right)  }\right)  ^{M_{h,i}}\\\text{(by
(\ref{sol.powerdet.multinom}), applied to the }r\times n\text{-matrix }%
D\in\mathbb{K}^{r\times n}\\\text{defined by }D_{h,i}=B_{i,h}C_{h,\sigma
\left(  i\right)  }\text{)}}}\nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\sum_{\substack{M\in
\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(  M\right)
\underbrace{\prod_{i=1}^{n}\prod_{h=1}^{r}\left(  B_{i,h}C_{h,\sigma\left(
i\right)  }\right)  ^{M_{h,i}}}_{=\left(  \prod_{i=1}^{n}\prod_{h=1}%
^{r}B_{i,h}^{M_{h,i}}\right)  \left(  \prod_{i=1}^{n}\prod_{h=1}%
^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}\right)  }\nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\sum_{\substack{M\in
\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(  M\right)  \left(
\prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)  \left(  \prod
_{i=1}^{n}\prod_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}\right)
\nonumber\\
&  =\sum_{\substack{M\in\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(
M\right)  \left(  \prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}\prod
_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}. \label{sol.powerdet.a.1}%
\end{align}


Now, for each $M\in\mathbb{N}^{r\times n}$, define an $n\times n$-matrix
$D_{M}\in\mathbb{K}^{n\times n}$ by%
\[
\left(  D_{M}\right)  _{i,j}=\prod_{h=1}^{r}C_{h,j}^{M_{h,i}}.
\]
Then, this matrix $D_{M}$ satisfies%
\begin{align}
\det\left(  D_{M}\right)   &  =\sum_{\sigma\in S_{n}}\left(  -1\right)
^{\sigma}\prod_{i=1}^{n}\underbrace{\left(  D_{M}\right)  _{i,\sigma\left(
i\right)  }}_{\substack{=\prod_{h=1}^{r}C_{h,\sigma\left(  i\right)
}^{M_{h,i}}\\\text{(by the definition of }D_{M}\text{)}}}\nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}%
\prod_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}.
\label{sol.powerdet.a.detDM=}%
\end{align}
If the matrix $M\in\mathbb{N}^{r\times n}$ has two equal columns (say, the
$p$-th and the $q$-th column of $M$ are equal), then the matrix $D_{M}$ has
two equal rows (viz., its $p$-th and its $q$-th row are equal) and thus
satisfies%
\begin{equation}
\det\left(  D_{M}\right)  =0. \label{sol.powerdet.a.2}%
\end{equation}


Now, (\ref{sol.powerdet.a.1}) becomes%
\begin{align}
&  \sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{k}\nonumber\\
&  =\sum_{\substack{M\in\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(
M\right)  \left(  \prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)
\underbrace{\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}%
^{n}\prod_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}}_{\substack{=\det
\left(  D_{M}\right)  \\\text{(by (\ref{sol.powerdet.a.detDM=}))}}}\nonumber\\
&  =\sum_{\substack{M\in\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(
M\right)  \left(  \prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)
\det\left(  D_{M}\right)  . \label{sol.powerdet.a.3}%
\end{align}


Now, assume that $k\in\left\{  0,1,\ldots,m-1\right\}  $. Then, $k<m$.

But any $r\times n$-matrix $M\in\mathbb{N}^{r\times n}$ having sum $<m$ must
have two equal columns (by the definition of $m$). Hence, any $r\times
n$-matrix $M\in\mathbb{N}^{r\times n}$ having sum $k$ must have two equal
columns (since it has sum $k<m$). Thus, any $r\times n$-matrix $M\in
\mathbb{N}^{r\times n}$ having sum $k$ must satisfy%
\[
\det\left(  D_{M}\right)  =0
\]
(by (\ref{sol.powerdet.a.2})). Now, (\ref{sol.powerdet.a.3}) becomes%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{k}=\sum_{\substack{M\in
\mathbb{N}^{r\times n};\\\Sigma M=k}}\mathbf{m}\left(  M\right)  \left(
\prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)  \underbrace{\det
\left(  D_{M}\right)  }_{\substack{=0\\\text{(by (\ref{sol.powerdet.a.3}))}%
}}=0.
\]
This solves part \textbf{(a)} of the exercise.

\textbf{(b)} Because of part \textbf{(a)}, all we need to do is to show that
there exists an $n\times n$-matrix $A\in\mathbb{K}^{n\times n}$ of rank $\leq
r$ satisfying%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{m}\neq0.
\]


In order to show this, let us assume the contrary. Thus,%
\begin{equation}
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left(  \sum_{i=1}%
^{n}A_{i,\sigma\left(  i\right)  }\right)  ^{m}=0
\label{sol.powerdet.b.bad-ass}%
\end{equation}
for each $n\times n$-matrix $A\in\mathbb{K}^{n\times n}$ of rank $\leq r$. In
particular, (\ref{sol.powerdet.b.bad-ass}) holds for each $n\times n$-matrix
$A$ of the form $A=BC$ with $B\in\mathbb{K}^{n\times r}$ being an $n\times
r$-matrix and $C\in\mathbb{K}^{r\times n}$ being an $r\times n$-matrix
(because any such matrix $A$ has rank $\leq r$). In other words, each $n\times
r$-matrix $B\in\mathbb{K}^{n\times r}$ and each $r\times n$-matrix
$C\in\mathbb{K}^{r\times n}$ satisfy%
\begin{equation}
\sum_{\substack{M\in\mathbb{N}^{r\times n};\\\Sigma M=m}}\mathbf{m}\left(
M\right)  \left(  \prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}\right)
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}\prod
_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}=0 \label{sol.powerdet.b.2}%
\end{equation}
\footnote{In fact, applying (\ref{sol.powerdet.a.1}) to $k=m$, we conclude
that the left hand side of (\ref{sol.powerdet.b.bad-ass}) equals the left hand
side of (\ref{sol.powerdet.b.2}). Thus, the equality (\ref{sol.powerdet.b.2})
follows from (\ref{sol.powerdet.b.bad-ass}).}. Hence, (\ref{sol.powerdet.b.2})
holds as a polynomial identity in the entries $B_{i,j}$ of $B$ and the entries
$C_{i,j}$ of $C$\ \ \ \ \footnote{This is because the field $\mathbb{K}$ is
infinite (since it has characteristic $0$).}. If we treat the $C_{i,j}$ as
constants (temporarily), then the left hand side of (\ref{sol.powerdet.b.2})
is a polynomial in the indeterminates $B_{i,j}$. By comparing coefficients in
(\ref{sol.powerdet.b.2}), we thus conclude that each $M\in\mathbb{N}^{r\times
n}$ satisfying $\Sigma M=m$ must satisfy%
\begin{equation}
\mathbf{m}\left(  M\right)  \sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma
}\prod_{i=1}^{n}\prod_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}=0
\label{sol.powerdet.b.3}%
\end{equation}
(because the monomials $\prod_{i=1}^{n}\prod_{h=1}^{r}B_{i,h}^{M_{h,i}}$ for
different $M\in\mathbb{N}^{r\times n}$ are distinct, and thus we can compare
coefficients in (\ref{sol.powerdet.b.2})). Since $\mathbf{m}\left(  M\right)
\neq0$, we can cancel $\mathbf{m}\left(  M\right)  $ from
(\ref{sol.powerdet.b.3}) (since $\mathbb{K}$ has characteristic $0$), and thus
obtain%
\begin{equation}
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}\prod
_{h=1}^{r}C_{h,\sigma\left(  i\right)  }^{M_{h,i}}=0. \label{sol.powerdet.b.4}%
\end{equation}
So (\ref{sol.powerdet.b.4}) is a polynomial identity in the indeterminates
$C_{i,j}$ that holds for each $M\in\mathbb{N}^{r\times n}$ satisfying $\Sigma
M=m$.

But there exists an $r\times n$-matrix $M\in\mathbb{N}^{r\times n}$ that has
no two equal columns and satisfies $\Sigma M=m$ (by the definition of $m$).
Consider this matrix $M$.

There exists a $\left(  p_{1},p_{2},\ldots,p_{r}\right)  \in\mathbb{N}^{r}$
such that the integers $\sum_{h=1}^{r}p_{h}M_{h,i}$ for $i\in\left\{
1,2,\ldots,n\right\}  $ are distinct\footnote{\textit{Proof.} Assume the
contrary. Thus, for each $\left(  p_{1},p_{2},\ldots,p_{r}\right)
\in\mathbb{N}^{r}$, there are at least two equal integers among the integers
$\sum_{h=1}^{r}p_{h}M_{h,i}$ for $i\in\left\{  1,2,\ldots,n\right\}  $. In
other words, for each $\left(  p_{1},p_{2},\ldots,p_{r}\right)  \in
\mathbb{N}^{r}$, we have%
\[
\prod_{1\leq i<j\leq n}\left(  \sum_{h=1}^{r}p_{h}M_{h,i}-\sum_{h=1}^{r}%
p_{h}M_{h,j}\right)  =0.
\]
Since $\mathbb{N}^{r}$ is Zariski-dense in the $\mathbb{Q}$-vector space
$\mathbb{Q}^{r}$, this shows that we have
\[
\prod_{1\leq i<j\leq n}\left(  \sum_{h=1}^{r}x_{h}M_{h,i}-\sum_{h=1}^{r}%
x_{h}M_{h,j}\right)  =0
\]
in the polynomial ring $\mathbb{Q}\left[  x_{1},x_{2},\ldots,x_{r}\right]  $.
Since $\mathbb{Q}\left[  x_{1},x_{2},\ldots,x_{r}\right]  $ is an integral
domain, we conclude that there exists a pair $\left(  i,j\right)  $ of
integers satisfying $1\leq i<j\leq n$ and
\begin{equation}
\sum_{h=1}^{r}x_{h}M_{h,i}-\sum_{h=1}^{r}x_{h}M_{h,j}=0.
\label{sol.powerdet.b.fn3.1}%
\end{equation}
Consider this $\left(  i,j\right)  $. From (\ref{sol.powerdet.b.fn3.1}), we
easily conclude that $M_{h,i}=M_{h,j}$ for all $h\in\left\{  1,2,\ldots
,r\right\}  $. In other words, the $i$-th column of $M$ equals the $j$-th
column of $M$. This contradicts the fact that the matrix $M$ has no two equal
columns. This contradiction completes the proof.}. Pick such a $\left(
p_{1},p_{2},\ldots,p_{r}\right)  $. For each $i\in\left\{  1,2,\ldots
,n\right\}  $, define a $q_{i}\in\mathbb{N}$ by $q_{i}=\sum_{h=1}^{r}%
p_{h}M_{h,i}$. Then, the integers $q_{1},q_{2},\ldots,q_{n}$ are distinct
(since the integers $\sum_{h=1}^{r}p_{h}M_{h,i}$ for $i\in\left\{
1,2,\ldots,n\right\}  $ are distinct).

Introduce $n$ new indeterminates $z_{1},z_{2},\ldots,z_{n}$. Substitute
$z_{j}^{p_{i}}$ for each $C_{i,j}$ in the identity (\ref{sol.powerdet.b.4}).
The result is the polynomial identity%
\[
\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}\prod
_{h=1}^{r}\left(  z_{\sigma\left(  i\right)  }^{p_{h}}\right)  ^{M_{h,i}}=0.
\]
Thus,%
\begin{equation}
0=\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}%
\underbrace{\prod_{h=1}^{r}\left(  z_{\sigma\left(  i\right)  }^{p_{h}%
}\right)  ^{M_{h,i}}}_{\substack{=z_{\sigma\left(  i\right)  }^{\sum_{h=1}%
^{r}p_{h}M_{h,i}}=z_{\sigma\left(  i\right)  }^{q_{i}}\\\text{(since }%
\sum_{h=1}^{r}p_{h}M_{h,i}=q_{i}\text{)}}}=\sum_{\sigma\in S_{n}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}z_{\sigma\left(  i\right)  }^{q_{i}}.
\label{sol.powerdet.b.6}%
\end{equation}


However, it is well-known that $\sum_{\sigma\in S_{n}}\left(  -1\right)
^{\sigma}\prod_{i=1}^{n}z_{\sigma\left(  i\right)  }^{q_{i}}\neq0$ in
$\mathbb{Q}\left[  z_{1},z_{2},\ldots,z_{n}\right]  $%
\ \ \ \ \footnote{\textit{Proof.} Recall that the integers $q_{1},q_{2}%
,\ldots,q_{n}$ are distinct. Thus, there are no cancellations in the sum
$\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}^{n}%
z_{\sigma\left(  i\right)  }^{q_{i}}$; that is, any two $\sigma\in S_{n}$ give
rise to distinct monomials. Hence, this sum is $\neq0$. Qed.}. This
contradicts (\ref{sol.powerdet.b.6}). This contradiction completes the proof.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AndDos]{AndDos}Titu Andreescu, Gabriel Dospinescu, \textit{Problems
from the Book}, XYZ Press 2008.

\bibitem[Grinbe15]{Grinbe15}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 \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .
\end{thebibliography}


\end{document}