Connected components $0-1$ matrices 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 if you only have steps $(i\pm1,j),(i,j\pm1)$?
What classes of matrices cannot have one component?
also posted: https://mathoverflow.net/questions/190981/connected-components-0-1-matrices
 A: If we only allow $(\pm 1, 0)$ or $(0, \pm 1)$ as steps,
$$A = \pmatrix{1&0&0\\0&0&0\\0&0&1}$$
suffices as a counter-example (no permutation will move the two ones into the same row or column). Allowing diagonal steps $(\pm 1, \pm 1)$ should work make the conjecture true, but I don't know how to prove it. (thinking about this at the moment)
Thoughts on diagonal stepping:
If $A$ contains a row/column pair such that $A_{i,\cdot} = e_j, A_{\cdot, j} = e_i$ (i.e. a "crosshair" of $0$'s with a $1$ in the middle, we can permute $(i,j)$ to $(1,1)$ by swapping row $i \leftrightarrow 1$ and column $j\leftrightarrow 1$ and obtain
$$A = \pmatrix{1&0\\0&A'}$$
wich has the property (call it $P$) iff $A'$ has $(P)$ (I hope). In other words we can focus on matrices without such rows.
If we can construct an $A'$ on the other hand such that every connected form of $A'$ satisfies

*

*There is at most one $1$ in the first row and column

*The $(1,1)$ entry is $0$
We get a counter-example for the original conjecture by taking $A$ as above
A: Answered here by probabilistic method.
https://mathoverflow.net/questions/190981/connected-components-0-1-matrices
"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."
