1 On the permuted max-algebraic eigenvector problem

By Peter Butkovic.

Let a ⊕ b = max(a, b), a ⊗ b = a + b for a, b ∈ \overline{ℝ} := ℝ ∪ \{−∞\} and extend these operations to matrices and vectors as in conventional linear algebra. The following max-algebraic eigenvector problem has been intensively studied in the past: Given A ∈ \overline{ℝ}^{n×n}, find all x ∈ \overline{ℝ}^{n}, x ≠ (−∞, ..., −∞)^{T} ( eigenvectors) such that A ⊗ x = λ ⊗ x for some λ ∈ \overline{ℝ}. In our talk we deal with the permuted eigenvector problem: Given A ∈ \overline{ℝ}^{n×n} and x ∈ \overline{ℝ}^{n}, is it possible to permute the components of x so that the arising vector x′ is a (max-algebraic) eigenvector of A? This problem can be proved to be NP -complete using a polynomial transformation from BANDWIDTH. As a by-product the following permuted max-linear system problem can also be shown NP -complete: Given A ∈ \overline{ℝ}^{m×n} and b ∈ \overline{ℝ}^{m}, is it possible to permute the components of b so that for the arising vector b′ the system A ⊗ x = b′ has a solution? Both problems can be solved in polynomial time when n does not exceed 3.