Extremality criteria for the supereigenvector space in max-plus algebra

Abstract

We present necessary and sufficient criteria for a max-algebraic supereigenvector, i.e., a solution of the system $A\otimes \text{x}\ge \text{x}$ with $A\in {\overline{\mathbb{R}}}^{n\times n}$ in max-plus algebra, to be an extremal. We also show that the suggested extremality criteria can be verified in $O(n^2)$ time for any given solution $\text{x}$.

23 pages, 1 figure

References in corpus (1)

• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems