《现代数值分析》课程参考资料（数值线性代数）Singular Values and Singular Value Inequalities（Mathias, Handbook of LA, 2014）

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).