×

On the \(\lambda \)-robustness of matrices over fuzzy algebra. (English) Zbl 1225.15027

Let \((B,\leq)\) be a non-empty, bounded, linearly ordered set. Define the operations \(a\oplus b=\max\{a,b\}\) and \(a\otimes b=\min\{a,b\}\) for \(a,b\in B\). Let \(A=[a_{ij}]_{n\times n}\) be a square matrix with coefficients in \(B\). A column vector \(x\in B^n\) is said to be a \(\lambda\)-eigenvector of \(A\) for some \(\lambda\in B\) if \(A\otimes x=\lambda\otimes x\).
The matrix \(A\) is called \(\lambda\)-robust if for every \(x\in B^n\) the vector \(A^k\otimes x\) is a \(\lambda\)-eigenvector of \(A\) for some \(k\in{\mathbb Z}^+\). Let \(V(A,\lambda)\) denote the set of all \(\lambda\)-eigenvectors of \(A\). The authors show that: When \(\lambda\geq\max\{ a_{ij}: 1\leq i,j\leq n\}\), \(A\) is \(\lambda\)-robust if and only if \(V(A,\lambda)=V(A^{\ell},\lambda)\) for each \(\ell\in{\mathbb Z}^+\). Note that \(V(A^{\ell},\lambda)=V(A^{\ell},I)\) for \(\ell\in{\mathbb Z}^+\) whenever \(\lambda\geq\max\{ a_{ij}: 1\leq i,j\leq n\}\). An \(O(n^3)\) time algorithm exists to decide whether \(A\) is \(\lambda\)-robust.
Let \(M(A)\) denote the set of all vectors \(x=[x_i]_{n\times 1}\in B^n\) with each \(x_i<c(A)\) for \(c(A)=\bigotimes_{i=1}^n\left(\bigoplus_{j=1}^n a_{ij}\right)\). The matrix \(A\) is called strongly \(\lambda\)-robust if for every \(x\in B^n\backslash M(A)\) the vector \(A^k\otimes x\) is the greatest \(\lambda\)-eigenvector \(\bigoplus_{y\in V(A,\lambda)}y\) of \(A\) for some \(k\in{\mathbb Z}^+\). A main result of the paper gives equivalent conditions for \(A\) being strongly \(\lambda\)-robust when \(\lambda > c(A)\). Details are too involved to describe here. Basing on this, an \(O(n^3)\) algorithm is introduced to decide whether \(A\) is strongly \(\lambda\)-robust.

MSC:

15B15 Fuzzy matrices
15A18 Eigenvalues, singular values, and eigenvectors
65F30 Other matrix algorithms (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Butkovič, P.; Cuninghame-Green, R. A., On matrix powers in max-algebra, Linear Algebra Appl., 421, 370-381 (2007) · Zbl 1131.15008
[2] Butkovič, P.; Cuninghame-Green, R. A.; Gaubert, S., Reducible spectral theory with applications to the robustness of matrices in max-algebra, SIAM J. Matrix Anal. Appl., 31, 1412-1431 (2009) · Zbl 1204.15019
[3] Cechlárová, K., Eigenvectors in bottleneck algebra, Linear Algebra Appl., 175, 63-73 (1992) · Zbl 0756.15014
[4] Cechlárová, K., On the powers of matrices in bottleneck/fuzzy algebra, Linear Algebra Appl., 246, 97-112 (1996) · Zbl 0866.15009
[5] Cechlárová, K., Efficient computation of the greatest eigenvector in fuzzy algebra, Tatra Mt. Math. Publ., 12, 73-79 (1997) · Zbl 0963.65041
[6] Cechlárová, K., Powers of matrices over distributive lattice—a review, Fuzzy Sets and Systems, 138, 627-641 (2003) · Zbl 1075.05537
[7] R.A. Cuninghame-Green, K. Cechlárová, On the realization of discrete-event dynamic systems in fuzzy algebra, Preprint 20/93, University of Birmingham, 1993.; R.A. Cuninghame-Green, K. Cechlárová, On the realization of discrete-event dynamic systems in fuzzy algebra, Preprint 20/93, University of Birmingham, 1993.
[8] Gavalec, M., Computing matrix period in max-min algebra, Discrete Appl. Math., 75, 63-70 (1997) · Zbl 0876.05070
[9] Gavalec, M., Computing orbit period in max-min algebra, Discrete Appl. Math., 100, 167-182 (2000) · Zbl 0998.15020
[10] Gavalec, M., Monotone eigenspace structure in fuzzy algebra, Linear Algebra Appl., 345, 149-167 (2002) · Zbl 0994.15010
[11] M. Gavalec, J. Plavka, J. Polák, On the \(O ( n^2 \log n )\lambda \); M. Gavalec, J. Plavka, J. Polák, On the \(O ( n^2 \log n )\lambda \) · Zbl 1041.90045
[12] Gondran, M., Valeurs propres et vecteurs propres en classification hierarchique, RAIRO Inform. Theor., 10, 39-46 (1976)
[13] M. Gondran, M. Minoux, Eigenvalues and eigenvectors in semimodules and their interpretation in graph theory, in: Proc. 9th Prog. Symp., 1976, pp. 133-148.; M. Gondran, M. Minoux, Eigenvalues and eigenvectors in semimodules and their interpretation in graph theory, in: Proc. 9th Prog. Symp., 1976, pp. 133-148. · Zbl 0453.05028
[14] M. Gondran, M. Minoux, Valeurs propres et vecteurs propres en theorie des graphes, Colloques Internationaux, CNRS, Paris, 1978, pp. 181-183.; M. Gondran, M. Minoux, Valeurs propres et vecteurs propres en theorie des graphes, Colloques Internationaux, CNRS, Paris, 1978, pp. 181-183. · Zbl 0414.15011
[15] Gondran, M.; Minoux, M., Graphs, Dioids and Semirings: New Models and Algorithms (2008), Springer · Zbl 1201.16038
[16] Kim, K. H., Boolean Matrix Theory and Application (1982), Marcel Dekker: Marcel Dekker New York
[17] Kirkland, S.; Pullman, N. J., Boolean spectral theory, Linear Algebra Appl., 175, 177-190 (1992) · Zbl 0769.15007
[18] Sanchez, E., Resolution of eigen fuzzy sets equations, Fuzzy Sets and Systems, 1, 69-74 (1978) · Zbl 0366.04001
[19] Semančíková, B., Orbits in max-min algebra, Linear Algebra Appl., 414, 38-63 (2006) · Zbl 1125.15020
[20] Semančíková, B., Orbits and critical components in max-min algebra, Linear Algebra Appl., 426, 415-447 (2007) · Zbl 1128.15008
[21] Tan, Yi-Jia, Eigenvalues and eigenvectors for matrices over distributive lattices, Linear Algebra Appl., 283, 257-272 (1998) · Zbl 0932.15005
[22] Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structure (1981), North Holland: North Holland Amsterdam · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.