On integer eigenvectors and subeigenvectors in the max-plus algebra

Let a⊕b=max(a,b) and a⊗b=a+b for View the MathML source and extend these operations to matrices and vectors as in conventional algebra. We study the problems of existence and description of integer subeigenvectors (P1) and eigenvectors (P2) of a given square matrix, that is integer solutions to Ax⩽λx and Ax=λx. It is proved that P1 can be solved as easily as the corresponding question without the integrality requirement (that is in polynomial time).

An algorithm is presented for finding an integer point in the max-column space of a rectangular matrix or deciding that no such vector exists. We use this algorithm to solve P2 for any matrix over View the MathML source. The algorithm is shown to be pseudopolynomial for finite matrices which implies that P2 can be solved in pseudopolynomial time for any irreducible matrix. We also discuss classes of matrices for which P2 can be solved in polynomial time.