Kybernetika 52 no. 1, 1-14, 2016

Computing the greatest X-eigenvector of a matrix in max-min algebra

Ján PlavkaDOI: 10.14736/kyb-2016-1-0001


A vector $x$ is said to be an eigenvector of a square max-min matrix $A$ if $A\otimes x=x$. An eigenvector $x$ of $A$ is called the greatest $\textit{\textbf{X}}$-eigenvector of $A$ if $x\in\textit{\textbf{X}}=\{x; {\underline x}\leq x\leq {\overline x}\}$ and $y\leq x$ for each eigenvector $y\in\textit{\textbf{X}}$. A max-min matrix $A$ is called strongly $\textit{\textbf{X}}$-robust if the orbit $x,A\otimes x, A^2\otimes x,\dots$ reaches the greatest $\textit{\textbf{X}}$-eigenvector with any starting vector of $\textit{\textbf{X}}$. We suggest an $O(n^3)$ algorithm for computing the greatest $\textit{\textbf{X}}$-eigenvector of $A$ and study the strong $\textit{\textbf{X}}$-robustness. The necessary and sufficient conditions for strong $\textit{\textbf{X}}$-robustness are introduced and an efficient algorithm for verifying these conditions is described.


eigenvector, interval vector, max-min matrix


08A72, 90B35, 90C47


  1. P. Butkovič: Max-linear Systems: Theory and Applications. Springer, 2010.   DOI:10.1007/978-1-84996-299-5
  2. K. Cechlárová: Eigenvectors in Bottleneck algebra. Linear Algebra Appl. 175 (1992), 63-73.   DOI:10.1016/0024-3795(92)90302-q
  3. M. Fiedler, J. Nedoma, J. Ramík, J. Rohn and K. Zimmermann: Linear Optimization Problems with Inexact Data. Springer-Verlag, Berlin 2006.   CrossRef
  4. 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
  5. M. Gavalec: Periodicity in Extremal Algebra. Gaudeamus, Hradec Králové 2004.   CrossRef
  6. M. Gavalec and J. Plavka: Fast algorithm for extremal biparametric eigenproblem. Acta Electrotechnica et Informatica 7 (2007), 3.   CrossRef
  7. M. Gavalec and J. Plavka: Monotone interval eigenproblem in max-min algebra. Kybernetika 46 (2010), 3, 387-396.   CrossRef
  8. V. Lacko and Š. Berežný: The color-balanced spanning tree problem. Kybernetika 41 (2005), 539-546.   CrossRef
  9. M. Molnárová and J. Pribiš: Matrix period in max-algebra. Discrete Applied Mathematics 103 (2000), 167-175.   DOI:10.1016/s0166-218x(99)00242-5
  10. M. Molnárová, H. Myšková and J. Plavka: The robustness of interval fuzzy matrices. Linear Algebra and Its Appl. 438 (2013), 8, 3350-3364.   DOI:10.1016/j.laa.2012.12.020
  11. 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
  12. 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
  13. 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
  14. J. Plavka and P. Szabó: On the $\lambda$-robustness of matrices over fuzzy algebra. Discrete Applied Math. 159 (2011), 5, 381-388.   DOI:10.1016/j.dam.2010.11.020
  15. J. Plavka: On the $O(n^3)$ algorithm for checking the strong robustness of interval fuzzy matrices. Discrete Applied Math. 160 (2012), 640-647.   DOI:10.1016/j.dam.2011.11.010
  16. J. Plavka: On the weak robustness of fuzzy matrices. Kybernetika 49 (2013), 1, 128-140.   CrossRef
  17. J. Rohn: Systems of linear interval equations. Linear Algebra and Its Appl. 126 (1989), 39-78.   DOI:10.1016/0024-3795(89)90004-9
  18. E. Sanchez: Resolution of eigen fuzzy sets equations. Fuzzy Sets and Systems 1 (1978), 69-74.   DOI:10.1016/0165-0114(78)90033-7
  19. 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
  20. Yi-Jia Tan: Eigenvalues and eigenvectors for matrices over distributive lattices. Lin. Algebra Appl. 283 (1998), 257-272.   DOI:10.1016/s0024-3795(98)10105-2
  21. K. Zimmermann: Extremální algebra (in Czech). Ekon. ústav ČSAV Praha, 1976.   CrossRef