On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum. (English) Zbl 1248.15023

In max algebras, a very important problem is the eigenproblem. There exist efficient algorithms for computing both eigenvalues and eigenvectors. The present paper deals with the two-sided generalized eigenproblem over a max algebra which does not seem to be well-known unlike the eigenproblem. The spectrum may include intervals and it is proved that any finite system of real intervals can be represented as spectrum of this eigenproblem.


15A80 Max-plus and related algebras
15A18 Eigenvalues, singular values, and eigenvectors
15A22 Matrix pencils
Full Text: arXiv EuDML Link


[1] Akian, M., Bapat, R., Gaubert, S.: Max-plus algebras. Handbook of Linear Algebra (L. Hogben, Discrete Math. Appl. 39, Chapter 25, Chapman and Hall 2006.
[2] Baccelli, F. L., Cohen, G., Olsder, G.-J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley 1992. · Zbl 0824.93003
[3] Binding, P. A., Volkmer, H.: A generalized eigenvalue problem in the max algebra. Linear Algebra Appl. 422 (2007), 360-371. · Zbl 1121.15011
[4] Brunovsky, P.: A classification of linear controllable systems. Kybernetika 6 (1970), 173-188. · Zbl 0199.48202
[5] Burns, S. M.: Performance Analysis and Optimization of Asynchronous Circuits. PhD Thesis, California Institute of Technology 1991.
[6] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra Appl. 367 (2003), 313-335. · Zbl 1022.15017
[7] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer 2010. · Zbl 1202.15032
[8] Cochet-Terrasson, J., Cohen, G., Gaubert, S., Gettrick, M. M., Quadrat, J. P.: Numerical computation of spectral elements in max-plus algebra. Proc. IFAC Conference on Systems Structure and Control, IRCT, Nantes 1998, pp. 699-706.
[9] Cuninghame-Green, R. A.: Minimax Algebra. Lecture Notes in Econom. and Math. Systems 166, Springer, Berlin 1979. · Zbl 0399.90052
[10] Cuninghame-Green, R. A., Butkovič, P.: The equation \(A\otimes x=B\otimes y\) over (max,+). Theoret. Comput. Sci. 293 (2003), 3-12. · Zbl 1021.65022
[11] Cuninghame-Green, R. A., Butkovič, P.: Generalised eigenproblem in max algebra. Proc. 9th International Workshop WODES 2008, pp. 236-241.
[12] Elsner, L., Driessche, P. van den: Modifying the power method in max algebra. Linear Algebra Appl. 332-334 (2001), 3-13. · Zbl 0982.65042
[13] Gantmacher, F. R.: The Theory of Matrices. Chelsea, 1959. · Zbl 0085.01001
[14] Gaubert, S., Sergeev, S.: The level set method for the two-sided eigenproblem. E-print · Zbl 1279.15024
[15] Heidergott, B., Olsder, G.-J., Woude, J. van der: Max-plus at Work. Princeton Univ. Press, 2005.
[16] McDonald, J. J., Olesky, D. D., Schneider, H., Tsatsomeros, M. J., Driessche, P. van den: Z-pencils. Electron. J. Linear Algebra 4 (1998), 32-38. · Zbl 0907.15010
[17] Mehrmann, V., Nabben, R., Virnik, E.: Generalization of Perron-Frobenius theory to matrix pencils. Linear Algebra Appl. 428 (2008), 20-38. · Zbl 1130.15007
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.