2013/05/02 by Mirjam Friesen, Friesen, Mirjam, Dirk Oliver Theis +1
Mathematics · #05C70 #15B34 #15B35 #68Q15 #94A05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C70 #msc:15B34 #msc:15B35 #msc:68Q15 #msc:94A05
paper · pdf · doi:10.48550/arxiv.1305.2468
This is an extended abstract; the full paper is arXiv:1208.2920
arxiv created 2013/05/02 · arxiv updated 2013/05/14
An n× n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k≠ ℓ we have Mk,ℓ Mℓ,k = 0. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n ≤ (\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.