On connecting combinatorial rectangles In communication complexity one important object is the combinatorial retangle. Given a $0-1$ square matrix $M$, do their exist permutations $\sigma,\pi$ such that $\sigma M\pi$ consists of only geometric rectangles? That is all the combinatorial rectangles are geometrically connected?
It's not possible.  Consider the following 3x3 boolean matrix:

1 1 0

1 0 1

0 1 1

For every pair of rows {r,r'} , there exists a column c such that {r,r'} X {c} is a combinatorial rectangle.  For any particular pair, we can permute the rows such that {r,r'} are adjacent.  However, since we have a combinatorial rectangle for all pairs of rows, it's not possible to permute the rows so that all such rectangles are geometrically connected simultaneously.