Monotone interval eigenproblem in max-min algebra. (English) Zbl 1202.15013

A triple \(({\mathcal B},\oplus,\otimes)\) is called a max-min algebra if \({\mathcal B}\) is a linearly ordered set, and \(\oplus=\max\), \(\otimes=\min\) are binary operations on \({\mathcal B}\). These operations are extended to matrices and vectors in a formal way. The eigenproblem of a given \(n\times n\) matrix \(A\) over \({\mathcal B}\) consists in finding a value \(\lambda\in{\mathcal B}\) (= eigenvalue) and a vector \(x\) (= eigenvector) with \(n\) components from \({\mathcal B}\) such that \(A\otimes x= \lambda\otimes x\) holds. This problem can be reduced to \(A\otimes x= x\) which is considered in the paper.
If \({\mathbf A}\) is an \(n\times n\) interval matrix and \({\mathbf X}\) is an interval vector with \(n\) components the interval eigenproblem for \({\mathbf A}\) and \({\mathbf X}\) consists in recognizing whether \(A\otimes x= x\) holds true for \(A\in{\mathbf A}\), \(x\in{\mathbf X}\). In dependence on the applied qualifiers a classification containing six different types of interval eigenvectors \({\mathbf X}\) is introduced, and a detailed characterization of all these types is given for so-called monotone eigenvectors. Moreover, relations between various types of such eigenvectors are presented, illustrated by a Hasse diagram. Simple examples show that certain other specific relations do not hold.


15A18 Eigenvalues, singular values, and eigenvectors
65G30 Interval and finite arithmetic
15A80 Max-plus and related algebras
Full Text: EuDML Link


[1] Cechlárová, K.: Eigenvectors in bottleneck algebra. Lin. Algebra Appl. 175 (1992), 63-73. · Zbl 0756.15014 · doi:10.1016/0024-3795(92)90302-Q
[2] Cechlárová, K.: Solutions of interval linear systems in \((\operatorname{max},+)\)-algebra. Proc. 6th Internat. Symposium on Operational Research, Preddvor, Slovenia 2001, pp. 321-326. · Zbl 1016.93049
[3] Cechlárová, K., Cuninghame-Green, R. A.: Interval systems of max-separable linear equations. Lin. Algebra Appl. 340 (2002), 215-224. · Zbl 1004.15009 · doi:10.1016/S0024-3795(01)00405-0
[4] Cuninghame-Green, R. A.: Minimax Algebra. (Lecture Notes in Economics and Mathematical Systems 166.) Springer-Verlag, Berlin 1979. · Zbl 0739.90073 · doi:10.1016/0165-0114(91)90130-I
[5] Fiedler, M., Nedoma, J., Ramík, J., Rohn, J., Zimmermann, K.: Linear Optimization Problems with Inexact Data. Springer-Verlag, Berlin 2006. · Zbl 1106.90051 · doi:10.1007/0-387-32698-7
[6] Gavalec, M.: Monotone eigenspace structure in max-min algebra. Lin. Algebra Appl. 345 (2002), 149-167. · Zbl 0994.15010 · doi:10.1016/S0024-3795(01)00488-8
[7] Gavalec, M., Zimmermann, K.: Classification of solutions to systems of two-sided equations with interval coefficients. Internat. J. Pure Applied Math. 45 (2008), 533-542. · Zbl 1154.65036
[8] Rohn, J.: Systems of linear interval equations. Lin. Algebra Appl. 126 (1989), 39-78. · Zbl 1061.15003 · doi:10.1137/S0895479801398955
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.