\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\def\Z{\mathbb Z}
\def\CC{\mathbb C}
\def\rank{\hbox{\rm \ rank}}
\begin{document}
%Butkovic
%Peter","p.butkovic@bham.ac.uk","
\section{On the permuted max-algebraic eigenvector problem} By {\sl Peter Butkovic}.  

\medskip  \noindent Let $a\oplus b=\max (a,b)$, $a\otimes b=a+b$ for $a,b\in \overline{\mathbb{R} }:=\mathbb{R}\cup \{-\infty \}$ and extend these operations to matrices and vectors as in conventional linear algebra. The following \textit{ max-algebraic} \textit{eigenvector problem} has been intensively studied in the past:\ Given $A\in \overline{\mathbb{R}}^{n\times n},$ find all $x\in  \overline{\mathbb{R}}^{n},x\neq (-\infty ,...,-\infty )^{T}$ (\textit{ eigenvectors}) such that $A\otimes x=\lambda \otimes x$ for some $\lambda \in \overline{\mathbb{R}}.$ In our talk we deal with the \textit{permuted eigenvector problem}: Given $A\in \overline{\mathbb{R}}^{n\times n}$ and $ x\in \overline{\mathbb{R}}^{n},$ is it possible to permute the components of  $x$ so that the arising vector $x^{\prime }$ 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  \textit{permuted max-linear system} \textit{problem} can also be shown $NP$ -complete: Given $A\in \overline{\mathbb{R}}^{m\times n}$ and $b\in  \overline{\mathbb{R}}^{m},$ is it possible to permute the components of $b$ so that for the arising vector $b^{\prime }$ the system $A\otimes x=b^{\prime }$ has a solution? Both problems can be solved in polynomial time when $n$ does not exceed $3$.
%Eigenvector; Permutation; NP-complete","15A18","68Q25","","04:52:25","Tue Mar 18 2008","81.105.65.177"
\end{document}
 zzzz
