Sparsification of Rectangular Matrices

Consider the problem of sparsifying a rectangular matrix with more columns than rows. This means forming linear combinations of the rows, while preserving the rank, such that the result contains as many zero entries as possible. A combinatorial search method is presented which sparsifies a matrix with exponentially many arithmetic operations in the worst case. Moreover, a method is presented which substantially reduces the combinatorial search space if the matrix gives rise to a non-trivial block structure.