Controllable and tolerable generalized eigenvectors of interval max-plus matrices

Gazda, Matej ; Plavka, Ján

Kybernetika, Tome 57 (2021) no. 6, pp. 922-938

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2021-6-0922

Classification : 08A72, 15A18, 15A80
Keywords: interval generalized eigenvector; fuzzy matrix

Bibliographie

[1] Allamigeon, X., Legay, A., Fahrenberg, U., Katz, R., Gaubert, S.: Tropical Fourier-Motzkin elimination, with an application to real-time verification. Int. J. Algebra Comput. 24 (2014), 5, 569-607. | DOI | MR

[2] Binding, P. A., Volkmer, H.: A generalized eigenvalue problem in the max algebra. Linear Algebra Appl. 422 (2007), 360-371. | DOI | MR

[3] Butkovič, P.: Max-linear Systems: Theory and Applications. Springer, 2010. | MR

[4] Butkovič, P., Jones, D.: On special cases of the generalized max-plus eigenproblem. SIAM J. Matrix Anal. Appl. 37 (2016), 1002-1021. | DOI | MR

[5] Cechlárová, K.: Solutions of interval linear systems in $(max,+)$-algebra. In: Proc. 6th International Symposium on Operational Research Preddvor, Slovenia 2001, pp. 321-326. | MR

[6] Cuninghame-Green, R. A.: Minimax algebra and applications. Advances in Imaging and Electron Physics 90 (1995), 1-121. | MR | Zbl

[7] Cuninghame-Green, R. A., Butkovič, P.: Generalised eigenproblem in max algebra. In: Proc. 9th IEEE International Workshop on Discrete Event Systems (WODES 2008), Goteborg 2008, pp.\.236-241.

[8] Gaubert, S., Sergeev, S.: The level set method for the two-sided max-plus eigenproblem. Discrete Event Dynamic Systems 23 (2013), 105-134. | DOI | MR

[9] Gavalec, M., Plavka, J., Ponce, D.: Tolerance types of interval eigenvectors in max-plus algebra. Inform. Sci. 367-368 (2016), 14-27. | DOI

[10] Gavalec, M., Plavka, J., Ponce, D.: Strong tolerance of interval eigenvectors in fuzzy algebra. Fuzzy Sets and Systems 369 (2019), 145-156. | DOI | MR

[11] Heidergott, B., Olsder, G.-J., Woude, J. van der: Max-plus at Work. Princeton University Press, 2005. | MR

[12] Karp, R. M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23 (1978), 309-311. | DOI | MR | Zbl

[13] Myšková, H., Plavka, J.: X-robustness of interval circulant matrices in fuzzy algebra. Linear Algebra Appl. 438 (2013), 6, 2757-2769. | DOI | MR

[14] Myšková, H., Plavka, J.: The robustness of interval matrices in max-plus algebra. Linear Algebra Appl. 445 (2014), 85-102. | DOI | MR

[15] Myšková, H.: Interval eigenvectors of circulant matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 3, 57-61. | DOI

[16] Myšková, H.: Weak stability of interval orbits of circulant matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 3, 51-56. | DOI

[17] Myšková, H.: Robustness of interval Toeplitz matrices in fuzzy algebra. Acta Electrotechnica et Informatica 12 (2012), 4, 56-60. | DOI

[18] Plavka, J.: On the weak robustness of fuzzy matrices. Kybernetika 49 (2013), 128-140. | MR | Zbl

[19] Plavka, J.: l-parametric Eigenproblem in max-algebra. Discrete Appl. Math. 150 (2005), 16-28. | DOI | MR

[20] Plavka, J.: The weak robustness of interval matrices in max-plus algebra. Discrete Appl. Math. 173 (2014) 92-101. | DOI | MR

[21] Plavka, J., Sergeev, S.: Reachability of eigenspaces for interval circulant matrices in max-algebra. Linear Algebra Appl. 550 (2018) 59-86. | DOI | MR

[22] Sergeev, S.: On the problem $Ax = \lambda Bx$ in max-algebra: every system of interval is a spectrum. Kybernetika 47 (2011), 715-721. | MR

[23] Sergeev, S.: Extremals of the supereigenvector cone in max algebra: A combinatorial description. Linear Algebra Appl. 479 (2015), 106-117. | DOI | MR

[24] Zimmermann, K.: Extremální algebra (in Czech). Ekon. ústav ČSAV Praha, 1976.