Covering the zeros of 0/1 matrix with submatrices

Divide-and-conquer works. It takes $O(\log n)$ submatrices to partition the $0$s. So, for large $n$, it takes fewer than $n$ submatrices.

Let $M'_n$ be the same as $M_n$ except with a $0$ in position $(1,n)$. Let $f(n)$ be the minimum number of submatrices required to cover $M'_n$. It takes at most $f(n)+2$ submatrices to cover the $0$s of $M_{n+1}$ since removing the first row and last column of $M_{n+1}$ produces $M'_n$ transposed.

Claim: $f(2n+1) \le f(n)+4$.

Proof: Use two submatrices to cover the top right quadrant $\{1,..,n\} \times \{n+2,...,2n+1\}$ and the bottom left quadrant $\{n+2,...,2n+1\} \times \{1,...,n\}$, then two more to cover the central row $\{n+1\} \times *$ and the central column $* \times \{n+1\}$.

The remainder is two copies of $M'_n$ that can be covered in parallel. If $S \subset \{1,...,n\}$ then let $S^+$ be $S \cup \{s+n+1|s\in S\}$. If $\{R_i \times C_i\}$ covers $M'_n$ then $\{R_i^+ \times C_i^+\}$ covers the $0$s in the top left and bottom right quadrants of $M'_{2n+1}$.

---

Since $f$ is nondecreasing, $f(2n) \le f(n)+4$, and $f(2^n) \le 4n$.

---

There is also a logarithmic lower bound. Let $I_n$ be the $n\times n$ identity matrix. Let $g(n)$ be the size of the minimal cover of the $0$s of $I_n$. Covering the zeros of $M_n$ also covers the zeros of any submatrix, including $\{1,3,5,...\} \times \{1,3,5,...\} = I_{\lceil n/2 \rceil}$ so $f(n) \ge g(\lceil n/2 \rceil)$.

Suppose you have a cover of the $0$s of $I_n$. Any submatrix is of the form $R \times C$ with $R$ and $C$ disjoint, so at least one of $R$ and $C$ has size at most $n/2$. Without loss of generality, let that be $C$. The other submatrices cover the size $n-\#C$ identity submatrix $(\{1,...,n\}\setminus C) \times (\{1,...,n\}\setminus C).$ So, $g(n) \ge 1+g(n-\#C) \ge 1+g(n/2).$ This implies $g(2^n) \ge n, f(2^n) \ge n-1.$ This means there is a logarithmic lower bound on the number of submatrices needed to cover the $0$s of $M_n$.

So, $f(n) = \Theta(\log n).$

Here is another proof that the number of submatrices needed to cover the zeros of $M_n$ is at least $O(log(n))$. Let $f(n)$ denotes the optimal number.

The argument uses the fact that the patterns of the columns are all different. Therefore the subsets of submatrices touching each column are also all different. With $f(n)$ submatrices, the number of different possible subsets is obviously $2^{f(n)}-1$ (-1 because there are no columns full of ones). Since there are $n$ columns, we have $2^{f(n)}-1\geq n$, or $f(n)\geq \log_2(n+1)$.

However, these arguments do not give the exact value of $f(n)$. Here are the best values I obtain for$3\leq n \leq 17$. I would be interested if anyone has an idea of what the following sequence is?

• $f(3)=3$
• $f(4)=4$
• $f(5)=5$
• $f(6)=5$
• $f(7)=6$
• $f(8)=6$
• $f(9)=6$
• $f(10)=7$
• $f(11)=7$
• $f(12)=7$
• $f(13)=7$
• $f(14)=7$
• $f(15)=7$
• $f(16)=7$
• $f(17)=7$