Kybernetika 52 no. 4, 497-513, 2016

Characterizing matrices with $\bf{X}$-simple image eigenspace in max-min semiring

Ján Plavka and Sergeĭ SergeevDOI: 10.14736/kyb-2016-4-0497

Abstract:

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\}$ is the unique solution of the system $A\otimes y=x$ in $\mbox{\boldmath$X$}$. The main result of this paper is a combinatorial characterization of such matrices in the linear algebra over max-min (fuzzy) semiring. 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.

Keywords:

max-min algebra, interval, weakly robust, weakly stable, eigenspace, simple image set

Classification:

15A80, 15A18, 08A72

paper.pdf

References:

  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.1137/110837942
  4. K. Cechlárová: Unique solvability of max-min fuzzy equations and strong regularity of matrices over fuzzy algebra. Fuzzy Sets and Systems 75 (1995), 165-177.   DOI:10.1016/0165-0114(95)00021-c
  5. K. Cechlárová: Efficient computation of the greatest eigenvector in fuzzy algebra. Tatra Mt. Math. Publ. 12 (1997), 73-79.   CrossRef
  6. K. Cechlárová: On the powers of matrices in bottleneck/fuzzy algebra. Linear Algebra Appl. 246 (1996), 97-112.   DOI:10.1016/0024-3795(94)00338-6
  7. R. A. Cuninghame-Green: Minimax algebra and applications. Adv. Imaging Electron Phys. 90 (1995), 1-121.   DOI:10.1016/s1076-5670(08)70083-1
  8. A. Di Nola and B. Gerla: Algebras of Łukasiewicz's 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
  9. 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
  10. M. Gavalec: Periodicity in Extremal Algebra. Gaudeamus, Hradec Králové 2004.   CrossRef
  11. M. Gavalec and J. Plavka: Fast algorithm for extremal biparametric eigenproblem. Acta Electrotechnica et Informatica 7 (2007), 3, 1-5.   CrossRef
  12. 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
  13. J. S. Golan: Semirings and Their Applications. Springer, 1999.   DOI:10.1007/978-94-015-9333-5
  14. M. Gondran and M. Minoux: Graphs, dioids and semirings: new models and algorithms. Springer, 2008.   CrossRef
  15. B. Heidergott, G.-J. Olsder and J. van der Woude: Max-plus at Work. Princeton University Press, 2005.   DOI:10.1515/9781400865239
  16. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and its Applications. Kluwer, Dordrecht 1997.   DOI:10.1007/978-94-015-8901-7
  17. 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.   DOI:10.1007/978-1-4757-2793-7
  18. G. L. Litvinov and V. P. Maslov (eds.): Idempotent Mathematics and Mathematical Physics. AMS, Contemporary Mathematics 377, 2005.   DOI:10.1090/conm/377
  19. G. L. Litvinov and S. N. Sergeev (eds.): Tropical and Idempotent Mathematics. AMS, Contemporary Mathematics 495, 2009.   DOI:10.1090/conm/495
  20. 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
  21. H. Myšková and J. Plavka: The X-robustness of interval fuzzy matrices. Linear Algebra Appl. 438 (2013), 6, 2757-2769.   DOI:10.1016/j.laa.2012.11.026
  22. 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
  23. 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
  24. 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
  25. J. Plavka and P. Szabó: On the $\lambda$-robustness of matrices over fuzzy algebra. Discrete Appl. Math. 159 (2011), 5, 381-388.   DOI:10.1016/j.dam.2010.11.020
  26. J. Plavka: On the weak robustness of fuzzy matrices. Kybernetika 49 (2013), 1, 128-140.   CrossRef
  27. J. Rohn: Systems of linear interval equations. Linear Algebra Appl. 126 (1989), 39-78.   DOI:10.1016/0024-3795(89)90004-9
  28. E. Sanchez: Resolution of eigen fuzzy sets equations. Fuzzy Sets and Systems 1 (1978), 69-74.   DOI:10.1016/0165-0114(78)90033-7
  29. 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
  30. 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
  31. K. Zimmernann: Extremální algebra (in Czech). Ekon.ústav ČSAV Praha, 1976.   CrossRef