Key points are not available for this paper at this time.
The Null Space Problem (NSP) is the following: Given a t n matrix A with t < n, find a sparsest basis for its null space (a null basis). We show that columns in a sparsest null basis correspond to minimal dependent sets of columns of A. Sparsest null bases are characterized by a greedy algorithm that augments a partial basis by a sparsest null vector. Despite this result, (NSP) is NP-hard since finding a sparsest null vector of A is NP-complete. We prove that the related problem of finding a sparsest null basis with an embedded identity matrix is NP-hard too. Finally, we study the zero–nonzero structure of sparsest null bases.
Coleman et al. (Wed,) studied this question.