2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.