Kybernetika 49 no. 6, 897-910, 2013

On tropical Kleene star matrices and alcoved polytopes

María Jesús de la Puente

Abstract:

In this paper we give a short, elementary proof of a known result in tropical mathematics, by which the convexity of the column span of a zero-diagonal real matrix $A$ is characterized by $A$ being a Kleene star. We give applications to alcoved polytopes, using normal idempotent matrices (which form a subclass of Kleene stars). For a normal matrix we define a norm and show that this is the radius of a hyperplane section of its tropical span.

Keywords:

tropical algebra, Kleene star, normal matrix, idempotent matrix, alcoved polytope, convex set, norm

Classification:

15A80, 52C07, 15A60

paper.pdf

References:

  1. M. Akian, R. Bapat and S. Gaubert: Max-plus algebra. In: Handbook of Linear Algebra, Chapter 25, (L. Hobgen, ed.), Chapman and Hall, Boca Raton 2007.   CrossRef
  2. X. Allamigeon, S. Gaubert and E. Goubault: Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete Comput. Geom. 49 (2013), 247-279.   CrossRef
  3. F. L. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat: Syncronization and Linearity. John Wiley, Chichester 1992.   CrossRef
  4. P. Butkovič: Max-algebra: the linear algebra of combinatorics? Linear Algebra Appl. 367 (2003), 313-335.   CrossRef
  5. P. Butkovič: Simple image set of $(\max,+)$ linear mappings. Discrete Appl. Math. 105 (2000), 73-86.   CrossRef
  6. P. Butkovič: Max-plus Linear Systems: Theory and Algorithms. Springer, Berlin 2010.   CrossRef
  7. P. Butkovič, H. Schneider and S. Sergeev: Generators, extremals and bases of max-cones. Linear Algebra Appl. 421 (2007), 394-406.   CrossRef
  8. G. Cohen, S. Gaubert and J. P. Quadrat: Duality and separation theorems in idempotent semimodules. Lineal Algebra Appl. 379 (2004), 395-422.   CrossRef
  9. R. Cuninghame-Green: Minimax algebra. Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1970.   CrossRef
  10. R. A. Cuninghame-Green: Minimax algebra and applications. In: Adv. Imag. Electr. Phys. 90, (P. Hawkes, ed.), Academic Press, San Diego 1995, pp. 1-121.   CrossRef
  11. R. A. Cuninghame-Green and P. Butkovič: Bases in max-algebra. Linear Algebra Appl. 389 (2004), 107-120.   CrossRef
  12. M. Develin and B. Sturmfels: Tropical convexity. Doc. Math. 9 (2004), 1-27; Erratum in Doc. Math. 9 (electronic), (2004), 205-206.   CrossRef
  13. Z. Izhakian, M. Johnson and M. Kambites: Pure dimension and projectivity of tropical politopes. arXiv: 1106.4525v2, 2012.   CrossRef
  14. A. Jiménez and M. J. de la Puente: Six combinatorial classes of maximal convex tropical polyhedra. arXiv: 1205.4162, 2012.   CrossRef
  15. M. Johnson and M. Kambites: Idempotent tropical matrices and finite metric spaces. To appear in Adv. Geom.; arXiv: 1203.2480, 2012.   CrossRef
  16. M. Joswig and K. Kulas: Tropical and ordinary convexity combined. Adv. Geom. 10 (2010), 333-352.   CrossRef
  17. H. W. Kuhn: The Hungarian method for the assignment problem. Naval Res. Logist. 2 (1955), 83-97.   CrossRef
  18. T. Lam and A. Postnikov: Alcoved polytopes I. Discrete Comput. Geom. 38 (2007), 453-478.   CrossRef
  19. T. Lam and A. Postnikov: Alcoved polytopes II. arXiv:1202.4015v1, 2012.   CrossRef
  20. G. L. Litvinov, V. P. Maslov and (eds.): Idempotent Mathematics and Mathematical Physics. Proc. Vienna 2003, Amer. Math. Soc. Contemp. Math. 377 (2005).   CrossRef
  21. G. L. Litvinov, S. N. Sergeev and (eds.): Tropical and Idempotent Mathematics. Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009).   CrossRef
  22. C. H. Papadimitriou and K. Steiglitz: Combinatorial optimization: algorithms and complexity. Corrected unabrideged republication by Dover, Mineola 1998.   CrossRef
  23. S. Sergeev: Multiorder, Kleene stars and cyclic proyectors in the geometry of max cones. In: \cite{Litvinov_ed_2}.   CrossRef
  24. S. Sergeev: Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl. 421 (2007), 182-201.   CrossRef
  25. S. Sergeev, H. Scheneider and P. Butkovič: On visualization, subeigenvectors and Kleene stars in max algebra. Linear Algebra Appl. 431 (2009), 2395-2406.   CrossRef
  26. A. Werner and J. Yu: Symmetric alcoved polytopes. arXiv: 1201.4378v1, 2012.   CrossRef
  27. M. Yoeli: A note on a generalization of boolean matrix theory. Amer. Math. Monthly 68 (1961) 552-557.   CrossRef
  28. K. Zimmermann: Extremální algebra. (In Czech.) Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV, 46, Prague 1976.   CrossRef