An ntimes n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k e ell we have M_{k,ell} M_{ell,k} = 0. Dietzfelbinger, Hromkoviv{c}, and Schnitger (1996) showed that n le (rk M)^2, regardless of
over which field the rank is computed, and asked whether the exponent on rk M can be improved. We settle this question for nonzero characteristic by constructing a family of matrices for which the bound is asymptotically tight. The construction uses linear recurring sequences.
An $ntimes n$ matrix $M$ is called a textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,ell} M_{ell,k} = 0$ for every $k e ell$. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that $n le (mbox{rk} M)^2$,
regardless of over which field the rank is computed, and asked whether the exponent on $mbox{rk} M$ 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))(mbox{rk} M)^2$.
