Return to Question

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 http://mathoverflow.net/questions/191248/maximum-connected-components-0-1-matrix)?

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

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

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 http://mathoverflow.net/questions/191248/maximum-connected-components-0-1-matrix)?

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 http://mathoverflow.net/questions/191248/maximum-connected-components-0-1-matrix)?

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

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

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

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 http://mathoverflow.net/questions/191248/maximum-connected-components-0-1-matrix)?