The (minimum) rank of typical fooling-set matrices

A fooling-set matrix is a square matrix with nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at least $\sqrt n$, for a matrix of order $n$. We ask for the typical minimum rank of a fooling-set matrix: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field $\FF$ closer to its lower bound $\sqrt{n}$ or to its upper bound $n$? We study random patterns with a given density $p$, and prove an $\Omega(n)$ bound for the cases when (a) $p$ tends to $0$ quickly enough; (b) $p$ tends to $0$ slowly, and $\abs{\FF}=O(1)$; (c) $p\in\lt]0,1\rt]$ is a constant. We leave open the case when $p\to 0$ slowly and $\FF$ is a large (e.g., $\FF=\GF(2^n)$, $\FF=\RR$).

Article

Download

View The (minimum) rank of typical fooling-set matrices