Count number of linearly independent subsets of columns of a binary matrix

Question

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?

Answer 1

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).