The Tropical Eigenvalue-Vector Problem from Algebraic, Graphical, and Computational Perspectives

Tropical mathematics describes both the max-plus and min-plus algebras. In the former, we understand addition to be the component-wise maximum function, while the minimum function represents addition in the latter. For example, 1 plus 2 is equivalent to max{1, 2} = 2 in the max-plus framework, whereas in min-plus algebra 1 plus 2 equals min{1, 2} = 1. In both algebras, we multiply elements by performing standard addition; hence, 1 times 2 yields 1+2 = 3. This seemingly fanciful arithmetic actually provides a language through which we elegantly describe everyday phenomena such as the long-term behavior of discrete event systems (assembly lines, computer networks, train schedules, etc). Extending the notion of tropical algebra to matrices and vectors, we find that determining eigenvalues and associated eigenvectors, allows us to construct event systems that behave predictably and stably. First, we explore the graph theoretic underpinnings of the tropical eigenvalue and associated eigenspaces so that we may better understand how they are computed. Considering two classes of tropical matrices, irreducible and reducible, we then look at how Karp’s Algorithm computes eigenvalues of the former and what its output when given a reducible system can tell us about long-term behavior