TOPICS
Search

Sparse Basis Problem


The sparse basis problem asks for a vector basis of a given subspace with the smallest total number of nonzero coordinates (Brualdi et al. 1995). A nonzero vector in the subspace is elementary if no other nonzero vector has support properly contained in its support. Selecting elementary vectors separately need not produce a linearly independent family.

Let A be an m×n matrix of matrix rank m, and let x_1,...,x_m be elementary vectors of its row space, with zero-coordinate sets J_1,...,J_m. A conjecture of Brualdi et al. (1995) asserted that, when the nonzero entries of A are algebraically independent over Q, these vectors form a vector basis iff

 rankA[:, intersection _(s in P)J_s]<=m-|P|

for every nonempty P subset= {1,...,m}, where A[:,J] denotes the submatrix with column indices in J. The condition is necessary over every field, but is not sufficient (Aliabadi 2026).

Aliabadi (2026) gives the 4×6 counterexample

 A=[a 0 0 0 0 k; 0 e 0 h 0 l; b 0 0 i j 0; 0 f g 0 0 0],

where the ten displayed nonzero entries are independent indeterminates over Q. There are elementary vectors with zero-coordinate sets {3,5,6}, {1,3,4}, {1,2,4}, and {2,5,6} satisfying every inequality, while their vector space span has dimension 3 and every proper subfamily is linearly independent. Another counterexample pattern has only four prescribed zero entries, without a claim that four is the minimum number of zeros.

The criterion does hold over every field, without a genericity assumption, when n-m<=1. For each m>=4, counterexamples of size m×(m+2) have span of dimension m-1. Thus the minimum column excess allowing a counterexample is exactly 2 for each such row rank. This refutes the extension to prescribed-zero matrices, while leaving the original results for fully generic matrices intact.


See also

Row Space, Subspace, Vector Basis

Explore with Wolfram|Alpha

References

Aliabadi, M. "A Counterexample to a Sparse Basis Conjecture of Brualdi, Friedland, and Pothen." 16 Nov 2026. https://arxiv.org/abs/2605.30401v3.Brualdi, R. A.; Friedland, S.; and Pothen, A. "The Sparse Basis Problem and Multilinear Algebra." SIAM J. Matrix Anal. Appl. 16, 1-20, 1995. https://doi.org/10.1137/S0895479892230067.

Cite this as:

Weisstein, Eric W. "Sparse Basis Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SparseBasisProblem.html

Subject classifications