Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

Marianne Akian; Ravindra Bapat; Stéphane Gaubert

doi:10.1016/j.crma.2004.05.001

Mathematical Analysis

Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

Presented by: Pierre-Louis Lions

Marianne Akian ¹; Ravindra Bapat ²; Stéphane Gaubert ¹

¹ INRIA, domaine de Voluceau, B.P. 105, 78153 Le Chesnay cedex, France
² Indian Statistical Institute, New Delhi, 110016, India

Comptes Rendus. Mathématique, Volume 339 (2004) no. 2, pp. 103-108.

Abstract
Résumé

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.

Nous étendons au cas des valeurs propres de faisceaux de matrices la théorie des perturbations de Višik, Ljusternik et Lidskiı̆, ce qui permet de résoudre certains cas dégénérés de cette théorie. Nous montrons que les asymptotiques au premier ordre des valeurs propres d'un faisceau perturbé peuvent être calculées génériquement au moyen de méthodes de l'algèbre min-plus et d'algorithmes d'affectation optimale. Nous illustrons ce résultat en discutant un problème de perturbation singulière considéré par Najman.

Received: 2004-02-25
Accepted: 2004-05-04
Published online: 2004-07-15

DOI: 10.1016/j.crma.2004.05.001

Author's affiliations:

Marianne Akian ¹; Ravindra Bapat ²; Stéphane Gaubert ¹

¹ INRIA, domaine de Voluceau, B.P. 105, 78153 Le Chesnay cedex, France
² Indian Statistical Institute, New Delhi, 110016, India

@article{CRMATH_2004__339_2_103_0,
     author = {Marianne Akian and Ravindra Bapat and St\'ephane Gaubert},
     title = {Perturbation of eigenvalues of matrix pencils and the optimal assignment problem},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {103--108},
     publisher = {Elsevier},
     volume = {339},
     number = {2},
     year = {2004},
     doi = {10.1016/j.crma.2004.05.001},
     language = {en},
}

TY  - JOUR
AU  - Marianne Akian
AU  - Ravindra Bapat
AU  - Stéphane Gaubert
TI  - Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 103
EP  - 108
VL  - 339
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2004.05.001
LA  - en
ID  - CRMATH_2004__339_2_103_0
ER  -

%0 Journal Article
%A Marianne Akian
%A Ravindra Bapat
%A Stéphane Gaubert
%T Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
%J Comptes Rendus. Mathématique
%D 2004
%P 103-108
%V 339
%N 2
%I Elsevier
%R 10.1016/j.crma.2004.05.001
%G en
%F CRMATH_2004__339_2_103_0

Marianne Akian; Ravindra Bapat; Stéphane Gaubert. Perturbation of eigenvalues of matrix pencils and the optimal assignment problem. Comptes Rendus. Mathématique, Volume 339 (2004) no. 2, pp. 103-108. doi : 10.1016/j.crma.2004.05.001. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.05.001/

References
Cited by

[1] M. Akian, R. Bapat, S. Gaubert, Generic asymptotics of eigenvalues and min-plus algebra, Rapport de recherche 5104, INRIA, Le Chesnay, France, February 2004. Also arXiv: | arXiv

[2] R.E. Burkard; P. Butkovič Finding all essential terms of a characteristic maxpolynomial, Discrete Appl. Math., Volume 130 (2003) no. 3, pp. 367-380

[3] F. Baccelli; G. Cohen; G.J. Olsder; J.-P. Quadrat Synchronization and Linearity, Wiley, 1992

[4] R.B. Bapat; T.E.S. Raghavan Nonnegative Matrices and Applications, Cambridge University Press, 1997

[5] R. Cuninghame-Green; P. Meijer An algebra for piecewise-linear minimax problems, Dicrete Appl. Math., Volume 2 (1980), pp. 267-294

[6] V. Lidskiı̆; V. Lidskiı̆ Perturbation theory of non-conjugate operators, Zh. Vychisl. Mat. i Mat. Fiz., Volume 1 (1965) no. 1, pp. 73-85

[7] J. Moro; J.V. Burke; M.L. Overton On the Lidskii–Vishik–Lyusternik perturbation theory for eigenvalues of matrices with arbitrary Jordan structure, SIAM J. Matrix Anal. Appl., Volume 18 (1997) no. 4, pp. 793-817

[8] Y. Ma; A. Edelman Nongeneric eigenvalue perturbations of Jordan blocks, Linear Algebra Appl., Volume 273 (1998), pp. 45-63

[9] B. Najman The asymptotic behavior of the eigenvalues of a singularly perturbed linear pencil, SIAM J. Matrix Anal. Appl., Volume 20 (1999) no. 2, pp. 420-427

[10] A. Schrijver Combinatorial Optimization, vol. A, Springer, 2003

[11] M.I. Višik; L.A. Ljusternik Solution of some perturbation problems in the case of matrices and self-adjoint or non-selfadjoint differential equations. I, Russian Math. Surveys, Volume 15 (1960) no. 3, pp. 1-73

Cited by Sources:

Comments - Policy