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.
- On Rota's problem about n bases in a rank n matroid
- New polynomial-time algorithms for Camion bases
- scientific article; zbMATH DE number 1953186
- Orientation of matrices
- Complementarity in Oriented Matroids
- An elementary proof that every matroid is an intersection of principal transversal matroids
- Improved bound for the Carathéodory rank of the bases of a matroid
- scientific article; zbMATH DE number 3843764
- On exchange properties for Coxeter matroids and oriented matroids
- Rota’s Basis Conjecture for Paving Matroids
This page was built for publication: A nonextremal Camion basis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260967)
