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$ submatrix of $A$ by removing columns and rows of the same indices (if row $i$ is to be removed so is column $i$) ?

$\begingroup$ Crossposted from cstheory.stackexchange.com/questions/33672/… $\endgroup$ – Emil Jeřábek supports Monica Jan 28 '16 at 11:25
There are many search strategies that might be tried. Note that if the coefficient of $X^{nk}$ 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$ $01$ 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,30removed1) <> 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.

$\begingroup$ Thanks Robert! Is there a quicker way of checking whether the coefficient of a characteristic polynomial is nonzero (without computing the characteristic polynomial itself)? $\endgroup$ – Nado Jan 29 '16 at 18:59

$\begingroup$ In principle yes: if you want the coefficient of $X^k$ you could work in a quotient ring mod the ideal $\langle X^{k+1}\rangle$. In practice, at least if using Maple, I suspect you're unlikely to beat the performance of CharacteristicPolynomial in the LinearAlgebra[Modular] package, which computes the whole characteristic polynomial mod $p$, unless perhaps $n$ is very large compared to $k$. $\endgroup$ – Robert Israel Jan 29 '16 at 22:28