  Hermitian and unitary matrices are two representatives of the class of normal
matrices whose full eigenvalue decomposition can be stably computed in
quadratic computing com plexity. Recently, fast and reliable eigensolvers
dealing with low rank perturbations of unitary and Hermitian matrices were
proposed. These structured eigenvalue problems appear naturally when computing
roots, via confederate linearizations, of polynomials expressed in, e.g., the
monomial or Chebyshev basis. Often, however, it is not known beforehand whether
or not a matrix can be written as the sum of an Hermitian or unitary matrix
plus a low rank perturbation. We propose necessary and sufficient conditions
characterizing the class of Hermitian or unitary plus low rank matrices. The
number of singular values deviating from 1 determines the rank of a
perturbation to bring a matrix to unitary form. A similar condition holds for
Hermitian matrices; the eigenvalues of the skew-Hermitian part differing from 0
dictate the rank of the perturbation. We prove that these relations are linked
via the Cayley transform. Based on these conditions we are able to identify the
closest Hermitian and unitary plus low rank matrix in Frobenius and spectral
norm and a practical Lanczos iteration to detect the low rank perturbation is
presented. Numerical tests prove that this straightforward algorithm is robust
with respect to noise.

Numerical Analysis;Numerical Analysis