Reducible Spectral Theory with Applications to the Robustness of Matrices in Max-Algebra
Peter Butkovič, R. A. Cuninghame‐Green, Stéphane Gaubert · SIAM Journal on Matrix Analysis and Applications · 2009
Let $a\oplus b=\max(a,b)$ and $a\otimes b=a+b$ for $a,b\in\overline{\mathbb{R}}:=\mathbb{R}\cup\{-\infty\}$. By max-algebra we understand the analogue of linear algebra developed for the pair of operations $(\oplus,\otimes)$, 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 $\varepsilon$ the max-algebraic “zero” vector, all the components of which are $-\infty$. The max-algebraic eigenvalue-eigenvector problem is the following: Given $A\in\overline{\mathbb{R}}^{n\times n}$, find all $\lambda\in\overline{\mathbb{R}}$ and $x\in\overline{\mathbb{R}}^{n}$, $x eq\varepsilon$, such that $A\otimes x=\lambda\otimes x$. Certain problems of scheduling lead to the following question: Given $A\in\overline{\mathbb{R}}^{n\times n}$, is there a k such that $A^{k}\otimes x$ is a max-algebraic eigenvector of A? If the answer is affirmative for every $x eq\varepsilon$, 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.