Let $M$ be a $0-1$ matrix.

Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you step on another $1$.

Can every $0-1$ be converted to a matrix of one component by permutations of rows and columns?

What classes of matrices cannot have one component?

also posted: http://math.stackexchange.com/questions/1072461/connected-components-0-1-matrices

(Say I proved it for $n$ components merged to one. Now say I have $n+1$ components. If I move the first $n$ components by induction argument, the last $(n+1)^{st}$ component may split up in exponentially many. Am I wrong about this?)

Every $M$ can be given by $M=\sum_{i=1}^nM_i$ where $M_i$ are $0-1$ and rank $1$ and disjoint when placed on $M$. Row and column reduce each $M_i$ to $P_i$ with just one $1$ entry. Consider $P=\sum_{i=1}^nP_i$. There are various different ways to convert to $P_i$ for every given $M_i$.

For each $M_i$ let $S_i$(area of rectangle) be the number of ways to reduce to point matrix $P_i$. Total ways is $S=\prod_{i=1}^nS_i$.

I think the question can be thought as finding a permutation of $P$ given a point reduction out of $S$ ways such that when you expand each $P_i$ to its $M_i$, the resulting matrix should be one component $0-1$ matrix. I also think working with smallest possible $n$ should suffice.

Is there an $M$ such that for all configuration of points $P_i$ from $S$ choices, any permutations on $P_i$ followed by expansions to $M_i$ would either keep $M$ disconnected or $M_i$ non-disjoint? I also think working with one candidate choice of $P_i$ out of $S$ many choices should suffice.