inria-00071479, version 1

## Generic Asymptotics of Eigenvalues and Min-Plus Algebra

Marianne Akian () 1, Ravindra Bapat, Stéphane Gaubert () 1

N° RR-5104 (2004)

Résumé : We consider a square matrix $\mathcal{A}_{\epsilon}$ whose entries have asymptotics of the form $(\mathcal{A}_{\epsilon})_{ij}= a_{ij}\epsilon^{A_{ij}}+o(\epsilon^{A_{ij}})$ when $\epsilon$ goes to $0$, for some complex coefficients $a_{ij}$ and real exponents $A_{ij}$. We look for asymptotics of the same type for the eigenvalues of $\mathcal{A}_\epsilon$. We show that the sequence of exponents of the eigenvalues of $\mathcal{A}_\epsilon$ is weakly (super) majorized by the sequence of corners of the min-plus characteristic polynomial of the matrix $A=(A_{ij})$, and that the equality holds for generic values of the coefficients $a_{ij}$. We derive this result from a variant of the Newton-Puiseux theorem which applies to asymptotics of the preceding type. We also introduce a sequence of generalized minimal circuit means of $A$, and show that this sequence weakly majorizes the sequence of corners of the min-plus characteristic polynomial of $A$. We characterize the equality case in terms of perfect matching. When the equality holds, we show that the coefficients of all the eigenvalues of $\mathcal{A}_\epsilon$ can be computed generically by Schur complement formulæ, which extend the perturbation formulae of Vivsik, Ljusternik and Lidskii, and have fewer singular cases.

• Domaine : Informatique/Autre
• Mots-clés : PERTURBATION THEORY / MAX-PLUS ALGEBRA / TROPICAL SEMIRING / SPECTRAL THEORY / NEWTON-PUISEUX THEOREM / AMOEBA / MAJORIZATION / GRAPHS / SCHUR COMPLEMENT / PERFECT MATCHING / OPTIMAL ASSIGNMENT / WKB ASYMPTOTICS / LARGE DEVIATIONS
• Référence interne : RR-5104

• inria-00071479, version 1
• oai:hal.inria.fr:inria-00071479
• Contributeur :
• Soumis le : Mardi 23 Mai 2006, 17:41:29
• Dernière modification le : Lundi 12 Mars 2007, 12:03:17