# Nonnegativity Preservation under Singular Values Perturbation

Authors: Emedin Montaño; Mario Salas; Ricardo L. Soto
Journal: Mathematical Problems in Engineering
 (2009)

---

## Abstract

We study how singular values and singular vectors of a matrixA change, under matrix perturbations of the form A+αuivi∗ and A+αupvq∗, p≠q, where α∈ℝ, A is an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n}, and uj,vk,j=1,…,m;k=1,…,n, are the left and right singular vectors,
respectively. In particular we give conditions under which this kind of
perturbations preserve nonnegativity and certain matrix structures.


---

## Body

## 1. Introduction

Asingular value decomposition of a matrix A∈ℂm×n is a factorization A=UΣV*, where Σ=diag{σ1,σ2,…,σr}∈ℝm×n,r=min{m,n},σ1≥σ2≥⋯≥σr≥0 and both U∈ℂm×m and V∈ℂn×n are unitary. The diagonal entries of Σ are called the singular values  of A. The columns uj of U are called  left singular vectors  of A and the columns vj of V are called  right singular vectors  of A. Every A∈ℂm×n has a singular value decompositionA=UΣV* and the following relations hold: Avj=σjuj,A*uj=σjvj, and uj*Avj=σj. If A∈ℝm×n, then U and V may be taken to be real (see [1]).LetA be an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n} and left and right singular vectors uj,vk,j=1,…,m;k=1,…,n, respectively. In this paper we study how singular values and singular vectors of A change, under matrix perturbations of the form A+αuivi* and A+αupvq*,p≠q,α∈ℝ. Perturbations of the form A+αuivi* were used in [2] to construct nonnegative matrices with prescribed extremal singular values. Both kinds of perturbations are closely related to the  inverse singular value problem  (ISVP), which is the problem of constructing a structured matrix from its singular values. ISVP arises in many areas of application, such as circuit theory, computed tomography, irrigation theory, mass distributions, and so forth (see [3]). The ISVP can be seen as an extension of the inverse eigenvalue problem  (IEP), which look for necessary and suffcient conditions for the existence of a structured matrix with prescribed spectrum. This problem arises in different applications, see for instance [4]. When the matrix is required to be nonnegative, we have the nonnegative inverse eigenvalue problem  (NIEP).In [5, 6] and references therein, in connection with the NIEP, it was used as a perturbation result due to Brauer [7], which shows how to modify one single eigenvalue of a matrix via a rank-one perturbation, without changing any of the remaining eigenvalues. This result was extended by Rado and presented by Perfect [8] to modify r eigenvalues of a matrix of order n,r≤n, via a perturbation of rank-r, without changing any of the n-r remaining eigenvalues. It was also used in conection with NIEP in [8, 9]. Since the eigenvalues and singular values of a matrix are closely related, the perturbation results of this paper, which preserve nonnegativity, may be also important in the NIEP. In particular, for the symmetric case, that is, the construction of a symmetric nonnegative matrix with prescribed spectrum, since the singular values are absolute values of the eigenvalues, similar results are obtained (see [10]). In [2] the following simple singular value version  of the Rado and Brauer results were given.Theorem 1.1.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr≥0,r=min{m,n}. Let
(1.1)U=(u1∣u2∣⋯∣up),V=(v1∣v2∣⋯∣vp),p≤r,
be matrices of order m×p and  n×p, whose columns are the left and right singular vectors, respectively, corresponding to σi,i=1,…,p. Let D=diag{d1,d2,…,dp} with σi+di≥0. Then A+UDV* has singular values
(1.2){σ1+d1,…,σp+dp,σp+1,…,σr}.Note that the singular values ofA+UDV* are not necessarily in nondecreasing order. However we can reorderer them by using an appropriate permutation.Corollary 1.2.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr≥0,r=min{m,n}. Let ui and vi, respectively, the left and right singular vectors corresponding to σi,i=1,…,r. Let α∈ℝ such that α+σi≥0,i=1,…,r. Then A+αuivi* has singular values
(1.3)σ1,…,σi-1,σi+α,σi+1,…,σr.Remark 1.3.
The perturbation given by Theorem1.1 allow us to have certain control on the spectral condition number of the perturbed matrix. That is, if κ2(A)=σ1/σr, then we may choose 0<α1≤σ1-σ2 and 0<αr≤σr-1-σr in such a way that
(1.4)κ2(A-α1u1v1*+αrurvr*)=σ1-α1σr+αr<κ2(A).The paper is organized as follows. In Section2 we consider perturbations of the form A+αuivi*, which we will call simple perturbations,  and give sufficient conditions under which the perturbation preserves nonnegativity. In Section 3 we discuss perturbations of the form A+αupvq*,p≠q, which, because of their different indices, we will call mixed perturbations. We also give sufficient conditions in order that mixed perturbations preserve nonnegativity. It is also shown that both, simple and mixed perturbations, preserve doubly stochastic structure. Finally, we show some examples to illustrate the results.


## 2. Nonnegativity Preservation under Simple Perturbations

LetA be an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n}. In this section we consider perturbations A+αuiviT, which preserve nonnegativity. Note that if A is an m×n nonnegative matrix, then the left and right singular vectors u1 and v1, corresponding to the maximal singular value σ1,respectively, are nonnegative. Hence, in this case, the matrix A+αu1v1T is nonnegative for all α>0.Now, let us consider the perturbationA+αuiviT, with i>1. Let us and vs be the left and right singular vectors corresponding to σs,s>1, respectively. Let α>0 and let the entry in position (i,k) of usvsT be negative. That is, (usvsT)ik<0. Then if A=(aik) is nonnegative,
(2.1)aik+α(usvsT)ik≥0iff0<α≤aik|(usvsT)ik|.
Thus, to preserve the nonnegativity of A it is enough to choose α in the interval
(2.2)(0,mini,kaik|(usvsT)ik|],
provided that aik>0, otherwise (usvsT)ik must be zero. Then from (2.2) and Theorem 1.1 we have the following result.Lemma 2.1.
LetA be an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n}. Let α be in the interval
(2.3)(0,minsmini,kaik|(usvsT)ik|].
Then A+αusvsT,s=2,…,r, is nonnegative with singular values
(2.4)σ1,…,σs-1,σs+α,σs+1,…,σr.Remark 2.2.
It is clear that if in Lemma2.1, α is taken in
(2.5)(0,minsmini,kaik|(usvsT)ik|),
then A+αusvsT,2≤s≤r, is positive with singular values
(2.6)σ1,…,σs-1,σs+α,σs+1,…,σr.
Moreover, for α in intervals in Lemma 2.1 and this remark, the nonnegativity is obtained independently of the chosen singular vectors us,vs.A more handle interval forα is given by the following lemma.Lemma 2.3.
LetA be an m×n positive matrix with singular values σ1≥⋯≥σr>0,r=min{m,n}. Let α be in the interval
(2.7)(0,σrmini,kaikσ1+∑j=1r-1σj].
Then A+αusvsT,2≤s≤r, is nonnegative with singular values
(2.8)σ1,…,σs-1,σs+α,σs+1,…,σr.Proof.
From (2.2) and since |aik|≤σ1, see [1, Corollary  3.1.3], we have
(2.9)maxi,k|(usvsT)ik|=maxi,k|aikσs-∑j=1,j≠srσjσs(ujvjT)ik|≤1σsmaxi,k|aik|+∑j=1,j≠srmaxi,kσjσs|(ujvjT)ik|≤1σsmaxi,k|aik|+∑j=1,j≠srmaxi,kσjσs≤σ1σs+∑j=1,j≠srσjσs≤1σs(2σ1+∑j=2,j≠srσj)=1σs(2σ1-σs+∑j=2rσj)=2σ1σs-1+∑j=2rσjσs≤2σ1σr-1+∑j=2rσjσr=σ1σr+∑j=1r-1σjσr.
Then
(2.10)1maxi,k|(usvsT)ik|≥σrσ1+∑j=1r-1σj,mini,kaikmaxi,k|(usvsT)ik|≥σrmini,kaikσ1+∑j=1r-1σj.
Hence we have
(2.11)(0,σrmini,kaikσ1+∑j=1r-1σj]⊆(0,mini,kaikmaxi,k|(usvsT)ik|]⊆(0,mini,kaik|(usvsT)ik|],(0,σrmini,kaikσ1+∑j=1r-1σj]⊆(0,minsmini,kaik|(usvsT)ik|].
Then, from Lemma 2.1 the result follows.Remark 2.4.
For positiveA=(aij), and α∈ℝ, we repeat the arguments from Lemmas 2.1 and 2.3 to obtain that if α is in the interval
(2.12)[-σrmini,kaikσ1+∑j=1r-1σj,σrmini,kaikσ1+∑j=1r-1σj],
then A+αusvsT,s=2,…,r, is nonnegative with singular values
(2.13)σ1,…,σs-1,|σs+α|,σs+1,…,σr.Now we consider rank-2 perturbations, A+UDV*, where U=(us,ut),D=diag{α1,α2},V=(vs,vt). That is, perturbations of the form A+α1usvsT+α2utvtT as in Theorem 1.1. Let A be an m×n positive matrix with singular values σ1≥⋯≥σr>0,r=min{m,n}. Then A+α1usvsT+α2utvtT will be nonnegative if
(2.14)aik+α1(usvsT)ik+α2(utvtT)ik≥0,i=1,…,m;j=1,…,n.
From the family of straight lines
(2.15)α2=-(usvsT)ik(utvtT)ikα1-aik(utvtT)ik,i=1,…,m;j=1,…,n,
it follows that they intersect the axes α1 and α2 at points
(2.16)(-aik(usvsT)ik,0),(0,aik(usvsT)ik),
where (usvsT)ik≠0 and (utvtT)ik≠0, respectively. Let
(2.17)E=maxi,k(usvsT)ik>0(-aik(usvsT)ik),F=maxi,k(utvtT)ik>0(-aik(utvtT)ik),G=mini,k(usvsT)ik<0(-aik(usvsT)ik),H=mini,k(utvtT)ik<0(-aik(utvtT)ik).
Let
(2.18)R1={(α1,α2):E≤α1≤0⋀-FEα1+F≤α2≤-HEα1+H},R2={(α1,α2):0≤α1≤G⋀-FGα1+F≤α2≤-HGα1+H}.
Then A+α1usvsT+α2utvtT is nonnegative for (α1,α2)∈R1∪R2.A more handle region for(α1,α2) is given by the following lemma.Lemma 2.5.
LetA be an m×n positive matrix with singular values σ1≥⋯≥σr>0,r=min{m,n}. Let P1=(E,0),P2=(0,F),P3=(G,0),P4=(0,H) be the intersection points in (2.17). Let
(2.19)(α1,α2)∈S={(x,y):∥(x,y)∥1}≤mink=1,2,3,4{∥Pk∥1},
where ∥·∥1 is the l1 norm. Then A+α1usvsT+α2utvtT,2≤s,t≤r, is nonnegative with singular values σ1,…,|σs+α1|,…,|σt+α2|,…,σr.Example 2.6.
Let(2.20)A=(124568494),
with singular values σ1=15.5687298,σ2=3.9581084, and σ3=0.9736668. Let
(2.21)U=(u2∣u3),V=(v2∣v3),D=diag{α1,α2},
where
(2.22)u2=(0.42198230.5264618-0.7380847),u3=(0.8658718-0.47531920.1560054),v2=(0.0257579-0.66699210.7446195),v3=(-0.91068400.29155410.2926616).
From (2.17) we compute E,F,G,H. Then, the intersection points are
(2.23)(-12.7300876,0),(7.1058357,0),(0,-7.9224079),(0,1.2681734),
and S={(x,y):∥(x,y)∥1≤1.2681734}. Thus, from Lemma 2.5, for (α1,α2)=(-1/2,1/2) we have
(2.24)A+α1u2v2T+α2u3v3T=(0.600302.26703.96965.20976.10637.73443.93858.77664.2976),
with singular values σ1,σ2+α1,σ3+α2.Remark 2.7.
LetA be an m×n complex matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n} and singular value decomposition A=UΣV*. In [11] it was defined the concept of energy of A as ℰ(A)=σ1+σ2+⋯+σr. If A is positive, then as an application of the rank-2 perturbation result, from Lemma 2.5 and Remark 2.4, we may construct, for
(2.25)0<α≤min{σrmini,kaikσ1+∑j=1r-1σj,σj},
a family of nonnegative matrices B=A+αuiviT-αujvjT, with ℰ(B)=ℰ(A). Now, suppose A is nonnegative with ℰ(A)≤C, where C is an upper bound. Then from (1.2), by taking  α=C-ℰ(A) we may construct a family of nonnegative matrices B=A+αu1v1T with ℰ(B)=ℰ(A)+α=C.Now, in order to show that simple perturbations preserve doubly stochastic structure we need the following lemma. First we introduce a definition and a notation. Ann×n matrix A=(aij) is said to be with constant row sums  if ∑j=1naij=α,i=1,2,…,n. We denote by CSα the set of all matrices with constant row sums equal to α.Lemma 2.8.
LetA be an n×n irreducible doubly stochastic matrix and let Ax=λx,xT=(x1,…,xn), with λ≠1. Then
(2.26)S(x)=x1+x2+⋯+xn=0.Proof.
SinceA is doubly stochastic, then
(2.27)S(Ax)=Σa1jxj+Σa2jxj+⋯+Σanjxj=x1Σai1+x2Σai2+⋯+xnΣain=S(x),
and S(Ax)=S(λx)=λS(x). Then,
(2.28)S(x)=λS(x),
and since λ≠1,S(x)=0.The following result shows that simple perturbations preserve doubly stochastic structure.Proposition 2.9.
LetA be an n×n irreducible doubly stochastic matrix. Then,
(2.29)(i)(A+α1u1v1T)∈CS1+α1,(A+α1u1v1T)T∈CS1+α1,(ii)(A+αiuiviT)∈CS1,(A+αiuiviT)T∈CS1;i=2,…,n,(iii)(A+∑i=1nαiuiviT)∈CS1+α1.Proof.
SinceA,AT∈CS1, then AAT∈CS1 and ATA∈CS1. Hence, the singular vectors u1 and v1 are
(2.30)u1=v1=1ne=1n(1,1,…,1)T.
Then α1u1v1T=α1v1u1T=(1/n)α1eeT and α1u1v1T∈CSα1. Thus (i) holds.  From Lemma 2.8, αiuiviTe=αi(viTe)ui=0 and (ii) holds. From (i) and (ii) we have (iii).Example 2.10.
Consider the matrix(2.31)A=(4321143221433214),
which is nonnegative generalized doubly stochastic, that is, A is nonnegative with A,AT∈CS10, and A has singular values 10,2.8284,2,8284,2. Let UΣV* be the singular value decomposition of A. Let D=diag{4,3,2,1}. Then
(2.32)B=A+UDV*=(6.25964.85002.24040.65011.08226.00814.41782.49192.24040.65016.25964.85004.41782.49191.08226.0081)
is nonnegative generalized doubly stochastic with singular values 14,5.8284,4.8284,3.


## 3. Nonnegativity Preservation under Mixed Perturbations

In this section we discuss matrix perturbations of the formA+αukvj*, with k≠j̇, which we will call mixed perturbations, and we study how the singular values and vectors change under this kind of perturbations. We also give sufficient conditions under which mixed perturbations preserve nonnegativity and preserve doubly stochastic structure. Let us start by considering the following particular case: let A be a 4×3 matrix with singular values σ1,σ2,σ3. Let A=UΣV* with U=(u1∣u2∣u3∣u4) andV=(v1∣v2∣v3). Let α≥0. That is,
(3.1)A=(u1∣u2∣u3∣u4)(σ1000σ2000σ3000)(v1*v2*v3*)=∑k=13σkukvk*.
The matrix αu1v2* has the singular value decomposition:
(3.2)αu1v2*=(u1∣u2∣u3∣u4)(α00000000000)(v2*v1*v3*)=(u1∣u2∣u3∣u4)(α00000000000)(010100001)(v1*v2*v3*)=(u1∣u2∣u3∣u4)(0α0000000000)(v1*v2*v3*).
Then,
(3.3)A+αu1v2*=(u1∣u2∣u3∣u4)(σ1α00σ2000σ3000)(v1*v2*v3*).
Now we compute the singular values of the matrix
(3.4)C=(σ1α00σ2000σ3000),
by computing the eigenvalues of C̃C̃T, where C̃=(σ1α0σ2). Since
(3.5)C̃C̃T=(α2+σ12ασ2ασ2σ22),
then
(3.6)tr(C̃C̃T)=α2+σ12+σ22=λ1+λ2,det(C̃C̃T)=σ12σ22=λ1λ2
with λ1,λ2 being the eigenvalues of C̃C̃*. Thus, we obtain
(3.7)λ1=α2+σ12+σ22+(α2+σ12+σ22)2-4σ12σ222,λ2=α2+σ12+σ22-(α2+σ12+σ22)2-4σ12σ222.
Hence, the singular values of A+αu1v2* are λ1,λ2,σ3.Now we generalize these results form×n matrices.Theorem 3.1.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr≥0,r=min{m,n}, and with singular value decomposition A=UΣV*, where
(3.8)U=(u1∣⋯∣uk∣⋯∣um),V=(v1∣⋯∣vj∣⋯∣vn),Σ=diag(σ1,σ2,…,σr),k,j≤r.
Let α∈ℝ. Then A+αukvj* has singular values,
(3.9){σ1,…σk-1,σ̃k,σk+1,…,σj-1,σ̃j,σj+1,…,σr},
where
(3.10)σ̃k=(α2+σk2+σj2+(α2+σk2+σj2)2-4σk2σj22)1/2,(3.11)σ̃j=(α2+σk2+σj2-(α2+σk2+σj2)2-4σk2σj22)1/2.Proof.
Without loss of generality we may assume thatm≥n and j>k. The matrix αukvj* has a singular value decomposition
(3.12)αukvj*=(±uk∣⋯∣uk-1∣u1∣uk+1∣⋯∣um)Σ̃(vj*⋮vj-1*v1*vj+1*⋮vn*),
where Σ̃=diag{|α|,0,…,0}. The decomposition in (3.12) can be written as
(3.13)αukvj*=UPkΣ̃QjV*,
where Pk and Qj are m×m and n×n permutation matrices of the form
(3.14)Pk=(Wk00Im-k),Qj=(Wj00In-j),
with
(3.15)Wl=(1Il-21)oforderl.
Since
(3.16)Σ̃=(α⋱⋱),thenPkΣ̃Qj=(⋱(α)k,j⋱),
where if α<0, we multiply the uk vector by minus one. Then
(3.17)A+αukvj*=U(Σ+PkΣ̃Qj)V*=U(Λ0)V*,
where
(3.18)Λ=(σ1⋱σk⋯α⋱⋮σjσn).
By applying row and column permutations on the matrix Σ+PkΣ̃Qj, it follows from (3.17) and (3.18) that the singular values of A+αukvj* are
(3.19){σ1,…,σk-1,σ̃k,σk+1,…,σj-1,σ̃j,σj+1,…,σn},
where σ̃k and σ̃j are as in (3.10) and (3.11), respectively.Observe that in Theorem3.1, A+αukvj* has singular values
(3.20){σ1,…σk-1,σ̃k,σk+1,…,σj-1,σ̃j,σj+1,…,σr},
if k,j≤r. If r<k≤m, then only σj, corresponding to the right singular vector vj, changes and take the form σ̃j=α2+σj2. A straightforward calculation shows that for α>0,σ̃k≤σk+α. Observe that
(3.21)σ̃j=α2+σj2≤σj+α.Example 3.2.
Let(3.22)A=(120613041150),
with singular values σ1=7.8207,σ2=5.6257,σ3=1.09.Let
(3.23)u1=(0.260300.703860.397760.52784)T,v2=(0.63252-0.716470.29425)T,
left and right singular vectors of A, respectively. Let α=1. Then, from (3.10) and (3.11), the matrix
(3.24)A+αu1v2*=(1.16461.81350.0765936.44520.495713.20710.251593.7151.1171.33394.62180.15532)
has singular values σ̃1=7.9477,σ̃2=5.5358 and σ3. By using Theorem 1.1 we have that A+u1v1*+u2v2* has singular values σ1+1=8.8207,σ2+1=6.6257,andσ3=1.09.Different from perturbations of the formA+αuiviT, the perturbation of Theorem 3.1 affects not only the singular values σk and σj, but also the corresponding left and right singular vectors uk and vj. To make this modification clear, we consider again the previous discussion to Theorem 3.1:
(3.25)A+αu1v2*=(u1∣u2∣u3∣u4)(σ1α00σ2000σ3000)(v1*v2*v3*).
Let
(3.26)C̃=(σ1α0σ2)=(ω11ω12ω21ω22)(σ̃100σ̃2)(υ11υ12υ21υ22)T,
the SVD of C̃ with σ̃1,σ̃2 obtained from (3.10) and (3.11), respectively. The left singular vectors of
(3.27)C=(σ1α00σ2000σ3000)
(eigenvectors of CCT) are
(3.28)ũ1=(ω11ω2100)T,ũ2=(ω12ω2200)T,ũ3=(0010)T=e3,ũ4=(0001)T=e4,
and its corresponding right singular vectors (eigenvectors of CTC) are
(3.29)ṽ1=(υ11υ210)T,ṽ2=(υ12υ220)T,ṽ3=(001)T=e3.
Thus, A+αu1v2* can be written as A+αu1v2*=ŨΣ̃Ṽ*, where
(3.30)Ũ=(u1∣u2∣u3∣u4)(ũ1∣ũ2∣ũ3∣ũ4)=(ω11u1+ω21u2∣ω12u1+ω22u2∣u3∣u4),Ṽ=(v1∣v2∣v3)(ṽ1∣ṽ2∣ṽ3)=(υ11v1+υ21v2∣υ12v1+υ22v2∣v3),Σ̃=diag(σ̃1,σ̃2,σ3).
Now, we generalize this result. Without loss generality we assume that k<j. From (3.17) and (3.18), by permuting rows and columns of the matrix Σ+PkΣ̃Qj, we have
(3.31)A+αukvj*=U1(Λ0)V1*withΛ=(σ1⋱σkασj⋱0σn),U1=(u1∣⋯∣uk∣uj∣⋯∣uk+1∣uj+1∣⋯∣um),V1=(v1∣⋯∣vk∣vj∣⋯∣vk+1∣vj+1∣⋯∣vn).
The singular vectors of (Λ0) are obtained from the singular vectors of the 2×2 matrix (σkα0σj). Let
(3.32)(σkα0σj)=(ω11ω12ω21ω22)(σ̃k00σ̃j)(υ11υ12υ21υ22)T.
Then the unitary matrices of the singular value decomposition of (Λ0) are
(3.33)U2=(Iω11ω12ω21ω22I)=(e1∣⋯∣ek-1∣ũk∣ũk+1∣ek+2∣⋯∣em),V2=(Iv11v12v21v22I)=(e1∣⋯∣ek-1∣ṽk∣ṽk+1∣ek+2∣⋯∣en),
of order m×m and n×n, respectively. Then
(3.34)A+αukvj*=Ũ(Λ̃0)Ṽ*withŨ=U1U2,Ṽ=V1V2,Λ̃=(σ1⋱σ̃kσ̃j⋱σn),
where σ̃k and σ̃j are not ordered. Since
(3.35)Ũ=(u1∣⋯∣ω11uk+ω21uj∣ω12uk+ω22uj∣⋯∣um),Ṽ=(v1∣⋯∣υ11vk+υ21vj∣υ12vk+υ22vj∣⋯∣vn),
then the singular vectors corresponding to σk,σj have been modified. We have prove the following result.Corollary 3.3.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n} and with singular value decomposition A=UΣV*, where
(3.36)U=(u1∣⋯∣uk∣⋯∣um),V=(v1∣⋯∣vj∣⋯vn),k,j≤r,Σ=diag{σ1,σ2,…,σr}.
Let α∈ℝ. Then A+αukvj* has left singular vectors,
(3.37)ũi=ui,i=1,…,m,i≠k,i≠j,ũk=ω11uk+ω21uj,ũj=ω12uk+ω22uj
and right singular vectors
(3.38)ṽi=vi,i=1,…,n,i≠k,i≠j,ṽk=υ11vk+υ21vj,ṽj=υ12vk+υ22vj.Observe that if2×2 orthogonal matrices in (3.32) are of the same type
(3.39)(cs-sc)or(css-c),
then a straight forward calculation shows that (3.37) and (3.38) become
(3.40)ũi=ui,i=1,…,m,i≠k,i≠j,ũk=c1uk-s1uj,ũj=s1uk+c1uj
and
(3.41)ṽi=vi,i=1,…,n,i≠k,i≠j,ṽk=c2vk-s2vj,ṽj=s2vk+c2vj,
respectively, while if they are of different type, then (3.38) becomes
(3.42)ṽi=vi,i=1,…,m,i≠k,i≠j,ṽk=c2vk+s2vj,ṽj=s2vk-c2vj.
From (3.10) and (3.11) it is clear that σ̃k>σ̃j with k<j. The following result tells us how the new singular values σ̃k,σ̃j relate with the previous singular values σk,σj.Corollary 3.4.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr≥0,r=min{m,n} and with singular value decomposition A=UΣV*, where
(3.43)U=(u1∣⋯∣uk∣⋯∣um),V=(v1∣⋯∣vj∣⋯vn),k,j≤r,Σ=diag{σ1,σ2,…,σr}.
Let σ̃k,σ̃j,k<j, be respectively, as in (3.10) and (3.11), the singular values of A+αukvj*. Then σ̃k>σk≥σj>σ̃j.Proof.
Since4σj2α2>0 we have
(3.44)(σk2+α2)2+σj4+2σj2(σk2+α2)-4σk2σj2>(σk2+α2)2+σj4-2σj2(σk2+α2),(σk2+σj2+α2)2-4σk2σj2>((σk2+α2)-σj2)2,σk2+α2+σj2-(σk2+σj2+α2)2-4σk2σj2<2σj2.
Thus
(3.45)σj>(12[σk2+α2+σj2-(σk2+σj2+α2)2-4σk2σj2])1/2.
In the same way,
(3.46)(σj2+α2)2+σk4+2σk2(σj2+α2)-4σk2σj2>(σj2+α2)2+σk4-2σk2(σj2+α2),(σk2+σj2+α2)2-4σk2σj2>(σk2-(σj2+α2))2,σk2+σj2+α2+(σk2+σj2+α2)2-4σk2σj2>2σk2.
Then
(3.47)σk<(12[σk2+α2+σj2+(σk2+σj2+α2)2-4σk2σj2])1/2.
Therefore,
(3.48)σ̃k>σk≥σj>σ̃j.
Observe that σi∈(σ̃j,σ̃k),i=k,k+1,…,j. In particular for k=1 and j=n, all singular values of A are in the interval (σ̃n,σ̃1).Now we extend the mixed perturbation result given by Theorem3.1 to rank-2 perturbations, that is, perturbations of the form B=A+α1uk1vj1+α2uk2vj2, with α1,α2 nonzero real numbers and uki,vji,i=1,2,ki<ji,k1<j1<k2<j2, being left and right singular vectors of A, respectively. Then as in (3.12)
(3.49)(±uk1,±uk2,…,u1,uk1+1,…,uk2-1,u2,uk2+1,…,um)Σ̃(vj1*vj2*⋮v1*vj1+1*⋮vj2-1*v2*vj2+1*⋮vn*),
with Σ̃=diag(|α1|,|α2|,0,…,0).  It is clear that the matrix in (3.49) can be written as
(3.50)UP1P2Σ̃Q2Q1V*,
where P1,P2,Q1,Q2 are permutation matrices of the form
(3.51)P1=(Wk1Im-k1),P2=(1Wk2Im-(k2+1)),Q1=(Wj1In-j1),Q2=(1Wj2In-(j2+1)).
From (3.50), the matrix in (3.49) is
(3.52)((α1)k1,j1(α2)k2,j2),
where if α1,α2 are negative, we multiply uk1,uk2 by minus one. Thus,
(3.53)B=A+α1uk1vj1*+α2uk2vj2*=U(Λ0)V*,
where
(3.54)Λ=(σ1⋱σk1⋯αk1,j1⋱⋮σj1⋱σk2⋯αk2,j2⋱⋮σj2⋱σn).
By permuting rows and columns of Λ it follows that singular values of (Λ0) are
(3.55)σ1,…,σk1-1,σk1+1,…,σj1-1,σj1+1,…,σk2-1,σk2+1,…,σj2-1,σj2+1,…,σn
together with the singular values of
(3.56)C1=(σk1αk1,j10σj1),C2=(σk2αk2,j20σj2).
Is immediate that the singular values of these matrices are
(3.57)σ̃k1=(α12+σk12+σj12+(α12+σk12+σj12)2-4σk12σj122)1/2,σ̃j1=(α12+σk12+σj12-(α12+σk12+σj12)2-4σk12σj122)1/2,σ̃k2=(α22+σk22+σj22+(α22+σk22+σj22)2-4σk22σj222)1/2,σ̃j2=(α22+σk22+σj22-(α22+σk22+σj22)2-4σk22σj222)1/2.
The matrix B=A+α1uk1vj1*+α2uk2vj2* can be written as
(3.58)B=Ũ(Λ̃0)Ṽ*withŨ=U1U2,Ṽ=V1V2,Λ̃=(σ1⋱σ̃k1σ̃j1⋱σ̃k2σ̃j2⋱σn),
where the σ̃’s are not ordered,
(3.59)U1=(u1,u2⋯uk1,uj1⋯uk1+1,uj1+1⋯uk2,uj2⋯uk2+1,uj2+1⋯um),V1=(v1,v2⋯vk1,vj1⋯vk1+1,vj1+1⋯vk2,vj2⋯vk2+1,vj2+1⋯vn),U2=(e1⋯ek1-1,ũk1ũk1+1,ek1+2⋯ek2-1,ũk2,ũk2+1,ek2+2⋯em),V2=(e1⋯ek1-1,ṽk1ṽk1+1,ek1+2⋯ek2-1,ṽk2,ṽk2+1,ek2+2⋯en).
We have proved the following result.Theorem 3.5.
LetA be an m×n matrix with singular values σ1≥σ2≥⋯≥σr≥0,r=min{m,n} and SVD A=UΣV*, where
(3.60)U=(u1,u2⋯uk1⋯uk2⋯um),V=(v1,v2⋯vj1⋯vj2⋯vn),ki,ji≤r,ki≠ji, are m×m and n×n unitary matrices, respectively, and Σ=diag{σ1,σ2,…,σr}. Let α1,α2 be real numbers. Then B=A+α1uk1vj1*+α2uk2vj2* has singular values
(3.61)⋃q=1q≠ki,jir{σq}∪{σ̃k1,σ̃j1,σ̃k2,σ̃j2},(3.62)σ̃ki=(αi2+σki2+σji2+(αi2+σki2+σji2)2-4σki2σji22)1/2,(3.63)σ̃ji=(αi2+σki2+σji2-(αi2+σki2+σji2)2-4σki2σji22)1/2i=1,2. The singular vectors are given by
(3.64)ũq=uq,q=1,…,m,q≠ki,q≠ji,i=1,2,ũk1=ω11(1)uk1+ω21(1)uj1,ũj1=ω12(1)uk1+ω22(1)uj1,ũk2=ω11(2)uk2+ω21(2)uj2,ũj2=ω12(2)uk2+ω22(2)uj2,
where the coefficients ω’s are obtained as before, and
(3.65)ṽq=vq,q=1,…,n,q≠ki,q≠ji,i=1,2,ṽk1=υ11(1)vk1+υ21(1)vj1,ṽj1=υ12(1)vk1+υ22(1)vj1,ṽk2=υ11(2)vk2+υ21(2)vj2,ṽj2=υ12(2)vk2+υ22(2)vj2.Now, as in Lemma2.1 in Section 2, we look for a condition to preserve nonnegativity when we deal with mixed perturbations. Let A be an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n}, and with singular value decomposition A=UΣV*, where
(3.66)U=(u1∣⋯∣up∣⋯∣um),V=(v1∣⋯∣vq∣⋯∣vn),p,q≤r,Σ=diag{σ1,σ2,…,σr}.
Then A+αupvqT is nonnegative for α>0 if aik+α(upvqT)ik≥0,i=1,…,m,k=1,…,n. If (upvqT)ik<0, then
(3.67)aik+α(upvqT)ik≥0iff0<α≤mini,kaik|(upvqT)ik|.
Then we have the following result.Lemma 3.6.
LetA be an m×n positive matrix with singular values σ1≥σ2≥⋯≥σr>0,r=min{m,n}. Let α be in the interval
(3.68)(0,minp,qmini,kaik|(upvqT)ik|].
Then A+αupvqT,1≤p≤m,1≤q≤n,p≠q, is nonnegative with singular values
(3.69)σ1,…,σp-1,σ̃p,σp+1,…,σq-1,σ̃q,σq+1,…,σr,
where σ̃p and σ̃q are defined as in (3.62) and (3.63), respectively.Example 3.7.
LetA=(123456) be with singular values σ1=9.5255,σ2=0.5143.A=UΣVT, where
(3.70)U=(0.22985-0.883460.408250.52474-0.24078-0.816500.819640.401900.40825),V=(0.619630.784890.78489-0.61963).
Then, from (3.68) we have for p=1,2,3;q=1,2,(3.71)minp,qmini,kaik|(upvqT)ik|=1.8268
and α∈(0,1.8268]. For α=1.8268, we have
(3.72)A+αu1v2T=(123456)+1.8268(0.18041-0.142420.41186-0.325140.64333-0.50787)=(1.32961.73983.75243.4066.17525.0722)
is nonnegative with singular values σ̃1=9.6996  and  σ̃2=0.5050.To show that mixed perturbations preserve doubly stochastic structure, observe from Lemma2.8 that upvqTe=0 for q=2,…,n. Then, if A is an n×n positive doubly stochastic matrix, we have that A+αupvqT is doubly stochastic.



---

*Source: 301582-2009-07-26.xml*