Fooling sets and rank

An $n\times n$ matrix $M$ is called a $\mathit{\text{fooling-set}}\mathit{\text{matrix}}\mathit{\text{of}}\mathit{\text{size}}n$ if its diagonal entries are nonzero and $M_{k,\mathrm{\ell }}{M}_{\mathrm{\ell },k}=0$ for every $k\mathrm{\ne }\mathrm{\ell }$. Dietzfelbinger, Hromkovi{\v{c}}, and Schnitger (1996) showed that $n\le (rkM{)}^2$, regardless of over which field the rank is computed, and asked whether the exponent on $rkM$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = \binom{\mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n=(1+o(1))(rkM{)}^2$.