Reducible Spectral Theory with Applications to the Robustness of Matrices in Max-Algebra

Let a circle plus b = max(a, b) and a circle times b = a + b for a, b is an element of (R) over bar := R boolean OR {-infinity}. By max-algebra we understand the analogue of linear algebra developed for the pair of operations (circle plus, circle times), extended to matrices and vectors. The symbol A(k) stands for the kth max-algebraic power of a square matrix A. Let us denote by epsilon the max-algebraic "zero" vector, all the components of which are -infinity. The max-algebraic eigenvalue-eigenvector problem is the following: Given A is an element of (R) over bar (n x n), find all lambda is an element of (R) over bar and x is an element of (R) over bar (n), x not equal epsilon, such that A circle times x = lambda circle times x. Certain problems of scheduling lead to the following question: Given A is an element of (R) over bar (n x n), is there a k such that A(k) circle times x is a max-algebraic eigenvector of A? If the answer is affirmative for every x not equal epsilon, then A is called robust. First, we give a complete account of the reducible max-algebraic spectral theory, and then we apply it to characterize robust matrices.