Kybernetika 57 no. 4, 594-612, 2021

Strong X-robustness of interval max-min matrices

Helena Myšková and Ján PlavkaDOI: 10.14736/kyb-2021-4-0594


In max-min algebra the standard pair of operations plus and times is replaced by the pair of operations maximum and minimum, respectively. A max-min matrix $A$ is called strongly robust if the orbit $x,A\otimes x, A^2\otimes x,\dots$ reaches the greatest eigenvector with any starting vector. We study a special type of the strong robustness called the strong \textit{\textbf{X}}-robustness, the case that a starting vector is limited by a lower bound vector and an upper bound vector. The equivalent condition for the strong \textit{\textbf{X}}-robustness is introduced and efficient algorithms for verifying the strong \textit{\textbf{X}}-robustness is described. The strong \textit{\textbf{X}}-robustness of a max-min matrix is extended to interval vectors \textit{\textbf{X}} and interval matrices \textit{\textbf{A}} using for-all-exists quantification of their interval and matrix entries. A complete characterization of AE/EA strong \textit{\textbf{X}}-robustness of interval circulant matrices is presented.


interval matrix, max-min algebra, strong robustness, AE(EA) robustness


15A18, 15A80, 93C55


  1. P. Butkovič and R. A. Cuninghame-Green: On matrix powers in max-algebra. Linear Algebra Appl 421 (2007), 370-381.   DOI:10.1016/j.laa.2006.09.027
  2. P. Butkovič, R. A. Cuninghame-Green and S. Gaubert: Reducible spectral theory with applications to the robustness of matrices in max-algebra. SIAM J. Matrix Anal. A 21 (2009), 1412-1431.   DOI:10.1137/080731232
  3. P. Butkovič, H. Schneider and S. Sergeev: Recognising weakly stable matrices. SIAM J. Control Optim. 50 (2012), 3029-3051.   DOI:10.1137/110837942
  4. K. Cechlárová: On the powers of matrices in bottleneck/fuzzy algebra. Linear Algebra Appl. 175 (1992), 63-73.   DOI:10.1016/0024-3795(92)90302-Q
  5. M. Gavalec and K. Zimmermann: Classification of solutions to systems of two-sided equations with interval coefficients. Int. J. Pure Appl. Math. 45 (2008), 533-542.   CrossRef
  6. M. Gavalec: Periods of special fuzzy matrices. Tatra Mt. Math. Publ. 16 (1999), 47-60.   CrossRef
  7. M. Gavalec: Periodicity in Extremal Algebra. Gaudeamus, Hradec Králové 2004.   CrossRef
  8. M. Gavalec, J. Plavka and H. Tomášková: Interval eigenproblem in max-min algebra. Lin. Algebra Appl. 440 (2014), 24-33.   DOI:10.1016/j.laa.2013.10.034
  9. J. S. Golan: Semi-rings and Their Applications. Springer, Berlin 1999.   CrossRef
  10. B. Heidergott, G.-J. Olsder and J. van der Woude: Max-plus at Work. Princeton University Press, Princeton 2005.   CrossRef
  11. M. Hladík: AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl. 465 (2015), 221-238.   DOI:10.1016/j.laa.2014.09.030
  12. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and its Applications. Kluwer, Dordrecht 1997.   CrossRef
  13. M. Molnárová, H. Myšková and J. Plavka: The robustness of interval fuzzy matrices. Linear Algebra Appl. 438 (2013), 3350-3364.   DOI:10.1016/j.laa.2012.12.020
  14. H. Myšková: On an algorithm for testing T4 solvability of max-plus interval systems. Kybernetika 48 (2012), 924-938.   CrossRef
  15. H. Myšková and J. Plavka: X-robustness of interval circulant matrices in fuzzy algebra. Linear Algebra Appl. 438 (2013), 2757-2769.   DOI:10.1016/j.laa.2012.11.026
  16. H. Myšková and J. Plavka: The robustness of interval matrices in max-plus algebra. Lin. Algebra Appl. 445 (2013), 85-102.   DOI:10.1016/j.laa.2013.12.008
  17. H. Myšková and J. Plavka: \textit{\textbf{X}}$^{AE}$ and \textit{\textbf{X}}$^{EA}$ robustness of max-min matrices. Discrete Appl Math 267 (2019), 142-150.   DOI:10.1016/j.dam.2019.04.021
  18. H. Myšková and J. Plavka: AE and EA robustness of interval circulant matrices in max-min algebra. Fuzzy Sets Syst. 384 (2020), 91-104.   DOI:10.1016/j.fss.2019.02.016
  19. J. Plavka: l-parametric Eigenproblem in max-algebra. Discrete Appl Math 150 (2005), 16-28.   CrossRef
  20. J. Plavka and P. Szabó: On the $\lambda$-robustness of matrices over fuzzy algebra. Discrete Appl. Math. 159 (2011), 381-388.   CrossRef
  21. J. Plavka: On the $O(n^3)$ algorithm for checking the strong robustness of interval fuzzy matrices. Discrete Appl. Math. 160 (2012), 640-647.   CrossRef
  22. 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
  23. J. Plavka: Computing the greatest {\bf X}-eigenvector of a matrix in max-min algebra. Kybernetika 52 (2016), 1-14.   DOI:10.14736/kyb-2016-1-0001
  24. B. Semančíková: Orbits in max-min algebra. Linear Algebra Appl. 414 (2006), 38-63.   DOI:10.1016/j.laa.2005.09.009
  25. 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
  26. Yi-Jia Tan: On the eigenproblem of matrices over distributive lattices. Linear Algebra Appl 374 (2003), 87-106.   DOI:10.1016/S0024-3795(03)00550-0
  27. K. Zimmernann: Extremální algebra (in Czech). Ekon. ústav ČSAV Praha, 1976.   CrossRef