On tropical Kleene star matrices and alcoved polytopes

María Jesús de la Puente

Kybernetika (2013)

  • Volume: 49, Issue: 6, page 897-910
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Puente, María Jesús de la. "On tropical Kleene star matrices and alcoved polytopes." Kybernetika 49.6 (2013): 897-910. <http://eudml.org/doc/260833>.

@article{Puente2013,
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.},
author = {Puente, María Jesús de la},
journal = {Kybernetika},
keywords = {tropical algebra; Kleene star; normal matrix; idempotent matrix; alcoved polytope; convex set; norm; tropical algebra; Kleene star matrices; normal idempotent matrices; alcoved polytopes; convex sets; matrix norms},
language = {eng},
number = {6},
pages = {897-910},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On tropical Kleene star matrices and alcoved polytopes},
url = {http://eudml.org/doc/260833},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Puente, María Jesús de la
TI - On tropical Kleene star matrices and alcoved polytopes
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 6
SP - 897
EP - 910
AB - 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.
LA - eng
KW - tropical algebra; Kleene star; normal matrix; idempotent matrix; alcoved polytope; convex set; norm; tropical algebra; Kleene star matrices; normal idempotent matrices; alcoved polytopes; convex sets; matrix norms
UR - http://eudml.org/doc/260833
ER -

References

top
  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., 10.1007/s00454-012-9469-6, Discrete Comput. Geom. 49 (2013), 247-279. MR3017909DOI10.1007/s00454-012-9469-6
  3. Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P., Syncronization and Linearity., John Wiley, Chichester 1992. 
  4. Butkovič, P., 10.1016/S0024-3795(02)00655-9, Linear Algebra Appl. 367 (2003), 313-335. Zbl1022.15017MR1976928DOI10.1016/S0024-3795(02)00655-9
  5. Butkovič, P., 10.1016/S0166-218X(00)00212-2, Discrete Appl. Math. 105 (2000), 73-86. Zbl0976.15013MR1780462DOI10.1016/S0166-218X(00)00212-2
  6. Butkovič, P., Max-plus Linear Systems: Theory and Algorithms., Springer, Berlin 2010. 
  7. Butkovič, P., Schneider, H., Sergeev, S., 10.1016/j.laa.2006.10.004, Linear Algebra Appl. 421 (2007), 394-406. Zbl1119.15018MR2294351DOI10.1016/j.laa.2006.10.004
  8. Cohen, G., Gaubert, S., Quadrat, J. P., 10.1016/j.laa.2003.08.010, Lineal Algebra Appl. 379 (2004), 395-422. Zbl1042.46004MR2039751DOI10.1016/j.laa.2003.08.010
  9. Cuninghame-Green, R., Minimax algebra., Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1970. Zbl0739.90073MR0580321
  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. Zbl0739.90073MR0403664
  11. 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
  12. Develin, M., Sturmfels, B., Tropical convexity., Doc. Math. 9 (2004), 1-27; Erratum in Doc. Math. 9 (electronic), (2004), 205-206. Zbl1054.52004MR2054977
  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., 10.1515/advgeom.2010.012, Adv. Geom. 10 (2010), 333-352. Zbl1198.14060MR2629819DOI10.1515/advgeom.2010.012
  17. Kuhn, H. W., 10.1002/nav.3800020109, Naval Res. Logist. 2 (1955), 83-97. Zbl1187.90015MR0075510DOI10.1002/nav.3800020109
  18. Lam, T., Postnikov, A., 10.1007/s00454-006-1294-3, Discrete Comput. Geom. 38 (2007), 453-478. Zbl1134.52019MR2352704DOI10.1007/s00454-006-1294-3
  19. Lam, T., Postnikov, A., Alcoved polytopes II., arXiv:1202.4015v1, 2012. MR2352704
  20. Litvinov, G. L., Maslov, V. P., Idempotent Mathematics and Mathematical Physics., Proc. Vienna 2003, Amer. Math. Soc. Contemp. Math. 377 (2005). Zbl1069.00011MR2145152
  21. Litvinov, G. L., Sergeev, S. N., Tropical and Idempotent Mathematics., Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009). Zbl1172.00019MR2581510
  22. Papadimitriou, C. H., Steiglitz, K., Combinatorial optimization: algorithms and complexity., Corrected unabrideged republication by Dover, Mineola 1998. Zbl0944.90066MR1637890
  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). MR2581526
  24. Sergeev, S., 10.1016/j.laa.2006.02.038, Linear Algebra Appl. 421 (2007), 182-201. Zbl1131.15009MR2294335DOI10.1016/j.laa.2006.02.038
  25. Sergeev, S., Scheneider, H., Butkovič, P., On visualization, subeigenvectors and Kleene stars in max algebra., Linear Algebra Appl. 431 (2009), 2395-2406. MR2563030
  26. Werner, A., Yu, J., Symmetric alcoved polytopes., arXiv: 1201.4378v1, 2012. 
  27. Yoeli, M., 10.2307/2311149, Amer. Math. Monthly 68 (1961) 552-557. Zbl0115.02103MR0126472DOI10.2307/2311149
  28. Zimmermann, K., Extremální algebra. (In Czech.), Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV, 46, Prague 1976. 

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.