1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nicoguaro Apr 15 '17 at 17:07
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.