Kybernetika 54 no. 3, 413-426, 2018

X-simplicity of interval max-min matrices

Ján Plavka and Štefan BerežnýDOI: 10.14736/kyb-2018-3-0413


A matrix $A$ is said to have \mbox{\boldmath$X$}-simple image eigenspace if any eigenvector $x$ belonging to the interval $\mbox{\boldmath$X$}=\{x\colon \underline x\leq x\leq\overline x\}$ containing a constant vector is the unique solution of the system $A\otimes y=x$ in \mbox{\boldmath$X$}. The main result of this paper is an extension of \mbox{\boldmath$X$}-simplicity to interval max-min matrix $\mbox{\boldmath$A$}=\{A\colon \underline A\leq A\leq\overline A\}$ distinguishing two possibilities, that at least one matrix or all matrices from a given interval have \mbox{\boldmath$X$}-simple image eigenspace. \mbox{\boldmath$X$}-simplicity of interval matrices in max-min algebra are studied and equivalent conditions for interval matrices which have \mbox{\boldmath$X$}-simple image eigenspace are presented. The characterized property is related to and motivated by the general development of tropical linear algebra and interval analysis, as well as the notions of simple image set and weak robustness (or weak stability) that have been studied in max-min and max-plus algebras.


max-min algebra, interval, eigenspace, simple image set


15A80, 15A18, 08A72


  1. P. Butkovič: Simple image set of $(\max,+)$ linear mappings. Discrete Appl. Math. 105 (2000), 73-86.   DOI:10.1016/s0166-218x(00)00212-2
  2. P. Butkovič: Max-linear Systems: Theory and Applications. Springer, 2010.   DOI:10.1007/978-1-84996-299-5
  3. P. Butkovič, H. Schneider and S. Sergeev: Recognising weakly stable matrices. SIAM J. Control Optim. 50 (2012), 5, 3029-3051.   DOI:10.1007/978-1-84996-299-5
  4. K. Cechlárová: Efficient computation of the greatest eigenvector in fuzzy algebra. Tatra Mt. Math. Publ. 12 (1997), 73-79.   DOI:10.1016/0024-3795(92)90302-q
  5. A. Di Nola and B. Gerla: Algebras of Łukasiewicz logic and their semiring reducts. In: Idempotent Mathematics and Mathematical Physics (G. L. Litvinov and V. P. Maslov, eds.), 2005, pp. 131-144.   DOI:10.1090/conm/377/06988
  6. A. Di Nola and C. Russo: Łukasiewicz transform and its application to compression and reconstruction of digital images. Inform. Sci. 177 (2007), 1481-1498.   DOI:10.1016/j.ins.2006.09.002
  7. M. Gavalec and K. Zimmermann: Classification of solutions to systems of two-sided equations with interval coefficients. Int. J. Pure Applied Math. 45 (2008), 533-542.   CrossRef
  8. M. Gavalec: Periodicity in Extremal Algebra. Gaudeamus, Hradec Králové 2004.   CrossRef
  9. M. Gavalec and J. Plavka: Fast algorithm for extremal biparametric eigenproblem. Acta Electrotechnica et Informatica 7 (2007), 3, 1-5.   CrossRef
  10. J. S. Golan: Semirings and Their Applications. Springer, 1999.   DOI:10.1007/978-94-015-9333-5_8
  11. M. Gondran and M. Minoux: Graphs, Dioids and Semirings: New Models and Algorithms. Springer 2008.   DOI:10.1007/978-0-387-75450-5
  12. B. Heidergott, G.-J. Olsder and J. van der Woude: Max-plus at Work. Princeton University Press, 2005.   DOI:10.1515/9781400865239
  13. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and its Applications. Kluwer, Dordrecht 1997.   DOI:10.1007/978-94-015-8901-7
  14. V. Kreinovich, A. Lakeyev, J. Rohn and R. Kahl: Computational Complexity and Feasibility of Data Processing and Interval Computations. Kluwer Academic Publishers, Dordrecht-Boston-London 1998.   CrossRef
  15. G. L. Litvinov and V. P. Maslov (eds.): Idempotent Mathematics and Mathematical Physics. AMS Contemporary Mathematics 377 (2005).   DOI:10.1090/conm/377
  16. G. L. Litvinov and S. N. Sergeev (eds.): Tropical and Idempotent Mathematics. AMS Contemporary Mathematics 495 (2009).   DOI:10.1090/conm/495
  17. M. Molnárová, H. Myšková and J. Plavka: The robustness of interval fuzzy matrices. Linear Algebra Appl. 438 (2013), 8, 3350-3364.   DOI:10.1016/j.laa.2012.12.020
  18. 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
  19. 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
  20. 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
  21. J. Plavka and P. Szabó: On the $\lambda$-robustness of matrices over fuzzy algebra. Discrete Applied Math. 159 (2011), 5, 381-388.   CrossRef
  22. J. Plavka and P. Szabó: The $O(n^2 )$ algorithm for the eigenproblem of an $\epsilon$-triangular Toeplitz matrices in max-plus algebra. Acta Electrotechnica et Informatica 9 (2009), 4, 50-54.   CrossRef
  23. J. Plavka: On the weak robustness of fuzzy matrices. Kybernetika 49 (2013), 1, 128-140.   CrossRef
  24. J. Plavka and S. Sergeev: Characterizing matrices with $X $-simple image eigenspace in max-min semiring. Kybernetika 52 (2016), 4, 497-513.   DOI:10.14736/kyb-2016-4-0497
  25. J. Rohn: Systems of linear interval equations. Linear Algebra and Its Appl.126 (1989), 39-78.   DOI:10.1016/0024-3795(89)90004-9
  26. E. Sanchez: Resolution of eigen fuzzy sets equations. Fuzzy Sets Systems 1 (1978), 69-74.   CrossRef
  27. S. Sergeev: Max-algebraic attraction cones of nonnegative irreducible matrices. Linear Algebra Appl. 435 (2011), 7, 1736-1757.   DOI:10.1016/j.laa.2011.02.038
  28. Yi-Jia Tan: Eigenvalues and eigenvectors for matrices over distributive lattices. Linear Algebra Appl. 283 (1998), 257-272.   DOI:10.1016/s0024-3795(98)10105-2
  29. Yi-Jia Tan: On the eigenproblem of matrices over distributive lattices. Lin. Algebra Appl. 374 (2003), 87-106.   DOI:10.1016/s0024-3795(03)00550-0
  30. K. Zimmernann: Extremální algebra (in Czech). Ekonomický ústav ČSAV Praha, 1976.   CrossRef