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
be an
matrix of matrix rank
, and let
be elementary vectors
of its row space, with zero-coordinate sets
. A conjecture of Brualdi et al. (1995)
asserted that, when the nonzero entries of
are algebraically
independent over
, these vectors form a vector
basis iff
for every nonempty , where
denotes the submatrix with
column indices in
. The condition is necessary over
every field, but is not sufficient (Aliabadi 2026).
Aliabadi (2026) gives the counterexample
where the ten displayed nonzero entries are independent indeterminates over . There are elementary vectors
with zero-coordinate sets
,
,
, and
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 . For each
, counterexamples of size
have span of dimension
. 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.