An algorithm for the eigenvalue perturbation problem: reduction of a κ-matrix to a Lidskii matrix

ABSTRACT

In this article, we present an algorithmic approach to the eigenvalue perturbation problem. We show that any matrix perturbation A(&egr;) of an arbitrary nilpotent Jordan canonical form J with all eigenvalues having an order of the form O(&egr;1/(a positive integer)) is similar to a matrix perturbation Atilde;(&egr;) in Arnold normal form that can be seen as generic. Calling A(&egr;) a &kgr;-matrix and Atilde;(&egr;) a Lidskii-Arnold matrix, we also provide a reduction algorithm for the computation of the Lidskii-Arnold form of a &kgr;-matrix. It is based on the minimization of the leading Jordan structure J and on Lidskii's genericity conditions for perturbed eigenvalues.

REFERENCES

• 1: V. Arnold. On matrices depending on parameters. Russian Math. Surveys, 26:29-43, 1971.
• 2: H. Baumgartel. Analytic perturbation theory for matrices and operators. Birkh. auser Verlag, Basel, 1985.
• 3: G. Chen. Solutions formelles de systemes d'equations differentielles lineaires ordinaires homogenes. Ph.D. Thesis, Universite Joseph Fourier, Grenoble, France, 1990.
• 4: Alan Edelman , Erik Elmroth , Bo KÅgström, A Geometric Approach to Perturbation Theory of Matrices and Matrix Pencils. Part II: A Stratification-Enhanced Staircase Algorithm, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.667-699, July 1999 [doi>10.1137/S0895479896310184]
• 5: E. Gansner. Acyclic digraphs, Young tableaux, and nilpotent matrices. SIAM J. Alg. Disc. Meth., 2:429-440, 1981.
• 6: C. P. Jeannerod, N. Maillard, and E. P . ugel. An algorithmic approach for the symmetric perturbed eigenvalue problem. Application to the solution of a Schr. odinger equation by akp-perturbation method. Proceedings IMACS ACA'98, 1998.
• 7: C.-P. Jeannerod , E. Pflügel, A reduction algorithm for matrices depending on a parameter, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.121-128, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309884]
• 8: T. Kato. Perturbation theory for linear operators. Springer, Berlin, 1980.
• 9: V. Lidskii. Perturbation theory of non-conjugate operators. U.S.S.R. Comput. Math. and Math. Phys., 1:73-85, 1965.
• 10: Y. Ma and A. Edelman. Nongeneric perturbations of Jordan blocks. Linear Algebra Appl., 273:45-63, 1998.
• 11: Julio Moro , James V. Burke , Michael L. Overton, On the Lidskii--Vishik--Lyusternik Perturbation Theory for Eigenvalues of Matrices with Arbitrary Jordan Structure, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.793-817, Oct. 1997 [doi>10.1137/S0895479895294666]
• 12: J. Moser. The order of a singularity in Fuchs theory. Math. Z., pages 379-398, 1960.
• 13: E. P . ugel. Resolution symbolique des systemes differentiels lineaires. Ph.D. Thesis, Universite Joseph Fourier, oct. 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory, Verification