# 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$) ?

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. • Thanks Robert! Is there a quicker way of checking whether the coefficient of a characteristic polynomial is non-zero (without computing the characteristic polynomial itself)? – Nado Jan 29 '16 at 18:59 • 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\$. – Robert Israel Jan 29 '16 at 22:28