Geodesic
Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra
Kybernetika, Tome 52 (2016) no. 1, pp. 1-14
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2016-1-0001
Classification : 08A72, 90B35, 90C47
Keywords: eigenvector; interval vector; max-min matrix 
@article{10_14736_kyb_2016_1_0001,
     author = {Plavka, J\'an},
     title = {Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra},
     journal = {Kybernetika},
     pages = {1--14},
     year = {2016},
     volume = {52},
     number = {1},
     doi = {10.14736/kyb-2016-1-0001},
     mrnumber = {3482607},
     zbl = {06562209},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-1-0001/}
}
TY  - JOUR
AU  - Plavka, Ján
TI  - Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra
JO  - Kybernetika
PY  - 2016
SP  - 1
EP  - 14
VL  - 52
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-1-0001/
DO  - 10.14736/kyb-2016-1-0001
LA  - en
ID  - 10_14736_kyb_2016_1_0001
ER  - 
%0 Journal Article
%A Plavka, Ján
%T Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra
%J Kybernetika
%D 2016
%P 1-14
%V 52
%N 1
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-1-0001/
%R 10.14736/kyb-2016-1-0001
%G en
%F 10_14736_kyb_2016_1_0001
Plavka, Ján. Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra. Kybernetika, Tome 52 (2016) no. 1, pp. 1-14. doi: 10.14736/kyb-2016-1-0001

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

[2] Cechlárová, K.: Eigenvectors in Bottleneck algebra. Linear Algebra Appl. 175 (1992), 63-73. | DOI | MR | Zbl

[3] Fiedler, M., Nedoma, J., Ramík, J., Rohn, J., Zimmermann, K.: Linear Optimization Problems with Inexact Data. Springer-Verlag, Berlin 2006. | MR | Zbl

[4] Gavalec, M., Zimmermann, K.: Classification of solutions to systems of two-sided equations with interval coefficients. Int. J. Pure Appl. Math. 45 (2008), 533-542. | MR | Zbl

[5] Gavalec, M.: Periodicity in Extremal Algebra. Gaudeamus, Hradec Králové 2004.

[6] Gavalec, M., Plavka, J.: Fast algorithm for extremal biparametric eigenproblem. Acta Electrotechnica et Informatica 7 (2007), 3. | MR

[7] Gavalec, M., Plavka, J.: Monotone interval eigenproblem in max-min algebra. Kybernetika 46 (2010), 3, 387-396. | MR | Zbl

[8] Lacko, V., Berežný, Š.: The color-balanced spanning tree problem. Kybernetika 41 (2005), 539-546. | MR | Zbl

[9] Molnárová, M., Pribiš, J.: Matrix period in max-algebra. Discrete Applied Mathematics 103 (2000), 167-175. | DOI | MR | Zbl

[10] Molnárová, M., Myšková, H., Plavka, J.: The robustness of interval fuzzy matrices. Linear Algebra and Its Appl. 438 (2013), 8, 3350-3364. | DOI | MR

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

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

[13] Plavka, J., Szabó, P.: 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.

[14] Plavka, J., Szabó, P.: On the $\lambda$-robustness of matrices over fuzzy algebra. Discrete Applied Math. 159 (2011), 5, 381-388. | DOI | MR | Zbl

[15] Plavka, J.: On the $O(n^3)$ algorithm for checking the strong robustness of interval fuzzy matrices. Discrete Applied Math. 160 (2012), 640-647. | DOI | MR

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

[17] Rohn, J.: Systems of linear interval equations. Linear Algebra and Its Appl. 126 (1989), 39-78. | DOI | MR | Zbl

[18] Sanchez, E.: Resolution of eigen fuzzy sets equations. Fuzzy Sets and Systems 1 (1978), 69-74. | DOI | MR | Zbl

[19] Sergeev, S.: Max-algebraic attraction cones of nonnegative irreducible matrices. Linear Algebra Appl. 435 (2011), 7, 1736-1757. | DOI | MR | Zbl

[20] Tan, Yi-Jia: Eigenvalues and eigenvectors for matrices over distributive lattices. Lin. Algebra Appl. 283 (1998), 257-272. | DOI | MR | Zbl

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

Cité par Sources :