×

Monotone eigenspace structure in max-min algebra. (English) Zbl 0994.15010

For a given \(n\times n\) matrix \(A\) in a max-min algebra, the set of all increasing eigenvectors, in notation \({\mathcal F}^\leq(A)\) is studied. It is shown that \({\mathcal F}^\leq(A)\) is a union of at most \(2^{n-1}\) intervals, and an explicit formula for the intervals is given. Moreover, it is shown that the endpoints of these intervals can be computed in \(O(n^2)\) time or in \(O(n)\) time, if an auxiliary \(n\times n\) matrix \(C(A)\) has been previously computed. The results enable a complete description of the structure of the whole eigenspace \({\mathcal F}(A)\).

MSC:

15A18 Eigenvalues, singular values, and eigenvectors
15B33 Matrices over special rings (quaternions, finite fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bacceli, F.; Cohen, G.; Olsder, G.; Quadrat, J. P., Synchronization and Linearity (1992), Wiley: Wiley New York · Zbl 0824.93003
[2] Butkovič, P., Strong regularity of matrices — a survey of results, Discrete Appl. Math., 48, 45-68 (1994) · Zbl 0804.06017
[3] Butkovič, P.; Cechlárová, K.; Szabó, P., Strong linear independence in bottleneck algebra, Linear Algebra Appl., 94, 133-155 (1987) · Zbl 0629.90093
[4] Cechlárová, K., Eigenvectors in bottleneck algebra, Linear Algebra Appl., 175, 63-73 (1992) · Zbl 0756.15014
[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.; Plávka, J., Linear independence in bottleneck algebras, Fuzzy Sets and Systems, 77, 337-348 (1996) · Zbl 0877.15017
[7] Cuninghame-Green, R. A., Minimax Algebra, (Lecture Notes in Economics and Mathematical Systems, vol. 166 (1979), Springer: Springer Berlin) · Zbl 0498.90084
[8] Di Nola, A.; Sessa, S.; Pedrycz, W.; Sanchez, E., Fuzzy Relation Equations and Their Applications to Knowledge Engineering (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0694.94025
[9] M. Gavalec, Solvability and unique solvability of max-min fuzzy equations, Fuzzy Sets and Systems 124 (2001) 385-393; M. Gavalec, Solvability and unique solvability of max-min fuzzy equations, Fuzzy Sets and Systems 124 (2001) 385-393 · Zbl 0994.03047
[10] M. Gavalec, J. Plávka, Strong regularity of matrices in general max-min algebra, Linear Algebra Appl. (submitted); M. Gavalec, J. Plávka, Strong regularity of matrices in general max-min algebra, Linear Algebra Appl. (submitted) · Zbl 1030.15016
[11] Gondran, M., Valeurs propres et vecteurs propres en classification hiérarchique, RAIRO Inform. Théor., 10, 39-46 (1976)
[12] Gondran, M.; Minoux, M., Eigenvalues and eigenvectors in semimodules and their interpretation in graph theory, (Proc. 9th Prog. Symp. (1976)), 133-148 · Zbl 0453.05028
[13] Gondran, M.; Minoux, M., Valeurs propres et vecteurs propres en théorie des graphes, (in: Colloques Internationaux, CNRS, Paris (1978)), 181-183 · Zbl 0414.15011
[14] Sanchez, E., Resolution of eigen fuzzy sets equations, Fuzzy Sets and Systems, 1, 69-74 (1978) · Zbl 0366.04001
[15] Tan, Yi.-Jia., Eigenvalues and eigenvectors for matrices over distributive lattices, Linear Algebra Appl., 283, 257-272 (1998) · Zbl 0932.15005
[16] Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures, Ann. Discrete Math., 10 (1981) · 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.