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.