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?
a & band update the vector usinga | bfor 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$