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

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

• This is an interesting question, indeed. The number of tests is a big number, considering that the vector space had only 33554432 elements. I came up with a couple of ideas to test that one of the submatrices does not have full rank. You can check the trace, this should be 1 (since you have an odd dimension). You can count the 1s per row, when a row does not have a single 1, it also fails. Unfortunately, these are not enough to prove that your matrix has full rank. For example, a matrix full of ones, pass both tests. – nicoguaro Apr 15 '17 at 17:07

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