Covering the zeros of 0/1 matrix with submatrices

Question

The matrices I am dealing with are $n\times n$ of the following type (with $n=7$):

$M_7=\begin{pmatrix}1&0&0&0&0&0&1 \\ 1&1&0&0&0&0&0 \\ 0&1&1&0&0&0&0 \\ 0&0&1&1&0&0&0 \\ 0&0&0&1&1&0&0 \\ 0&0&0&0&1&1&0 \\ 0&0&0&0&0&1&1\end{pmatrix}$.

$M_n$ only has $1$'s on the main diagonal, on the diagonal just below the main diagonal and on the most upper right entry (that is, the entry (1,n)).

I define submatrices of $M_n$ with two subsets representing the rows and columns. For example the submatrix of $M_7$ defined by $r_1=\{1,2\}$ and $c_1=\{1,3,7\}$ is $\begin{pmatrix}1&0&1 \\ 1&0&0\end{pmatrix}$.

My problem is the following: I want to cover only the zeros of $M_n$ with as few submatrices as possible. The submatrices do not have to be disjoint.

Obviously, there is always an easy solution with $n$ submatrices. For $M_7$, this solution is:

• $r_1=\{1\}$ and $c_1=\{2,3,4,5,6\}$
• $r_2=\{2\}$ and $c_2=\{3,4,5,6,7\}$
• $r_3=\{3\}$ and $c_3=\{1,4,5,6,7\}$
• $r_4=\{4\}$ and $c_4=\{1,2,5,6,7\}$
• $r_5=\{5\}$ and $c_5=\{1,2,3,6,7\}$
• $r_6=\{6\}$ and $c_6=\{1,2,3,4,7\}$
• $r_7=\{7\}$ and $c_7=\{1,2,3,4,5\}$

But can we cover $M_n$ with less submatrices? I suppose the problem is difficult so I am looking for any help. For example, if we have the cover for a matrix $M_n$, can we use the submatrices to cover $M_{n+1}$?

Thank you in advance for any advice!

EDIT: I found a solution with 6 submatrices for the example $M_7$:

• $r_1=\{5,6,7\}$ and $c_1=\{1,2,3\}$
• $r_2=\{1,2\}$ and $c_2=\{3,4,5,6\}$
• $r_3=\{3,4,5\}$ and $c_3=\{1,6,7\}$
• $r_4=\{1,4\}$ and $c_4=\{2,5\}$
• $r_5=\{2,6\}$ and $c_5=\{4,7\}$
• $r_6=\{3,7\}$ and $c_6=\{4,5\}$

EDIT II For the matrix $M_{15}$, there is a solution with 7 submatrices:

• $r_1=\{1,2,7,10,15\}$ and $c_1=\{3,4,5,8,11,12,13\}$
• $r_2=\{1,2,3,6,12,13\}$ and $c_2=\{4,7,8,9,10,14\}$
• $r_3=\{1,4,5,11,14,15\}$ and $c_3=\{2,6,7,8,9,12\}$
• $r_4=\{2,3,4,9,10,11,12\}$ and $c_4=\{5,6,7,13,14,15\}$
• $r_5=\{3,4,5,6,7,8,9\}$ and $c_5=\{1,10,11,12,13,14,15\}$
• $r_6=\{5,6,7,8,13,14,15\}$ and $c_6=\{1,2,3,9,10,11\}$
• $r_7=\{8,9,10,11,12,13,14\}$ and $c_7=\{1,2,3,4,5,6,15\}$

Answer 1

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).$

Answer 2

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$