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$:

• $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$

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$