THE SPARSE BASIS PROBLEM AND MULTILINEAR-ALGEBRA

Let A be a k x 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 the y are algebraically independent over the rational number field. Then e very 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 elementar y vectors of W. A simple combinatorial condition that is both necessar y and sufficient for a set of k elementary vectors of W to form a basi s 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 miners of order m of the (m - 1)st compound of an m x n matrix with algebraically indepe ndent entries, which is proved using multilinear algebra techniques. T his combinatorial condition for linear independence is a first step to wards the design of algorithms that compute sparse bases for the row a nd null space without imposing artificial structure constraints to ens ure linear independence.