I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.


I want to find the linear combinations with as few columns as possible. So for example, I don't want to find the 2 combinations: C1 + C2 - C4 = 0 and C1 + C2 -C4 - C5 + C6 = 0, but I want to find C1 + C2 - C4 = 0 and - C5 + C6 = 0.


I can calculate easily all linear combination (I use SVD to find a base of the kernel of the matrix). However, the results do not satisfy my constraints of having as many 0 as possible.


Does any one know a method to do this?


Thanks!



Find base of kernel with as many 0 as possible
It sounds like you're describing an instance of the "sparse null basis problem" – this was the title of what (I believe is) the seminal work on this problem, by Coleman and Pothen. You can find their 1984 tech report at <http://ecommons.library.cornell.edu/handle/1813/6438>, and it may be helpful to search for work that cites theirs. See also the paper of Brualdi, Friedland and Pothen found at <https://cs.uwaterloo.ca/research/tr/1993/40/CS-93-40.pdf>. (That's the one I remember reading years ago, which is about how long it's been since I looked at anything related to this stuff.) I seem to recall that there is some nice matroid theory involved. In any case, it seems there has been some work on the more applied side of things as well. For example, I found [this recent paper](http://link.springer.com/article/10.1007%2Fs11075-012-9599-1) from the journal *Numerical Algorithms* which is entitled "An efficient algorithm for sparse null space basis problem using ABS methods".


