Fooling-sets and rank

Fooling-sets and rank

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

Full description

Saved in:
Bibliographic Details
Main Authors: Friesen, Mirjam, Hamed, Aya, Lee, Troy, Oliver Theis, Dirk
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2015
Subjects:
DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
Online Access:https://hdl.handle.net/10356/107304
http://hdl.handle.net/10220/25431
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.

Similar Items