Journal of Computational and Applied Mathematics 143 (2002) 141 – 144
www.elsevier.com/locate/cam
Letter to the editor
An upper bound for the condition number of a matrix
in spectral norm
G. Piazza, T. Politi ∗
Dipartimento Interuniversitario di Matematica, Politecnico di Bari, Via Orabona 4, I-70125 Bari, Italy
Received 2 May 2001; received in revised form 16 January 2002
Abstract
In this note we generalize an upper bound given in Guggenheimer et al. (College Math. J. 26(1) (1995) 2)
for the condition number of a matrix as a function of the determinant, the Frobenius norm and of k singular
values. If no singular value is known it is possible to derive an upper bound for the condition number applying
c 2002 Published by Elsevier Science
lower and upper bounds for the product of a subset of singular values.
B.V.
MSC: 15A12; 65F35
Keywords: Condition number; Singular values
1. Introduction
The condition number (A) = AA−1 of a nonsingular matrix A plays an important role in
the numerical solution of linear systems since it measures the sensivity of the solution of linear
systems Ax = b to the perturbations on A and b. There are several methods that permit to nd good
approximations of the condition number of a general square matrix. In [2] the following upper bound
of the condition number (A) in spectral norm is shown:
AF n
2
√
2 (A) 6
(1)
|det A|
n
as a function of the determinant and the Frobenius norm of A since solving a linear system with
A as coecient matrix by Gaussian elimination, the determinant can be easily computed. In the
following section we give an upper bound for 2 (A) involving also a subset of the singular values
The work has been supported by M.U.R.S.T. 40% project.
Corresponding author. Tel.: +39-080-544264; fax: +39-080-5962612.
E-mail address: pptt@pascal.dm.uniba.it (T. Politi).
∗
c 2002 Published by Elsevier Science B.V.
0377-0427/02/$ - see front matter
PII: S 0 3 7 7 - 0 4 2 7 ( 0 2 ) 0 0 3 9 6 - 5
142
G. Piazza, T. Politi / Journal of Computational and Applied Mathematics 143 (2002) 141 – 144
of A. In fact if some singular values are explicitly known, or if a lower bound for their product is
known, an upper bound for 2 (A) is provided so that (1) can be seen as a particular case.
2. The main result
Let i , i = 1; : : : ; n; be the singular values of a nonsingular complex matrix A of order n, such that
1 ¿ 2 ¿ · · · ¿ n−1 ¿ n ¿ 0:
We recall that the condition number of A in spectral norm is
1
2 (A) =
n
and we consider, for 1 6 k 6 n − 1:
2 2 2
2 2
· · · n2−1 :
P = 1 1 · · · k k · k+1
p1 q1
p k qk
Since
n
i ;
|det A| =
i=1
we have
k
k
n−1
k
k
i2 i2 2 i2 1 |det A|2
P=
i =
pi i=1 qi
pi i=1 qi
n2
i=1
i=1
i=k+1
k
k
1
12 1 i2
|det A|2 = 22 (A)
= 2
n p1 q1 i=2 pi qi
pi q i
i=1
From the arithmetic–geometric mean inequality, taking
1
1
+ = 1 for i = 1; : : : ; n;
pi
qi
with qi ¿ 0 and pi ¿ 0, for all i, we have
n+k −1
k
k
A2F
1
2
2
2
2 (A)
|det A| 6
i
p
n+k −1
i qi
i=1
i=1
k
i=2
i2
|det A|2 :
and hence
n+k −1
A2F
1
;
(2)
|det A|2 n + k − 1
where, for k = 1 we suppose ki=2 i2 = 1:
In order to obtain the sharpest upper bound for 2 (A) let us consider the following minimization
problem:
k
1
1
minimize
+ = 1; i = 1; : : : ; k:
pi qi subject to
pi
qi
i=1
22 (A) 6
k
pi q i
i=1
k
2
i=2 i
G. Piazza, T. Politi / Journal of Computational and Applied Mathematics 143 (2002) 141 – 144
143
Hence, we consider a function de ned by
(p; q) =
k
p i qi =
i=1
k
i=1
pi2
;
pi − 1
where p = (p1 ; : : : ; pn ) and q = (q1 ; : : : ; qn ). Di erentiating with respect to pj yields:
k
2
pi pj (pj − 2)
@
=
; for j = 1; : : : ; n:
@pj
pi − 1
(pj − 1)2
i=1; i=j
The minimum is reached when pi = 2 for all i, and for symmetry pi = qi = 2 for i = 1; : : : ; n.
Hence we have the following upper bound for 2 (A):
n+k −1
1
AF
2k
√
:
(3)
2 (A) 6 k
|det
A|
n
+
k
−
1
i
i=2
We observe that if k = 1 (3) coincides with (1) shown in [2]. The bound (3) requires the knowledge
of k singular values of matrix A. If this subset of singular values
is not available it is possible to
derive a bound for 2 (A) using some recent bounds obtained for ki=1 i . For example in [3] the
following lower bound is derived
n−k
Ck ( ; )
n
(n−k)=2
|det A|
n−k 6 1 2 : : : k
i=1 ri
and the following upper bound
n
1 : : : k 6
kCn−k ( ; )
where Ck ( ; ) is the function
Ck ( ; ) =
and
k
k=2
1 − n=k 1=k
;
1 − (n−k)=k 1=k
i=1
ri
k+
n
i=k+1 ti
k=2
n
0 6 6 1; 0 6 ¡ 1
|det A|2
= n
2
i=1 ri
while ri denotes the 2-norm of the ith row of A and
ri 2
; i = n − k + 1; : : : ; n:
ti =
rn − k
Since the condition number of matrix A in spectral norm is the same of A, where is a permutation
matrix, we have supposed r1 ¿ r2 ¿ · · · ¿ rn .
The bounds depend on the arbitrary parameter ; 0 6 6 1. If = 0 then Ck ( ; ) = 1, for every
. The value of that gives optimal bounds is the root of the equation:
k
n
n=k 1=k
−
+ 1 = 0;
n−k
n−k
144
G. Piazza, T. Politi / Journal of Computational and Applied Mathematics 143 (2002) 141 – 144
i.e. the value that maximizes the function Ck ( ; ) (see [3] for further details). Once computed the
LU factorization of A the bound (3) with the further bounds on the product of the singular values
could be used as an a posteriori bound for 2 (A). In [1] an algorithm to compute a bound for ∞ (A)
is given. It requires the knowledge of the LU factorization of A and can be applied also to bound
2 (A) exploiting the relation between the 2-norm and the in nity norm of a matrix. In [4] we have
compared this bound with (1) and (3). In particular, the numerical tests show that if A is a matrix
of dimension n 6 15 possessing n − 1 singular values clustered to 1 and the 2-norm of the rows
close to 1 then (3) can be slightly sharper than the one given in [1] (but both give the same order
of magnitude). The reason of this behaviour seems to be that in this case the bounds for the product
of the singular values are very sharp (see [3]).
Remark. Bound (3) can be used also to give an upper estimate for the lower singular values of A.
In fact if k = n − 1 we nd
and
1
2n−1
A2F
6 n− 1
n
( i=2 i )(1 n =1 n )|det A| 2
2n − 2
1
6
A2F :
n2
|det A|2
Finally; the following lower bound is obtained:
|det A|
6 n ≡ min :
(n=2)
2 −1 AF
References
[1] G.H. Golub, C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1989.
[2] H.W. Guggenheimer, A.S. Edelman, C.R. Johnson, A simple estimate of the condition number of a linear system,
College Math. J. 26 (1) (1995) 2–5.
[3] R. Peluso, G. Piazza, Bounds for products of singular values of a matrix, Rend. Mat. 19 (1999) 507–522.
[4] G. Piazza, T. Politi, On the estimates of the condition number of a matrix in spectral norm, Rapporto no. 35=01
Dipartimento Interuniversitario di Matematica, Universita degli Studi e Politecnico di Bari.