Total Positive Definiteness of Hermite Interval MatricesJunwei Shao,Xiaorong HouFaculty of Science,Ningbo University,Zhejiang,PRCE-mail:junweishao@,houxiaorong@AbstractThe definition of total positive definiteness of Hermite interval matrices is given and asufficient and necessary criterion is derived to verify this property.Key words:Interval matrices;Hermite interval matrices;Total positive definitenessAMS subject classification(2000):15A18,65Y991IntroductionDetermining the total positive definiteness(and related properties)of symmetric interval matrices plays important roles in global optimization problems[1][2].For cases in real number field,papers[3][4]gave a sufficient and necessary criterion.In this paper,we mainly discussed the problem in complex numberfield,and gave the definition of total positive definiteness of Hermite interval matrices and its sufficient and necessary criterion which only needed to check positive definiteness of4n−1(n−1)!Hermite vertex matrices for a n×n Hermite interval matrix.2Some notationsWefirst introduce following definitions and notations according to paper[4].For a square real matrix A,we denote its transpose by A T,its spectral radius byρ(A), and its absolute matrix by|A|=(|A ij|),where A ij represents the element in i-th row and j-th column of Matrix A.For a n×n real symmetric matrix,eigenvalues are all real,we denote them from large to small byλ1(A)≥λ2(A)≥···≥λn(A).And matrix inequalities as A≤B or A<B are to be understood componentwise.Let A c and∆be n×n real matrices,and∆≥0,we define the following setA I=[A,A]=[A c−∆,A c+∆]={A:A c−∆≤A≤A c+∆}(1) as n×n real interval matrix.When some matrix A in A I satisfying A ij=(A)ij or A ij=(A)ij, i,j=1,...,n,then we call A a vertex matrix of A I.From this definition,we know that A I has at most2n2vertex matrices.When A c,∆are symmetric matrices,we call A I a real symmetric interval matrix,it has at most2n(n+1)/2symmetric vertex matrices.With each real symmetric matrix A I=[A c−∆,A c+∆],we shall associate the symmetric interval matrixA I s=[A c−∆ ,A c+∆ ](2)whereA c=12A c+A T c,∆ =12∆+∆here we know,if A∈A I,then12A+A T∈A I s.Now we introduce following setY={z:z∈R n,|z j|=1,j=1,...n},its cardinal number is2n.For each z∈Y,we define T z as the n×n diagonal matrix whose diagonal vector is z,and letA z=A c−T z∆T z(3)Then,for each pair i,j,we have(A z)ij=(A c−∆)ij if z i z j=1;and(A z)ij=(A c+∆)ij if z i z j=−1.So A z∈A I,in fact,A z is a vertex matrix of A I.Since A−z=A z,{A z|z∈Y} have at most2n−1different matrices(exactly2n−1when∆>0).When A I is symmetric,A z is also symmetric.Now we define function f:R n×n→R1f(A)=minx=0x T Axx T x(4)When f(A)≥0,we say that A is positive semidefinite(that is,for each x,x T Ax≥0, this definition conforms to the usual one).Similarly,when f(A)>0,we say that A is positive definite(that is,for each x=0,x T Ax>0).Real interval matrix A I is total positive (simi)definite if every A∈A I is positive(simi)definite.For the total positive(semi)definiteness of real interval matrices,we have the following elegant theorem.Theorem1.[4]Let A I be a interval matrix,then the following assertions are equivalent: (i)A I is total positive(semi)definite;(ii)A I s is total positive(semi)definite;(iii)A z is total positive(semi)definite for each z∈Y.From theorem1,it only needs to check positive(semi)definiteness of2n−1vertex matrices to determine the positive(semi)definiteness of a interval matrix.This result in paper[4]is an improvement on the one in paper[3],in the latter,it needs to check positive(semi)definiteness of2n(n−1)/2vertex matrices.Further,in paper[5],it was proved that the problem of deter-mining the total positive definiteness of a symmetric interval matrix is HP-hard.Now we consider interval matrices in complex numberfield and corresponding results.3Main resultsFirst we introduce corresponding definitions in the complex numberfield.For an n×n complex matrix C=(c rs),we denote its Hermite transpose by C H,when C=C H,we call C a Hermite matrix,it is well known that its eigenvalues are all real numbers, we denote them from large to small byλ1(C)≥λ2(C)≥...≥λn(C).Let A I,B I be n×n real interval matrices,whereA I=[A,A],B I=[B,B].We define an n×n complex interval matrix asC I=A I+iB I={A+Bi:A∈A I,B∈B I}(5)When A,B are vertex matrices of A I,B I respectively,we call A+Bi a vertex matrix of C I.It can be seen that C I has2n2×2n2=22n2vertex matrices.When A I,B I are real symmetric interval matrices,and B=−B,we can define the following n×n Hermite interval matrix:C I H={A+Bi:A∈A I,B∈B I,A is symmetric,B is antisymmetric}(6) It has at most2n(n+1)/2×2n(n−1)/2=2n2Hermite vertex matrices.Now we define the function g:C IH→R1asg(C)=minx=0x H Cxx H x(7)In fact,g(C)=λn(C).When g(C)≥0,we say that C is positive semidefinite(that is,foreach x,x H Cx≥0,this confirms the usual definition),similarly,when g(C)>0,we say that C is positive definite(that is,for each x=0,we have x H Cx>0).A Hermite interval matrix is total positive(semi)definite if each C∈C IHis positive(semi)definite.Theorem2.The minimum eigenvalues of Hermite matrices in an n×n Hermite intervalmatrix C IHobtain the minimal value at some Hermite vertex matrix.Proof.Suppose A+Bi is some Hermite matrix in C IH ,and X+Y i=(x1+y1i,x2+y2i,...,x n+y n i)T is the eigenvector which has modular1correspond to the smallest eigenvalueλn(A+Bi). Let U be the n-dimension all-1column vector,thenλn(A+Bi)=(X+Y i)H(A+Bi)(X+Y i)=U T((A+Bi)◦((X+Y i)(X+Y i)H))U(8)Where A◦B represents the Hardmard production of matrices A and B,that is,the matrix of productions of correspond elements of A and B.Next,we construct a matrix Q=(u rs+iv rs)n×n as follows:u rs=A rs,x r x s+y r y s≥0A rs,x r x s+y r y s<0v rs=B rs,x r y s−x s y r≥0B rs,x r y s−x s y r<0From the definition,we know that Q is a Hermite matrix and satisfies:u rr=A rr,v rr=B rr,u rs(x r x s+y r y s)≤A rs(x r x s+y r y s),v rs(x r y s−x x y r)≤B rs(x r y s−x x y r).therefore((u rs+iv rs)(x r+iy r)(x s−iy s))=u rs(x r x s+y r y s)+v rs(x r y s−x s y r)≤A rs(x r x s+y r y s)+B rs(x r y s−x s y r)= ((A rs+iB rs)(x r+iy r)(x s−iy s)),where (x)represents the real part of number x.Thus such Q we constructed satisfies (Q◦((X+Y i)(X+Y i)H))≤ ((A+Bi)◦((X+Y i)(X+Y i)H)),where (W n×n)=( (W ij))n×n.Note thatλn(A+Bi)=min{Z H(A+Bi)Z: Z =1,Z∈C n},thus we haveλn(Q)=min{Z H QZ: Z =1,Z∈C n}≤(X+Y i)H Q(X+Y i)=U T(Q◦((X+Y i)(X+Y i)H))U=U T (Q◦((X+Y i)(X+Y i)H))U≤U T ((A+Bi)◦((X+Y i)(X+Y i)H))U=U T((A+Bi)◦((X+Y i)(X+Y i)H))U=(X+Y i)H(A+Bi)(X+Y i)=λn(A+Bi)(9)Since A+Bi is an arbitrary Hermite matrix in C IH ,it follows that the minimum of minimaleigenvalues of Hermite matrices in C IH is obtained at some vertex Hermitematrix.Since g(C)=λn(C),we haveCorollary1.n×n Hermite interval matrix C IHis total positive(semi)definite if and only if its2n2Hermite vertex matrices are positive(semi)definite.In fact,the number of vertex matrices can be reduced to4n−1(n−1)!in Theorem2and its corollary.To prove it,we need the following auxiliary statement.First we define the sign of matrix A=(a ij)as sign(A)=(sign(a ij))and we set sign0=1.Lemma.The cardinal number of the setS n={(sign(XX T+Y Y T),sign(XY T−Y X T)):X,Y∈R n}is at most4n−1(n−1)!.Proof.We use induction on n.For n=1,S1={(sign(x21+y21),sign0)}={(1,1)},its cardinal number is1.Now suppose that the statement required is proved for S n−1.Letαi,j=(XX T+Y Y T)ij=x i x j+y i y jβi,j=(XY T−Y X T)ij=x i y j−x j y ithen we haveαj,k(x2i+y2i)=(αi,jαi,k+βi,jβi,k)βj,k(x2i+y2i)=(αi,jβi,k−αi,kβi,j)αi,j=αj,iβi,j=−βj,iαi,i≥0βi,i=0so it suffices to prove that the number of different combinations of signs of(α1,n,β1,n,α2,n,β2,n,...,αn−1,n,βn−1,n)is4(n−1).We can assume that x2i+y2i=0for each i,otherwise,the elements in i-th row and i-th column are all zeros,which can be reduced to the case corresponds to S n−1.Thereforeαj,n=αi,jαi,n+βi,jβi,nx2i+y2iβj,n=αi,jβi,n−αi,nβi,jx2i+y2i(10)Further,we havesign(αj,n)=sign(αi,jαi,n),ifαi,jβi,jαi,nβi,n≥0sign(βj,n)=sign(αi,jβi,n),ifαi,jβi,jαi,nβi,n<0(11)Fix the signs ofα1,n andβ1,n,then it suffices to prove that the number of different combinations of signs of(α2,n,β2,n,...,αn−1,n,βn−1,n)is n−1.Indeed,the number of different combinations of signs of(α1,n,β1,n)is equal to4,it therefore deduces the statement required.From(11),we know that,when wefixα1,n andβ1,n,signs ofµ2,µ3,...,µn−1are deter-mined,whereµj=αj,n orβj,n,and we denote the other number in{αj,n,βj,n}exceptµj by ˜µj.Now we choose a sign of˜µ2,again,signs ofµ2,˜µ2determine signs of someµj,˜µj,without loss of generality,we assume that they determine signs ofµ3,...,µk+2,˜µk+3,...,˜µn−1.Wefirst proved that,ifα2,n,β2,n determine a sign of the same numberµj asα1,n,β1,n do, then they determine a same sign ofµj,that is,ifsign(α1,jβ1,jα1,nβ1,n)=sign(α2,jβ2,jα2,nβ2,n)(12) thensign(α1,jα1,n)=sign(α2,jα2,n)or sign(α1,jβ1,n)=sign(α2,jβ2,n)(13) Indeed,wefirst assume thatα1,jβ1,jα1,nβ1,n≥0.Ifα1,2β1,2α1,nβ1,n≥0,thenα1,2β1,2α1,jβ1,j≥0,sosign(α2,n)=sign(α1,2α1,n),sign(α2,j)=sign(α1,2α1,j).Thereforesign(α2,jα2,n)=sign(α1,2α1,jα1,2α1,n)=sign(α1,jα1,n).While ifα1,2β1,2α1,nβ1,n<0,thenα1,2β1,2α1,jβ1,j<0,sosign(β2,n)=sign(α1,2β1,n),sign(β2,j)=sign(α1,2β1,j).Thereforesign(β2,jβ2,n)=sign(α1,2β1,jα1,2β1,n)=sign(β1,jβ1,n).with the assumptionsign(α1,jβ1,jα1,nβ1,n)=sign(α2,jβ2,jα2,nβ2,n)=1,we can deduce thatsign(α1,jα1,n)=sign(α2,jα2,n).Similarly,ifα1,jβ1,jα1,nβ1,n<0,we can prove thatsign(α1,jβ1,n)=sign(α2,jβ2,n).We now use induction to prove that whenµ2,˜µ2determine signs of the same k numbers asα1,n,β1,n do,then number of different combinations of signs of(α3,n,β3,n,...,αn−1,n,βn−1,n)after we chooseα1,n,β1,n,α2,n,β2,nis equal to k+1.When k equals1,the statement is obviously true,in the following,we suppose it has been proved for cases correspond numbers less then k.Now we choose˜µ3,thenµ3,˜µ3determine signs of p numbers in{µ4,...,µk+2},and k−1−p numbers in{˜µ4,...,˜µk+2}.From the induction hypothesis,we know this˜µ3corresponds p+1different combinations of signs of(α4,n,β4,n,...,αn−1,n,βn−1,n),while when we choose the opposite sign for˜µ3with the former one we choose,µ3,˜µ3determine signs of k−1−p numbers in{µ4,...,µk+2},and p numbers in{˜µ4,...,˜µk+2},this˜µ3 corresponds k−1−p+1=k−p different combinations of signs of(α4,n,β4,n,...,αn−1,n,βn−1,n).So the total number of different combinations of signs of(α3,n,β3,n,...,αn−1,n,βn−1,n)is equal to(p+1)+(k−p)=k+1,this is what we require.Now return to the proof of the lemma,sinceµ2,˜µ2determine signs ofµ3,...,µk+2,˜µk+3,...,˜µn−1,this µ2,˜µ2corresponds k +1different combinations of signs of them,while when we choose ˜µ2with opposite sign,then µ2,˜µ2determine signs of˜µ3,...,˜µk +2,µk +3,...,µn −1,this µ2,˜µ2corresponds n −k −3+1=n −k −2different combinations of signs of them,so the total number of different combinations of signs of(α2,n ,β2,n ,...,αn −1,n ,βn −1,n )is equal to (k +1)+(n −k −2)=n −1,as was required.Now we define a set V n for the Hermite interval matrix C I H=A I +iB I :Q =(u rs +iv rs )∈V n ⇔(M,N )∈S n ,and u rs = A rs ,M rs =1A rs ,M rs =−1,v rs = B rs ,N rs =1B rs ,N rs =−1(14)then from the proof of theorem 2,we can reduce the number of Hermite vertex matrices we used in it and its corollary.Theorem 2 .The minimum eigenvalues of Hermite matrices in a n ×n Hermite intervalmatrix C I H obtain the minimal value at a Hermite vertex matrix in V n corresponding to C I H.Corollary 1 .n ×n Hermite interval matrix C I H is total positive (semi)definite if and only if all Hermite vertex matrices in V n corresponding to C I Hare positive (semi)definite.References[1]Adjiman C S,Dallwig S,Floudas C A,et al.A Global Optimization Method,αBB,forGeneral Twice-differentiable Constrained NLPs–i.Theoretical Advances [J].Computers Chem.Engng,1998,Vol.22:1137-1158.[2]Adjiman C S,Androulakis I P,Floudas C A.A Global Optimization Method,αBB,forGeneral Twice-differentiable Constrained NLPs–ii.Implementation and Computational Results [J].Computers Chem.Engng,1998,Vol.22:1159-1179.[3]ShiZhicheng,GaoWeibin.A Necessary and Sufficient Condition for the Positive-definiteness of Interval Symmetric Matrices [J].Internat.J.Control.1986,Vol.43:325-328.[4]Rohn Jiri.Positive Definiteness and Stability of Interval Matrices [J].SIAM J.MatrixAnal.Appl.1994,Vol.15,No.1:175-184.[5]Rohn Jiri.Checking positive definiteness or stability of symmetric interval matrices isNP-hard [J].Comment.Math.Univ.Carolinae.1994,Vol.35,No.4:795-797。
