Fooling-sets and rank
Oliver Theis, Dirk
Date of Issue2015
School of Physical and Mathematical Sciences
An n x n matrixM is called a fooling-set matrix of size n if its diagonal entries are nonzero and Mk,l; Ml,k = 0 for every k ≠ l. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n ≤ (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 = (rkM+1 2). In nonzero characteristic, we construct an infinite family of matrices with n = (1+o(1))(rkM)2.
European journal of combinatorics
© 2015 Elsevier Ltd. This is the author created version of a work that has been peer reviewed and accepted for publication by European Journal of Combinatorics, Elsevier Ltd. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [Article DOI: http://dx.doi.org/10.1016/j.ejc.2015.02.016].