Kybernetika 47 no. 5, 715-721, 2011

On the problem AX=lambda BX in max algebra: every system of intervals is a spectrum

Sergeĭ Sergeev

Abstract:

We consider the two-sided eigenproblem A * x = λ * B * x over max algebra. It is shown that any finite system of real intervals and points can be represented as spectrum of this eigenproblem.

Keywords:

extremal algebra, tropical algebra, generalized eigenproblem

Classification:

15A80, 15A22, 91A46, 93C65

paper.pdf

References:

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