\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{}
%TCIDATA{}
%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