Geodesic
On tropical Kleene star matrices and alcoved polytopes
Kybernetika, Tome 49 (2013) no. 6, pp. 897-910 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 15A60, 15A80, 52C07
Keywords: tropical algebra; Kleene star; normal matrix; idempotent matrix; alcoved polytope; convex set; norm 
@article{KYB_2013_49_6_a4,
     author = {Puente, Mar{\'\i}a Jes\'us de la},
     title = {On tropical {Kleene} star matrices and alcoved polytopes},
     journal = {Kybernetika},
     pages = {897--910},
     year = {2013},
     volume = {49},
     number = {6},
     mrnumber = {3182647},
     zbl = {1297.15029},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a4/}
}
TY  - JOUR
AU  - Puente, María Jesús de la
TI  - On tropical Kleene star matrices and alcoved polytopes
JO  - Kybernetika
PY  - 2013
SP  - 897
EP  - 910
VL  - 49
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a4/
LA  - en
ID  - KYB_2013_49_6_a4
ER  - 
%0 Journal Article
%A Puente, María Jesús de la
%T On tropical Kleene star matrices and alcoved polytopes
%J Kybernetika
%D 2013
%P 897-910
%V 49
%N 6
%U http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a4/
%G en
%F KYB_2013_49_6_a4
Puente, María Jesús de la. On tropical Kleene star matrices and alcoved polytopes. Kybernetika, Tome 49 (2013) no. 6, pp. 897-910. http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a4/

[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 | MR

[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 | MR | Zbl

[5] Butkovič, P.: Simple image set of $(\max,+)$ linear mappings. Discrete Appl. Math. 105 (2000), 73-86. | DOI | MR | Zbl

[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 | MR | Zbl

[8] Cohen, G., Gaubert, S., Quadrat, J. P.: Duality and separation theorems in idempotent semimodules. Lineal Algebra Appl. 379 (2004), 395-422. | DOI | MR | Zbl

[9] Cuninghame-Green, R.: Minimax algebra. Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1970. | MR | Zbl

[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 | Zbl

[11] Cuninghame-Green, R. A., Butkovič, P.: Bases in max-algebra. Linear Algebra Appl. 389 (2004), 107-120. | DOI | MR | Zbl

[12] Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9 (2004), 1-27; Erratum in Doc. Math. 9 (electronic), (2004), 205-206. | MR | Zbl

[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 | MR | Zbl

[17] Kuhn, H. W.: The Hungarian method for the assignment problem. Naval Res. Logist. 2 (1955), 83-97. | DOI | MR | Zbl

[18] Lam, T., Postnikov, A.: Alcoved polytopes I. Discrete Comput. Geom. 38 (2007), 453-478. | DOI | MR | Zbl

[19] Lam, T., Postnikov, A.: Alcoved polytopes II. arXiv:1202.4015v1, 2012. | MR

[20] Litvinov, G. L., Maslov, V. P.: Idempotent Mathematics and Mathematical Physics. Proc. Vienna 2003, Amer. Math. Soc. Contemp. Math. 377 (2005). | MR | Zbl

[21] Litvinov, G. L., Sergeev, S. N.: Tropical and Idempotent Mathematics. Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009). | MR | Zbl

[22] Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Corrected unabrideged republication by Dover, Mineola 1998. | MR | Zbl

[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

[24] Sergeev, S.: Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl. 421 (2007), 182-201. | DOI | MR | Zbl

[25] Sergeev, S., Scheneider, H., Butkovič, P.: On visualization, subeigenvectors and Kleene stars in max algebra. Linear Algebra Appl. 431 (2009), 2395-2406. | MR

[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 | MR | Zbl

[28] Zimmermann, K.: Extremální algebra. (In Czech.). Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV, 46, Prague 1976.