Abstract
We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ⊥ and the double tropical orthogonalization A ⊥ ⊥ of a subset A of the vector space (R∪ { ∞}) n. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.
| Original language | English |
|---|---|
| Pages (from-to) | 157-174 |
| Number of pages | 18 |
| Journal | Applicable Algebra in Engineering Communication and Computing |
| Volume | 32 |
| Issue number | 2 |
| Early online date | 29 Nov 2019 |
| DOIs | |
| Publication status | Published - 31 Mar 2021 |
Funding
We thank M. Joswig, N. Kalinin, H. Markwig, and T. Theobald for useful discussions, and anonymous referees for constructive remarks and suggestions. Part of this research was carried out during our joint visit in September 2017 to the Hausdorff Research Institute for Mathematics at Bonn University, under the program Applied and Computational Algebraic Topology, to which we are very grateful. D. Grigoriev was partly supported by the RSF Grant 16-11-10075. Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. We thank M. Joswig, N. Kalinin, H. Markwig, and T. Theobald for useful discussions, and anonymous referees for constructive remarks and suggestions. Part of this research was carried out during our joint visit in September 2017 to the Hausdorff Research Institute for Mathematics at Bonn University, under the program Applied and Computational Algebraic Topology, to which we are very grateful. D. Grigoriev was partly supported by the RSF Grant 16-11-10075.
Keywords
- Tropical algebra
- Computer algebra
- Complexity