nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

29.11.2019 | Original Paper

Complexity of deciding whether a tropical linear prevariety is a tropical variety

verfasst von: Dima Grigoriev, Nicolai Vorobjov

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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^\perp \) and the double tropical orthogonalization \(A^{\perp \perp }\) of a subset A of the vector space \(({{\mathbb {R}}}\cup \{ \infty \})^n\). We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Vorheriger Artikel A modified Dual-Ouroboros public-key encryption using Gabidulin codes

Nächster Artikel LCD codes from weighing matrices

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22(1), 43 (2012) MathSciNetCrossRef

Bogart, T., Jensen, A.N., Speyer, D., Sturmfels, B., Thomas, R.R.: Computing tropical varieties. J. Symb. Comput. 42(1–2), 54–73 (2007)MathSciNetCrossRef

Butkovic, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekon.-Mat. Obzor 20, 203–214 (1984)MathSciNetMATH

Chistov, A.: An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time. J. Soviet Math. 34, 1838–1882 (1986)CrossRef

Chistov, A.: Polynomial complexity of Newton–Puiseux algorithm. Lect. Notes Comput. Sci. 233, 247–255 (1986)MathSciNetCrossRef

Develin, M., Santos, F., Sturmfels, B.: On the rank of a tropical matrix. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, vol. 52. MSRI Publications (2005)

Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1–27 (2004)MathSciNetMATH

Dress, A., Wenzel, W.: Algebraic, tropical, and fuzzy geometry. Beitr. Algebra Geom. 52(2), 431–461 (2011)MathSciNetCrossRef

Gaubert, S., Katz, R.D.: Minimal half-spaces and external representation of tropical polyhedra. J. Algebr. Comb. 33(3), 325–348 (2011)MathSciNetCrossRef

10.

Görlach, P., Ren, Y., Sommars, J.: Detecting tropical defects of polynomial equations (2018). arXiv:1809.03350

11.

Grigoriev, D.: Polynomial factoring over a finite field and solving systems of algebraic equations. J. Soviet Math. 34, 1762–1803 (1986)CrossRef

12.

Grigoriev, D.: Complexity of solving tropical linear systems. Comput. Complex. 22, 71–88 (2013)MathSciNetCrossRef

13.

Grigoriev, D.: Polynomial complexity recognizing a tropical linear variety. Lect. Notes Comput. Sci. 9301, 152–157 (2015)MathSciNetCrossRef

14.

Grigoriev, D., Podolskii, V.: Complexity of tropical and min-plus linear prevarieties. Comput. Complex. 24(1), 31–64 (2015)MathSciNetCrossRef

15.

Grigoriev, D., Vorobjov, N.: Orthogonal tropical linear prevarieties. In: CASC 2018, Lecture Notes in Computer Science, vol. 11077, pp. 187–196 (2018)

16.

Grigoriev, D., Vorobjov, N.: Upper bounds on Betti numbers of tropical prevarieties. Arnold Math. J. 4(1), 127–136 (2018)MathSciNetCrossRef

17.

Hept, K., Theobald, T.: Tropical bases by regular projections. Proc. Am. Math. Soc. 137(7), 2233–2241 (2009)MathSciNetCrossRef

18.

Jensen, A., Markwig, H., Markwig, T.: An algorithm for lifting points in a tropical variety. Collect. Math. 59(2), 129–165 (2008)MathSciNetCrossRef

19.

Jensen, A., Yu, J.: Stable intersections of tropical varieties. J. Algebr. Comb. 43(1), 101–128 (2016)MathSciNetCrossRef

20.

Joswig, M.: Essentials of Tropical Combinatorics. Springer, Berlin (2014)

21.

Joswig, M.: The Cayley trick for tropical hypersurfaces with a view toward Ricardian economics. In: Homological and Computational Methods in Commutative Algebra, Springer INdAM Series, vol. 20. Springer (2017)

22.

Joswig, M., Schröter, B.: The degree of a tropical basis. Proc. Am. Math. Soc. 146(3), 961–970 (2018)MathSciNetCrossRef

23.

Kazarnovskii, Ya., Khovanskii, A.G.: Tropical noetherity and Gröbner bases. St. Petersb. Math. J. 26(5), 797–811 (2015)CrossRef

24.

Lang, S.: Algebra. Springer, Berlin (2002)CrossRef

25.

Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry. American Mathematical Society, Providence (2015)CrossRef

26.

Markwig, T., Ren, Y.: Computing tropical varieties over fields with valuation. Found. Comput. Math. (2019). https://doi.org/10.1007/s10208-019-09430-2

27.

Murota, K., Tamura, A.: On circuit valuation of matroids. Adv. Appl. Math. 26, 192–225 (2001)MathSciNetCrossRef

28.

Osserman, B., Payne, S.: Lifting tropical intersections. Doc. Math. 18, 121–175 (2013)MathSciNetMATH

29.

Richter-Gebert, J., Sturmfels, B., Theobald, T.: First steps in tropical geometry. In: Litvinov, G., Maslov, V. (eds.) Idempotent Mathematics and Mathematical Physics (Proceedings Vienna 2003), Contemporary Mathematics, vol. 377. American Mathematical Society, pp 289–317 (2005)

30.

Speyer, D.: Tropical linear spaces (2008). arXiv:0410455

31.

Yu, J., Yuster, D.S.: Representing tropical linear spaces by circuits. In: The 19th International Conference on Formal Power Series and Algebraic Combinatorics, 2007 (2006). arXiv:0611579

Titel: Complexity of deciding whether a tropical linear prevariety is a tropical variety
verfasst von: Dima Grigoriev
Nicolai Vorobjov
Publikationsdatum: 29.11.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2021
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-019-00407-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2021

On the self-dual codes with an automorphism of order 5

A modified Dual-Ouroboros public-key encryption using Gabidulin codes

LCD codes from weighing matrices

Parametrization of generalized Heisenberg groups

On the classification of binary self-dual codes admitting imprimitive rank 3 permutation groups