ℓ-Parametric eigenproblem in max-algebra

Denote a⊕b=max(a,b), and a⊗b=a+b for a,b∈R and extend this pair of operations to matrices and vectors in the same way as in conventional linear algebra, that is, if A=(aij),B=(bij),C=(cij) are real matrices or vectors of compatible sizes then C=A⊗B if cij=Σk⊕aik⊗bkj for all i,j. The symbol diag(d1,d2,…,dn) denotes the matrix D with diagonal elements equal to d1,d2,…,dn and off-diagonal elements equal to -∞. For an arbitrary parameter ε∈R and given square matrices A=(aij), D=diag(d1,d2,…,dℓ,0,…,0),dj=ε,1⩽j⩽ℓ, we study the ℓ-parametric eigenproblem, i.e. problem of finding all xε=(x1(ε),x2(ε),…,xn(ε)) and λεℓ, satisfying Aεℓ⊗xε=λεℓ⊗xε,where Aεℓ=A⊗D. We introduce some properties of general ℓ-parametric eigenproblem and the O(n3) algorithm which gives all solutions of the 1-parametric eigenproblem with respect to ε.