Rump, Siegfried M.Siegfried M.Rump2021-04-282021-04-281997-01-01SIAM Journal on Matrix Analysis and Applications 18 (1): 83-103 (1997-01-01)http://hdl.handle.net/11420/9391The normwise distance of a matrix A to the nearest singular matrix is well known to be equal to ∥A∥/cond(A) for norms subordinate to a vector norm. However, there is no hope for finding a similar formula or even a simple algorithm for computing the componentwise distance to the nearest singular matrix for general matrices. This is because Poljak and Rohn [Math. Control Signals Systems, 6 (1993), pp. 1-9] showed that this is an NP-hard problem. Denote the minimum Bauer-Skeel condition number achievable by column scaling by K. Demmel [SIAM J. Matrix Anal. Appl., 13 (1992), pp. 10-19] showed that K is a lower bound for the componentwise distance to the nearest singular matrix. In our paper we prove that 2.4 · n ·K is an upper bound. This extends and proves a conjecture by Demmel and Higham (in the cited paper by Demmel). We give an explicit set of examples showing that such an upper bound cannot be better than n · K . Asymptotically, we show that n1+ln 2+∈ · K is a valid upper bound. -1 1.7 -1 -1 -1en1095-7162SIAM journal on matrix analysis and applications1997183103Soc.Componentwise distanceNP-hardnessOptimal Bauer-Skeel condition numberSingular matrixInformatikMathematikBounds for the componentwise distance to the nearest singular matrixJournal Article10.1137/S0895479895289170Other