\documentstyle[art10,amssymbols]{article} % Comment out to choose single or ``double'' space \renewcommand{\baselinestretch}{1.1}\small\normalsize %\renewcommand{\baselinestretch}{1.4}\small\normalsize %\setlength{\textwidth}{6.3in} %\setlength{\textheight}{8.8in} \setlength{\textwidth}{6.7in} \setlength{\textheight}{9.5in} \setlength{\oddsidemargin}{0.0 in} \setlength{\evensidemargin}{0.0 in} \setlength{\topmargin}{-0.3in} %\setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \flushbottom \newtheorem{theorem} {Theorem}[section]% \newtheorem{lemma} [theorem]{Lemma} % \newtheorem{proposition}[theorem]{Proposition} % \newtheorem{corollary} [theorem]{Corollary} % \newtheorem{claim} [theorem]{Claim} % \newtheorem{conjecture} [theorem]{Conjecture} % \newtheorem{problem} [theorem]{Problem} % \newtheorem{remark} [theorem]{Remark} % \newtheorem{note} [theorem]{Note} % \newtheorem{algorithm} [theorem]{Algorithm} % \newtheorem{example} [theorem]{Example} % \newtheorem{observation}[theorem]{Observation} % \newtheorem{numbered} [theorem]{\hspace{3em}} % \newtheorem{defn} [theorem]{\sc Definition} % % % Put those little boxes at the end of proofs and proofless theorems. % \newenvironment{proof}{\noindent{\sc Proof.}}{\hspace*{\fill}\raisebox{-.2ex}{$\Box$}\vspace{2ex}\par} %\newcommand{\noproof}{\vspace{-\baselineskip}\hspace*{\fill}\raisebox{1.8ex}{$\Box$}\vspace{2ex}\par}% \newcommand{\noproof}{\vspace{-\baselineskip}\vspace{-1.3ex}\hspace*{\fill}{$\Box$}\vspace{2ex}\par}% \date{Sept. 21, 1995} % Here are my macros \newcommand{\RR}{\ifx\Bbb\undefined{\mbox{\boldmath$\cal R$}}\else{\Bbb R}\fi} \newcommand{\bs}{\backslash} \newcommand{\se}{\subseteq} \newcommand{\set}[2]{\{#1 \colon #2\}} % the set of #1 such that #2 % stacks #1 over #2 for with curly left brace \newcommand{\case}[2]{{\left\{\begin{array}{ll} #1\\#2 \end{array}\right.}} % stacks {#1 if \mbox {#2}} over {#1 if \mbox{#2}} for with curly left brace \newcommand{\scase}[4]{{\left\{\begin{array}{ll} #1 & \mbox{if #2}\\#3 \mbox{if #4} \end{array}\right.}} \newfont{\fraktur}{eufm10} %\newcommand{\es}{\varnothing} \newcommand{\es}{\emptyset} \renewcommand{\phi}{\varphi} \newcommand{\drop}{\smallsetminus} \newcommand{\goesto}{\rightarrow} \newcommand{\cl}{\complement} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\aij}{(a_{ij})} \newcommand{\si}{\sigma} \newcommand{\sign}{\mbox{\rm sign}} \thispagestyle{empty} \begin{document} \begin{center} {\bf Solution to Problem 10470 proposed by D. Knuth in \\ the American Math. Monthly, 102 no.\ 7 (1995) p.\ 655\\ \it Luis Goddyn, Dept.\ of Mathematics and Statistics,\\ Simon Fraser University, Burnaby, BC, Canada V5A 1S6\\ {\tt goddyn@sfu.ca}\\ Sept 21, 1995 } \end{center} \noindent {\bf Answer to part~(a).} Let $\aij$ be an $n$ by $n$ matrix and let $M$ be the set of permutations $\si$ of $[n] := \{1,2,\ldots,n\}$ such that $\prod_{i=1}^n a_{i,\si(i)} \ne 0$. Let $\si \in M$, and suppose that $\si$ has exactly $z(\si)$ orbits on $[n]$. %Let $Z$ be one of these orbits. If $\aij$ is a special matrix, then for each orbit $Z$ of $\si$, the multiset $\{a_{i,\si(i)} : i \in Z\}$ contains exactly one $1$, with the remaining entries being $-1$. Thus $\prod_{i=1}^n a_{i,\si(i)} = (-1)^{n - z(\si)} = \sign(\si)$ and we have the following. %Thus the determinant expansion gives the following. \be\label{one} \mbox{\it For any special matrix $\aij,\; \det \aij = \sum_{\si \in M} \sign(\si) \prod_{i=1}^n a_{i,\si(i)} = %\sum_{\si \in M} \sign(\si) (-1)^{n-z(\si)} = |M|$.} \ee %Let $\aij$ be an $n$ by $n$ matrix. A subset $S \se [n]$ is called a {\it barrier} of $\aij$ if $|N(S)| < |S|$ where %For $S \se [n]$ we define $N(S) := \{j\in [n] : \exists i \in S, a_{ij} \ne 0\}.$ %Such a subset $S$ is called a {\it barrier} of $\aij$ if %$|N(S)| < |S|$. Phillip Hall's theorem (On representatives of subsets. {\it J.\ London Math.\ Soc.\ }{\bf 10} (1935) 26--30) asserts the following. \begin{center} {\it For any matrix $\aij$, $|M| = 0$ if and only if $\aij$ has a barrier.} \end{center} %From this and (\ref{one}) we have the following. %\be\label{three} %\parbox{5.5in}{\it A special matrix $\aij$ is minimal if and only if %it has a barrier, %but changing any entry $a_{ij}$ with $i \ge j$ from $0$ to $1$ %results in a matrix with no barriers.} %\ee With this and (\ref{one}) we have shown that a special matrix $\aij$ is minimal if and only if it has a barrier, but changing any entry $a_{ij}$ with $i \ge j$ from $0$ to $1$ results in a matrix with no barriers. Let $\aij$ be a special $n$ by $n$ matrix, and let $S \se [n]$. Because of the $-1$ entries in $\aij$ we have $\{ i+1: i \in S - \{n\} \} \se N(S)$ whence $|N(S)| \ge |S|-1$. If $S$ is a barrier, then this inequality is tight and we have the following. \be\label{two} \mbox{\it Every barrier $S$ of an $n$ by $n$ special matrix contains $n$ and satisfies $N(S) = \{j : j-1 \in S - \{n\}\}$.} \ee Let $\aij$ be a minimal matrix and let $S$ be a barrier of $\aij$ having minimum cardinality. Suppose there is an entry $a_{ij} =0$ such that $j \le i$. If either $i \not\in S$ or $j \in N(S)$, then $S$ is also a barrier of the special matrix obtained by changing $a_{ij}$ to $1$, contradicting the minimality of $\aij$. It follows that $S$ is the unique barrier of $\aij$ and, by~(\ref{two}), the entries of $\aij$ are completely determined by $S$ as follows. \be\label{three} a_{ij} = \left\{\begin{array}{rl} %1 & \mbox{if $j\le i$ and $i \not\in S$} \\ %1 & \mbox{if $j\le i$ and $j-1 \in S$} \\ 1 & \mbox{if $j\le i$ and either $i \not\in S$ or $j-1 \in S$} \\ -1 & \mbox{if $j=i+1$} \\ 0 & \mbox{otherwise.} \end{array}\right. \ee As (\ref{three}) defines an $n$ by $n$ minimal matrix for any subset $S \se [n]$ with $n\in S$, there are exactly~$2^{n-1}$ such matrices. \vspace{1ex} \noindent {\bf Answer to part~(b).} Let $S = \{s_1,s_2,\ldots,s_k\} \se [n]$ where $s_1 < s_2 < \cdots < s_k = n$, let $T = [n]-S$, and let $\aij$ be the minimal matrix determined by $S$ as above. Each $1$ which appears in $\aij$ has one of two types: \begin{description} \item[\it type-$T$\rm : ] $a_{ij}=1$ where $i \in T$ and $1 \le j \le i$. \item[\it type-$S$\rm : ] $a_{ij}=1$ where $i \in S$, $j-1 \in S$ and $j\le i$. \end{description} The number of type-$T$ entries in~$\aij$ is $\sum T$. %= {{n+1} \choose 2} - \sum S$. %To calculate the number of type-$S$ ones in $\aij$, We count the type-$S$ entries %in $\aij$ by summing over the columns in $\{j: j-1 \in S\}$; for any $r \in \{1,2,\ldots,k-1\}$, there are exactly $k-r$ type-$S$ entries $a_{ij}$ with $j = s_r + 1$, namely those with $i \in S \cap \{j, j+1,\ldots,n\} = \{ s_{r+1}, s_{r+2}, \ldots, s_k\}$. In total there are $\sum_{r=1}^{k-1} (k-r) = {{|S|} \choose 2}$ %Summing over $r=1,2,\ldots k$, there are %$(k-1)+(k-2)+\cdots +1 = {{|S|} \choose 2}$ type-$S$ entries in $\aij$. The number of zeros appearing on or below the diagonal in $\aij$ is calculated ${{n+1}\choose{2}} - \sum T - {{|S|} \choose 2} = \sum S - {{|S|} \choose 2} = \sum_{r=1}^k (s_r-r+1)$. For a fixed $k$, this sum is maximized when $S = \{ n-k+1, n-k+2, \ldots,n\}$ whence the sum equals $k(n-k+1)$. This expression attains the maximum value $\lfloor (n+1)^2/4 \rfloor$ when $k$ is an integer closest to $(n+1)/2$. %This is maximized when $k$ is a nearest integer to $(n+1)/2$, %whence the sum is $\lfloor (n+1)^2/4 \rfloor$. Including the zeros above the diagonal, we have that the maximum number of zeros in an $n$ by $n$ minimal matrix is $$\lfloor (n+1)^2/4\rfloor + {{n-1}\choose 2} = \lfloor (3n^2-4n+5)/4\rfloor = n^2 - \lceil (n+5)(n-1)/4\rceil.$$ \hfill $\Box$ \end{document}