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...
| Κύριοι συγγραφείς: | , , , |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Journal Article |
| Γλώσσα: | English |
| Έκδοση: |
2015
|
| Θέματα: | |
| Διαθέσιμο Online: | https://hdl.handle.net/10356/107304 http://hdl.handle.net/10220/25431 |
| Περίληψη: | 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. |
|---|