The Sparse Basis Problem and Multilinear Algebra

Let A be a k n underdetermined matrix. The sparse basis problem for the row space W of A is to find a basis of W with the fewest number of nonzeros. Suppose that all the entries of A are nonzero, and that they are algebraically independent over the rational number field. Then every nonzero vector in W has at least n - k + 1 nonzero entries. Those vectors in W with exactly n - k + 1 nonzero entries are the elementary vectors of W. A simple combinatorial condition that is both necessary and sufficient for a set of k elementary vectors of W to form a basis of W is presented here. A similar result holds for the null space of A where the elementary vectors now have exactly k + 1 nonzero entries. These results follow from a theorem about nonzero minors of order m of the (m - 1) st compound of an m n matrix with algebraically independent entries, which is proved using multilinear algebra techniques. This combinatorial condition for linear independence is a first step towards the design of algorithms that compute sparse bases for the row and null space without imposing artificial structure constraints to ensure linear independence.