Structure and dimension of the eigenspace of a concave Monge matrix (Q1028473)

Consider the max-plus algebra \(G:=\mathbb R\cup\{ -\infty\}\) with the binary operations \(\oplus= \max\) and \(\otimes= +\). The set \(G_{n}\) of \(n\times n\) matrices over \(G\) forms a max-plus algebra with the usual definitions of matrix addition and multiplication in terms of \(\oplus\) and \(\otimes\). For each \(A\in G_{n}\), define \(A^{(k)}:=A\otimes\dots\otimes A\) (\(k\) factors) and \(\Delta(A):=A\oplus A^{(2)}\oplus\dots\oplus A^{(n)}\). It is known [see \textit{R. A. Cunninghame-Greene}, Minimax algebras, in Lect. Notes Econom. and Math. Syst. 166, Springer-Verlag, Berlin (1979)] that each \(A\in G_{n}\) has a unique eigenvalue \(\lambda(A)\) for which there is a finite \(n\)-vector \(x\) such that \(A\otimes x=\lambda(A)\otimes x\). Moreover, the eigenspace for \(\lambda(A)\) is equal to the set of all linear combinations of the columns of \(\Delta(-\lambda(A)\otimes A)\) for which the diagonal element is \(0\) (such column vectors are called fundamental eigenvectors). A matrix \(\left[ a_{ij}\right] \) in \(G_{n}\) is called concave Monge if \(a_{ij}+a_{kl}\geq a_{il}+a_{kj}\) for all \(i<k,j<l\). The authors show that in the special case of an \(n\times n\) concave Monge matrix it is possible to compute the structure and dimension of this eigenspace in \(O(n)\) time.