<p>It's not possible.  Consider the following 3x3 boolean matrix:</p>

<p>1 1 0</p>

<p>1 0 1</p>

<p>0 1 1</p>

<p>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 <em>all</em> pairs of rows, it's not possible to permute the rows so that all such rectangles are geometrically connected simultaneously.</p>

CC BY-SA 3.0
2014-12-23T02:28:44.433Z
2014-12-23T02:28:44.433Z
Joshua Brody
<p>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?</p>

<communication-complexity>
On connecting combinatorial rectangles
Turbo
# On connecting combinatorial rectangles

(Asked by: username_0 on 2014-12-23)

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?

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2014-12-23. Score: 4 | Accepted answer

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.


---

