| Title:
|
On tropical Kleene star matrices and alcoved polytopes (English) |
| Author:
|
Puente, María Jesús de la |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
49 |
| Issue:
|
6 |
| Year:
|
2013 |
| Pages:
|
897-910 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
tropical algebra |
| Keyword:
|
Kleene star |
| Keyword:
|
normal matrix |
| Keyword:
|
idempotent matrix |
| Keyword:
|
alcoved polytope |
| Keyword:
|
convex set |
| Keyword:
|
norm |
| MSC:
|
15A60 |
| MSC:
|
15A80 |
| MSC:
|
52C07 |
| idZBL:
|
Zbl 1297.15029 |
| idMR:
|
MR3182647 |
| . |
| Date available:
|
2014-01-27T12:28:48Z |
| Last updated:
|
2015-03-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143578 |
| . |
| Reference:
|
[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. |
| Reference:
|
[2] Allamigeon, X., Gaubert, S., Goubault, E.: Computing the vertices of tropical polyhedra using directed hypergraphs..Discrete Comput. Geom. 49 (2013), 247-279. MR 3017909, 10.1007/s00454-012-9469-6 |
| Reference:
|
[3] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P.: Syncronization and Linearity..John Wiley, Chichester 1992. |
| Reference:
|
[4] Butkovič, P.: Max-algebra: the linear algebra of combinatorics?.Linear Algebra Appl. 367 (2003), 313-335. Zbl 1022.15017, MR 1976928, 10.1016/S0024-3795(02)00655-9 |
| Reference:
|
[5] Butkovič, P.: Simple image set of $(\max,+)$ linear mappings..Discrete Appl. Math. 105 (2000), 73-86. Zbl 0976.15013, MR 1780462, 10.1016/S0166-218X(00)00212-2 |
| Reference:
|
[6] Butkovič, P.: Max-plus Linear Systems: Theory and Algorithms..Springer, Berlin 2010. |
| Reference:
|
[7] Butkovič, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max-cones..Linear Algebra Appl. 421 (2007), 394-406. Zbl 1119.15018, MR 2294351, 10.1016/j.laa.2006.10.004 |
| Reference:
|
[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, MR 2039751, 10.1016/j.laa.2003.08.010 |
| Reference:
|
[9] Cuninghame-Green, R.: Minimax algebra..Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1970. Zbl 0739.90073, MR 0580321 |
| Reference:
|
[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. Zbl 0739.90073, MR 0403664 |
| Reference:
|
[11] Cuninghame-Green, R. A., Butkovič, P.: Bases in max-algebra..Linear Algebra Appl. 389 (2004), 107-120. Zbl 1059.15001, MR 2080398, 10.1016/j.laa.2004.03.022 |
| Reference:
|
[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, MR 2054977 |
| Reference:
|
[13] Izhakian, Z., Johnson, M., Kambites, M.: Pure dimension and projectivity of tropical politopes..arXiv: 1106.4525v2, 2012. |
| Reference:
|
[14] Jiménez, A., Puente, M. J. de la: Six combinatorial classes of maximal convex tropical polyhedra..arXiv: 1205.4162, 2012. |
| Reference:
|
[15] Johnson, M., Kambites, M.: Idempotent tropical matrices and finite metric spaces..To appear in Adv. Geom.; arXiv: 1203.2480, 2012. |
| Reference:
|
[16] Joswig, M., Kulas, K.: Tropical and ordinary convexity combined..Adv. Geom. 10 (2010), 333-352. Zbl 1198.14060, MR 2629819, 10.1515/advgeom.2010.012 |
| Reference:
|
[17] Kuhn, H. W.: The Hungarian method for the assignment problem..Naval Res. Logist. 2 (1955), 83-97. Zbl 1187.90015, MR 0075510, 10.1002/nav.3800020109 |
| Reference:
|
[18] Lam, T., Postnikov, A.: Alcoved polytopes I..Discrete Comput. Geom. 38 (2007), 453-478. Zbl 1134.52019, MR 2352704, 10.1007/s00454-006-1294-3 |
| Reference:
|
[19] Lam, T., Postnikov, A.: Alcoved polytopes II..arXiv:1202.4015v1, 2012. MR 2352704 |
| Reference:
|
[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, MR 2145152 |
| Reference:
|
[21] Litvinov, G. L., Sergeev, S. N.: Tropical and Idempotent Mathematics..Proc. Moscow 2007, Amer. Math. Soc. Contemp. Math. 495 (2009). Zbl 1172.00019, MR 2581510 |
| Reference:
|
[22] Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity..Corrected unabrideged republication by Dover, Mineola 1998. Zbl 0944.90066, MR 1637890 |
| Reference:
|
[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 |
| Reference:
|
[24] Sergeev, S.: Max-plus definite matrix closures and their eigenspaces..Linear Algebra Appl. 421 (2007), 182-201. Zbl 1131.15009, MR 2294335, 10.1016/j.laa.2006.02.038 |
| Reference:
|
[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 |
| Reference:
|
[26] Werner, A., Yu, J.: Symmetric alcoved polytopes..arXiv: 1201.4378v1, 2012. |
| Reference:
|
[27] Yoeli, M.: A note on a generalization of boolean matrix theory..Amer. Math. Monthly 68 (1961) 552-557. Zbl 0115.02103, MR 0126472, 10.2307/2311149 |
| Reference:
|
[28] Zimmermann, K.: Extremální algebra. (In Czech.).Výzkumná publikace ekonomicko-matematické laboratoře při ekonomickém ústavu ČSAV, 46, Prague 1976. |
| . |
