Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
tropical algebra; Kleene star; normal matrix; idempotent matrix; alcoved polytope; convex set; norm
tropical algebra; Kleene star; normal matrix; idempotent matrix; alcoved polytope; convex set; norm
Summary:
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.
References:
[1] Akian, M., Bapat, R., Gaubert, S.: Max-plus algebra. In: Handbook of Linear Algebra, Chapter 25, (L. Hobgen, ed.), Chapman and Hall, Boca Raton 2007.
[2] Allamigeon, X., Gaubert, S., Goubault, E.: Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete Comput. Geom. 49 (2013), 247-279. DOI 10.1007/s00454-012-9469-6 | MR 3017909
[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. DOI 10.1016/S0024-3795(02)00655-9 | MR 1976928 | Zbl 1022.15017
[5] Butkovič, P.: Simple image set of $(\max,+)$ linear mappings. Discrete Appl. Math. 105 (2000), 73-86. DOI 10.1016/S0166-218X(00)00212-2 | MR 1780462 | Zbl 0976.15013
[6] Butkovič, P.: Max-plus Linear Systems: Theory and Algorithms. Springer, Berlin 2010.
[7] Butkovič, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max-cones. Linear Algebra Appl. 421 (2007), 394-406. DOI 10.1016/j.laa.2006.10.004 | MR 2294351 | 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. DOI 10.1016/j.laa.2003.08.010 | MR 2039751 | Zbl 1042.46004
[9] Cuninghame-Green, R.: Minimax algebra. Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1970. MR 0580321 | Zbl 0739.90073
[10] Cuninghame-Green, R. A.: Minimax algebra and applications. In: Adv. Imag. Electr. Phys. 90, (P. Hawkes, ed.), Academic Press, San Diego 1995, pp. 1-121. MR 0403664 | Zbl 0739.90073
[11] Cuninghame-Green, R. A., Butkovič, P.: Bases in max-algebra. Linear Algebra Appl. 389 (2004), 107-120. DOI 10.1016/j.laa.2004.03.022 | MR 2080398 | 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. MR 2054977 | Zbl 1054.52004
[13] Izhakian, Z., Johnson, M., Kambites, M.: Pure dimension and projectivity of tropical politopes. arXiv: 1106.4525v2, 2012.
[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.
[16] Joswig, M., Kulas, K.: Tropical and ordinary convexity combined. Adv. Geom. 10 (2010), 333-352. DOI 10.1515/advgeom.2010.012 | MR 2629819 | Zbl 1198.14060
[17] Kuhn, H. W.: The Hungarian method for the assignment problem. Naval Res. Logist. 2 (1955), 83-97. DOI 10.1002/nav.3800020109 | MR 0075510 | Zbl 1187.90015
[18] Lam, T., Postnikov, A.: Alcoved polytopes I. Discrete Comput. Geom. 38 (2007), 453-478. DOI 10.1007/s00454-006-1294-3 | MR 2352704 | Zbl 1134.52019
[19] Lam, T., Postnikov, A.: Alcoved polytopes II. arXiv:1202.4015v1, 2012. MR 2352704
[20] Litvinov, G. L., Maslov, V. P.: Idempotent Mathematics and Mathematical Physics. Proc. Vienna 2003, Amer. Math. Soc. Contemp. Math. 377 (2005). MR 2145152 | Zbl 1069.00011
[21] Litvinov, G. L., Sergeev, S. N.: Tropical and Idempotent Mathematics. Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009). MR 2581510 | Zbl 1172.00019
[22] Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Corrected unabrideged republication by Dover, Mineola 1998. MR 1637890 | Zbl 0944.90066
[23] Sergeev, S.: Multiorder, Kleene stars and cyclic proyectors in the geometry of max cones. In: Litvinov, G. L., Sergeev, S. N.: Tropical and Idempotent Mathematics. Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009). MR 2581526
[24] Sergeev, S.: Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl. 421 (2007), 182-201. DOI 10.1016/j.laa.2006.02.038 | MR 2294335 | 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. MR 2563030
[26] Werner, A., Yu, J.: Symmetric alcoved polytopes. arXiv: 1201.4378v1, 2012.
[27] Yoeli, M.: A note on a generalization of boolean matrix theory. Amer. Math. Monthly 68 (1961) 552-557. DOI 10.2307/2311149 | MR 0126472 | 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.
Search
Partner of
