17 Singular Values and Singular value Inequalities 17.1 Definitionsand Characterizations 17-1 173 17.5 17-7 atrix Approxima 17-12 176 of Sums and Products of General Matrices17-13 Roy Mathias 17.7 Miscellaneous Results and Generalizations..........17-14 University of Birmingham References.....17-15 17.1 Definitions and Characterizations Singular values and the singular value decomposition are defined in Chapter 5.6.Additional information on computation of the singular value decomposition can be found in Chapter 45.A brief history of the singular value decomposition and early references can be found in H9,Chap.3]. Throughout this chapter,=min(m,n),and if ACx"has real eigenvalues,then they are ordered 1(A)≥..≥入n(A). Definitions: For A Cx",define the singular value vector sv(A)=(a(A),...(A)). ForA∈Cmxm,definer(A)≥·≥rm(A)and ci(A)≥…≥cn(A)to be the ordered Euclidean row and column lengths of A,that is,the square roots of the ordered diagonal entries of AA* and A*A. For ACdefine l(AA).This is called the spectral absolute value of A.(This is also called the absolute value,but the latter term will not be used in this chapter due to potential confusion with the entry-wise absolute value of A,denoted Al.) m of e matrix A∈C a factorization A=UP, is positive semidefinite andUC satisfies U'U =I 17-1
17 Singular Values and Singular Value Inequalities Roy Mathias University of Birmingham 17.1 Definitions and Characterizations .................. 17-1 17.2 Singular Values of Special Matrices.................. 17-3 17.3 Unitarily Invariant Norms .......................... 17-5 17.4 Inequalities ........................................ 17-7 17.5 Matrix Approximation ............................. 17-12 17.6 Characterization of the Eigenvalues of Sums of Hermitian Matrices and Singular Values of Sums and Products of General Matrices .......... 17-13 17.7 Miscellaneous Results and Generalizations .......... 17-14 References ................................................ 17-15 17.1 Definitions and Characterizations Singular values and the singular value decomposition are defined in Chapter 5.6. Additional information on computation of the singular value decomposition can be found in Chapter 45. A brief history of the singular value decomposition and early references can be found in [HJ91, Chap. 3]. Throughout this chapter, q = min{m, n}, and if A ∈ Cn×n has real eigenvalues, then they are ordered λ1(A) ≥···≥ λn(A). Definitions: For A ∈ Cm×n, define the singular value vector sv(A) = (σ1(A), ... , σq (A)). For A ∈ Cm×n, define r1(A) ≥ ··· ≥ rm(A) and c1(A) ≥ ··· ≥ cn(A) to be the ordered Euclidean row and column lengths of A, that is, the square roots of the ordered diagonal entries of AA∗ and A∗A. For A ∈ Cm×n define |A|pd = (A∗A)1/2. This is called the spectral absolute value of A. (This is also called the absolute value, but the latter term will not be used in this chapter due to potential confusion with the entry-wise absolute value of A, denoted |A|.) A polar decomposition or polar form of the matrix A ∈ Cm×n with m ≥ n is a factorization A = U P , where P ∈ Cn×n is positive semidefinite and U ∈ Cm×n satisfies U∗U = In. 17-1
17-2 Handbook of Linear Algebra Facts: The following facts can be found in most books on matrix theory,for example [HJ91,Chap.3]or [Bha97八. L.TakeA∈Cmm,and set -6d Then ;(A)=o;(B)for i =1....,q and o;(B)=0 for i>q.We may choose the zero blocks in B to ensure that B is square.In this way we can often generalize results on the singular values of square matrices to rectangular matrices.For simplicity of exposition,in this chapter we will sometimes state a result for square matrices rather than the more general result for rectangular matrices. 2.(Unitary invariance)Take ACx.Then for any unitaryUCx and VECx", (A)=(UAV),i=1,2,,9 3.Take A,BCx.There are unitary matricesUCm and VCx such that A=UBV if and only if a(A)=a(B),i=1,2.....q. 4.LetA∈g 5.Letde cex"Then df (or.. Let Sdenote the set of subspaces ofC"of dimension i.Then fori=... o(A)=eA=盟IA, A=惑照-A=殿照-A, 6.Let ACx"and define the Hermitian matrix -[ee :6 of1arc主o（以，o,（togcthe with川zaos.The matri1sca n- matrix.Its use allows one to deduce singular value results from results for 7t人=UPeof九Then g,(A)=Ag )matRew Av:Uec,vec uU-vry -hb. Πa,(A)=max[ldetU*AV:U∈Cmxk,V∈Cxk,U*U=V*V=k. If m=n,then 立W=mr{AU)l:,UU= We cannot replace the n by a generalk
17-2 Handbook of Linear Algebra Facts: The following facts can be found in most books on matrix theory, for example [HJ91, Chap. 3] or [Bha97]. 1. Take A ∈ Cm×n, and set B = A 0 0 0 . Then σi(A) = σi(B) for i = 1, ... , q and σi(B) = 0 for i > q. We may choose the zero blocks in B to ensure that B is square. In this way we can often generalize results on the singular values of square matrices to rectangular matrices. For simplicity of exposition, in this chapter we will sometimes state a result for square matrices rather than the more general result for rectangular matrices. 2. (Unitary invariance) Take A ∈ Cm×n . Then for any unitary U ∈ Cm×m and V ∈ Cn×n, σi(A) = σi(U AV), i = 1, 2, ... , q. 3. Take A, B ∈ Cm×n. There are unitary matrices U ∈ Cm×m and V ∈ Cn×n such that A = UBV if and only if σi(A) = σi(B), i = 1, 2, ... , q. 4. Let A ∈ Cm×n. Then σ2 i (A) = λi(AA∗) = λi(A∗A) for i = 1, 2, ... , q. 5. Let A ∈ Cm×n. Let Si denote the set of subspaces of Cn of dimension i. Then for i = 1, 2, ... , q, σi(A) = min X ∈Sn−i+1 max x∈X ,x2=1 Ax2 = min Y∈Si−1 max x⊥Y,x2=1 Ax2, σi(A) = max X ∈Si min x∈X ,x2=1 Ax2 = max Y∈Sn−i min x⊥Y,x2=1 Ax2. 6. Let A ∈ Cm×nand define the Hermitian matrix J = 0 A A∗ 0 ∈ Cm+n,m+n. The eigenvalues of J are ±σ1(A), ... , ±σq (A) together with |m − n| zeros. The matrix J is called the Jordan–Wielandt matrix. Its use allows one to deduce singular value results from results for eigenvalues of Hermitian matrices. 7. Take m ≥ n and A ∈ Cm×n. Let A = U P be a polar decomposition of A. Then σi(A) = λi(P ), i = 1, 2, ... , q. 8. Let A ∈ Cm×n and 1 ≤ k ≤ q. Then k i=1 σi(A) = max{Re tr U∗AV : U ∈ Cm×k , V ∈ Cn×k, U∗ U = V∗V = Ik }, k i=1 σi(A) = max{|detU∗AV| : U ∈ Cm×k , V ∈ Cn×k , U∗ U = V∗V = Ik }. If m = n, then n i=1 σi(A) = max n i=1 |(U∗AU)ii| : U ∈ Cn×n, U∗ U = In . We cannot replace the n by a general k ∈ {1, ... , n}.
Singular Values and Singular Value Inequalities 17-3 9.LctA∈Cmx".A yields (a)a(AT)=(A')=0(A=a(A),fori=1,2,,9. 0(A)=0+(A),i=1,...,n (c)For any jeN G:(A°A))=a2(A,i=1,,q: G,(A*AyA)=(A(A*A)=+'(A）i=1,q: 10.Let UP be a sition of A∈Cmx(G sitive semidefinite factor Pi value s equal to )The pos ned if a ha ingu ion U:)P 11.Take A,with Uu nitary.Then A=UlAlp if and only if A =A'lpU. Examples: 1.Take 11-3-5 1-5-311 -5111-3 [-3111-5 The singular value decomposition of A is A=UV,where=diag(20,12,8,4),and 1-1 1111 -1 Thesingular valuesof Aare 20,12,8,4.Let Qdenote thepermutation matrix that takes() to(x,2).Let P=Alpd =QA.The polar decomposition of A is A=QP.(To see this note that a permutation matrix is unitary and that P is positive definite by Gerschgorin's theorem.) Note also that IAldA*lpd =AQ. 17.2 Singular Values of Special Matrices In this section,we resent some matrices where the singular values(or some of the singular values)are known,and facts about the singular values of certain structured matrices. Facts: The following results can be obtained by straightforward computations if no specific reference is given. 1.Let D=diag(),where the are integers,and let H and H be Hadamard matrices. (See Chapter 32.2.)Then the matrix HDH has integer entries and has integer singular values lal,…,nlca
Singular Values and Singular Value Inequalities 17-3 9. Let A ∈ Cm×n. A yields (a) σi(AT ) = σi(A∗) = σi(A¯) = σi(A), for i = 1, 2, ... , q. (b) Let k = rank(A). Then σi(A†) = σ −1 k−i+1(A) for i = 1, ... , k, and σi(A†) = 0 for i = k + 1, ... , q. In particular, if m = n and A is invertible, then σi(A−1 ) = σ −1 n−i+1(A), i = 1, ... , n. (c) For any j ∈ N σi((A∗A)j ) = σ2 j i (A), i = 1, ... , q; σi((A∗A)j A∗) = σi(A(A∗A)j ) = σ2 j+1 i (A) i = 1, ... , q. 10. Let U P be a polar decomposition of A ∈ Cm×n (m ≥ n). The positive semidefinite factor P is uniquely determined and is equal to |A|pd . The factor U is uniquely determined if A has rank n. If A has singular value decomposition A = U1U∗ 2 (U1 ∈ Cm×n, U2 ∈ Cn×n), then P = U2U∗ 2 , and U may be taken to be U1U∗ 2 . 11. Take A,U ∈ Cn×n with U unitary. Then A = U|A|pd if and only if A = |A∗|pdU. Examples: 1. Take A = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 11 −3 −5 1 1 −5 −3 11 −5 1 11 −3 −3 11 1 −5 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . The singular value decomposition of A is A = UV∗, where = diag(20, 12, 8, 4), and U = 1 2 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ −1 1 −1 1 −1 −1 11 1 −1 −1 1 1 1 11 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ and V = 1 2 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ −1 1 −1 1 1 1 11 1 −1 −1 1 −1 −1 11 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . The singular values of Aare 20, 12, 8, 4. Let Q denote the permutation matrix that takes (x1, x2, x3, x4) to (x1, x4, x3, x2). Let P = |A|pd = Q A. The polar decomposition of A is A = Q P . (To see this, note that a permutation matrix is unitary and that P is positive definite by Gerschgorin’s theorem.) ˇ Note also that |A|pd = |A∗|pd = AQ. 17.2 Singular Values of Special Matrices In this section, we present some matrices where the singular values (or some of the singular values) are known, and facts about the singular values of certain structured matrices. Facts: The following results can be obtained by straightforward computations if no specific reference is given. 1. Let D = diag(α1, ... , αn), where the αi are integers, and let H1 and H2 be Hadamard matrices. (See Chapter 32.2.) Then the matrix H1D H2 has integer entries and has integer singular values n|α1|, ... , n|αn|.
17-4 Handbook of Linear Algebra 2.(2x2 matrix)Take.Set D=Idet(A),N=singular values of A are N士N-4D 3.LetX∈Cmx"have singular values≥…≥ag(q=min(m,nj.Set A= 「12x ∈Cm+,m+n The m+n singular values of A are 1+V+1,…,g+V+1,l山V+1-4√+1-am 4.[HJ91,Theorem 4.2.15]Let ACm and BCx have rank mand n.The nonzero singular values of A B are ai(A)oj(B),i=1,...,mj=1,...,n. 5.LctA∈C" be normal with eigenvalues.. ,and let p be a polynomial.Then the singular values of p(A)are Ip(,=1,...,n.In particular,if A is a circulant with first row o,... then A has singular values k=1,,m 6.TakeA∈Cx la 7.[Kit9 ia些foub邮ohastic,e)=A二Ahca川ingar ae monic polyno mial p()）=t+ N+y=4a,lVN--4a 2 2 8.[Hig96,p.167]Takes,cR such that s2+2=1.The matrix 「1-c-c···-c1 A=diag(1,s,.,s-l） is called a Kahan matrix.If c and s are positive,then(A)=s"21+c. 9.[GE95,Lemma3.l】Take0=d<d2<…<d.and0≠a∈C.Let d A= The singular values of A satisfy the equation f0=1+
17-4 Handbook of Linear Algebra 2. (2 × 2 matrix) Take A ∈ C2×2 . Set D = | det(A)| 2, N = A2 F . The singular values of A are N ± √N2 − 4D 2 . 3. Let X ∈ Cm×n have singular values σ1 ≥···≥ σq (q = min{m, n}). Set A = I 2X 0 I ∈ Cm+n,m+n. The m + n singular values of A are σ1 + σ2 1 + 1, ... , σq + σ2 q + 1, 1, ... , 1, σ2 q + 1 − σq , ... , σ2 1 + 1 − σ1. 4. [HJ91, Theorem 4.2.15] Let A ∈ Cm1×n1 and B ∈ Cm2×n2 have rank m and n. The nonzero singular values of A ⊗ B are σi(A)σj(B), i = 1, ... , m, j = 1, ... , n. 5. Let A ∈ Cn×n be normal with eigenvalues λ1, ... , λn, and let p be a polynomial. Then the singular values of p(A) are |p(λk )|, k = 1, ... , n. In particular, if A is a circulant with first rowa0, ... , an−1, then A has singular values n−1 j=0 aie−2πijk/n , k = 1, ... , n. 6. Take A ∈ Cn×n and nonzero x ∈ Cn. If Ax = λx and x∗A = λx∗, then |λ| is a singular value of A. In particular, if A is doubly stochastic, then σ1(A) = 1. 7. [Kit95] Let A be the companion matrix corresponding to the monic polynomial p(t) = tn + an−1tn−1 +···+ a1t + a0. Set N = 1 + n−1 i=0 |ai| 2. The n singular values of A are N + N2 − 4|a0| 2 2 , 1, ... , 1, N − N2 − 4|a0| 2 2 . 8. [Hig96, p. 167] Take s,c ∈ R such that s 2 + c 2 = 1. The matrix A = diag(1,s, ... ,s n−1 ) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 −c −c ··· −c 1 −c ··· −c ... ... . . . ... −c 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ is called a Kahan matrix. If c and s are positive, then σn−1(A) = s n−2 √1 + c. 9. [GE95, Lemma 3.1] Take 0 = d1 < d2 < ··· < dn and 0 = zi ∈ C. Let A = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ z1 z2 d2 . . . ... zn dn ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . The singular values of A satisfy the equation f (t) = 1 +n i=1 |zi| 2 d2 i − t2 = 0
Singular Values and Singular Value Inequalities 17-5 and exactly one lies in each of the intervals (d,d)...,(d,d )(dd+l).Let=(A). The left and right ith singular vectors of A are u/lul and v/vl2 respectively,where 1 10.(Bidiagonal)Take B= ∈CX If all the;and B:are nonzero,then B is called an unreduced bidiagonal matrix and (a)The singular values of B are distinct. (b)The singular values of B depend only on the moduli of... (c)The largest singular value of B isa strictly increasing function of the modulus of each of the ai and Bi. (d)The smallest singular value of B is n of the modulus of each of the (e)(High relative accuracy)Take>1 and multiply one of the entries of B byt to give B.Then T-la:(B)≤o,(B)≤ta(B). 11.[HJ85,Sec.4.4,prob.26]Let A Cx"be skew-symmetric(and possibly complex).The nonzero singular values of A occur in pairs. 17.3 Unitarily Invariant Norms Throughout this section,=min(m, Definitions: is unitarily invariant (ui.)if =UAV for any unitary UCm and VeC" and any A∈c hg:Rso de te a general unitarily invaria ,R is a permu 40 lute norm if it is a norm,and in addition (M =80l ,n)ar and al The Ky Fan Axk=∑m(A),k=1,2.,9 The Schatten-p norms of A Cmx"are P IAllsp=∑oP(A)=rIA3)p0≤p<o lAlls.o =a1(A)
Singular Values and Singular Value Inequalities 17-5 and exactly one lies in each of the intervals (d1, d2), ... , (dn−1, dn), (dn, dn + z2). Let σi = σi(A). The left and right ith singular vectors of A are u/u2 and v/v2 respectively, where u = z1 d2 1 − σ2 i , ··· , zn d2 n − σ2 i T and v = −1, d2z2 d2 2 − σ2 i , ··· , dnzn d2 n − σ2 i T . 10. (Bidiagonal) Take B = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ α1 β1 α2 ... ... βn−1 αn ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ∈ Cn×n. If all the αi and βi are nonzero, then B is called an unreduced bidiagonal matrix and (a) The singular values of B are distinct. (b) The singular values of B depend only on the moduli of α1, ... , αn, β1, ... , βn−1. (c) The largest singular value of B is a strictly increasing function of the modulus of each of the αi and βi . (d) The smallest singular value of B is a strictly increasing function of the modulus of each of the αi and a strictly decreasing function of the modulus of each of the βi . (e) (High relative accuracy) Take τ > 1 and multiply one of the entries of B by τ to give Bˆ . Then τ −1σi(B) ≤ σi(Bˆ ) ≤ τσi(B). 11. [HJ85, Sec. 4.4, prob. 26] Let A ∈ Cn×n be skew-symmetric (and possibly complex). The nonzero singular values of A occur in pairs. 17.3 Unitarily Invariant Norms Throughout this section, q = min{m, n}. Definitions: A vector norm · on Cm×n is unitarily invariant (u.i.) if A=U AV for any unitary U ∈ Cm×m and V ∈ Cn×n and any A ∈ Cm×n. ·U I is used to denote a general unitarily invariant norm. A function g : Rn → R+ 0 is a permutation invariant absolute norm if it is a norm, and in addition g (x1, ... , xn) = g (|x1|, ... , |xn|) and g (x) = g (P x) for all x ∈ Rn and all permutation matrices P ∈ Rn×n. (Many authors call a permutation invariant absolute norm a symmetric gauge function.) The Ky Fan k norms of A ∈ Cm×n are AK,k = k i=1 σi(A), k = 1, 2, ... , q. The Schatten-p norms of A ∈ Cm×n are AS,p = q i=1 σ p i (A) 1/p = tr |A| p pd 1/p 0 ≤ p < ∞ AS,∞ = σ1(A).
17-6 Handbook of Linear Algebra The trace norm of ACmx"is Other norms discussed in this section sch as the spectral norm:((A)m) and the Frobenius Warning:There is potential for considerable confusion.For example,llAll2 =llAllk=Alls,while l.llso unless m=1),and generally llAll2,llAlls.2 and llAllk.2 are all different,as are llAll, Alls.1 and llAllk.I.Nevertheless,many authors use ll lk for lllx&and lp for lllls.p. Facts: The following standard facts can be found in many texts,eg(H91,5]and [Bha97,Chap.IV]. 1.It is unitarily invariant ifand only if there isa permutation invariant e normgon such that ,ogA)for all A∈Cm nd letg bet ponding permutation invariant the dual norms (se 801As·0g1) mae+pe、 3H9 Chapter 37) rm are d while the =,A.1... 4.For amy 5.Ifll.lis F≤IA2≤IA on C,then N(A) A+a u.i.norm on Cx.A norm that arises in this way is called a 6.Let A,BCx be given.The following areequivalent (a)AluB for all unitarily invariant normsv (b)lAllks llBllK&fork=1,2.....q. ()(a(A,.…,g(A)≤w(a(B,…,og(B)l.(≤is defined in Preliminaries) The equivalence of the first two conditions is Fan's Dominance Theorem. 7.The Ky-Fan-k norms can be represented in terms of an extremal problem involving the spectral norm and the trace norm.Take A C"x".Then IlAllK&min(llll+:+Y=A)k=1,...,q. 8.[HJ91,Theorem 3.3.14]Take A,B Cmx".Then This isan important result in developing the theory of unitarily invariant norms
17-6 Handbook of Linear Algebra The trace norm of A ∈ Cm×n is Atr = q i=1 σi(A) = AK,q = AS,1 = tr |A|pd . Other norms discussed in this section, such as the spectral norm ·2 (A2 = σ1(A) = maxx=0 Ax2 x2 ) and the Frobenius norm ·F (AF = ( q i=1 σ2 i (A))1/2 = ( m i=1 n j=1 |ai j| 2)1/2), are defined in Section 7.1. and discussed extensively in Chapter 37. Warning: There is potential for considerable confusion. For example, A2 = AK,1 = AS,∞, while ·∞ =·S,∞ ( unless m = 1), and generally A2, AS,2 and AK,2 are all different, as are A1, AS,1 and AK,1. Nevertheless, many authors use ·k for ·K,k and ·p for ·S,p . Facts: The following standard facts can be found in many texts, e.g., [HJ91, §3.5] and [Bha97, Chap. IV]. 1. Let · be a norm on Cm×n. It is unitarily invariant if and only if there is a permutation invariant absolute norm g on Rq such that A = g (σ1(A), ... , σq (A)) for all A ∈ Cm×n. 2. Let · be a unitarily invariant norm onCm×n, and let g be the corresponding permutation invariant absolute norm g . Then the dual norms (see Chapter 37) satisfy AD = g D(σ1(A), ... , σq (A)). 3. [HJ91, Prob. 3.5.18] The spectral norm and trace norm are duals, while the Frobenius norm is self dual. The dual of ·S,p is ·S,p˜ , where 1/p + 1/p˜ = 1 and AD K,k = max A2, Atr k , k = 1, ... , q. 4. For any A ∈ Cm×n, q−1/2AF ≤ A2 ≤ AF . 5. If · is a u.i. norm on Cm×n, then N(A) = A∗A1/2 is a u.i. norm on Cn×n. A norm that arises in this way is called a Q-norm. 6. Let A, B ∈ Cm×n be given. The following are equivalent (a) AU I ≤ BU I for all unitarily invariant norms ·U I . (b) AK,k ≤ BK,k for k = 1, 2, ... , q. (c) (σ1(A), ... , σq (A)) w (σ1(B), ... , σq (B)). ( w is defined in Preliminaries) The equivalence of the first two conditions is Fan’s Dominance Theorem. 7. The Ky–Fan-k norms can be represented in terms of an extremal problem involving the spectral norm and the trace norm. Take A ∈ Cm×n. Then AK,k = min{Xtr + kY2 : X + Y = A} k = 1, ... , q. 8. [HJ91, Theorem 3.3.14] Take A, B ∈ Cm×n. Then |trAB∗| ≤ q i=1 σi(A)σi(B). This is an important result in developing the theory of unitarily invariant norms.
Singular Values and Singular Value Inequalities 17-7 Examples: 1.The matrix A in Example 1 of Section 17.1 has singular values20,128,and 4.So IIAll2 =20,IlAllF =24,IlAllr =44; 1AlK.1=20,1Ax2=32,IAK.3=40,1AK4=44 1Als.1=44,1As2=√624，IAls3=√/10304=21.7605,1A5.x=20. 17.4 Inequalities Definitions: Pinching is defined recursively.If A21 A22 of B is Facts: Thbe found dad eor eamle Chap.5 ules anothe 1.(Submatrices)Take AC and let B denote A with one of its rows or columns deleted.Then 之A公om dod.Then o42(A)≤o(B)≤0(A),i=1,...,9-2 Thei+2 ca B be an (m-k)x(n-1)submatrix of A.Then O+k+H(A)≤a(B)≤o(A,i=1,,q-(k+I). 4.Take AC and let B be A with some of its rows and/or columns set to zero.Then(B)s A) 1 5.Let B bea qualitiesΠ1(B)≤o(A)and (B)1.(Example 1) 6.(Singular values ofA+B)Let A.BC (a)sv(A+B)sv(A)+sv(B),or equivalently ∑o(A+B)≤∑o,(A)+∑0(B,i=1,,9 i=1 (b)Ifi+j-1s q andi,jEN,then (A+B)s(A)+aj(B)
Singular Values and Singular Value Inequalities 17-7 Examples: 1. The matrix A in Example 1 of Section 17.1 has singular values 20, 12, 8, and 4. So A2 = 20, AF = √624, Atr = 44; AK,1 = 20, AK,2 = 32, AK,3 = 40, AK,4 = 44; AS,1 = 44, AS,2 = √624, AS,3 = √3 10304 = 21.7605, AS,∞ = 20. 17.4 Inequalities Throughout this section, q = min{m, n} and if A ∈ Cm×n has real eigenvalues, then they are ordered λ1(A) ≥···≥ λn(A). Definitions: Pinching is defined recursively. If A = A11 A12 A21 A22 ∈ Cm×n, B = A11 0 0 A22 ∈ Cm×n, then B is a pinching of A. (Note that we do not require the Aii to be square.) Furthermore, any pinching of B is a pinching of A. For positive α, β, define the measure of relative separation χ(α, β) = |√α/β − √β/α|. Facts: The following facts can be found in standard references, for example [HJ91, Chap. 3], unless another reference is given. 1. (Submatrices) Take A ∈ Cm×n and let B denote A with one of its rows or columns deleted. Then σi+1(A) ≤ σi(B) ≤ σi(A), i = 1, ... , q − 1. 2. Take A ∈ Cm×n and let B be A with a row and a column deleted. Then σi+2(A) ≤ σi(B) ≤ σi(A), i = 1, ... , q − 2. The i + 2 cannot be replaced by i + 1. (Example 2) 3. Take A ∈ Cm×n and let B be an (m − k) × (n − l) submatrix of A. Then σi+k+l(A) ≤ σi(B) ≤ σi(A), i = 1, ... , q − (k + l). 4. Take A ∈ Cm×n and let B be A with some of its rows and/or columns set to zero. Then σi(B) ≤ σi(A), i = 1, ... , q. 5. Let B be a pinching of A. Then sv(B) w sv(A). The inequalities k i=1 σi(B) ≤ k i=1 σi(A) and σk (B) ≤ σk (A) are not necessarily true for k > 1. (Example 1) 6. (Singular values of A + B) Let A, B ∈ Cm×n. (a) sv(A + B) w sv(A) + sv(B), or equivalently k i=1 σi(A + B) ≤ k i=1 σi(A) + k i=1 σi(B), i = 1, ... , q. (b) If i + j − 1 ≤ q and i, j ∈ N, then σi+ j−1(A + B) ≤ σi(A) + σj(B).
17-8 Handbook of Linear Algebra (c)We have the weak majorization Isv(A+B)-sv(A)sv(B)or,equivalently,if 1i0,we have ”aAa8)≤7”aA8. ia(AB)≤Πa,(Aa(B), (b)Ifi,j ENandi+j-1s n,then +j-(AB)0,then (AB)>0and io(A)≤Πmax{。 「O(AB)O(B)1 k+ .≥and d≥…≥i.Then lldiag(x(n1)....x(am))ur s(S*-S-u+-T-v) (0【TT73)](Thompson'sStandard Multiplicative Inequalities))Take 1≤i<…<iw≤nand 1≤<…<jm≤.lfim+jm≤m+n,then Ⅱ+h-uB)≤Ⅱw,(8 8.[Bha97,X.1]Take A,B C"x" (a)If AB is normal,then Ⅱ(AB)≤Ⅱ，(BA,k=19, and,consequently,sv(AB)sv(BA),and ABBAllUr
17-8 Handbook of Linear Algebra (c) We have the weak majorization |sv(A + B) − sv(A)| w sv(B) or, equivalently, if 1 ≤ i1 0, we have i=n −k+1 i=n σi(A)σi(B) ≤ i=n −k+1 i=n σi(AB), k i=1 σi(AB) ≤ k i=1 σi(A)σi(B), k i=1 σ p i (AB) ≤ k i=1 σ p i (A)σ p i (B). (b) If i, j ∈ N and i + j − 1 ≤ n, then σi+ j−1(AB) ≤ σi(A)σj(B). (c) σn(A)σi(B) ≤ σi(AB) ≤ σ1(A)σi(B), i = 1, 2, ... , n. (d) [LM99] Take 1 ≤ j1 0, then σji(AB) > 0 and n i=n−k+1 σi(A) ≤ k i=1 max σji(AB) σji(B) , σji(B) σji(AB) ≤ k i=1 σi(A). (e) [LM99] Take invertible S, T ∈ Cn×n. Set A˜ = S AT. Let the singular values of A and A˜ be σ1 ≥···≥ σn and σ˜1 ≥···≥ σ˜n. Then diag(χ(σ1, σ˜1), , ... , χ(σn, σ˜n))U I ≤ 1 2 S∗ − S−1 U I + T∗ − T−1 U I . (f) [TT73] (Thompson’s Standard Multiplicative Inequalities) Take 1 ≤ i1 < ··· < im ≤ n and 1 ≤ j1 < ··· < jm ≤ n. If im + jm ≤ m + n, then m s=1 σis + js −s(AB) ≤ m s=1 σis(A) m s=1 σjs(B). 8. [Bha97, §IX.1] Take A, B ∈ Cn×n. (a) If AB is normal, then k i=1 σi(AB) ≤ k i=1 σi(B A), k = 1, ... , q, and, consequently, sv(AB) w sv(B A), and ABU I ≤ B AU I .
Singular Values and Singular Value Inequalities 17-9 (b)If AB is Hermitian,then sv(AB)sv(H(BA))and llABllur H(BA)Ilui,where H(X)=(X+X)/2. 9.(Term-wise singular value inequalities)[Zha2,p.28]Take A,BCm.Then 20;(AB")s i(A*A+B*B),i=1.....q and,more generally,if p,and 1/p+/=1,then 0:(AB*)<g: 、p The2a(A'B)≤a(A+B产B）and(A+B)≤(Al+Bl)are not tru in general (Example 3),but we do have IA*BI呢，≤A*Allv:lB*BuI LBhe97.Prop.I5 ITake AeC Then十49≤2a.i=2… 11.[LM02](Block triangular matrices)Let A S T ∈Cx"(R∈CpxP)have singular values a之…之aa.Lctk=min(p,n-pl.Thcn (a)If omin(R)(T),then o(R)≤，i=l,,p ≤i-p(T,i=p+1…,n b)(a1(S).,0m(S》≤(@1-m…,k-a-k+i (c)If A is invertible,then (a(T-1SR-l,,m(T-lSR-l)≤w(a-a,…,a+1-a）, (-品4-） 卫Log(d)-[人Ag Ai2 Az2 Cxbe positive definite with eigenvalues≥…≥x Assume An∈Cpxp.Setk=minip,n-pl.Then IiA)≤Ⅱa(Ana(Aahj=lk (a(APA2,m(APA)≤w(V万-VV-Va-+ (a1(4'A2,ax(4A2)》≤w)(xa,n,X2b入m-k+) Ifk =n/2,then Anllrs Anllur IAzllur. l3.(Singular values and eigenvalues))LetA∈Cx.Assume1(Al≥…≥ln(Al.Then (a)Π，l(Al≤Πtm(A,k=l,,m,with equality fork=m
Singular Values and Singular Value Inequalities 17-9 (b) If AB is Hermitian, then sv(AB) w sv(H(B A)) and ABU I ≤ H(B A)U I , where H(X) = (X + X∗)/2. 9. (Term-wise singular value inequalities) [Zha02, p. 28] Take A, B ∈ Cm×n. Then 2σi(AB∗) ≤ σi(A∗A + B∗B), i = 1, ... , q and, more generally, if p, p˜ > 0 and 1/p + 1/p˜ = 1, then σi(AB∗) ≤ σi (A∗A)p/2 p + (B∗B)p˜/2 p˜ = σi |A| p pd p + |B| p˜ pd p˜ . The inequalities 2σ1(A∗B) ≤ σ1(A∗A + B∗B) and σ1(A + B) ≤ σ1(|A|pd + |B|pd ) are not true in general (Example 3), but we do have A∗B2 U I ≤ A∗AU I B∗BU I . 10. [Bha97, Prop. III.5.1] Take A ∈ Cn×n. Then λi(A + A∗) ≤ 2σi(A), i = 1, 2, ... , n. 11. [LM02] (Block triangular matrices) Let A = ⎡ ⎣ R 0 S T ⎤ ⎦ ∈ Cn×n (R ∈ Cp×p ) have singular values α1 ≥···≥ αn. Let k = min{p, n − p}. Then (a) If σmin(R) ≥ σmax(T), then σi(R) ≤ αi , i = 1, ... , p αi ≤ σi−p (T), i = p + 1, ... , n. (b) (σ1(S), ... , σk (S)) w (α1 − αn, ··· , αk − αn−k+1). (c) If A is invertible, then (σ1(T−1 S R−1 , ... , σk (T−1 S R−1 ) w α−1 n − α−1 1 , ··· , α−1 n−k+1 − α−1 k , (σ1(T−1 S), ... , σk (T−1 S)) w 1 2 α1 αn − αn α1 , ··· , αk αn−k+1 − αn−k+1 αk . 12. [LM02] (Block positive semidefinite matrices) Let A = ⎡ ⎣ A11 A12 A∗ 12 A22 ⎤ ⎦ ∈ Cn×n be positive definite with eigenvalues λ1 ≥···≥ λn. Assume A11 ∈ Cp×p . Set k = min{p, n − p}. Then j i=1 σ2 i (A12) ≤ j i=1 σi(A11)σi(A22), j = 1, ... , k, σ1 A−1/2 11 A12 , ... , σk A−1/2 11 A12 w λ1 − λn, ... , λk − λn−k+1 , σ1 A−1 11 A12 , ... , σk A−1 11 A12 w 1 2 (χ(λ1, λn), ... , χ(λk , λn−k+1)). If k = n/2, then A122 U I ≤ A11U I A22U I . 13. (Singular values and eigenvalues) Let A ∈ Cn×n. Assume |λ1(A)|≥···≥|λn(A)|. Then (a) k i=1 |λi(A)| ≤ k i=k σi(A), k = 1, ... , n, with equality for k = n
17-10 Handbook of Linear Algebra (b)Fix p 0.Then fork=1,2....n ∑AAIs∑A. i Equality holds withk=n if and only if equality holds for all k=1,2.....n,if and only if A is normal. (c)[HJ91,p.180](Yamamoto's theorem)limg((A))=(A),i=1,...,n. 14.[LM01]LetCand,i=1,...,nbe ordered in nonincreasing absolute value.There is a matrix A with eigenvalues and singular values...if and only if Ⅱl≤Ⅱo,k=1,with cquality for=m In addition: (a)The matrix A can be taken to be upper triangular with the eigenvalues on the diagonal in any order. (b)Ifthe complex entries in ur in conjugate pairs,then A may be taken to be in real Schur form,with the 1x I and 2x 2 blocks on the diagonal in any order. (c)There is a finite construction of the upper triangular matrix in cases(a)and(b). (d)Ifn,then A cannot always be taken to be bidiagonal.(Example 5) 15.[Zha02,Chap.2](Singular values ofAo B)Take A,BCx". (a)o:(Ao B)s min(r:(A),ci(B)1-a1(B),i=1,2.....n. (b)We have the following weak majorizations: N Cmin(r (A),c(A)l;(B),=1.... ☐7Ao=a公o(g8以k=1 (c)Take X,YC"x".If A=XY,then we have the weak majorization (d)If B is positive semidefinite with diagonal entriesbbthen ∑(AoB)≤∑a(Ak=l i=l bositive definite then so is a o b (Schur product the If bothn an B ars their sigenvalues and the s eigenvalues and we have the weak multiplicative majorizations Π(B)(A)≤Ⅱ4(≤ΠA(BA≤Ⅱ(AoB.k=1,2, The inequalities are still valid if we replace Ao B by Ao BT.(Note BT is not necessarily the same as B*=B.)
17-10 Handbook of Linear Algebra (b) Fix p > 0. Then for k = 1, 2, ... , n, k i=1 |λp i (A)| ≤ k i=1 σ p i (A). Equality holds with k = n if and only if equality holds for all k = 1, 2, ... , n, if and only if A is normal. (c) [HJ91, p. 180] (Yamamoto’s theorem) limk→∞(σi(Ak ))1/k = |λi(A)|, i = 1, ... , n. 14. [LM01] Let λi ∈ C and σi ∈ R+ 0 , i = 1, ... , n be ordered in nonincreasing absolute value. There is a matrix A with eigenvalues λ1, ... , λn and singular values σ1, ... , σn if and only if k i=1 |λi| ≤ k i=1 σi , k = 1, ... , n, with equality for k = n. In addition: (a) The matrix A can be taken to be upper triangular with the eigenvalues on the diagonal in any order. (b) If the complex entries in λ1, ... , λn occur in conjugate pairs, then A may be taken to be in real Schur form, with the 1 × 1 and 2 × 2 blocks on the diagonal in any order. (c) There is a finite construction of the upper triangular matrix in cases (a) and (b). (d) If n > 2, then A cannot always be taken to be bidiagonal. (Example 5) 15. [Zha02, Chap. 2] (Singular values of A ◦ B) Take A, B ∈ Cn×n. (a) σi(A ◦ B) ≤ min{ri(A),ci(B)} · σ1(B), i = 1, 2, ... , n. (b) We have the following weak majorizations: k i=1 σi(A ◦ B) ≤ k i=1 min{ri(A),ci(A)}σi(B), k = 1, ... , n, k i=1 σi(A ◦ B) ≤ k i=1 σi(A)σi(B), k = 1, ... , n, k i=1 σ2 i (A ◦ B) ≤ k i=1 σi((A∗A) ◦ (B∗B)), k = 1, ... , n. (c) Take X, Y ∈ Cn×n. If A = X∗Y, then we have the weak majorization k i=1 σi(A ◦ B) ≤ k i=1 ci(X)ci(Y)σi(B), k = 1, ... , n. (d) If B is positive semidefinite with diagonal entries b11 ≥···≥ bnn, then k i=1 σi(A ◦ B) ≤ k i=1 biiσi(A), k = 1, ... , n. (e) If both A and B are positive definite, then so is A ◦ B (Schur product theorem). In this case the singular values of A, B and A ◦ B are their eigenvalues and B A has positive eigenvalues and we have the weak multiplicative majorizations n i=k λi(B)λi(A) ≤ n i=k biiλi(A) ≤ n i=k λi(B A) ≤ n i=k λi(A ◦ B), k = 1, 2, ... , n. The inequalities are still valid if we replace A ◦ B by A ◦ B T . (Note B T is not necessarily the same as B∗ = B.)
