Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

DOI10.1016/J.CRMA.2004.05.001MaRDI QIDQ1876909zbMATH OpenOpenAlexFDO

Authors Marianne Akian, R. B. Bapat, Stéphane Gaubert

Publication date 20 August 2004

Published in Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0402438

zbMATH Keywords

asymptoticseigenvaluesmatrix pencilsmin-plus algebraoptimal assignment algorithmsperturbation

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Matrix pencils (15A22) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Spectrum, resolvent (47A10) Perturbation theory of linear operators (47A55) Functions whose values are linear operators (operator- and matrix-valued functions, etc., including analytic and meromorphic ones) (47A56) Combinatorial optimization (90C27)

Abstract: We consider a matrix pencil whose coefficients depend on a positive parameter $epsilon$, and have asymptotic equivalents of the form $aepsilo{n}^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.

Recommendations

• First order spectral perturbation theory of square singular matrix pencils
• Rank one perturbations of matrix pencils
• Perturbation theory for rectangular matrix pencils
• The Asymptotic Behavior of the Eigenvalues of a Singularly Perturbed Linear Pencil
• Perturbation of the Eigenvalues of Quadratic Matrix Polynomials

Cites work

• An algebra for piecewise-linear minimax problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Finding all essential terms of a characteristic maxpolynomial.
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1033392 (Why is no real title available?)
• scientific article; zbMATH DE number 3267082 (Why is no real title available?)
• Nongeneric eigenvalue perturbations of Jordan blocks
• On the Lidskii--Vishik--Lyusternik Perturbation Theory for Eigenvalues of Matrices with Arbitrary Jordan Structure
• The Asymptotic Behavior of the Eigenvalues of a Singularly Perturbed Linear Pencil
• THE SOLUTION OF SOME PERTURBATION PROBLEMS FOR MATRICES AND SELFADJOINT OR NON-SELFADJOINT DIFFERENTIAL EQUATIONS I

Cited in

(11)

• Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
• The level set method for the two-sided max-plus eigenproblem
• Tropical bounds for eigenvalues of matrices
• Fixing two eigenvalues by a minimal perturbation
• Non-archimedean valuations of eigenvalues of matrix polynomials
• Max-Plus Algebraic Statistical Leverage Scores
• Max-plus singular values
• Tropical Vandermonde matrices
• On some aspects of spectral theory for infinite bounded non-negative matrices in max algebra
• On the spectrum in max algebra
• On some aspects of perturbation analysis for matrix cone optimization induced by spectral norm

This page was built for publication: Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1876909)