Extracting a full rank matrix from a 0-1 matrix 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$) ? 
 A: 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.
