# Complexity involving connected components of 0/1 matrix

Assume 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$ and one can shown there that there are matrices that cannot be brought to one component.

Is the decision problem "Can a given matrix $A$ be permuted into at most $k$ components?" in $coNP$ (it is clearly in $NP$ ("YES" certificate is a permutation with $\leq k$ components)) and could it be $NP$-complete (I think this problem is in $NPI$)? $k$ is part of input.

I do not have explicit matrices but a counting argument will easily give you existence.

• "permuted into" by applying the same permutation to the rows and columns, or by applying $\hspace{.81 in}$ possibly-different permutations to the rows and columns? ​ ​ – user6973 Sep 19 '16 at 8:19
• different ofcourse – T.... Sep 19 '16 at 8:29
• Do you have an example of a matrix that can't be permuted to have only one component? – Andrew Morgan Sep 19 '16 at 12:50
• @AndrewMorgan I dont but it is easy to prove by counting arguments. – T.... Sep 19 '16 at 15:48
• Related MO question with proof of existence of matrices with more than one component: mathoverflow.net/questions/190981/… – John Machacek Sep 26 '16 at 14:01

The matrix will have a small top-left corner that will contain the important information, and many additional rows and columns to impose a structure on this part. In particular, I claim that with properly chosen additional rows and columns, we can achieve that instead of arbitrary permutations, we can restrict the problem to permutations that do not change the rows and can swap only given pairs of adjacent columns, or otherwise the number of components would be larger than $k$.
Since I didn't provide any details about the additional part, it is not clear how $k$ depends on $n$. Can $k$ be kept constant?
• $k$ is not constant but it is an interesting reduction still thinking. – T.... Sep 27 '16 at 21:38
• I think it is quite possible that you can make the additional part such that $k$ becomes a constant, if that's what you want. – domotorp Sep 28 '16 at 4:11