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

Gavalec, Martin; Plavka, Ján

Kybernetika 46, No. 3, 387-396 (2010).

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.

Reviewer: Günter Mayer (Rostock)

MSC:

15A18	Eigenvalues, singular values, and eigenvectors
65G30	Interval and finite arithmetic
15A80	Max-plus and related algebras

Keywords:

eigenvector; interval coefficients; monotone interval eigenproblem; max-min algebra; monotone interval vector; strong eigenvector; universal eigenvector; tolerance eigenvector; interval matrix; Hasse diagram

References:

[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 · www.mathematicsweb.org
[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