7
$\begingroup$

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\}$
$\endgroup$
  • 1
    $\begingroup$ My guess is that some sort of divide-and-conquer gives a cover with $O(\log n)$ submatrices. What lower bounds do you have? $\endgroup$ – Douglas Zare Jan 7 '16 at 23:13
  • $\begingroup$ @DouglasZare That would be great to have such a divide-and-conquer method! I do have a lower bound, but I must admit it is quite bad. For $M_7$, if we look at the entries (1,2), (2,3), (4,7) and (7,1), none can be in the same submatrix of another, so we have at least 4 different submatrices. But even for greater $n$, I am not able to find more than 4 entries verifying this property. $\endgroup$ – user85022 Jan 7 '16 at 23:33
  • 3
    $\begingroup$ Given $M_n$, you can define a bipartite graph $G_n$ with bipartition $A$ and $B$ where $a_i$ is adjacent to $b_j$ if $M_{i,j}=0$. Your question then becomes what is the minimum number of complete bipartite subgraphs needed to partition the edges of $G_n$. You can do this for any square $0$-$1$ matrix, so if you are interested in matrices besides $M_n$, then Googling biclique covering number will turn up a lot of useful links. $\endgroup$ – Tony Huynh Jan 8 '16 at 2:08
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ great answer, I started writing this out after doing a small example but you beat me to it. $\endgroup$ – kodlu Jan 7 '16 at 23:57
  • 2
    $\begingroup$ Very nice! It helps me a lot, thanks! But I have a question which may seems stupid, but is it still possible that the optimal value is much less than $O(log(n))$? Even a constant from a certain $n$? $\endgroup$ – user85022 Jan 8 '16 at 0:33
  • $\begingroup$ I ask that question because of the solution I just found for $M_{15}$ (see EDIT II in the question). $\endgroup$ – user85022 Jan 8 '16 at 0:53
  • 5
    $\begingroup$ @user85022: I added a lower bound. $\endgroup$ – Douglas Zare Jan 8 '16 at 1:46
2
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.