12
$\begingroup$

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)?

Improve this question
$\endgroup$
18
  • 4
    $\begingroup$ Since you allow diagonal steps, all such matrices are connected. An inductive argument should handle an arbitrary rectangular 0-1 matrix. $\endgroup$
    – The Masked Avenger
    Commented Dec 17, 2014 at 20:47
  • 3
    $\begingroup$ This question sounds so classically simple and charming that once you see it you cannot dismiss it. You have to say: yes, no, or I cannot answer it. There are no comments about the question being known. No simple argument was given to indicate that the problem is easy one way or another, so that its simplicity is deceptive. I see no reason why this question's value for MO should be doubted. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 20, 2014 at 20:54
  • 8
    $\begingroup$ Why is this question on hold? It seems quite interesting to me. $\endgroup$
    – Richard Stanley
    Commented Dec 20, 2014 at 21:45
  • 11
    $\begingroup$ The answer is "No". Take a random size $n$ matrix with each entry being $1$ with probability $1/2$. Then the probability that we don't have any isolated $1$ is about $e^{-cn^2}$. The permutations are just $e^{Cn\log n}$, which (outside the state of Kansas) is a slower growing function. An old trick, of course, but still useful :-) $\endgroup$
    – fedja
    Commented Dec 21, 2014 at 16:28
  • 2
    $\begingroup$ @Turbo I have already explained how it ended as a comment ;-). Also, it is neither "my" (I wish I were 1/10000000 as brilliant as Paul Erdos), nor "idea" (the proof is complete, though the exposition may be somewhat terse). However I promise that if I find an explicit example before anybody else, I'll post it as an answer :-) $\endgroup$
    – fedja
    Commented Dec 21, 2014 at 21:03

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ @Turbo: $2^{cn^2}\cdot 2^{dn\log n}$, and I called it $\lesssim 2^{c'n^2}$ for good measure; it's really $2^{(c+o(1))n^2}$. $\endgroup$
    – Christian Remling
    Commented Dec 21, 2014 at 21:36
  • 1
    $\begingroup$ THe 3x3 blocks block partition construction reminds me the Garden of Eden early cellurar automata theory invented by Stan Ulam--it was Ulam's reaction to the engineering electric-mechanical John von Neumann's idea of the self-reproducing automaton. The Garden of Eden was introduced by someone else, after Ulam. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 21, 2014 at 22:15
  • 1
    $\begingroup$ @Fedja's proof (Christian's presentation) can be applied to a weaker connectivity, where constant $1$ is replaced by $D$, so that $\ x\ y\in\mathbb Z^2\ $ are considered connected when $\ ||x-y||\le D$ (and the connectivity distributes over entire lattice). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 21, 2014 at 23:02
  • 1
    $\begingroup$ @Turbo - This sort of argument is very loose, so you likely won't get any sort of precise statement or "estimates" out of it. It only shows even that there are at least two components when $n \geq 96462$ (you could likely tweak the argument to lower that bound a bit, of course, but it will still be quite large). $\endgroup$
    – Nathaniel Johnston
    Commented Dec 21, 2014 at 23:15
  • 4
    $\begingroup$ First, you can enhance the probabilistic argument by tweaking the parameters. Let $p$ be the probability of $1$ in every cell. Then the probability of no isolated $1$ is $[(1-p(1-p)^8]^{n^2/9}$, which, for $p=1/9$ is less than $1/(n!)^2$ for $n\approx 3000$ already (not small yet, but somewhat better than $96462$). Second, you can change the way you place 1's from totally random to semi-deterministic, which, if executed intelligently, may shave off another factor of 10. At last, you can use computers to check sizes up to 8 or so (16 or so, if you spend some time on the algorithm design first). $\endgroup$
    – fedja
    Commented Dec 22, 2014 at 1:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .