3
$\begingroup$

I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly independent.

Straightforward approach would be to iterate over all subsets of columns of size up to $m$ (because column rank cannot be higher than a row rank), and then check corresponding submatrix if it has full column rank. For instance, if $m=25$ and $n=50$, this way one needs to test $$ \binom{50}{1} + \binom{50}{2} + \dotsb + \binom{50}{25} \approx 6.3 \times 10^{14} $$ matrices. Hence one needs a really fast algorithm to test if a particular submatrix has a full column rank.

For example, assume I have 500 cores and I want to calculate the subject in 24h. Then I need to test $1.4 \times 10^7$ submatrices per second per core. Old good Gaussian elimination fails with this task (right?). Can I do something much faster than it?

Another approach might be some optimised method like branch and bounds, so that one does not need to check all the submatrices - but only a small portion of them. For example we can build the subsets recursively, and if we encounter a subset of columns that are linearly dependent, we can safely throw away all of the supersets of this subset - as they will never become linearly independent. However, I am not sure about either complexity or running time of this approach. I am to implement it now to see the running time behaviour.

P.S. All operations are over Galois field $\mathbb F_2$.

P.P.S. Do you think this problem is in NP?

$\endgroup$
  • 1
    $\begingroup$ Two tips: store for each column a bitvector (fits in a 64-bit int in your example) that contains an 1 if vector $i$ and $j$ are dependent. Then if you keep a bitvector for each subset you can do a quick dependence check with a & b and update the vector using a | b for the new subset. On top of that, combine subsets of size $2n$ from subsets of size $n$, and if a subset of size $n$ is fully independent from every other subset of size $n$ multiply the result of $2n$ by 2 and remove that subset from consideration. This should reduce the impact of a combinatoric explosion. $\endgroup$ – orlp Apr 15 '17 at 23:21
1
$\begingroup$

Snook, Counting bases of representable matroids shows that counting the number of maximal linearly independent subsets of columns is $\mathsf{\# P}$-complete. Your problem is probably also $\mathsf{\#P}$-complete. This suggests that you need an enumerative approach.

On the other hand, you can efficiently (in theory) approximate the number of maximal linearly independent subsets arbitrarily well, see for example Anari et al., Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid (might be an overkill).

$\endgroup$

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.