A nonextremal Camion basis (Q1260967)

A column basis \(B\) of a real \(m\times n\) matrix \(A\) of rank \(m\) is a Camion basis of \(A\) if there are nonsingular diagonal matrices \(C\) and \(D\) such that \(CB^{-1}AD\) is nonnegative. Camion bases have many geometric and combinatorial interpretations and have been generalized to oriented matroids. \textit{P. Camion} [J. Combinat. Theory 4, 301-362 (1968; Zbl 0174.295)] first showed that every real matrix has at least one Camion basis, and \textit{R. W. Shannon} [Geom. Dedicata 8, 179-187 (1979; Zbl 0423.51013)] proved that every matrix \(A\) as above has at least \(n\) Camion bases and that every volumn of \(A\) is contained in at least \(m\) of these bases. \textit{R. G. Bland} and \textit{D. H. Cho} [Balancing configurations in \(\mathbb{R}^ d\) by reflection of points. Tech. Rep. 733, SORIE, Cornell Univ. (1987)] showed that if a basic solution \(x(B,b)\) of \(Ax=b\), where \(B\) is as above and \(b\) is in general position with respect to the columns of \(A\), is a vertex of the convex hull of all basic solutions of \(Ax=b\), then \(B\) is a Camion basis of \(A\). This raises the natural question whether every Camion basis can be obtained in this way. The answer is yes for \(m\leq 2\) and for \(n-m\leq 2\), but no in general: the authors construct a \(3\times 21\) matrix \(A\) and a Camion basis of \(A\) and show that these yield a counterexample. Computer algebra methods play a critical role in its construction.