The rank of a matrix has been used a number of times to prove lower
bounds on various types of complexity. In particular it has been used
for the size of monotone formulas and monotone span programs. In most
cases that this approach was used, there is not a single matrix
associated with the function in question, but one has to minimize the
rank over a set of matrices (eg., \cite{razborov,gal}). Usually, this
makes the techniques very difficult to apply. In this note we define a
certain combinatorial structure that enables us to use the rank lower
bound directly. We shall not prove new lower bound, we only show that
some previous lower bounds on monotone span programs can be simply
derived using this structure. It is open whether our approach can
produce better lower bounds.
The following open problem was stated in ECCC TR02-007
(Pavel Pudlak: Monotone complexity and the rank of matrices).
Let A be a family of subsets of [n], and B be a family
of k-tuples of subsets of [n], such that for each subset
a in A and each k-tuple in B, the subset a has a nonempty
intersection with exactly one member of the k-tuple.
Associate with the sets A and B a matrix specifying the
location of the intersection for each (subset, k-tuple) pair.
The question was, is it possible that the rank of the
associated matrix is larger than n^O(logn) for some sets A,B.
We show that the answer to this question is no.
