Kybernetika 50 no. 3, 408-435, 2014

Distances on the tropical line determined by two points

María Jesús de la PuenteDOI: 10.14736/kyb-2014-3-0408


Let $p'$ and $q'$ be points in $\R^n$. Write $p'\sim q'$ if $p'-q'$ is a multiple of $(1,\ldots,1)$. Two different points $p$ and $q$ in $\R^n/\sim$ uniquely determine a tropical line $L(p,q)$ passing through them and stable under small perturbations. This line is a balanced unrooted semi-labeled tree on $n$ leaves. It is also a metric graph. If some representatives $p'$ and $q'$ of $p$ and $q$ are the first and second columns of some real normal idempotent order $n$ matrix $A$, we prove that the tree $L(p,q)$ is described by a matrix $F$, easily obtained from $A$. We also prove that $L(p,q)$ is caterpillar. We prove that every vertex in $L(p,q)$ belongs to the tropical linear segment joining $p$ and $q$. A vertex, denoted $pq$, closest (w.r.t tropical distance) to $p$ exists in $L(p,q)$. Same for $q$. The distances between pairs of adjacent vertices in $L(p,q)$ and the distances $\dd(p,pq)$, $\dd(qp,q)$ and $\dd(p,q)$ are certain entries of the matrix $|F|$. In addition, if $p$ and $q$ are generic, then the tree $L(p,q)$ is trivalent. The entries of $F$ are differences (i. e., sum of principal diagonal minus sum of secondary diagonal) of order 2 minors of the first two columns of $A$.


normal matrix, idempotent matrix, tropical distance, integer length, tropical line, caterpillar tree, metric graph


15A80, 14T05


  1. M. Akian, R. Bapat and S. Gaubert: Max-plus algebra. In: Handbook of Linear Algebra (L. Hobgen, ed.), Chapman and Hall, Boca Raton 2007, chapter 25.   CrossRef
  2. F. L. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat: Synchronization and Linearity. John Wiley, Chichester, New York 1992.   CrossRef
  3. M. Baker and X. Faber: Metric properties of the tropical Abel-Jacobi map. J. Algebr. Comb. 33 (2011), 349-381.   CrossRef
  4. L. J. Billera, S. P. Holmes and K. Vogtmann: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27 (2001), 4, 733-767.   CrossRef
  5. E. Brugallé: Un peu de géométrie tropicale. Quadrature 74 (2009), 10-22.   CrossRef
  6. E. Brugallé: Some aspects of tropical geometry. Newsletter Europ. Math. Soc. 83 (2012), 23-28.   CrossRef
  7. P. Butkovič: Simple image set of $(\max,+)$ linear mappings. Discrete Appl. Math. 105 (2000), 73-86.   CrossRef
  8. P. Butkovič: Max-plus Linear Systems: Theory and Algorithms. Springer-Verlag, Berlin 2010.   CrossRef
  9. M. Chan: Tropical hyperelliptic curves. J. Algebr. Comb. 37 (2013), 331-359.   CrossRef
  10. G. Cohen, S. Gaubert and J. P. Quadrat: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379 (2004), 395-422.   CrossRef
  11. R. A. Cuninghame-Green: Minimax algebra. Lecture Notes in Econom and Math. Systems 166, Springer-Verlag, Berlin 1970.   CrossRef
  12. R. A. Cuninghame-Green: Minimax algebra and applications. In: Adv. Imag. Electr. Phys. 90 (P. Hawkes, ed.), Academic Press, New York 1995, pp. 1-121.   CrossRef
  13. R.A. Cuninghame-Green and P. Butkovič: Bases in max-algebra. Linear Algebra Appl. 389 (2004) 107-120.   CrossRef
  14. M. Develin and B. Sturmfels: Tropical convexity. Doc. Math. 9 (2004), 1-27; Erratum in Doc. Math. 9 (electronic) (2004), 205-206.   CrossRef
  15. M. Develin, F. Santos and B. Sturmfels: On the rank of a tropical matrix. In: Discrete and Computational Geometry (E. Goodman, J. Pach and E. Welzl, eds.), MSRI Publications, Cambridge Univ. Press, Cambridge 2005, pp. 213-242.   CrossRef
  16. M. Einsiedler, M. Kapranov and D. Lind: Non-archimedean amoebas and tropical varieties. J. Reine Angew. Math. 601 (2006), 139-157.   CrossRef
  17. A. Gathmann: Tropical algebraic geometry. Jahresber. Deutsch. Math.-Verein 108 (2006), 1, 3-32.   CrossRef
  18. S. Gaubert and Max Plus: Methods and applications of $(\max, +)$ linear algebra.    CrossRef
  19. M. Gondran and M. Minoux: Graphs, Dioids and Semirings. New Models and Algorithms. Springer-Verlag, Berlin 2008.   CrossRef
  20. J. Gunawardena (ed.): Idempotency. Publications of the Newton Institute, Cambridge Univ. Press, Cambridge 1998.   CrossRef
  21. I. Itenberg, E. Brugallé and B. Tessier: Géométrie tropicale. Editions de l'École Polythecnique, Paris, 2008.   CrossRef
  22. I. Itenberg, G. Mikhalkin and E. Shustin: Tropical Algebraic Geometry. Birkh{ä}user, Basel 2007.   CrossRef
  23. M. Johnson and M. Kambites: Idempotent tropical matrices and finite metric spaces. Adv. in Geom. 14 (2014), 2, 253-276. DOI: \href{}{10.1515/advgeom-2013-0034}   CrossRef
  24. A. Jiménez and M. J. de la Puente: Six combinatorial classes of maximal convex tropical polyhedra. ArXiv: \href{}{1205.4162}, 2012.   CrossRef
  25. D. Joyner, A. Ksir and C. G. Melles: Automorphism groups on tropical curves. Some cohomology calculations. Beitr. Algebra Geom. 53 (2012), 1, 41-56.   CrossRef
  26. J. Linde and M. J. de la Puente: Matrices commuting with a given normal tropical matrix. ArXiv: \href{}{1209.0660v2}, 2014.   CrossRef
  27. G. L. Litvinov, V. P. Maslov and (eds.): Idempotent mathematics and mathematical physics. Proc. Vienna 2003, American Mathematical Society, Contemp. Math. 377 (2005).   CrossRef
  28. G. L. Litvinov, S. N. Sergeev and (eds.): Tropical and idempotent mathematics. Proc. Moscow 2007, American Mathematical Society, Contemp. Math. 495 (2009).   CrossRef
  29. G. Mikhalkin: Tropical geometry and its applications. In: Proc. International Congress of Mathematicians, ICM Madrid 2006, (M. Sanz-Sol{é} et al., eds.), Invited lectures, v. II, EMS Ph., Zurich 2006, pp. 827-852.   CrossRef
  30. G. Mikhalkin: Moduli spaces of rational tropical curves. In: Proc. 13th Gökova Geometry-Topology Conference 2006 (S. Akbulut, T. Onder and R. J. Stern, eds.), International Press, Cambridge, MA 2007, pp. 39-51.   CrossRef
  31. G. Mikhalkin: What is a tropical curve? Notices AMS 2007, 511-513.   CrossRef
  32. M. J. de la Puente: On tropical Kleene star matrices and alcoved polytopes. Kybernetika 49 (2013), 6, 897-910.   CrossRef
  33. J. Richter-Gebert, B. Sturmfels and T. Theobald: First steps in tropical geometry. In: \cite{Litvinov_ed}, pp. 289-317.   CrossRef
  34. D. Speyer and B. Sturmfels: The tropical Grassmannian. Adv. Geom. 4 (2004), 389-411.   CrossRef
  35. D. Speyer and B. Sturmfels: Tropical mathematics. Math. Mag. 82 (2009), 163-173.   CrossRef
  36. B. Sturmfels: Solving systems of polynomial equations. CBMS Regional Conference Series in Math. 97, AMS, Providence 2002.   CrossRef
  37. B. Sturmfels and J. Yu: Classification of six-point metrics. Electron. J. Combinatorics 11 (2004), 44 pp.   CrossRef
  38. L. F. Tabera: Tropical constructive Pappus's theorem. IMRN 39 (2005), 2373-2389.   CrossRef
  39. O. Viro: Dequantization of real algebraic geometry on logarithmic paper. European Congress of Mathematics, Vol. I (Barcelona 2000), Prog. Math. 201, Birkh{ä}user, Basel, 2001, pp. 135-146.   CrossRef
  40. O. Viro: On basic concepts of tropical geometry. Proc. Steklov Inst. Math. 273 (2011), 252-282.   CrossRef
  41. E. Wagneur: Finitely generated modulo\"{\i}ds. The existence and unicity problem for bases. In: Analysis and Optimization of Systems, Antibes, 1988 (J. L. Lions and A. Bensoussan, eds.), LNCIS 111, Springer-Verlag, Berlin 1988, pp. 966-976.   CrossRef
  42. M. Yoeli: A note on a generalization of boolean matrix theory. Amer. Math. Monthly 68 (1961), 6, 552-557.   CrossRef
  43. K. Zimmermann: Extremální algebra. Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV 46 (1976), Prague 1976, in Czech.   CrossRef