RATIONAL FACTORIZATIONS OF COMPLETELY POSITIVE MATRICES 7 1 MATHIEUDUTOURSIKIRIC´, ACHILLSCHU¨RMANN,ANDFRANKVALLENTIN 0 2 Abstract. In this note it is proved that every rational matrix which lies in b the interior of the cone of completely positive matrices also has a rational e cp-factorization. F 6 ] C 1. Introduction O The cone of completely positive matrices is central to copositive programming, . h see [3] and also to several topics in matrix theory, see [1]. However, so far, this t cone is quite mysterious, many basic questions about it are open. In [2] Berman, a m Du¨r, and Shaked-Monderer ask: Given a matrix A∈CPn all of whose entries are integral, does A always have a rational cp-factorization? [ The cone of completely positive matrices is defined as the convex cone spanned 2 by symmetric rank-1-matrices xxT where x lies in the nonnegative orthant Rn : ≥0 v 8 CP =cone{xxT :x∈Rn }. n ≥0 4 1 A cp-factorization of a matrix A is a factorization of the form 3 m .0 A=XαixixTi with αi ≥0 and xi ∈Rn≥0, for i=1,...,m. 1 i=1 0 We talk about a rational cp-factorization when the α ’s are rational numbers and 7 i 1 when the xi’s are rational vectors. Of course, in a rational cp-factorization we can : assume that the x ’s are integral vectors. v i In this note we prove the following theorem: i X Theorem 1.1. Every rational matrix which lies in the interior of the cone of r a completely positive matrices has a rational cp-factorization. SotofullyanswerthequestionofBerman,Du¨r,andShaked-Monderer,itremains to consider the boundary of CP . n 2. Proof of Theorem 1.1 For the proof we will need a classical result from simultaneous Diophantine approximation, a theorem of Dirichlet, which we state here. One can find a proof of Dirichlet’s theorem for example in the book [4, Theorem 5.2.1] of Gr¨otschel, Lov´asz,and Schrijver. Date:February4,2017. 1991 Mathematics Subject Classification. 90C25. Keywordsandphrases. copositiveprogramming,completelypositivematrix,cp-factorization. 1 2 M.DutourSikiri´c,A.Schu¨rmann,F.Vallentin Theorem 2.1. Let α ,...,α be real numbers and let ε be a real number with 1 n 0 < ε < 1. Then there exist integers p ,...,p and a natural number q with 1 n 1≤q ≤ε−n such that p ε (cid:12)(cid:12)αi− i(cid:12)(cid:12)≤ for all i=1,...,n. (cid:12) q (cid:12) q (cid:12) (cid:12) Thenextlemmacollectsstandard,easy-to-provefactsaboutconvexcones. LetE be aEuclideanspacewithinner producth·,·i. LetK ⊆E be aproper convex cone, which means that K is closed, has a nonempty interior, and satisfies K ∩(−K)= {0}. Its dual cone is defined as K∗ ={y ∈E :hx,yi≥0 for all x∈K}. Lemma 2.2. Let K ⊆E be a proper convex cone. Then, (1) int(K)={x∈E :hx,yi>0 for all y ∈K∗\{0}}, where int(K) is the topological interior of K, and (2) K∗ =(cl(K))∗, where cl(K) is the topological closure of K. Weneedsomemorenotation: WithSn wedenotethevectorspaceofsymmetric matriceswithnrowsandncolumnswhichis aEuclideanspacewithinner product hA,Bi= Trace(AB) = n A B . The cone of copositive matrices is the dual Pi,j=1 ij ij cone of CP : n COP =CP∗ ={B ∈Sn :hA,Bi≥0 for all A∈CP}. n n Its interior equals int(COP )={B ∈Sn :hB,xxTi>0 for all x∈Rn \{0}}. n ≥0 We also define the following rational subcone of CP : n C˜P =cone{vvT :v ∈Zn }. n ≥0 We prepare the proof of the paper’s main result by two lemmata which might be useful facts themselves. Lemma 2.3. The set R={B ∈Sn :hB,vvTi≥1 for all v ∈Zn \{0}}, ≥0 is contained in the interior of the cone of copositive matrices COP . n Proof. Since the set of nonnegative rational vectors Qn lies dense in the nonneg- ≥0 ative orthant Rn , we have the inclusion R ⊆ COP . Suppose for contradiction ≥0 n that the set on the left is not contained in int(COP ): There is a matrix B with n hB,vvTi ≥ 1 for all v ∈ Zn \{0} and there is a nonzero vector x ∈ Rn with ≥0 ≥0 T hB,xx i=0. By induction on n (and reordering if necessary) we may assume that all entries of x are strictly positive, x >0 for all i=1,...,n, since otherwise, we can reduce i the situation to the case of smaller dimension by considering a suitable submatrix of B. Hence, the vector x lies in the interior of the nonnegative orthant. Therefore, and because B ∈ COP , we have for every vector y ∈ Rn and ε > 0 sufficiently n small the inequality 1 T T T 0≤ (x+εy) B(x+εy)=2x By+εy By ε Rationalfactorizationsofcompletelypositivematrices 3 and similarly 1 T T T 0≤ (x−εy) B(x−εy)=−2x By+εy By ε T From this, equality x B = 0 follows. From this, we also see that B is positive semidefinite. This implies that (αx+y)TB(αx+y)=yTBy for α∈R and y ∈Rn. WeapplyDirichlet’sapproximationtheorem,Theorem2.1tothevectorxandto ε∈(0,1). Weobtainavectorp=(p ,...,p )andanaturalnumberq. Sincex >0 1 n i we may without loss of generality assume that p ≥ 0. Thus, by the assumption i T B ∈R, we have hB,pp i≥1. Define y =qx−p where kyk ≤ε. ∞ Since B is positive semidefinite, there is a constant C such that yTBy ≤ Ckyk2 ∞ for all y ∈Rn. Putting everything together we get 1≤hB,ppTi=(qx−y)TB(qx−y)=yTBy ≤Ckyk2 ≤Cε2, ∞ which yields a contradiction for small enough values of ε. (cid:3) Lemma 2.4. Let A be a completely positive matrix which lies in the interior of CP and let λ be a sufficiently large positive real number. Then the set n P(A,λ)={B ∈Sn :hA,Bi≤λ, hB,vvTi≥1 for all v ∈Zn \{0}} ≥0 is a full-dimensional polytope. Proof. Forsufficiently largeλa sufficiently smallballarounda suitable multiple of A is contained in P(A,λ), which shows that P(A,λ) has full dimension. By the theorem of Minkowski and Weyl, see for example [5, Corollary 7.1c], polytopesareexactlyboundedpolyhedra. SoitsufficestoshowthatthesetP(A,λ) is a bounded polyhedron. First we show that P(A,λ) is bounded: For suppose not. Then there is B ∈ 0 P(A,λ) and B ∈ Sn, with B 6= 0, so that the ray B +αB , with α ≥ 0, lies 1 1 0 1 completely in P(A,λ). In particular hB ,vvTi ≥ 0 for all v ∈ Zn . Hence, B lies 1 ≥0 1 in the dual cone of C˜P . On the other hand hA,B i ≤ 0. Hence, by Lemma 2.2 n 1 (1), B 6∈COP \{0}, but by Lemma 2.2 (2), 1 n C˜P∗ =(cl(C˜P ))∗ =CP∗ =COP , n n n n so B =0, yielding a contradiction. 1 Now we show that P(A,λ) is a polyhedron: For suppose not. Then there is a sequencev ∈Zn \{0}ofinfinitely manypairwisedifferentnonzerolattice vectors i ≥0 T sothatthereareB ∈P(A,λ)withhB ,v v i=1. Since P(A,λ)iscompact,there i i i i exists a subsequence B which converges to B∗ ∈ P(A,λ). Define the sequence ij u = v /kv k which lies in the compact set Rn ∩Sn−1 where Sn−1 denotes the ij ij ij ≥0 unit sphere. Hence there is a subsequence converging to u∗ ∈ Sn−1, in particular u∗ 6=0. Denote the indices of this subsequence with k, then 1=hB ,v vTi=kv k2hB ,u uTi. k k k k k k k When k tends to infinity, the squared norms kv k2 tend to infinity as well, since k weuseinfinitely manypairwisedifferentlatticevectorsandthereexistonlyfinitely 4 M.DutourSikiri´c,A.Schu¨rmann,F.Vallentin manylatticevectorsuptosomegivennorm. SohB ,u uTitendstohB∗,u∗(u∗)Ti= k k k 0, and by Lemma 2.3 we obtain a contradiction. (cid:3) Now we prove the main result and finish the paper. Proof of Theorem 1.1. Let A be matrix having rational entries only and lying in theinterioroftheconeofcompletelypositivematrices. ThenP(A,λ)isapolytope according to the previous lemma. We minimize the linear functional B 7→ hA,Bi over P(A,λ). The minimum is attained at one of the polytopes’ vertices, B∗ ∈ P(A,λ). Thenwechoosethoselatticevectorsv ∈Zn ,withi=1,...,mforwhich i ≥0 equality hB∗,v vTi=1 holds. Because of the minimality of hA,B∗i it follows i i T (3) A∈cone{v v :i=1,...,m}. i i Otherwise,seeforexample[5,Theorem7.1],wefindaseparatinglinearhyperplane T orthogonalto C separating A and cone{v v :i=1,...,m}: i i T hC,Ai<0 and hC,v v i≥0 for all i=1,...,m. i i Then for sufficiently small µ>0 we would have B∗+µC ∈P(A,λ) but hB∗+µC,Ai<hB∗,Ai, which contradicts the minimality of hA,B∗i. WeapplyCarath´eodory’stheorem(seeforexample[5,Corollary7.1i])to(3)and T choose a subset I ⊆ {1,...,m} so that v v are linearly independent and so that i i T T A lies in cone{v v : i ∈ I}. Since A is a rational matrix and since the v v ’s are i i i i linearlyindependentrationalmatrices,thereisaunique choiceofrationalnumbers α ∈Q ,withi∈I,sothatA= α v vT holds,whichgivesadesiredrational i ≥0 Pi∈I i i i cp-factorization. (cid:3) Acknowledgements We thank Naomi Shaked-Monderer for comments on the manuscript. References [1] A.Bermanand N. Shaked-Monderer, Completely Positive Matrices, WorldScientific Pub- lishingCo.,2003. [2] A. Berman, M. Du¨r, and N. Shaked-Monderer, Open problems in the theory of completely positive and copositive matrices,ElectronicJ.LinearAlgebra29(2015), 46–58. [3] M.Du¨r,CopositiveProgramming-aSurvey,pp.3–20in: RecentAdvancesinOptimization anditsApplicationsinEngineering(M.Diehl,F.Glineur,E.Jarlebring,W.Michiels(ed.)), Springer,2010. [4] M.Gr¨otschel,L.Lova´sz,andA.Schrijver,Geometric Algorithms and Combinatorial Opti- mization,Springer,1988. [5] A.Schrijver,Theory of Linearand IntegerProgramming, Wiley,1986. M.Dutour Sikiric´, Rudjer Boskovic´ Institute, Bijenicka 54,10000Zagreb,Croatia E-mail address: [email protected] A.Schu¨rmann,Universita¨tRostock, InstituteofMathematics,18051Rostock, Ger- many E-mail address: [email protected] F. Vallentin, MathematischesInstitut, Universita¨t zu Ko¨ln, Weyertal86–90,50931 Ko¨ln,Germany E-mail address: [email protected]