On integer eigenvectors and subeigenvectors in the max-plus algebra

Peter Butkovic, Marie MacCaig

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
8 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)3408–3424
JournalLinear Algebra and its Applications
Early online date29 Jan 2013
Publication statusPublished - 15 Apr 2013


Dive into the research topics of 'On integer eigenvectors and subeigenvectors in the max-plus algebra'. Together they form a unique fingerprint.

Cite this