The Componentwise Distance to the Nearest Singular Matrix

Abstract

The singular value decomposition of a square matrix A answers two questions. First, it measures the distance from A to the nearest singular matrix, measuring distance with the two-norm. It also computes the condition number, or the sensitivity of $A^{ - 1} $ to perturbations in A, where sensitivity is also measured with the two-norm. As is well known, these two quantities, the minimum distance to singularity and the condition number, are essentially reciprocals. Using the algorithm of Golub and Kahan [SIAM J. Numer. Anal., Ser. B, 2 (1965), pp. 205–224] and its descendants, these quantities may be computed in $O(n^3 )$ operations. More recent sensitivity analysis extends this analysis to perturbations of different maximum sizes in each entry of A. One may again ask about distance to singularity, condition numbers, and complexity in this new context. It is shown that there can be no simple relationship between distance to singularity and condition number, because the condition number can be computed in polynomial time and the distance to singularity is NP-complete. Nonetheless, there are some useful inequalities relating the two, especially in the case of componentwise relative perturbations.