Zhou et al. Journal of Inequalities and Applications (2016) 2016:113 DOI 10.1186/s13660-016-1053-9

RESEARCH

Open Access

Perturbation bounds for eigenvalues of diagonalizable matrices and singular values Duanmei Zhou1* , Guoliang Chen2 , Guoxing Wu3 and Xiaoyan Chen4 *

Correspondence: [email protected] College of Mathematics and Computer Science, Gannan Normal University, 341000 Ganzhou, People’s Republic of China Full list of author information is available at the end of the article 1

Abstract Perturbation bounds for eigenvalues of diagonalizable matrices are derived. Perturbation bounds for singular values of arbitrary matrices are also given. We generalize some existing results. MSC: 65F15; 15A18; 65F35; 15A42 Keywords: perturbation bound; eigenvalue; diagonalizable matrix; singular value

1 Introduction Many problems in science and engineering lead to eigenvalue and singular value problems for matrices. Perturbation bounds of eigenvalues and singular values play an important role in matrix computations. Let Sn be the set of all n! permutations of {, , . . . , n}. If x = (x , x , . . . , xn ) and π ∈ Sn , then the vector xπ is defined as (xπ () , xπ () , . . . , xπ (n) ). A square matrix is called doubly stochastic if its elements are real nonnegative numbers and if the sum of the elements in each row and in each column is equal to . Let Cn×n be the set of n × n complex matrices. Let A = (aij ) ∈ Cn×n , we use the notation (see [, ])  Ap =

n 

 p |aij |

for p ≥ ,

 n n  

 pq  p

p

(.)

i,j=

 Aq,p =

j=

|akj |q

for p > , q > ,

k=

  + = . p q

(.)

Let T ∈ Cn×n and assume that   (k) (k) ∈ Cn×n , (k) = diag λ(k)  , λ , . . . , λn

k = , . . . , ,

are diagonal matrices. In [], the following classical result is given: n    () ()   () λ λ – λ() λ()   T() – () T()  ≥ s (T) n i i π (i) π (i) 

(.)

i=

© 2016 Zhou et al. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 2 of 11

for some π ∈ Sn , where sn (T) is the smallest singular value of T. The inequality has many applications in bounding the (relative) perturbation for eigenvalues and singular values, such as [–] and the references therein. We generalize (.) in Section . Let λ(A) denote the spectrum of matrix A. In , Ikramov [] defined the ‘Hölder distance dp (λ(A), λ(B)) between the spectra’ of the matrices A and B, which have the eigenvalues λ , λ , . . . , λn and μ , μ , . . . , μn , respectively, by the equation: 





dp λ(A), λ(B) = min π ∈Sn

n 

 p |λi – μπ (i) |

p

.

(.)

i=

If A and B are Hermitian matrices and  ≤ p < , [] obtained   dp λ(A), λ(B) ≤ A – Bp ,

(.)

which partially generalizes the Hoffman-Wielandt theorem []. However, for normal matrices (.) can no longer be valid. The purpose of this paper is to obtain several inequalities similar to (.) for diagonalizable matrices. We exhibit some upper bounds and lower bounds for dp (λ(A), λ(B)) of diagonalizable matrices A and B in Section . Majorization is one of the most powerful techniques for deriving inequalities. We use majorization to get some perturbation bounds for singular values. For simplicity of the notations, in most cases in this paper the vectors in Rn are regarded as row vectors, but when they are multiplied by matrices we regard them as column vectors. Given a real vector x = (x , x , . . . , xn ) ∈ Rn , we rearrange its components as x[] ≥ x[] ≥ · · · ≥ x[n] . Definition . ([], p.) For x = (x , x , . . . , xn ), y = (y , y , . . . , yn ) ∈ Rn , if k  i=

x[i] ≤

k 

y[i] ,

k = , , . . . , n,

i=

then we say that x is weakly majorized by y and denote x ≺w y. If x ≺w y and n i= yi , then we say that x is majorized by y and denote x ≺ y.

n

i= xi

=

Let s ≥ s ≥ · · · ≥ sn and δ ≥ δ ≥ · · · ≥ δn be the singular values of the complex matrices A = (aij ) ∈ Cn×n and B = (bij ) ∈ Cn×n , respectively. In [], p., and [], p., the following classical result is given: n  i=

|si – δi | ≤

n 

|aij – bij | .

(.)

i,j=

We generalize the inequality (.) in Section .

2 Perturbation bounds for eigenvalues of diagonalizable matrices Let A ◦ B denote the Hadamard product of matrices A and B. A denotes the spectral norm of matrix A. AT denotes the transpose of matrix A. For two n-square real matrices A, B, we write A ≤e B to mean that B –A is (entrywise) nonnegative. For A = (aij ) ∈ Cn×n and a real number t > , we denote A|◦|t ≡ (|aij |t ) ∈ Cn×n . Let sn (A) and s (A) be the smallest and

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 3 of 11

the largest singular values of A, respectively. The following entrywise inequalities involve the smallest and the largest singular values. Lemma . ([], p.) Let A ∈ Cn×n and let p, q be real numbers with  < p ≤  and q ≥ . Then there exist two doubly stochastic matrices B, C ∈ Cn×n such that sn (A)p B ≤e A|◦|p

(.)

A|◦|q ≤e s (A)q C.

(.)

and

Theorem . Let T ∈ Cn×n and let p, q be real numbers with  < p ≤  and q ≥ . Assume (k) (k) n×n , k = , . . . , , are diagonal matrices. Then there are that (k) = diag(λ(k)  , λ , . . . , λn ) ∈ C permutations π and ν of Sn such that n   ()   () ()   T() – () T() p ≥ sp (T) λ λ – λ() λ() p n i i π (i) π (i) p

(.)

i=

and n    () ()   () λ λ – λ() λ() q .  T() – () T() q ≤ sq (T)  i i ν(i) ν(i) q

(.)

i=

Proof Set T = (tij ) ∈ Cn×n . Then n      () () () () p  T() – () T() p = |tij |p λ() i λj – λi λj p i,j=

  = eT T |◦|p ◦ M e,

(.)

() () () p n×n , e = (, , . . . , )T ∈ Cn . Applying inequality (.), we where M = (|λ() i λj – λi λj | ) ∈ C have

T |◦|p ≥ spn (T)B, where B = (bij ) is a doubly stochastic matrix. Then  ()     T() – () T() p ≥ eT sp (T)B ◦ M e = sp (T)eT (B ◦ M)e. n n p Since B is doubly stochastic, by Birkhoff ’s theorem ([, ], p.) B is a convex combination of permutation matrices:

B=

n!  i=

τi Pi ,

τi ≥ ,

n!  i=

τi = , Pi are permutation matrices.

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 4 of 11

Suppose eT (B ◦ Pk )e = min{eT (B ◦ Pi )e |  ≤ i ≤ n!} and Pk corresponds to π ∈ Sn . Then  ()   T() – () T() p ≥ sp (T)eT (B ◦ M)e n p  n!   p T τi Pi ◦ M e = sn (T)e i=

≥ spn (T)

n! 

τi eT (Pk ◦ M)e

i=

= spn (T)eT (Pk ◦ M)e = spn (T)

n   () ()  λ λ – λ() λ() p . i i π (i) π (i) i=

Proving (.). 

Use (.), (.), and the Birkhoff theorem, we can deduce the inequality (.).

Remark . If we take p = , we get Theorem . in []. So, the bound in inequality (.) generalizes the bound of Theorem . in []. Next, we apply Theorem . to get some perturbation bounds for the eigenvalues of diagonalizable matrices. Let A = (aij ) ∈ Cn×n and B = (bij ) ∈ Cn×n . When p > , q > ,  q

 p

+

= , then (see []) ABp ≤ Ap Bq,p ,   ABp ≤ AT q,p Bp .

(.) (.)

If B is nonsingular, then we have Ap ≤ ABp . B– q,p

(.)

If A is nonsingular, then we have Bp ≤ ABp . (A– )T q,p

(.)

For normal matrices the statement of Theorem  in [] (inequality (.)) can no longer be valid. However, we have the following theorem. Theorem . Assume that both A ∈ Cn×n and B ∈ Cn×n are diagonalizable and admit the following decompositions: A = D  D– 

and B = D  D–  ,

(.)

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 5 of 11

where D and D are nonsingular, and  = diag(λ , λ , . . . , λn ) and  = diag(μ , μ , . . . , μn ). Then there are permutations π and ν of Sn such that 

n 

 p

   T   D q,p D– D A – Bp , ≤  D–   q,p

(.)

   T   D q,p D– D A – Bp , ≤  D–   q,p

(.)

|λi – μπ (i) |

p

i=



n 

 p |λi – μν(i) |p

i=

where  < p ≤  and

 p

+

 q

= .

Proof Using (.), we have   – p A – Bpp = D  D–  – D   D  p    – p –  = D  D–  D  – D  D   D  p

(.)

  – p A – Bpp = D  D–  – D   D  p    – p –  = D D–  D   –  D  D  D  p .

(.)

and

We give a proof of (.) with the help of (.). Similarly one can prove (.) using (.). Applying (.) and (.) to (.) we obtain p

A – Bpp ≥

–  D–  D – D D  p . p – T p (D ) q,p D q,p

Using inequality (.), there is a permutation π of Sn such that n      D– D – D– D  p ≥ sp D– D |λi – μπ (i) |p .   n  p i=

So we have n 

p

|λi – μπ (i) |p ≤

i=

p

T (D–  ) q,p D q,p A – Bpp . p sn (D– D )  

We use the relations    –   – –   D D  ≤ D D–  s– n D D =   to get the inequality in (.).



Theorem . Under the hypotheses of Theorem ., there are permutations π and ν of Sn such that 

n  i=

 q |λi – μπ (i) |

q

≥

A – Bq , – (D )T p,q D–  p,q D D 

(.)

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113



n 

 q |λi – μν(i) |

≥

q

i=

where q ≥  and

 p

+

 q

Page 6 of 11

A – Bq , – (D )T p,q D–  p,q D D 

(.)

= .

Proof Using (.), we have   – q A – Bqq = D  D–  – D   D  q    – q –  = D  D–  D  – D  D   D  q

(.)

  – q A – Bqq = D  D–  – D   D  q    – q –  = D D–  D   –  D  D  D  q .

(.)

and

Applying (.) and (.) to (.) we obtain q  q  – q  –    A – Bqq ≤ (D )T p,q  D–  D – D D  q D p,q . Using inequality (.), there exists a permutation π of Sn such that n      D– D – D– D  q ≤ sq D– D |λi – μπ (i) |q ,     q i=

so we have n 

|λi – μπ (i) |q ≥

i=

q A – Bq . q q q – (D )T p,q D–  p,q s (D D )

We use the relations    –   –      s D–  D = D D ≤ D D  to get the inequality in (.). The proof of inequality (.) is similar to the proof of (.) and is omitted here.



For  ≤ p ≤ , it is well known [] that the scalar function (.) of a matrix A is a submultiplicative matrix norm. However, it is true for  < p ≤ . Actually, according to the Cauchy-Schwarz inequality, we have ABpp

 n p n  n      = aik bkj     i= j=

≤

n  n  i= j=

k=



n  k=

   |aik |



n  k=

  p |bkj |



.

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 7 of 11



Since for fixed vector x = (x , x , . . . , xn ), the function p → (|x |p + |x |p + · · · + |xn |p ) p is decreasing on (, ∞), ABpp

≤

n  n 



i= j=

 =

n  k=

n  n 

 |aik |

p



|aik |

p

i= k=

n 

 |bkj |

p

k= n  n 



|bkj |

p

j= k=

= App Bpp . That is, ABp ≤ Ap Bp .

(.)

If B is nonsingular, then     Ap = ABB– p ≤ ABp B– p . So we have Ap ≤ ABp . B– p

(.)

Similarly, when A is nonsingular, then     Bp = A– ABp ≤ A– p ABp . That is, Bp ≤ ABp . A– p

(.)

Theorem . Under the assumptions of Theorem ., there are permutations π and ν of Sn such that 

n 

 p |λi – μπ (i) |

p

 –       ≤ D–  p D p D D A – Bp ,

(.)

 –       ≤ D–  p D p D D A – Bp ,

(.)

i=



n 

 p |λi – μν(i) |

p

i=

where  < p ≤ . Proof The proof is similar to the proof of Theorem . and is omitted here. Remark . Since  Aq,p =

 n n   j=

k=

 pq  p |akj |

q

 ≤

 n n   j=

k=

 pp  p |akj |

p

= Ap



Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 8 of 11

and    T A  ≤ AT  = Ap q,p p for  < p ≤  and p + q = , the bounds in (.) and (.) are always sharper than those in (.) and (.), respectively. When p = q = , then AB ≤ min{A B, AB }. We obtain 

n 

  |λi – μπ (i) |



i=



n 

   –     ≤ D–  D  D D A – B    –     ≤ D–  D  D D A – B ,

 

   –     ≤ D–  D  D D A – B

|λi – μν(i) |



i=

   –     ≤ D–  D  D D A – B .

Since  Ap,q =

 n n   j=

 pq  q |akj |

p

 ≤

 n n   j=

k=

 pp  p |akj |

p

= Ap

k=

and  T   A  ≤ AT  = Ap p,q p for q ≥  and

 p

+

 q

= , we have the following corollary.

Corollary . Under the same conditions as in Theorem ., there are permutations π and ν of Sn such that 

n 

 q |λi – μπ (i) |

q

≥

A – Bq , – D p D–  p D D 

≥

A – Bq , – D–  D  p D D   p

i=



n 

 q |λi – μν(i) |q

i=

where q ≥  and

 p

 q

+

= .

Remark . When p = q = , we obtain 

n 

  |λi – μπ (i) |



≥

A – B A – B ≥ , – – – D D– D D  D D      D D 

≥

A – B A – B ≥ . – – – D– D D D  D D    D D    

i=



n  i=

  |λi – μν(i) |

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 9 of 11

3 Perturbation bounds for singular values For brevity we only consider square matrices. The generalizations from square matrices to rectangular matrices are obvious, and usually problems on singular values of rectangular matrices can be converted to the case of square matrices by adding zero rows or zero columns. For a Hermitian matrix G ∈ Cn×n , we always denote λ(G) = (λ (G), λ (G), . . . , λn (G)), where λ (G) ≥ λ (G) ≥ · · · ≥ λn (G) are the eigenvalues of G in decreasing order. Lemma . (Lidskii [], Lemma . []) If G, H ∈ Cn×n are Hermitian matrices, then λ(G) – λ(H) ≺ λ(G – H). Lemma . ([], p.) Let f (t) be a convex function, x = (x , x , . . . , xn ), y = (y , y , . . . , yn ) ∈ Rn . Then x≺y



⇒

   f (x ), f (x ), . . . , f (xn ) ≺w f (y ), f (y ), . . . , f (yn ) .

Theorem . Let σ (A) ≥ σ (A) ≥ · · · ≥ σn (A), σ (B) ≥ σ (B) ≥ · · · ≥ σn (B) and σ (A – B) ≥ σ (A – B) ≥ · · · ≥ σn (A – B) be the singular values of the complex matrices A = (aij ), B = (bij ) and A – B, respectively. Then n n     σi (A) – σi (B)p ≤ |aij – bij |p , i=

(.)

i,j=

n n     q σi (A) – σi (B)q ≥ σi (A – B), i=

(.)

i=

where  ≤ p ≤ ,  < q ≤ . Proof Let ϕ(A) 



 A∗ A 



, ϕ(B) 



 B∗ B 

 . Then



  (A – B)∗ ϕ(A – B) = . A–B  ϕ(A), ϕ(B), ϕ(A – B) are three Hermitian matrices. Assume that U∗ AV = diag(σ (A), σ (A), . . . , σn (A)), U∗ BV = diag(σ (B), σ (B), . . . , σn (B)) and U∗ (A – B)V = diag(σ (A – B), σ (A – B), . . . , σn (A – B)) are singular value decompositions with U , U , U , V , V , V unitary. Then   V Q  √  U

 V , –U

  V Q  √  U

V –U



  V and Q  √  U

are unitary matrices and   Q∗ ϕ(A)Q = diag σ (A), σ (A), . . . , σn (A), –σ (A), –σ (A), . . . , –σn (A) ,   Q∗ ϕ(B)Q = diag σ (B), σ (B), . . . , σn (B), –σ (B), –σ (B), . . . , –σn (B)

V –U



Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 10 of 11

and  Q∗ ϕ(A – B)Q = diag σ (A – B), σ (A – B), . . . , σn (A – B),  – σ (A – B), –σ (A – B), . . . , –σn (A – B) . By Lemma ., we have  σ (A) – σ (B), σ (A) – σ (B), . . . , σn (A) – σn (B), σn (B) – σn (A), . . . , σ (B) – σ (A), σ (B) – σ (A)  ≺ σ (A – B), σ (A – B), . . . , σn (A – B),  –σn (A – B), . . . , –σ (A – B), –σ (A – B) .



(.)

First consider the case  ≤ p ≤ . Since the function f (t) = |t|p is convex on (–∞, +∞), applying Lemma . with f (t) to the majorization (.) yields       σ (A) – σ (B)p , σ (A) – σ (B)p , . . . , σn (A) – σn (B)p ,        σn (B) – σn (A)p , . . . , σ (B) – σ (A)p , σ (B) – σ (A)p  p  p p p ≺w σ (A – B), σ (A – B), . . . , σnp (A – B), σnp (A – B), . . . , σ (A – B), σ (A – B) . In particular,        σ (A) – σ (B)p , σ (A) – σ (B)p , . . . , σn (A) – σn (B)p  p  p ≺w σ (A – B), σ (A – B), . . . , σnp (A – B) .

(.)

According to Theorem  of [] or Theorem . of [], we have n 

p

σi (A – B) ≤

i=

n 

|aij – bij |p

(.)

i,j=

for  ≤ p ≤ . Combining (.) and (.), we obtain (.). When  < q ≤ , by considering the convex function g(t) = –|t|q , on (–∞, +∞), applying Lemma . with g(t) to the majorization (.) yields q  q  q  q    –σ (A) – σ (B) , . . . , –σn (A) – σn (B) , –σn (B) – σn (A) , . . . , –σ (B) – σ (A)  q  q ≺w –σ (A – B), . . . , –σnq (A – B), –σnq (A – B), . . . , –σ (A – B) . In particular, q  q  q    –σ (A) – σ (B) , –σ (A) – σ (B) , . . . , –σn (A) – σn (B)  q  q ≺w –σ (A – B), –σ (A – B), . . . , –σnq (A – B) . From (.), we get (.).

(.) 

Remark . From inequality (.), if p = , we get the inequality (.). So the inequality (.) generalizes the inequality (..) of [], p., and Theorem . of [], p..

Zhou et al. Journal of Inequalities and Applications (2016) 2016:113

Page 11 of 11

Competing interests The authors declare that they have no competing interests. Authors’ contributions All authors conceived of the study, participated in its design and coordination, drafted the manuscript, participated in the sequence alignment, and read and approved the final manuscript. Author details 1 College of Mathematics and Computer Science, Gannan Normal University, 341000 Ganzhou, People’s Republic of China. 2 Department of Mathematics, East China Normal University, 200241 Shanghai, People’s Republic of China. 3 Department of Mathematics, Northeast Forestry University, 150040 Harbin, People’s Republic of China. 4 Library, Gannan Normal University, 341000 Ganzhou, People’s Republic of China. Acknowledgements This work is supported by the National Natural Science Foundation of China (No. 11501126, No. 11471122), the Youth Natural Science Foundation of Jiangxi Province (No. 20151BAB211011), the Science Foundation of Jiangxi Provincial Department of Education (No. GJJ150979), and the Supporting the Development for Local Colleges and Universities Foundation of China - Applied Mathematics Innovative team building. Received: 19 January 2016 Accepted: 28 March 2016 References 1. Li, R: Norms of certain matrices with applications to variations of the spectra of matrices and matrix pencils. Linear Algebra Appl. 182, 199-234 (1993) 2. Ostrowski, A: Über Normen von Matrizen. Math. Z. 63, 2-18 (1955) 3. Elsner, L, Friedland, S: Singular value, doubly stochastic matrices, and applications. Linear Algebra Appl. 220, 161-169 (1995) 4. Chen, X: On perturbation bounds of generalized eigenvalues for diagonalizable pairs. Numer. Math. 107, 79-86 (2007) 5. Li, R: Spectral variations and Hadamard products: some problems. Linear Algebra Appl. 278, 317-326 (1998) 6. Li, W, Sun, W: Combined perturbation bounds: I. Eigensystems and singular value decompositions. SIAM J. Matrix Anal. Appl. 29, 643-655 (2007) 7. Ikramov, KhD: Some estimates for the eigenvalues of matrices. Zh. Vychisl. Mat. Mat. Fiz. 10(1), 172-177 (1970) 8. Hoffman, AJ, Wielandt, HW: The variation of the spectrum of a normal matrix. Duke Math. J. 20, 37-39 (1953) 9. Zhan, X: Matrix Inequalities. LNM, vol. 1790. Springer, Berlin (2002) 10. Horn, RA, Johnson, CR: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) 11. Sun, JG: Matrix Perturbation Analysis. Science Press, Beijing (2001) 12. Birkhoff, G: Tres observaciones sobre el Algebra lineal. Rev. Univ. Nac. Tucumán Ser. A, Mat. Fis. Teor. 5, 147-151 (1946) 13. Horn, RA, Johnson, CR: Matrix Analysis. Cambridge University Press, Cambridge (1985) 14. Lidskii, VB: On the characteristic numbers of a sum and product of symmetric matrices. Dokl. Akad. Nauk SSSR 75, 769-772 (1950) 15. Ikramov, KhD: A simple proof of the generalized Schur inequality. Linear Algebra Appl. 199, 143-149 (1994)