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\}$



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


