Projects per year
Abstract
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 maxcolumn 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.
An algorithm is presented for finding an integer point in the maxcolumn 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 language  English 

Pages (fromto)  3408–3424 
Journal  Linear Algebra and its Applications 
Volume  438 
Early online date  29 Jan 2013 
DOIs  
Publication status  Published  15 Apr 2013 
Fingerprint
Dive into the research topics of 'On integer eigenvectors and subeigenvectors in the maxplus algebra'. Together they form a unique fingerprint.Projects
 1 Finished

PerronFrobenius Theory and MaxAlgebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils