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.

How about using counting arguments? Will those help here?

Given a connected matrix, we can count the number of permutations that permute the matrix to 'distinct' matrices. This can be done by looking at $M_i$s that admit the largest number permutation that change $M_i$ to something different from $M_i$.

We probably can guess the number of ways different possibilities of $M_i$s that will give to 'distinct' $M$s that cannot be obtained from permutation of another.

We know the total number of $0-1$ matrices is $2^{m^2}$. From this can we guess number of disconnected is bounded away from $0$ or bounded towards $0$?

Analysis of Christian Remling's answer for $n=9$:

$c=0.9996866089930690374784429428213$ So probability of no counterexamples is atleast $$2^{81(-1+0.9996866089930690374784429428213)}=2^{81(3.1339100693096252155705717870308e-4)}=2^{-0.02538467156140796424612163147495}=0.9825585800827572008199109379506$$ If you add the $dn\log n$ term, we may not get any matrices for counter examples at all. So counting does not seem to work robustly to provide a proof for small $n$?

Analysis for large $n$:

For large $n$, $2^{cn^2+dn\log n-c'n^2}=2^{n^2(c-c')+nd\log n}=2^{n^2((c-c')+d\frac{\log n}{n})}$ seems to go to $1$ as $\frac{\log n}{n}\rightarrow 0$ and since $(2^n-1)^{\frac{1}{n}}\rightarrow 2$ would yield $c'\rightarrow c$ for large $n$. Again this fails to yield a proof. Am I wrong about this?