On integer eigenvectors and subeigenvectors in the max-plus algebra (Q1947102)

The max-plus ring consists of the extended reals \(\bar \mathbb{R}:=\) \(\left\{ -\infty\right\} \cup\mathbb{R} \) with operations \(\oplus\) and \(\otimes\) where \(a\oplus b:=\max(a,b)\) and \(a\otimes b:=a+b\) (\(-\infty\) is the zero and \(0\) is the unity element of this ring). These operations are extended to matrices in a natural way and (confusingly) the multiplication symbol \(\otimes\) will be omitted. Matrix algebras over the max-plus ring arise naturally in various combinatorial scheduling problems and other applications (see, for example [\textit{C. A. Brackley} et al., J. Theoretical Biology 303, 128 (2011)]). The authors are interested in determining when an \(n\times n\) matrix \(A=[a_{ij}]\) (over the max-plus ring) has integer eigenvectors or, more generally, integer subeigenvectors (a subeigenvector \(x\) satisfies \(Ax\leq\lambda x\) for some \(\lambda\in\) \(\bar \mathbb{R} \)). The second problem is much easier than the first, and a simple algorithm for determining whether \(A\) has an integer subeigenvector for \(\lambda\) (and, if so, describing them all) is provided. The question of integer eigenvectors is much more complicated, but the following result gives a flavour of what is proved. Associate with \(A\) a directed graph with adjacency matrix \(B:=[b_{ij}]\) where \(b_{ij}=0\) if \(a_{ij}=-\infty\) and \(b_{ij}=1\) otherwise, and call \(A\) irreducible when this graph is strongly connected. Now define \(\lambda(A):=\max(a_{i_{1}i_{2}}+\dots+a_{i_{k}i_{1}})/k\) where the maximum is over all \(k=1,\dots,n\) and all \(k\)-cycles \((i_{1},\dots,i_{k})\). Corollary 3.5: If \(A\) is irreducible and the entries of \(A\) lie in the extended integers \(\bar \mathbb{Z}:=\left\{ -\infty\right\} \cup \mathbb{Z}\), then \(A\) has an integer eigenvector if and only if \(\lambda(A)\in \mathbb{Z}\). The last two sections of the paper investigate algorithms for determining whether for a matrix \(A\) over the max-plus ring there is an integer vector \(x\) such that \(Ax\) is also integer.