###### Options

# Bounds for the componentwise distance to the nearest singular matrix

Publikationstyp

Journal Article

Publikationsdatum

1997-01-01

Sprache

English

Author

Institut

TORE-URI

Enthalten in

Volume

18

Issue

1

Start Page

83

End Page

103

Citation

SIAM Journal on Matrix Analysis and Applications 18 (1): 83-103 (1997-01-01)

Publisher DOI

Scopus ID

Publisher

Soc.

The 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 -1