We present a selection of bounds for the condition number of a nonsingular matrix
in terms of quantities that might be known or can be estimated.
General Matrices
From the inequality , for any matrix norm, where
is the spectral radius (the largest magnitude of any eigenvalue of
) we have
Fir the -norm, this bound is an equality for a normal matrix (one for which
), but it can be arbitrarily weak for nonnormal matrices.
Guggenheimer, Edelman, and Johnson (1995) obtain the bound
The proof of the bound applies the arithmetic–geometric mean inequality to the numbers
, where the
are the singular values of
. This bound can be arbitrarily weak but it is an approximate equality when
are of similar order of magnitude.
Merikoski, Urpala, Virtanen, Tam, and Uhlig (1997) obtain the bound
Their proof uses a more refined application of the arithmetic–geometric mean inequality, and they show that this bound is the smallest that can be obtained based on ,
, and
only. Hence (3) is no larger than (2), and they show that it can be smaller by no more than 1.5. Equality holds in (3) if and only if
.
As an example, for three random matrices with
, generated by
gallery('randsvd')
with three different singular value dsitributions:
Mode | (2) | (3) |
---|---|---|
One large singular value | 9.88e+07 | 9.88e+07 |
One small singular value | 1.21e+01 | 1.20e+01 |
Geometrically distributed singular values | 5.71e+04 | 5.71e+04 |
We note that for larger the formula (3) is prone to overflow, which can be avoided by evaluating it in higher precision arithmetic.
Hermitian Positive Definite Matrices
Merikoski et al. (1997) also give a version of (3) for Hermitian positive definite :
This is the smallest bound that can be obtained based on ,
, and
only. Equality holds in (4) if and only if the eigenvalues
of
satisfy
. We can rewrite this upper bound as
which gives the weaker bound
This bound is analogous to (2) and is up to a factor larger than (4), this factor being attained for
.
If then (4) reduces to
These bounds hold for any positive definite matrix with unit diagonal, that is, any nonsingular correlation matrix.
We can sometimes get a sharper bound than (4) and (5) by writing , where
and
(thus
is a correlation matrix), using
and bounding using (6). For example, for the
Pascal matrix
the condition number is . The bounds from (4) and (5) are both
, whereas combining (4) and (7) gives a bound of
.
Notes
Many other condition number bounds are available in the literature. All have their pros and cons and any bound based on limited information such as traces of powers of and the determinant will be potentially very weak.
A drawback of the bounds (3)–(6) is that they require . Sometimes the determinant is easily computable, as for a Vandermonde matrix, or can be bounded: for example,
for a matrix with integer entries. If a Cholesky, LU, or QR factorization of
is available then
is easily computable, but in this case a good order of magnitude estimate of the condition number can be cheaply computed using condition estimation techniques (Higham, 2002, Chapter 15).
The bounds (3) and (4) are used by Higham and Lettington (2021) in investigating the most ill conditioned symmetric matrices with integer elements bounded by
; see What Is the Wilson Matrix?
References
This is a minimal set of references, which contain further useful references within.
- Heinrich Guggenheimer, Alan Edelman, and Charles Johnson, A Simple Estimate of the Condition Number of a Linear System, College Math. J. 26, 2–5, 1995.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
- Nicholas J. Higham and Matthew C. Lettington, Optimizing and Factorizing the Wilson Matrix, to appear in Amer. Math. Monthly, 2021.
- Jorma Kaarlo Merikoski, Uoti Urpala, Ari Virtanen, Tin-Yau Tam, and Frank Uhlig, A Best Upper Bound for the 2-Norm Condition Number of a Matrix, Linear Algebra Appl. 254, 355–365, 1997.