Distances on the tropical line determined by two points

María Jesús de la Puente

Kybernetika (2014)

  • Volume: 50, Issue: 3, page 408-435
  • ISSN: 0023-5954

Abstract

top
Let p ' and q ' be points in ℝ n . Write p ' ∼ q ' if p ' - q ' is a multiple of ( 1 , ... , 1 ) . Two different points p and q in ℝ n / ∼ 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 p q , 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 d ( p , p q ) , d ( q p , q ) and d ( 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 .

How to cite

top

Puente, María Jesús de la. "Distances on the tropical line determined by two points." Kybernetika 50.3 (2014): 408-435. <http://eudml.org/doc/261938>.

@article{Puente2014,
abstract = {Let $p^\{\prime \}$ and $q^\{\prime \}$ be points in $\mathbb \{R\}^n$. Write $p^\{\prime \}\sim q^\{\prime \}$ if $p^\{\prime \}-q^\{\prime \}$ is a multiple of $(1,\ldots ,1)$. Two different points $p$ and $q$ in $\mathbb \{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^\{\prime \}$ and $q^\{\prime \}$ 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 $\operatorname\{d\}(p,pq)$, $\operatorname\{d\}(qp,q)$ and $\operatorname\{d\}(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$.},
author = {Puente, María Jesús de la},
journal = {Kybernetika},
keywords = {tropical distance; integer length; tropical line; normal matrix; idempotent matrix; caterpillar tree; metric graph; tropical distance; integer length; tropical line; normal matrix; idempotent matrix; caterpillar tree; metric graph},
language = {eng},
number = {3},
pages = {408-435},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distances on the tropical line determined by two points},
url = {http://eudml.org/doc/261938},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Puente, María Jesús de la
TI - Distances on the tropical line determined by two points
JO - Kybernetika
PY - 2014
PB - Institute of Information Theory and Automation AS CR
VL - 50
IS - 3
SP - 408
EP - 435
AB - Let $p^{\prime }$ and $q^{\prime }$ be points in $\mathbb {R}^n$. Write $p^{\prime }\sim q^{\prime }$ if $p^{\prime }-q^{\prime }$ is a multiple of $(1,\ldots ,1)$. Two different points $p$ and $q$ in $\mathbb {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^{\prime }$ and $q^{\prime }$ 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 $\operatorname{d}(p,pq)$, $\operatorname{d}(qp,q)$ and $\operatorname{d}(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$.
LA - eng
KW - tropical distance; integer length; tropical line; normal matrix; idempotent matrix; caterpillar tree; metric graph; tropical distance; integer length; tropical line; normal matrix; idempotent matrix; caterpillar tree; metric graph
UR - http://eudml.org/doc/261938
ER -

References

top
  1. Akian, M., Bapat, R., Gaubert, S., Max-plus algebra., In: Handbook of Linear Algebra (L. Hobgen, ed.), Chapman and Hall, Boca Raton 2007, chapter 25. 
  2. Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P., Synchronization and Linearity., John Wiley, Chichester, New York 1992. Zbl0824.93003MR1204266
  3. Baker, M., Faber, X., 10.1007/s10801-010-0247-3, J. Algebr. Comb. 33 (2011), 349-381. Zbl1215.14060MR2772537DOI10.1007/s10801-010-0247-3
  4. Billera, L. J., Holmes, S. P., Vogtmann, K., 10.1006/aama.2001.0759, Adv. Appl. Math. 27 (2001), 4, 733-767. Zbl0995.92035MR1867931DOI10.1006/aama.2001.0759
  5. Brugallé, E., 10.1051/quadrature/2009015, Quadrature 74 (2009), 10-22. Zbl1202.14055DOI10.1051/quadrature/2009015
  6. Brugallé, E., Some aspects of tropical geometry., Newsletter Europ. Math. Soc. 83 (2012), 23-28. Zbl1285.14069MR2934649
  7. Butkovič, P., 10.1016/S0166-218X(00)00212-2, Discrete Appl. Math. 105 (2000), 73-86. MR1780462DOI10.1016/S0166-218X(00)00212-2
  8. Butkovič, P., Max-plus Linear Systems: Theory and Algorithms., Springer-Verlag, Berlin 2010. MR2681232
  9. Chan, M., 10.1007/s10801-012-0369-x, J. Algebr. Comb. 37 (2013), 331-359. Zbl1266.14050MR3011346DOI10.1007/s10801-012-0369-x
  10. Cohen, G., Gaubert, S., Quadrat, J. P., Duality and separation theorems in idempotent semimodules., Linear Algebra Appl. 379 (2004), 395-422. Zbl1042.46004MR2039751
  11. Cuninghame-Green, R. A., Minimax algebra., Lecture Notes in Econom and Math. Systems 166, Springer-Verlag, Berlin 1970. Zbl0739.90073MR0580321
  12. Cuninghame-Green, R. A., Minimax algebra and applications., In: Adv. Imag. Electr. Phys. 90 (P. Hawkes, ed.), Academic Press, New York 1995, pp. 1-121. Zbl0739.90073
  13. Cuninghame-Green, R.A., Butkovič, P., 10.1016/j.laa.2004.03.022, Linear Algebra Appl. 389 (2004) 107-120. Zbl1059.15001MR2080398DOI10.1016/j.laa.2004.03.022
  14. Develin, M., Sturmfels, B., Tropical convexity., Doc. Math. 9 (2004), 1-27; Erratum in Doc. Math. 9 (electronic) (2004), 205-206. Zbl1054.52004MR2054977
  15. Develin, M., Santos, F., Sturmfels, B., 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. Zbl1095.15001MR2178322
  16. Einsiedler, M., Kapranov, M., Lind, D., Non-archimedean amoebas and tropical varieties., J. Reine Angew. Math. 601 (2006), 139-157. Zbl1115.14051MR2289207
  17. Gathmann, A., Tropical algebraic geometry., Jahresber. Deutsch. Math.-Verein 108 (2006), 1, 3-32. Zbl1109.14038MR2219706
  18. Gaubert, S., Plus, Max, Methods and applications of ( max , + ) linear algebra. 
  19. Gondran, M., Minoux, M., Graphs, Dioids and Semirings. New Models and Algorithms., Springer-Verlag, Berlin 2008. Zbl1201.16038MR2389137
  20. (ed.), J. Gunawardena, Idempotency., Publications of the Newton Institute, Cambridge Univ. Press, Cambridge 1998. Zbl1144.68006MR1608365
  21. Itenberg, I., Brugallé, E., Tessier, B., Géométrie tropicale., Editions de l'École Polythecnique, Paris, 2008. 
  22. Itenberg, I., Mikhalkin, G., Shustin, E., Tropical Algebraic Geometry., Birkhäuser, Basel 2007. Zbl1165.14002MR2292729
  23. Johnson, M., Kambites, M., 10.1515/advgeom-2013-0034, Adv. in Geom. 14 (2014), 2, 253-276. DOI: 10.1515/advgeom-2013-0034 (http://dx.doi.org/10.1515/advgeom-2013-0034) DOI10.1515/advgeom-2013-0034
  24. Jiménez, A., Puente, M. J. de la, Six combinatorial classes of maximal convex tropical polyhedra., ArXiv: 1205.4162 (http://arxiv.org/abs/1205.4162), 2012. 
  25. Joyner, D., Ksir, A., Melles, C. G., 10.1007/s13366-011-0049-3, Beitr. Algebra Geom. 53 (2012), 1, 41-56. Zbl1286.14077MR2890362DOI10.1007/s13366-011-0049-3
  26. Linde, J., Puente, M. J. de la, Matrices commuting with a given normal tropical matrix., ArXiv: 1209.0660v2 (http://arxiv.org/abs/1209.0660), 2014. 
  27. Litvinov, G. L., Maslov, V. P., Idempotent mathematics and mathematical physics., Proc. Vienna 2003, American Mathematical Society, Contemp. Math. 377 (2005). Zbl1069.00011MR2145152
  28. Litvinov, G. L., Sergeev, S. N., Tropical and idempotent mathematics., Proc. Moscow 2007, American Mathematical Society, Contemp. Math. 495 (2009). Zbl1172.00019MR2581510
  29. Mikhalkin, G., 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. Zbl1103.14034MR2275625
  30. Mikhalkin, G., 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. Zbl1203.14027MR2404949
  31. Mikhalkin, G., What is a tropical curve?, Notices AMS 2007, 511-513. MR2305295
  32. Puente, M. J. de la, On tropical Kleene star matrices and alcoved polytopes., Kybernetika 49 (2013), 6, 897-910. MR3182647
  33. Richter-Gebert, J., Sturmfels, B., Theobald, T., First steps in tropical geometry., In: [27], pp. 289-317. Zbl1093.14080MR2149011
  34. Speyer, D., Sturmfels, B., 10.1515/advg.2004.023, Adv. Geom. 4 (2004), 389-411. Zbl1065.14071MR2071813DOI10.1515/advg.2004.023
  35. Speyer, D., Sturmfels, B., 10.4169/193009809X468760, Math. Mag. 82 (2009), 163-173. Zbl1227.14051MR2522909DOI10.4169/193009809X468760
  36. Sturmfels, B., Solving systems of polynomial equations., CBMS Regional Conference Series in Math. 97, AMS, Providence 2002. Zbl1101.13040MR1925796
  37. Sturmfels, B., Yu, J., Classification of six-point metrics., Electron. J. Combinatorics 11 (2004), 44 pp. Zbl1053.52019MR2097310
  38. Tabera, L. F., 10.1155/IMRN.2005.2373, IMRN 39 (2005), 2373-2389. MR2181355DOI10.1155/IMRN.2005.2373
  39. Viro, O., 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. Zbl1024.14026MR1905317
  40. Viro, O., On basic concepts of tropical geometry., Proc. Steklov Inst. Math. 273 (2011), 252-282. Zbl1237.14074MR2893551
  41. Wagneur, E., Finitely generated moduloï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. MR0956331
  42. Yoeli, M., 10.2307/2311149, Amer. Math. Monthly 68 (1961), 6, 552-557. Zbl0115.02103MR0126472DOI10.2307/2311149
  43. Zimmermann, K., Extremální algebra., Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV 46 (1976), Prague 1976, in Czech. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.