The Null Space Problem I. Complexity

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.