Maximum upper left sub-matrix with zeros by row and column permutation

Question

I have a square matrix filled with zeros and ones and I am allowed to permute the row and column order with the same permutation for rows and columns. The goal is to find a permutation such that there is a square sub-matrix in the upper left corner filled with only zeros and this sub-matrix has maximum dimensions.

Background:

I want to efficiently solve linearised sub-problems of a non-linear system of equations where the Jacobian has many constant entries. The idea is to perform the necessary inversion of the Jacobian using the Schur-complement and pre-computed inverse of an upper left sub-matrix of constant entries. This greatly reduces the computational work load because only a much smaller sub-matrix of the non-linear terms has to be inverted in each iteration.

My question relates to the permutation (re-arrangement) of the unknown variables (row and column swaps on the Jacobian) such that the pre-computed inverse is as large as possible. In this respect the above mentioned one and zero matrix entries correspond to the non-linear resp. constant terms of the Jacobian.

I have researched quite a bit since I thought the this kind of problem might be quite common (maybe it has some meaning in graph-theory) and that my special application would have already come to many other peoples minds. Maybe I'm lacking the correct vocabulary, but I couldn't find even a lead to the solution.

Example:

This matrix $$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\0 & 1 & 0 & 0 & 1 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 1 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} $$ can be permuted by $ \left[\begin{matrix} 1 & 4 & 6 & 3 & 7 & 5 & 8 & 2\end{matrix}\right] $ to give this matrix with an upper left 4 by 4 sub-matrix of only zeros: $$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} $$

Of course this permutation is not unique because at least the last 6 rows and columns can be permuted arbitrarily without changing the upper left sub-matrix.

Answer 1

After one night of sleeping over it, I found a possible answer myself:

1. Build a complete graph with $n$ vertices, where $n$ is the dimension of the matrix filled with zeros and ones.
2. Remove all edges in this graph between vertices $i$ and $j$ if not all elements $(i,i)$, $(i,j)$, $(j,i)$, $(j,j)$ of the matrix are equal to zero.
3. Any maximum clique of the thus created graph represents the rows/columns that, when permuted to be the top/left most, will yield the desired upper left square sub-matrix filled with only zeros.

Algorithms to find a maximum clique are known and proven to work reliable.