Fast counting of all submatrices of a binary matrix with a full column rank

Question

I have a binary full-rank matrix of size, say, $25 \times 50$. I need to count how many subsets of its columns form matrices with a full column rank, i.e. all the columns in the subset are linearly independent.

Straightforward approach would be to iterate over all subsets of columns of size up to $25$, and then check corresponding submatrix if it has full column rank. This way one needs to test $$ \binom{50}{1} + \binom{50}{2} + \dotsb + \binom{50}{25} = 626\,155\,256\,640\,187 \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 on one core. Old good Gaussian elimination fails with this task. 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. However, I don't see at the moment what can be done in this direction.

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

Answer 1

Interesting question. To me this looks like a modified column subset selection problem. The problem concerns the determination of a permutation matrix $P$ so that :

$$ AP = (A_1 \quad A_2) $$ for the real or complex matrix $A$. Columns of $A_1$ is supposed to be very linearly independent, while redundant columns of $A$ are stored in $A_2$. You could probably decompose your problem into multiple subset selection problems, like a tree search (don't know how to do this yet). Here are some references on the topic:

Avron, Haim, and Christos Boutsidis. "Faster subset selection for matrices and applications." SIAM Journal on Matrix Analysis and Applications 34.4 (2013): 1464-1499. http://www.boutsidis.org/Boutsidis_SIMAX_13a.pdf

Civril, Ali, and Malik Magdon-Ismail. "Column subset selection via sparse approximation of SVD." Theoretical Computer Science 421 (2012): 1-14. http://www.sciencedirect.com/science/article/pii/S0304397511009388

Arai, Hiromasa, Crystal Maung, and Haim Schweitzer. "Optimal Column Subset Selection by A-Star Search." AAAI. 2015. https://pdfs.semanticscholar.org/abda/eb770487773d20ee887107569d4e36278972.pdf