Reducible spectral theory with applications to the robustness of matrices in max-algebra

Let a ⊕ b = max(a, b) and a ⊗ b = a + b for a, b ∈ ℝ̄ := ℝ ∪ {-∞}. By max-algebra we understand the analogue of linear algebra developed for the pair of operations (⊕,⊗), extended to matrices and vectors. The symbol A ^κ stands for the κth max-algebraic power of a square matrix A. Let us denote by ε the max-algebraic "zero" vector, all the components of which are -∞. The max-algebraic eigenvalue-eigenvector problem is the following: Given A ∈ ℝ ^n×n, find all λ ∈ ℝ ̄ and x ∈ ℝ̄ ⁿ, x ≠= ε, such that A⊗x = λ⊗x. Certain problems of scheduling lead to the following question: Given A ∈ ℝ̄ ^n×n, is there a κ such that Aκ ⊗ x is a max-algebraic eigenvector of A? If the answer is affirmative for every x ≠= ε, 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.