Computing Elementary Vectors over Integral Domains
- Marcus Aichmayr (Universität Kassel)
Abstract
Elementary vectors - support-minimal vectors in a subspace - play a central role in areas such as linear inequality systems, linear and oriented matroids, the sparse basis problem, reaction network theory, and optimization.
We present a new algorithm for the enumeration of elementary vectors, avoiding scalar multiples. Its correctness is ensured via the Grassmann–Plücker identity. Our method computes elementary vectors over arbitrary integral domains using maximal minors, making it applicable to algebraic numbers, field extensions, and matrices with parameters.
We demonstrate our approach with examples and discuss one application to the solvability of linear inequality systems. Our implementation is available as part of our SageMath package.
