Comptes Rendus
no. 2
Mathematical Analysis
Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
[Perturbation de valeurs propres de faisceaux matriciels et problème d'affectation optimale]

Présenté par : Pierre-Louis Lions

Marianne Akian1 ; Ravindra Bapat2 ; Stéphane Gaubert1
1 INRIA, domaine de Voluceau, B.P. 105, 78153 Le Chesnay cedex, France
2 Indian Statistical Institute, New Delhi, 110016, India
Comptes Rendus. Mathématique, Volume 339 (2004) no. 2, pp. 103-108.

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.05.001
Marianne Akian 1 ; Ravindra Bapat 2 ; Stéphane Gaubert 1

1 INRIA, domaine de Voluceau, B.P. 105, 78153 Le Chesnay cedex, France
2 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/

[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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Invertibility of functional Galois connections

Marianne Akian; Stéphane Gaubert; Vassili Kolokoltsov

C. R. Math (2002)

Rank of elliptic surfaces and base change

Cecilia Salgado

C. R. Math (2009)