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

Ján Plavka

Kybernetika (2016)

  • Volume: 52, Issue: 1, page 1-14
  • ISSN: 0023-5954

Abstract

top
A vector x is said to be an eigenvector of a square max-min matrix A if A ⊗ x = x . An eigenvector x of A is called the greatest 𝐗 -eigenvector of A if x ∈ 𝐗 = { x ; x ̲ ≤ x ≤ x ¯ } and y ≤ x for each eigenvector y ∈ 𝐗 . A max-min matrix A is called strongly 𝐗 -robust if the orbit x , A ⊗ x , A 2 ⊗ x , ⋯ reaches the greatest 𝐗 -eigenvector with any starting vector of 𝐗 . We suggest an O ( n 3 ) algorithm for computing the greatest 𝐗 -eigenvector of A and study the strong 𝐗 -robustness. The necessary and sufficient conditions for strong 𝐗 -robustness are introduced and an efficient algorithm for verifying these conditions is described.

How to cite

top

Plavka, Ján. "Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra." Kybernetika 52.1 (2016): 1-14. <http://eudml.org/doc/276804>.

@article{Plavka2016,
abstract = {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\}\}=\lbrace x; \{\underline\{x\}\}\le x\le \{\overline\{x\}\}\rbrace $ and $y\le 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.},
author = {Plavka, Ján},
journal = {Kybernetika},
keywords = {eigenvector; interval vector; max-min matrix},
language = {eng},
number = {1},
pages = {1-14},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Computing the greatest $\{\bf X\}$-eigenvector of a matrix in max-min algebra},
url = {http://eudml.org/doc/276804},
volume = {52},
year = {2016},
}

TY - JOUR
AU - Plavka, Ján
TI - Computing the greatest ${\bf X}$-eigenvector of a matrix in max-min algebra
JO - Kybernetika
PY - 2016
PB - Institute of Information Theory and Automation AS CR
VL - 52
IS - 1
SP - 1
EP - 14
AB - 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}}=\lbrace x; {\underline{x}}\le x\le {\overline{x}}\rbrace $ and $y\le 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.
LA - eng
KW - eigenvector; interval vector; max-min matrix
UR - http://eudml.org/doc/276804
ER -

References

top
  1. Butkovič, P., 10.1007/978-1-84996-299-5, Springer, 2010. DOI10.1007/978-1-84996-299-5
  2. Cechlárová, K., 10.1016/0024-3795(92)90302-q, Linear Algebra Appl. 175 (1992), 63-73. Zbl0756.15014MR1179341DOI10.1016/0024-3795(92)90302-q
  3. Fiedler, M., Nedoma, J., Ramík, J., Rohn, J., Zimmermann, K., Linear Optimization Problems with Inexact Data., Springer-Verlag, Berlin 2006. Zbl1106.90051MR2218777
  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. Zbl1154.65036MR2426231
  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. MR2655335
  7. Gavalec, M., Plavka, J., Monotone interval eigenproblem in max-min algebra., Kybernetika 46 (2010), 3, 387-396. Zbl1202.15013MR2676076
  8. Lacko, V., Berežný, Š., The color-balanced spanning tree problem., Kybernetika 41 (2005), 539-546. Zbl1249.05053MR2180362
  9. Molnárová, M., Pribiš, J., 10.1016/s0166-218x(99)00242-5, Discrete Applied Mathematics 103 (2000), 167-175. Zbl0952.05043MR1762209DOI10.1016/s0166-218x(99)00242-5
  10. Molnárová, M., Myšková, H., Plavka, J., 10.1016/j.laa.2012.12.020, Linear Algebra and Its Appl. 438 (2013), 8, 3350-3364. MR3023281DOI10.1016/j.laa.2012.12.020
  11. Myšková, H., 10.2478/v10198-012-0032-4, Acta Electrotechnica et Informatica 12 (2012), 3, 51-56. DOI10.2478/v10198-012-0032-4
  12. Myšková, H., 10.2478/v10198-012-0033-3, Acta Electrotechnica et Informatica 12 (2012), 3, 57-61. DOI10.2478/v10198-012-0033-3
  13. Plavka, J., Szabó, P., The O ( n 2 ) algorithm for the eigenproblem of an ϵ -triangular Toeplitz matrices in max-plus algebra., Acta Electrotechnica et Informatica 9 (2009), 4, 50-54. 
  14. Plavka, J., Szabó, P., 10.1016/j.dam.2010.11.020, Discrete Applied Math. 159 (2011), 5, 381-388. Zbl1225.15027MR2755915DOI10.1016/j.dam.2010.11.020
  15. Plavka, J., 10.1016/j.dam.2011.11.010, Discrete Applied Math. 160 (2012), 640-647. MR2876347DOI10.1016/j.dam.2011.11.010
  16. Plavka, J., On the weak robustness of fuzzy matrices., Kybernetika 49 (2013), 1, 128-140. Zbl1267.15026MR3097386
  17. Rohn, J., 10.1016/0024-3795(89)90004-9, Linear Algebra and Its Appl. 126 (1989), 39-78. Zbl1061.15003MR1040771DOI10.1016/0024-3795(89)90004-9
  18. Sanchez, E., 10.1016/0165-0114(78)90033-7, Fuzzy Sets and Systems 1 (1978), 69-74. Zbl0366.04001MR0494745DOI10.1016/0165-0114(78)90033-7
  19. Sergeev, S., 10.1016/j.laa.2011.02.038, Linear Algebra Appl. 435 (2011), 7, 1736-1757. Zbl1226.15017MR2810668DOI10.1016/j.laa.2011.02.038
  20. Tan, Yi-Jia, 10.1016/s0024-3795(98)10105-2, Lin. Algebra Appl. 283 (1998), 257-272. Zbl0932.15005MR1657171DOI10.1016/s0024-3795(98)10105-2
  21. Zimmermann, K., Extremální algebra (in Czech)., Ekon. ústav ČSAV Praha, 1976. MR0403587

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.