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 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.
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 language | English |
---|---|
Pages (from-to) | 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 max-plus algebra'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils