Is it possible to determine if this matrix is ill-conditioned?

Question

I want to better understand ill-conditioning for matrices. Say we're given any matrix $A$ where some elements are $10^6$ in magnitude and some are $10^{-7}$ in magnitude. Does that guarantee that this matrix has a condition number greater than 100? Greater than 1000? Even though we haven't specified which elements of $A$ contain those values?

Answer 1

I addressed a very similar question on scicomp.SE, but I suppose it's good to have an answer here. The point is that neither the size of the entries nor the size of the determinant is a guarantee that your matrix is well- or ill-conditioned. For that, one would need to look at the matrix's singular values, to use a common criterion. In particular, the 2-norm condition number of a matrix is the largest singular value divided by the tiniest singular value; if the smallest singular value is zero, the matrix is singular, and if the smallest singular value is very tiny relative to the largest singular value, you have ill-conditioning.

For instance, matrices of the form

$$\begin{pmatrix}10^{12}&10^{-12}&\cdots&10^{-12}\\10^{-12}&10^{12}&\ddots&\vdots\\\vdots&\ddots&\ddots&10^{-12}\\10^{-12}&\cdots&10^{-12}&10^{12}\end{pmatrix}$$

($10^{12}$ on the diagonal, and $10^{-12}$ off-diagonal) are well conditioned (the ratio of the largest to the smallest singular value is very nearly equal to $1$), while the family of upper triangular matrices

$$\begin{pmatrix}1&2&\cdots&2\\&1&\ddots&\vdots\\&&\ddots&2\\&&&1\end{pmatrix}$$

studied by Alexander Ostrowski and Jim Wilkinson have a condition number equal to $\cot^2\dfrac{\pi}{4n}$, where $n$ is the size of the matrix.