So I give a sketch why the problem is NP-complete.
It is very sketchy, which you can take as a sign of trust that you're a smart guy, and not at all a sign of laziness on my part.
We will reduce a variant of PLANAR-SAT, where we also require that the edges connecting the variable to its negated and unnegated occurrences form adjacent intervals in the rotation of the vertex of the variable; e.g., if each variable occurs at most once negated.
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$.
If we can achieve this, then in the top-left corner we "draw" the graph of our PLANAR-SAT, such that at the heart of each vertex there is a pair of swappable columns.
Every other row is constant on these two columns, so only the neighborhood of the vertex is effected.
And at this vertex the negated clause-edges come from one side, the unnegated from the other, the swappable column decides which ones are connected to some main component.
Therefore, the CNF is satisfiable if and only if all clauses can be connected to the main component.
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?
