Article ID Journal Published Year Pages File Type
4602595 Linear Algebra and its Applications 2008 9 Pages PDF
Abstract

Let a⊕b=max(a,b) and a⊗b=a+b for and extend these operations to matrices and vectors as in conventional linear algebra. The following eigenvector problem has been intensively studied in the past: Given find all (eigenvectors) such that A⊗x=λ⊗x for some The present paper deals with the permuted eigenvector problem: Given and is it possible to permute the components of x so that it becomes a (max-algebraic) eigenvector of A? Using a polynomial transformation from BANDWIDTH we prove that the integer version of this problem is NP-complete.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory