THE SPARSE BASIS PROBLEM AND MULTILINEAR ALGEBRA?

RICHARD A. BRUALDIy , SHMUEL FRIEDLANDz , AND ALEX POTHENx

Abstract. Let A be a k by 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 by 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.

AMS(MOS) subject classifications: primary 65F50, 65K05, 15A69. Keywords. elementary vector, matrix compound, null-space basis, row-space basis, sparse matrix, wedge product.

1. Introduction. Many situations in computational linear algebra and numerical optimization require the computation of a sparse basis for the row space or the null space of a sparse, underdetermined matrix A. The sparse row space basis problem (hereafter the row space problem) is to compute a basis for the row space of A with the fewest number of nonzeros. Similarly, the sparse null space basis problem (hereafter the null space problem) is to compute a basis for the null space of A with the fewest number of nonzeros. It turns out that both these problems are computationally intractable: they are NP-hard [1, 8, 9]. Under a nondegeneracy assumption called the matching property, Hoffman and McCormick [5, 8] designed polynomial time algorithms to solve the row space problem. Sparsest null bases can be characterized by means of a matroid greedy algorithm [1, 9], yet the null space problem turned out to be harder than the row space problem; heuristic algorithms to compute sparse null bases were designed and implemented in [2, 4].

All algorithms known to us for computing sparse null bases have two components:

? Written April 1992; revised July 1993. A part of this work was done while the authors were visiting the Institute for Mathematics and Its Applications (IMA) at the University of Minnesota. We thank the IMA for its support.
y Department of Mathematics, University of Wisconsin, Madison, WI 53706 (brualdi@math.wisc. edu). This author's research was partially supported by NSF Grant DMS-8901445 and by NSA Grant MDA904-89-H-2060.
z Department of Mathematics, University of Illinois at Chicago, Chicago, IL 60680 (u12735@uicvm. bitnet).
x Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada (apothen@narnia.uwaterloo.ca, na.pothen@na-net.ornl.gov). This author was supported by NSF grant CCR-9024954 and by U.S. Department of Energy grant DE-FG02-91ER25095 at the Pennsylvania State University and by the Canadian Natural Sciences and Engineering Research Council under grant OGP0008111 at the University of Waterloo.