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: <https://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$? 




---


Christian's answer based on fedja's comment solves the problem. Infact the approach can be recursively used to get multiple component matrices for any constant number of components $k$.


It would be nice to know how big $k$ can be for a given $n$. Is there any estimate for $k$ as a function of $n$ (posted as question in <https://mathoverflow.net/questions/191248/maximum-connected-components-0-1-matrix>)?



Connected components $0-1$ matrices
This is fedja's beautiful comment, posted as an answer for better visibility:


Not all matrices can be brought to one component form by exchanging rows/columns.


Consider large $n\times n$ matrices with all possible entries equal to $0,1$. By partitioning this into $3\times 3$ blocks, we see that the number of matrices with no isolated $1$'s is $\lesssim (2^9-1)^{n^2/9}=2^{cn^2}$, $c<1$, because one of the $2^9$ possible blocks is off-limits, the one with a lonely $1$ in the center. For each such matrix, there are at most $(n!)^2\lesssim 2^{dn\log n}$ row/column permuted matrices that can be obtained from it.


So the number of matrices that can be brought to one component form is $\lesssim 2^{c'n^2}$ with $c'<1$, and this is $\ll 2^{n^2}$, the number of all matrices.


