Structure and dimension of the eigenspace of a concave Monge matrix

The eigenspace structure for a given n×nn×n concave Monge matrix in a max-plus algebra is described. Based on the description, an O(n)O(n) algorithm for computing the eigenspace dimension is formulated, which is faster than the previously known algorithms. Analogous results for convex Monge matrices have been published in [M. Gavalec, J. Plavka, Structure of the eigenspace of a Monge matrix in max-plus algebra, Discrete Appl. Math. 156 (2008) 596–606].