Monochromatic Rectangle Tiling 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&#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:

Is $\chi$ = $\chi&#39;$?
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$.

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:

$\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&#39; \geq 6$. However, it is easy to see $\chi \leq 5$. So $\chi \neq \chi&#39;$.