8483 articles  [version française]

inria-00071463, version 1

Perturbation of eigenvalues of matrix pencils and optimal assignment problem

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

N° RR-5120 (2004)

Abstract: We consider a matrix pencil whose coefficients depend on a positive parameter epsilon, and have asymptotic equivalents of the form aepsilon^A when epsilon goes to zero, where the leading coefficient a is complex, and the leading exponent A is real. We show that the asymptotic equivalent of every eigenvalue of the pencil can be determined generically from the asymptotic equivalents of the coefficients of the pencil. The generic leading exponents of the eigenvalues are the «eigenvalues» of a min-plus matrix pencil. The leading coefficients of the eigenvalues are the eigenvalues of auxiliary matrix pencils, constructed from certain optimal assignment problems.

  • 1:  MAXPLUS (INRIA Rocquencourt)
  • INRIA
  • Domain : Computer Science/Other
  • Keywords : PERTURBATION THEORY / MAX-PLUS ALGEBRA / TROPICAL SEMIRING / SPECTRAL THEORY / MATRIX PENCIL / NEWTON-PUISEUX THEOREM / AMOEBA / GRAPHS / OPTIMAL ASSIGNEMENT PROBLEM / HUNGARIAN ALGORITHM / WKB ASYMPTOTICS / LARGE DEVIATIONS
  • Internal note : RR-5120
 
  • inria-00071463, version 1
  • http://hal.inria.fr/inria-00071463
  • oai:hal.inria.fr:inria-00071463
  • From: Rapport De Recherche Inria <>
  • Submitted on: Tuesday, 23 May 2006 17:37:32
  • Updated on: Monday, 12 March 2007 12:14:38