If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of the same indices (if row $i$ is to be removed so is column $i$) ? 



Extracting a full rank matrix from a 0-1 matrix
There are many search strategies that might be tried. Note that if the coefficient of $X^{n-k}$ in the characteristic polynomial $P\_A(X)$ of $A$ is nonzero, such a submatrix does exist. This is not an if and only if, but if the submatrix exists, then for most $t = (t\_1,\ldots, t\_n)$, all $t\_i$ nonzero, it will work for $D\_t A$ where $D\_t$ is the diagonal matrix with diagonal entries $t$. Of course the rank of
any submatrix of $D\_t A$ is the same as the rank of the corresponding submatrix of $A$. The characteristic polynomial over the integers is rather hard to compute, as some very large coefficients can occur, however we can improve matters considerably by choosing a conveniently sized prime $p$ and doing the calculations mod $p$ (with the $t\_i$ nonzero integers mod $p$). We can then start removing rows and corresponding columns one at a time, keeping the property of having the appropriate coefficient in the characteristic polynomial of $D\_t A$ mod $p$ nonzero.


EDIT: I tried an example in Maple with a $100 \times 100$ $0-1$ matrix $M$ of rank $70$ which I constructed so that the submatrix with rows and columns $1\ldots7, 11\ldots 17, \ldots, 91 \ldots 97$ had full rank.
I randomly chose prime $p = 2412337$. Using the Modular subpackage of the LinearAlgebra package, it took $0.006$ seconds to compute the characteristic polynomial mod $p$ and look at the coefficient of $X^{30}$, which turned out to be nonzero (so I didn't have to bother with a $D\_t$). Then it took $0.209$ seconds to loop over indices $i$ to see if removing row and column $i$ kept the appropriate coefficient nonzero:



```
removed:= 0: 
RowsAndColumns:= [$1..100]:
for i from 1 to 100 while removed < 30 do
  RCtry:= subs(i=NULL,RowsAndColumns);
  if coeff(CharacteristicPolynomial(p,M[RCtry,RCtry],X),X,30-removed-1) <> 0 then
    removed:= removed+1;
    RowsAndColumns:= RCtry;
  fi
od:

```

The result was a set of $70$ row and column indices (not surprisingly, different from the ones I had set up) for a submatrix of full rank.


