Structure of the eigenspace of a Monge matrix in max-plus algebra (Q2476248)

Matrix computations using maximum and minimum operations have been considered by many authors in optimization problems. The steady states of discrete events processes correspond to eigenvectors of max-plus matrices, so the characterization of the eigenspace structure is important for the applications purposes. Let \(G=\mathbb R\cup\left\{-\infty\right\}\), where \(\mathbb R\) is the set of real numbers. Let \(\oplus\) be the maximum binary operation on \(G\) and \(\otimes\) be the usual addition operation on \(G\). (The infinite element is neutral with respect to the maximum operation and absorbing with respect to the addition). Then \(\left(G,\oplus,\otimes\right)\) is a max-plus algebra. For any natural number \({n}>{0}\) let \(N=\left\{1,2,3,\dots,n\right\}\), and Let \(G_{n}\) be the set of all \({n}\times{n}\) matrices over \(G\). A matrix \(A=(a_{ij})\in{G_{n}}\) is called a Monge matrix if \[ a_{ij}+a_{kl}\leq a_{il}+a_{kj},\quad\text{for all}\;{i}<{k}, {j}<{l}. \] The authors describe the structure of the eigenspace of a Monge matrix in detail. They use some well known techniques to compute the equivalence classes connected with cycles of the zero weight in the associated digraph of the given Monge matrix. They present an algorithm, which can be done in \(O(n^{2})\) time, or with some additional conditions in \(O(n)\) time, to compute and describe completely the structure of the eigenspace and the eigenspace dimension. The paper contains some research ideas for interested researchers.