Max-plus definite matrix closures and their eigenspaces. (English) Zbl 1131.15009

This paper provides a contribution to the geometrical understanding of earlier algebraic results on max-plus eigenspaces [cf. P. Butkovič, Discrete Appl. Math. 105, 73–86 (2000; Zbl 0976.15013); P. Butkovič and R. A. Cuninghame-Green, Linear Algebra Appl. 421, No. 2–3, 370–381 (2007; Zbl 1131.15008)] by regarding the max-plus semiring \(\mathbb R _{\max}:= \mathbb R \cup \{-\infty\}\) with its simplifying total order and using basic tools of max-algebra.
Definite forms for a given matrix \(A= (a_{ij}) \in \mathbb R^{n\times n}_{\max}\) with nonzero (finite) permanent are considered and it is shown that the closures of all of them coincide, so resulting in the “definite closure” operation. The author presents a description of the eigenspace \(eig(A)\) and the faces of it for a definite matrix \(A\). Employing a representation (op. cit.), he concludes that \(eig(A)\) has a non-empty interior if and only if \(A\) has a strong permanent. Finally, this interior is fully detailed by means of Hilbert distances.


15A18 Eigenvalues, singular values, and eigenvectors
06F15 Ordered groups
15A30 Algebraic systems of matrices
15B33 Matrices over special rings (quaternions, finite fields, etc.)
Full Text: DOI arXiv


[1] Baccelli, F.; Cohen, G.; Olsder, G.-J.; Quadrat, J.-P., Synchronization and linearity. an algebra for discrete event systems, (1992), Wiley New York
[2] Butkovič, P., Simple image set of (MAX,+) linear mappings, Discrete appl. math., 105, 73-86, (2000) · Zbl 0976.15013
[3] Butkovič, P., MAX-algebra: linear algebra of combinatorics?, Linear algebra appl., 367, 313-335, (2003) · Zbl 1022.15017
[4] Carré, B.A., An algebra for network routing problems, J. inst. math. appl., 7, 273-299, (1971) · Zbl 0219.90020
[5] Cohen, G.; Gaubert, S.; Quadrat, J.-P., Duality and separation theorems in idempotent semimodules, Linear algebra appl., 379, 395-422, (2004), Available from: · Zbl 1042.46004
[6] Cuninghame-Green, R.A., Minimax algebra, Lecture notes in economics and mathematical systems, vol. 166, (1979), Springer Berlin
[7] Cuninghame-Green, R.A.; Butkovič, P., Bases in MAX-algebra, Linear algebra appl., 389, 107-120, (2004) · Zbl 1059.15001
[8] Develin, M.; Santos, F.; Sturmfels, B., On the rank of a tropical matrix, (), 213-242, Available from: · Zbl 1095.15001
[9] Develin, M.; Sturmfels, B., Tropical convexity, Doc. math., 9, 1-27, (2004), Available from: · Zbl 1054.52004
[10] S. Gaubert, Théorie des Systèmes Linéaires dans les Dioïdes, Thèse, Ecole des Mines des Paris, Paris, 1992.
[11] Kolokoltsov, V.N.; Maslov, V.P., Idempotent analysis and its applications, (1997), Kluwer Academic Publishers Dordrecht · Zbl 0941.93001
[12] G.L. Litvinov, V.P. Maslov, Correspondence principle for idempotent calculus and some computer applications, Bures-Sur-Yvette: Institut des Hautes Etudes Scientifiques (IHES/M/95/33), 1995; See also: J. Gunawardena (Ed.), Idempotency, Publ. of the I. Newton Institute, Cambridge University Press, 1998, pp. 420-443. · Zbl 0897.68050
[13] Litvinov, G.L.; Maslov, V.P.; Shpiz, G.B., Idempotent functional analysis: an algebraical approach, Math. notes, 69, 5, 696-729, (2001), Available from: · Zbl 1017.46034
[14] Litvinov, G.L.; Maslova, E.V., Universal numerical algorithms and their software implementation, Program. comput. software, 26, 5, 275-280, (2000) · Zbl 0968.68194
[15] P. Moller, Théorie Algébraique des Systèmes à Evénements Discrets, Thèse, Ecole des Mines des Paris, Paris, 1988.
[16] Rote, G., A systolic array algorithm for the algebraic path problem, Computing, 34, 191-219, (1985) · Zbl 0562.68056
[17] E. Wagneur, Moduloids and Pseudomodules-1-dimension theory, in: J.L. Lions, A. Bensoussan (Eds.), Analysis and Optimization of Systems, Lecture Notes in Control and Information Sciences, 1988. · Zbl 0757.06008
[18] Wagneur, E., Moduloids and pseudomodules-1-dimension theory, Discrete math., 98, 57-73, (1991) · Zbl 0757.06008
[19] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, (1981), North Holland Amsterdam · Zbl 0466.90045
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.