Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components

Let A be a matrix with distinct eigenvalues and let w(A) be the distance from A to the set of defective matrices (using either the 2-norm or the Frobenius norm). Define A(epsilon), the epsilon-pseudospectrum of A, to be the set of points in the complex plane which are eigenvalues of matricesA + E with parallel to E parallel to < epsilon, and let c(A) be the supremum of all epsilon with the property that A(epsilon) has n distinct components. Demmel and Wilkinson independently observed in the 1980s that w(A) >= c(A), and equality was established for the 2-norm by Alam and Bora in 2005. We give new results on the geometry of the pseudospectrum near points where first coalescence of the components occurs, characterizing such points as the lowest generalized saddle point of the smallest singular value of A - zl over z is an element of C. One consequence is that w(A) = c(A) for the Frobenius norm too, and another is the perhaps surprising result that the minimal distance is attained by a defective matrix in all cases. Our results suggest a new computational approach to approximating the nearest defective matrix by a variant of Newton's method that is applicable to both generic and nongeneric cases. Construction of the nearest defective matrix involves some subtle numerical issues which we explain, and we present a simple backward error analysis showing that a certain singular vector residual measures how close the computed matrix is to a truly defective matrix. Finally, we present a result giving lower bounds on the angles of wedges contained in the pseudospectrum and emanating from generic coalescence points. Several conjectures and questions remain open. (C) 2010 Elsevier Inc. All rights reserved.