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'$?