Previous |  Up |  Next


extremal algebra; tropical algebra; generalized eigenproblem
We consider the two-sided eigenproblem $A\otimes x=\lambda\otimes B\otimes x$ over max algebra. It is shown that any finite system of real intervals and points can be represented as spectrum of this eigenproblem.
[1] Akian, M., Bapat, R., Gaubert, S.: Max-plus algebras. In: Handbook of Linear Algebra (L. Hogben, ed.), Discrete Math. Appl. 39, Chapter 25, Chapman and Hall 2006. DOI 10.1201/9781420010572.ch25
[2] Baccelli, F. L., Cohen, G., Olsder, G.-J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley 1992. MR 1204266 | Zbl 0824.93003
[3] Binding, P. A., Volkmer, H.: A generalized eigenvalue problem in the max algebra. Linear Algebra Appl. 422 (2007), 360–371. MR 2305125 | Zbl 1121.15011
[4] Brunovsky, P.: A classification of linear controllable systems. Kybernetika 6 (1970), 173–188. MR 0284247 | Zbl 0199.48202
[5] Burns, S. M.: Performance Analysis and Optimization of Asynchronous Circuits. PhD Thesis, California Institute of Technology 1991. MR 2686560
[6] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra Appl. 367 (2003), 313–335. MR 1976928
[7] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer 2010. MR 2681232 | 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. In: 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. MR 0580321 | 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. DOI 10.1016/S0304-3975(02)00228-1 | MR 1957609 | Zbl 1021.65022
[11] Cuninghame-Green, R. A., Butkovič, P.: Generalised eigenproblem in max algebra. In: 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. MR 1839423
[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
[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. MR 1643088
[17] Mehrmann, V., Nabben, R., Virnik, E.: Generalization of Perron-Frobenius theory to matrix pencils. Linear Algebra Appl. 428 (2008), 20–38. MR 2372583
Partner of
EuDML logo