On the Spectral Decomposition of Hermitian Matrices Modified by Low Rank Perturbations with Applications

We consider the problem of computing the eigenvalues and vectors of a matrix H = H + D which is obtained from an indefinite Hermitian low rank modification D of a Hermitian matrix H with known spectral decomposition. It is shown that the eigenvalues of H can easily be located to any desired accuracy by means of the inertia of a Hermitian matrix of small order whose elements depend nonlinearly on the eigenvalue parameter. The results are applied to the singular value decomposition of arbitrary modified matrices and to the spectral decomposition of modified unitary and of Hermitian Toeplitz matrices. For both the singular value decomposition and the unitary eigenvalue problem, divide and conquer algorithms based on rank one modifications are presented.