| Title:
|
Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra (English) |
| Author:
|
Plavka, Ján |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
52 |
| Issue:
|
1 |
| Year:
|
2016 |
| Pages:
|
1-14 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
eigenvector |
| Keyword:
|
interval vector |
| Keyword:
|
max-min matrix |
| MSC:
|
08A72 |
| MSC:
|
90B35 |
| MSC:
|
90C47 |
| idZBL:
|
Zbl 06562209 |
| idMR:
|
MR3482607 |
| DOI:
|
10.14736/kyb-2016-1-0001 |
| . |
| Date available:
|
2016-03-21T17:46:25Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144857 |
| . |
| Reference:
|
[1] Butkovič, P.: Max-linear Systems: Theory and Applications..Springer, 2010. 10.1007/978-1-84996-299-5 |
| Reference:
|
[2] Cechlárová, K.: Eigenvectors in Bottleneck algebra..Linear Algebra Appl. 175 (1992), 63-73. Zbl 0756.15014, MR 1179341, 10.1016/0024-3795(92)90302-q |
| Reference:
|
[3] Fiedler, M., Nedoma, J., Ramík, J., Rohn, J., Zimmermann, K.: Linear Optimization Problems with Inexact Data..Springer-Verlag, Berlin 2006. Zbl 1106.90051, MR 2218777 |
| Reference:
|
[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. Zbl 1154.65036, MR 2426231 |
| Reference:
|
[5] Gavalec, M.: Periodicity in Extremal Algebra..Gaudeamus, Hradec Králové 2004. |
| Reference:
|
[6] Gavalec, M., Plavka, J.: Fast algorithm for extremal biparametric eigenproblem..Acta Electrotechnica et Informatica 7 (2007), 3. MR 2655335 |
| Reference:
|
[7] Gavalec, M., Plavka, J.: Monotone interval eigenproblem in max-min algebra..Kybernetika 46 (2010), 3, 387-396. Zbl 1202.15013, MR 2676076 |
| Reference:
|
[8] Lacko, V., Berežný, Š.: The color-balanced spanning tree problem..Kybernetika 41 (2005), 539-546. Zbl 1249.05053, MR 2180362 |
| Reference:
|
[9] Molnárová, M., Pribiš, J.: Matrix period in max-algebra..Discrete Applied Mathematics 103 (2000), 167-175. Zbl 0952.05043, MR 1762209, 10.1016/s0166-218x(99)00242-5 |
| Reference:
|
[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. MR 3023281, 10.1016/j.laa.2012.12.020 |
| Reference:
|
[11] Myšková, H.: Weak stability of interval orbits of circulant matrices in fuzzy algebra..Acta Electrotechnica et Informatica 12 (2012), 3, 51-56. 10.2478/v10198-012-0032-4 |
| Reference:
|
[12] Myšková, H.: Interval eigenvectors of circulant matrices in fuzzy algebra..Acta Electrotechnica et Informatica 12 (2012), 3, 57-61. 10.2478/v10198-012-0033-3 |
| Reference:
|
[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. |
| Reference:
|
[14] Plavka, J., Szabó, P.: On the $\lambda$-robustness of matrices over fuzzy algebra..Discrete Applied Math. 159 (2011), 5, 381-388. Zbl 1225.15027, MR 2755915, 10.1016/j.dam.2010.11.020 |
| Reference:
|
[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. MR 2876347, 10.1016/j.dam.2011.11.010 |
| Reference:
|
[16] Plavka, J.: On the weak robustness of fuzzy matrices..Kybernetika 49 (2013), 1, 128-140. Zbl 1267.15026, MR 3097386 |
| Reference:
|
[17] Rohn, J.: Systems of linear interval equations..Linear Algebra and Its Appl. 126 (1989), 39-78. Zbl 1061.15003, MR 1040771, 10.1016/0024-3795(89)90004-9 |
| Reference:
|
[18] Sanchez, E.: Resolution of eigen fuzzy sets equations..Fuzzy Sets and Systems 1 (1978), 69-74. Zbl 0366.04001, MR 0494745, 10.1016/0165-0114(78)90033-7 |
| Reference:
|
[19] Sergeev, S.: Max-algebraic attraction cones of nonnegative irreducible matrices..Linear Algebra Appl. 435 (2011), 7, 1736-1757. Zbl 1226.15017, MR 2810668, 10.1016/j.laa.2011.02.038 |
| Reference:
|
[20] Tan, Yi-Jia: Eigenvalues and eigenvectors for matrices over distributive lattices..Lin. Algebra Appl. 283 (1998), 257-272. Zbl 0932.15005, MR 1657171, 10.1016/s0024-3795(98)10105-2 |
| Reference:
|
[21] Zimmermann, K.: Extremální algebra (in Czech)..Ekon. ústav ČSAV Praha, 1976. MR 0403587 |
| . |
