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.
Download