<p>As can be seen in the comments, Jukka provides a $2 \times 4$ counter example, which is further generalized by Peter to $4 \times 4$ to meet the requirements. Both analysis and program verification (use dynamic programming to calculate $\chi'$) can be performed to make sure $\chi \neq \chi&#39;$ is possible when $n = 4$.</p>

<p>Actually Peter's generalization can be used to show there is an $n \times n$ matrix s.t. $\chi \neq \chi&#39;$ for any $n$. The counter example is shown below:</p>

<p>$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
\vdots \\
0 0 0 0 0 \cdots 0
\end{bmatrix}$</p>

<p>There's a unique column with two 1's. At least one continuous rectangle is needed to cover the 0's in this column. And this continuous rectangle doesn't cover any elements in the two rows corresponding to the two 1's. Remove this continuous rectangle and the rest will be a $2 \times n$ matrix:</p>

<p>$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0
\end{bmatrix}$</p>

<p>which needs at least 5 continuous rectangles to cover. So $\chi&#39; \geq 6$. However, it is easy to see $\chi \leq 5$. So $\chi \neq \chi&#39;$.</p>

CC BY-SA 3.0
2011-05-26T17:31:08.137Z
Let's not forget that the question makes little sense in terms of communication complexity. The notions of being continuous or geometrical in terms of rectangles are mostly misleading. Unless you can SHOW that these are the only interesting rectangles! Which might be true in some sense.
Hartmut Klauck
CC BY-SA 3.0
2011-05-26T22:56:04.567Z
can you accept this if it works: so that the question doesn't come up later ?
Suresh Venkat
CC BY-SA 3.0
2011-05-27T00:51:43.777Z
@ Suresh Not until 7 hours later...
Cyker
CC BY-SA 3.0
2011-05-27T00:57:17.483Z
@ Hartmut Continuous rectangles are easy to view. So in some sense they're preferred if possible, i.e., there's a row/col permutation which makes $\chi = \chi'$. Intuitively, unrestricted rectangles are much powerful than continuous ones so this might be impossible. And the answer to this question just verifies this.
Cyker
CC BY-SA 3.0
2011-05-26T09:33:19.187Z
2011-05-26T09:38:34.300Z
2011-05-26T09:38:34.300Z
Cyker
<p>This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M_{n \times n}$. A <strong>rectangle</strong> is defined as a submatrix $A \times B$ where $A \subseteq \{0,1\}^n$ and $B \subseteq \{0,1\}^n$. A rectangle is said to be <strong>monochromatic</strong> if all its elements are 0 (or all are 1). Define the minimum number of monochromatic rectangles needed to tile the whole matrix $M$ as $\chi$.</p>

<p>But the tiling defined as above might be difficult to visualize. For example, consider</p>

<p>$\begin{bmatrix}
1 0 1 0 \\
0 0 0 0 \\
1 0 1 0 \\
0 0 0 0
\end{bmatrix}$</p>

<p>At first glance it might be that $\chi$ is very large. But after permuting the second and third row/column, we have</p>

<p>$\begin{bmatrix}
1 1 0 0 \\
1 1 0 0 \\
0 0 0 0 \\
0 0 0 0
\end{bmatrix}$</p>

<p>then $\chi$ is easily seen to be 3 (since permutation doesn't change $\chi$).</p>

<p>To ease visulization, we define a <strong>contiguous rectangle</strong> as a rectangle with additional requirement that both $A$ and $B$ are contiguous. (For ex. $\{1,2,3\}$ is contiguous but $\{1,3,4\}$ isn't.) Assume $M&#39;$ is formed from $M$ by a row/column permutation (which means you can permute any rows and any columns of $M$). Define $\chi&#39;(M&#39;)$ as the mininum number of contiguous rectangles needed to tile $M&#39;$. Define $\chi&#39; = \min\{\chi&#39;(M&#39;)$ | for any $M&#39;\}$. The question is:</p>

<p>Is $\chi$ = $\chi&#39;$?</p>

CC BY-SA 3.0
2011-05-25T12:33:29.183Z
Why aren't the two examples above good enough to disprove $\chi = \chi'$? They have the same $\chi$ and different $\chi'$.
Peter Shor 
CC BY-SA 3.0
2011-05-25T16:05:43.727Z
@Peter Sorry for not making it clear. Actually $\chi'$ is defined using the most visually friendly matrix $M'$, which is a row/col permutation of $M$, not necessarily $M$ itself. Otherwise the problem is trivial...It has been updated. Thanks!
Cyker
CC BY-SA 3.0
2011-05-25T16:48:24.547Z
You were interested in square matrices, but it seems that at least in the general case it should be easy to show that the answer is "no". For instance, the $2 \times 4$ matrix with the rows 0011 and 0101 can be tiled with 4 non-contiguous rectangles, but it seems that no matter how you permute the rows and columns, you need at least 5 contiguous rectangles.
Jukka Suomela
CC BY-SA 3.0
2011-05-25T17:54:43.943Z
If you add two rows consisting of 0000 to @Jukka's 2 x 4 matrix, you get a 4 x 4 counterexample. You need at least 6 contiguous rectangles for this matrix. There is a unique column containing two 0's and two 1's. The tiling contains at least one rectangle covering the two 0's this column, and if you throw this rectangle away, you get a tiling of Jukka's matrix with at least one fewer rectangle.
Peter Shor 
CC BY-SA 3.0
2011-05-25T19:34:06.560Z
I wonder if one or both of these comments should be answers so that they can be accepted and the Community ghost doesn't keep floating this question up
Suresh Venkat
CC BY-SA 3.0
2011-05-25T20:03:57.453Z
Perhaps @cyker could put together the comments, double-check it, fill in the missing details, write an answer, and accept it?
Jukka Suomela
<co.combinatorics><communication-complexity>
Monochromatic Rectangle Tiling
Cyker
# Monochromatic Rectangle Tiling

(Asked by: username_0 on 2011-05-25)

This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M\_{n \times n}$. A **rectangle** is defined as a submatrix $A \times B$ where $A \subseteq \{0,1\}^n$ and $B \subseteq \{0,1\}^n$. A rectangle is said to be **monochromatic** if all its elements are 0 (or all are 1). Define the minimum number of monochromatic rectangles needed to tile the whole matrix $M$ as $\chi$.

But the tiling defined as above might be difficult to visualize. For example, consider

$\begin{bmatrix}
1 0 1 0 \\
0 0 0 0 \\
1 0 1 0 \\
0 0 0 0
\end{bmatrix}$

At first glance it might be that $\chi$ is very large. But after permuting the second and third row/column, we have

$\begin{bmatrix}
1 1 0 0 \\
1 1 0 0 \\
0 0 0 0 \\
0 0 0 0
\end{bmatrix}$

then $\chi$ is easily seen to be 3 (since permutation doesn't change $\chi$).

To ease visulization, we define a **contiguous rectangle** as a rectangle with additional requirement that both $A$ and $B$ are contiguous. (For ex. $\{1,2,3\}$ is contiguous but $\{1,3,4\}$ isn't.) Assume $M'$ is formed from $M$ by a row/column permutation (which means you can permute any rows and any columns of $M$). Define $\chi'(M')$ as the mininum number of contiguous rectangles needed to tile $M'$. Define $\chi' = \min\{\chi'(M')$ | for any $M'\}$. The question is:

Is $\chi$ = $\chi'$?

**Tags:** co.combinatorics, communication-complexity

> **Comments:**
> **username_1**: Why aren't the two examples above good enough to disprove $\chi = \chi'$? They have the same $\chi$ and different $\chi'$.  
> **username_0**: @Peter Sorry for not making it clear. Actually $\chi'$ is defined using the most visually friendly matrix $M'$, which is a row/col permutation of $M$, not necessarily $M$ itself. Otherwise the problem is trivial...It has been updated. Thanks!  
> **username_2**: You were interested in square matrices, but it seems that at least in the general case it should be easy to show that the answer is "no". For instance, the $2 \times 4$ matrix with the rows 0011 and 0101 can be tiled with 4 non-contiguous rectangles, but it seems that no matter how you permute the rows and columns, you need at least 5 contiguous rectangles.  
> **username_1**: If you add two rows consisting of 0000 to @Jukka's 2 x 4 matrix, you get a 4 x 4 counterexample. You need at least 6 contiguous rectangles for this matrix. There is a unique column containing two 0's and two 1's. The tiling contains at least one rectangle covering the two 0's this column, and if you throw this rectangle away, you get a tiling of Jukka's matrix with at least one fewer rectangle.  
> **username_3**: I wonder if one or both of these comments should be answers so that they can be accepted and the Community ghost doesn't keep floating this question up  
> **username_2**: Perhaps @cyker could put together the comments, double-check it, fill in the missing details, write an answer, and accept it?  

---

## 1 answers

### Answer by username_0 on 2011-05-26. Score: 6 | Accepted answer

As can be seen in the comments, Jukka provides a $2 \times 4$ counter example, which is further generalized by Peter to $4 \times 4$ to meet the requirements. Both analysis and program verification (use dynamic programming to calculate $\chi'$) can be performed to make sure $\chi \neq \chi'$ is possible when $n = 4$.

Actually Peter's generalization can be used to show there is an $n \times n$ matrix s.t. $\chi \neq \chi'$ for any $n$. The counter example is shown below:

$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
\vdots \\
0 0 0 0 0 \cdots 0
\end{bmatrix}$

There's a unique column with two 1's. At least one continuous rectangle is needed to cover the 0's in this column. And this continuous rectangle doesn't cover any elements in the two rows corresponding to the two 1's. Remove this continuous rectangle and the rest will be a $2 \times n$ matrix:

$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0
\end{bmatrix}$

which needs at least 5 continuous rectangles to cover. So $\chi' \geq 6$. However, it is easy to see $\chi \leq 5$. So $\chi \neq \chi'$.

> **Comments:**
> **username_4**: Let's not forget that the question makes little sense in terms of communication complexity. The notions of being continuous or geometrical in terms of rectangles are mostly misleading. Unless you can SHOW that these are the only interesting rectangles! Which might be true in some sense.  
> **username_3**: can you accept this if it works: so that the question doesn't come up later ?  
> **username_0**: @ Suresh Not until 7 hours later...  
> **username_0**: @ Hartmut Continuous rectangles are easy to view. So in some sense they're preferred if possible, i.e., there's a row/col permutation which makes $\chi = \chi'$. Intuitively, unrestricted rectangles are much powerful than continuous ones so this might be impossible. And the answer to this question just verifies this.  

---

