Fooling-sets and rank

Abstract: An

n i m e s n

matrix

M

is called a extit{fooling-set matrix of size

n

} if its diagonal entries are nonzero and

M_{k, e l l} M_{e l l, k} = 0

for every

k e e l l

. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that

n l e (m b o x r k M)^{2}

, regardless of over which field the rank is computed, and asked whether the exponent on

m b o x r k M

can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size

. In nonzero characteristic, we construct an infinite family of matrices with

n = (1 + o (1)) (m b o x r k M)^{2}

.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Fooling-sets and rank