no. 17 · Wednesday 18 November 2026
A counterexample to a basis conjecture of Brualdi, Friedland, and Pothen
Abstract
Brualdi, Friedland, and Pothen conjectured that certain rank inequalities characterize bases consisting of elementary vectors in the row space of a matrix whose nonzero entries are algebraically independent. We give a $4\times6$ counterexample: all the inequalities hold, but the four elementary vectors form a minimally dependent family. A construction using two planes in a common three-dimensional subspace explains the dependence and gives a second counterexample pattern with only four prescribed zeros. We also prove that the proposed criterion is valid over every field when the number of columns exceeds the row rank by at most one. A direct-sum extension gives counterexamples of size $m\times(m+2)$ for every $m\ge4$. Thus the minimum column excess permitting a counterexample is exactly two in every such rank.
- comments
- We replaced the \(4\times8\) example with a \(4\times6\) sparse generic matrix, with complete verification of elementary vectors, rank inequalities, and dependence. We also proved that the four vectors are minimally dependent: every proper subfamily is independent. 6 pages. Comments welcome!
- fields
- Combinatorics