Skip to Main content Skip to Navigation

Generic Asymptotics of Eigenvalues and Min-Plus Algebra

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:41:29 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:12:56 PM


  • HAL Id : inria-00071479, version 1



Marianne Akian, Ravindra Bapat, Stéphane Gaubert. Generic Asymptotics of Eigenvalues and Min-Plus Algebra. [Research Report] RR-5104, INRIA. 2004. ⟨inria-00071479⟩



Record views


Files downloads