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

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?

• 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. – orlp Apr 15 '17 at 23:21

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.