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

biclique covering numberwill turn up a lot of useful links. $\endgroup$ – Tony Huynh Jan 8 '16 at 2:08