Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

We extend the perturbation theory of Vi?ik, Ljusternik and Lidski?? to the case of eigenvalues of matrix pencils. This extension allows us to solve certain degenerate cases of this theory. We show that the first order asymptotics of the eigenvalues of a perturbed matrix pencil can be computed generically by methods of min-plus algebra and optimal assignment algorithms. We illustrate this result by discussing a singular perturbation problem considered by Najman. To cite this article: M. Akian et al., C. R. Acad. Sci. Paris, Ser. I 339 (2004).