On tropical Kleene star matrices and alcoved polytopes. (English) Zbl 1297.15029

A matrix \(A = (a_{ij}) \in {\mathbb R}^{n \times n}\) with zero diagonal induces the (possibly empty) alcoved polytope \[ C_A := \left\{ x \in {\mathbb R}^{n-1} : a_{in} \leq x_i \leq -a_{ni}, \, a_{ik} \leq x_i-x_k \leq -a_{ki}; \, i,k=1,\ldots,n-1; i \not= k \right\}. \] Then the main result of the paper states that a matrix \(A\) of the mentioned type is a Kleene star if and only if \[ C_A = \text{span}(A) \cap \left\{ x_n = 0 \right\}. \] The author gives an application of this to alcoved polytopes using normal idempotent matrices which form a subclass of Kleene stars: If \(A\) is a normal matrix, then \[ ||| A ||| = r (\text{span}(A) \cap \left\{ x_n=0 \right\}), \] where \(|||A||| := \text{max}_{i,j}|a_{ij}|\), and where \(r\) denotes the tropical radius of a subset of \({\mathbb R}^{n-1}\) containing the origin. If, in addition, \(A\) is idempotent then \(|||A||| = r(C_A)\).


15A80 Max-plus and related algebras
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
Full Text: arXiv Link


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