Kybernetika 57 no. 6, 922-938, 2021

Controllable and tolerable generalized eigenvectors of interval max-plus matrices

Matej Gazda and Ján PlavkaDOI: 10.14736/kyb-2021-6-0922


By max-plus algebra we mean the set of reals $\mathbb{R}$ equipped with the operations $a\oplus b=\max\{a,b\}$ and $a\otimes b= a+b $ for $a,b\in \mathbb{R}.$ A vector $x$ is said to be a generalized eigenvector of max-plus matrices $A, B\in\mathbb{R}(m,n)$ if $A\otimes x=\lambda\otimes B\otimes x$ for some $\lambda\in \mathbb{R}$. The investigation of properties of generalized eigenvectors is important for the applications. The values of vector or matrix inputs in practice are usually not exact numbers and they can be rather considered as values in some intervals. In this paper the properties of matrices and vectors with inexact (interval) entries are studied and complete solutions of the controllable, the tolerable and the strong generalized eigenproblem in max-plus algebra are presented. As a consequence of the obtained results, efficient algorithms for checking equivalent conditions are introduced.


interval generalized eigenvector, fuzzy matrix


15A80, 15A18, 08A72


  1. X. Allamigeon, A. Legay, U. Fahrenberg, R. Katz and S. Gaubert: Tropical Fourier-Motzkin elimination, with an application to real-time verification. Int. J. Algebra Comput. 24 (2014), 5, 569-607.   DOI:10.1142/S0218196714500258
  2. P. A. Binding and H. Volkmer: A generalized eigenvalue problem in the max algebra. Linear Algebra Appl. 422 (2007), 360-371.   DOI:10.1016/j.laa.2006.09.023
  3. P. Butkovič: Max-linear Systems: Theory and Applications. Springer, 2010.   CrossRef
  4. P. Butkovič and D. Jones: On special cases of the generalized max-plus eigenproblem. SIAM J. Matrix Anal. Appl. 37 (2016), 1002-1021.   DOI:10.1137/15M1041031
  5. K. Cechlárová: Solutions of interval linear systems in $(max,+)$-algebra. In: Proc. 6th International Symposium on Operational Research Preddvor, Slovenia 2001, pp. 321-326.   CrossRef
  6. R. A. Cuninghame-Green: Minimax algebra and applications. Advances in Imaging and Electron Physics 90 (1995), 1-121.   CrossRef
  7. R. A. Cuninghame-Green and P. Butkovič: Generalised eigenproblem in max algebra. In: Proc. 9th IEEE International Workshop on Discrete Event Systems (WODES 2008), Goteborg 2008, pp.\.236-241.   CrossRef
  8. S. Gaubert and S. Sergeev: The level set method for the two-sided max-plus eigenproblem. Discrete Event Dynamic Systems 23 (2013), 105-134.   DOI:10.1007/s10626-012-0137-z
  9. M. Gavalec, J. Plavka and D. Ponce: Tolerance types of interval eigenvectors in max-plus algebra. Inform. Sci. 367-368 (2016), 14-27.   DOI:10.1016/j.ins.2016.05.023
  10. M. Gavalec, J. Plavka and D. Ponce: Strong tolerance of interval eigenvectors in fuzzy algebra. Fuzzy Sets and Systems 369 (2019), 145-156.   DOI:10.1016/j.fss.2018.11.015
  11. B. Heidergott, G.-J. Olsder and J. van der Woude: Max-plus at Work. Princeton University Press, 2005.   CrossRef
  12. R. M. Karp: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23 (1978), 309-311.   DOI:10.1016/0012-365X(78)90011-0
  13. H. Myšková and J. Plavka: X-robustness of interval circulant matrices in fuzzy algebra. Linear Algebra Appl. 438 (2013), 6, 2757-2769.   DOI:10.1016/j.laa.2012.11.026
  14. H. Myšková and J. Plavka: The robustness of interval matrices in max-plus algebra. Linear Algebra Appl. 445 (2014), 85-102.   DOI:10.1016/j.laa.2013.12.008
  15. H. Myšková: Interval eigenvectors of circulant matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 3, 57-61.   DOI:10.2478/v10198-012-0033-3
  16. H. Myšková: Weak stability of interval orbits of circulant matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 3, 51-56.   DOI:10.2478/v10198-012-0032-4
  17. H. Myšková: Robustness of interval Toeplitz matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 4, 56-60.   DOI:10.2478/v10198-012-0048-9
  18. J. Plavka: On the weak robustness of fuzzy matrices. Kybernetika 49 (2013), 128-140.   CrossRef
  19. J. Plavka: l-parametric Eigenproblem in max-algebra. Discrete Appl. Math. 150 (2005), 16-28.   CrossRef
  20. J. Plavka: The weak robustness of interval matrices in max-plus algebra. Discrete Appl. Math. 173 (2014) 92-101.   DOI:10.1016/j.dam.2014.03.018
  21. J. Plavka and S. Sergeev: Reachability of eigenspaces for interval circulant matrices in max-algebra. Linear Algebra Appl. 550 (2018) 59-86.   DOI:10.1016/j.laa.2018.03.041
  22. S. Sergeev: On the problem $Ax = \lambda Bx$ in max-algebra: every system of interval is a spectrum. Kybernetika 47 (2011), 715-721.   CrossRef
  23. S. Sergeev: Extremals of the supereigenvector cone in max algebra: A combinatorial description. Linear Algebra Appl. 479 (2015), 106-117.   DOI:10.1016/j.laa.2015.03.025
  24. K. Zimmermann: Extremální algebra (in Czech). Ekon. ústav ČSAV Praha, 1976.   CrossRef