Construction of exceptional copositive matrices Thanks: Q This work was performed within the project COMPUTE, funded within the QuantERA II Programme that has received funding from the EU’s H2020 research and innovation programme under the GA No 101017733 ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ Thanks: 1 Supported by the Slovenian Research Agency grant J1-60011. Thanks: 2 Supported by the Slovenian Research Agency program P1-0288 and grants J1-50002, J1-3004, J1-60011. Tea Štrekelj 1, Aljaž Zalar 2,Q Abstract . An n × n n\times n symmetric matrix A A is copositive if the quadratic form x T ​ A ​ x x^{T}Ax is nonnegative on the nonnegative orthant ℝ ≥ 0 n \mathbb{R}^{n}_{\geq 0} . The cone of copositive matrices contains the cone of matrices which are the sum of a positive semidefinite matrix and a nonnegative one and the latter contains the cone of completely positive matrices. These are the matrices of the form B ​ B T BB^{T} for some n × r n\times r matrix B B with nonnegative entries. The above inclusions are strict for n ≥ 5 . n\geq 5. The first main result of this article is a free probability inspired construction of exceptional copositive matrices of all sizes ≥ 5 \geq 5 , i.e., copositive matrices that are not the sum of a positive semidefinite matrix and a nonnegative one. The second contribution of this paper addresses the asymptotic ratio of the volume radii of compact sections of the cones of copositive and completely positive matrices. In a previous work by the authors, it was shown that, by identifying symmetric matrices naturally with quartic even forms, and equipping them with the L 2 L^{2} inner product and the Lebesgue measure, the ratio of the volume radii of sections with a suitably chosen hyperplane is bounded below by a constant independent of n n as n n tends to infinity. In this paper, we extend this result by establishing an analogous bound when the sections of the cones are unit balls in the Frobenius inner product. 2020 Mathematics Subject Classification 13J30, 47L07, 52A40 (Primary); 90C22, 90C27 (Secondary) 1. Introduction Copositive and completely positive matrices have gained considerable attention in recent years. They appear in combinatorial analysis, computational mechanics, dynamical systems, control theory and especially in optimization. This is because many combinatorial and nonconvex quadratic optimization problems can be formulated as linear problems over the larger cone of copositive or the smaller cone of completely positive matrices [ KP02 , Bur09 , RRW10 , DR21 ] . In this article we streamline the proof of the main result of [ KŠZ24 ] , which compares the asymptotic volumes of these two cones of matrices. Moreover, we give an explicit construction of exceptional matrices , i.e., matrices that belong to the larger cone, but not to the smaller one. 1.1. Notation For n\in\mathbb{N} denote by M_{n}(\mathbb{R}) the n\times n real matrices and let \mathbb{S}_{n}=\left\{A\in M_{n}(\mathbb{R})\colon A^{T}=A\right\} be its subspace of real symmetric matrices, where T stands for the usual transposition of matrices. Denote by \mathbb{R}[{\tt x}] be the vector space of real polynomials in the variables {\tt x}=(x_{1},\ldots,x_{n}) and let \mathbb{R}[{\tt x}]_{k} be its subspace of forms of degree k , i.e., homogeneous polynomials from \mathbb{R}[{\tt x}] of degree k . To any matrix A=[a_{ij}]_{i,j=1}^{n}\in\mathbb{S}_{n} we associate the quadratic form (1.1) p_{A}({\tt x}):={\tt x}^{T}A{\tt x}=\sum_{i,j=1}^{n}a_{ij}x_{i}x_{j}\in\mathbb{R}[{\tt x}]_{2}. 1.2. Basic definitions and background This article studies the inclusion properties of the cones of the following classes of matrices. Definition 1.1 . A matrix A\in\mathbb{S}_{n} is: (1) copositive if p_{A} is nonnegative on the nonnegative orthant \mathbb{R}^{n}_{\geq 0}:=\{(x_{1},\ldots,x_{n})\colon x_{i}\geq 0,\ i=1,\ldots,n\}, i.e., p_{A}({\tt x})\geq 0 for every {\tt x}\in\mathbb{R}^{n}_{\geq 0} . Equivalently, A is copositive iff the quartic form (1.2) q_{A}({\tt x}):=p_{A}(x_{1}^{2},\ldots,x_{n}^{2})\in\mathbb{R}[{\tt x}]_{4} is nonnegative on \mathbb{R}^{n} . We write \coPos_{n} for the cone of all n\times n copositive matrices. (2) positive semidefinite (PSD) if all of its eigenvalues are nonnegative. Equivalently, A is PSD iff p_{A}({\tt x})\geq 0 for all {\tt x}\in\mathbb{R}^{n} iff A=BB^{T} for some matrix B\in M_{n}(\mathbb{R}) . We write A\succeq 0 to denote that A is PSD and \psd_{n} stands for the cone of all n\times n PSD matrices. (3) nonnegative (NN) if all of its entries are nonnegative, i.e., A=[a_{ij}]_{i,j=1}^{n} with a_{ij}\geq 0 for i,j=1,\ldots,n . We write \nn_{n} for the cone of all n\times n NN matrices. (4) SPN (sum of a positive semidefinite matrix and a nonnegative one) if it is of the form A=P+N , where P\in\psd_{n} and N\in\nn_{n} . We write \SPN_{n}:=\psd_{n}+\nn_{n} for the cone of all n\times n SPN matrices. (5) doubly nonnegative (DNN) if it is PSD and NN. We use \DNN_{n}:=\psd_{n}\cap\nn_{n} for the cone of all n\times n DNN matrices. (6) completely positive (CP) 1 1 1 Despite the similar name, the CP matrices considered here are not related to the CP maps ubiquitous in operator algebra [ Pau02 ] . if A=BB^{T} for some r\in\mathbb{N} and n\times r entrywise nonnegative matrix B . We write \cp_{n} for the cone of all n\times n CP matrices. The presented matrices clearly form the following chain of inclusions: (1.3) \coPos_{n}\supseteq\SPN_{n}\supseteq\psd_{n}\cup\nn_{n}\supseteq\DNN_{n}\supseteq\cp_{n}. After formulating a combinatorial problem as a conic linear problem over \cop_{n} or \cp_{n}, the complexity of the problem is reduced to the constraints of the respective cone. However, the membership problem for \COP_{n} is co-NP-complete [ MK87 ] and NP-hard for \CP_{n} [ DG14 ] . For this reason, Parrilo [ Par00 ] proposed an increasing hierarchy of cones K_{n}^{(r)}:=\{A\in\mathbb{S}_{n}\colon(\sum_{i=1}^{n}x_{i}^{2})^{r}\cdot p_{A}({\tt x})\text{ is a sum of squares of forms}\}, which give a tractable inner approximation of the cone \COP_{n} based on semidefinite programming. Clearly, (1.4) \bigcup_{r\in\mathbb{N}_{0}}K_{n}^{(r)}\subseteq\COP_{n}, and a result of Pólya [ Pól28 ] gives a statement on the quality of the approximation, namely \mathrm{int}(\COP_{n})\subseteq\bigcup_{r\in\mathbb{N}_{0}}K_{n}^{(r)}. It was shown in [ Par00 , p. 63–64] that K_{n}^{(0)}=\SPN_{n} . Also, \SPN_{n}=\COP_{n} for n\leq 4 by [ MM62 ] . Whence, K_{n}^{(0)}=\COP_{n} and the inclusion in ( 1.4 ) is in fact equality for n\leq 4 (see also [ Dia62 ] ). However, for n\geq 5 , the cone K_{n}^{(0)} is strictly contained in \COP_{n}. For n=5, the strict inclusion is testified by the so-called Horn matrix [ HN63 ] (1.5) H=\begin{pmatrix}[r]1&-1&1&1&-1\\ -1&1&-1&1&1\\ 1&-1&1&-1&1\\ 1&1&-1&1&-1\\ -1&1&1&-1&1\end{pmatrix} giving a standard example of a copositive matrix that is not \SPN . Further, H\in K_{5}^{(1)} by [ Par00 ] , but \COP_{5}\neq K_{5}^{(r)} for any r\in\mathbb{N} by [ DDGH13 ] . Very recently it was shown in [ LV22b , SV24 ] that for n=5, the inclusion in ( 1.4 ) is also equality, while for n\geq 6, the inclusion becomes strict [ LV22a ] . The aim of this paper is first to find further testimonies of the gap between \cop and \cp matrices. Next, we imply that this construction cannot be randomized by showing that the asymptotic ratio of the volume radii of compact sections of the cones \cop and \cp is strictly positive as n goes to infinity. A nice exposition on the classes of matrices defined above can be found in [ BSM21 ] and some open problems regarding \COP and \CP are presented in [ BDSM15 ] . 1.3. Main results The first main result is a bootstrap method to find exceptional doubly nonnegative (e-DNN) matrices, i.e., doubly nonnegative matrices that are not completely positive. We first find a seed e-DNN matrix of size 5\times 5, which then gives rise to a family of e-DNN matrices of arbitrary sizes \geq 5. The construction is inspired by the free probability construction in [ CHN17 ] of positive maps between matrix spaces that are not completely positive. For each f\in L^{\infty}[0,1] consider the corresponding multiplication operator M_{f} on L^{2}[0,1]; that is M_{f}\,g=fg for g\in L^{2}[0,1]. With respect to the standard orthonormal basis for L^{2}[0,1] given by (1.6) \mathcal{B}:=\big\{1\big\}\cup\big\{\sqrt{2}\cos(2k\pi x)\colon k\in\mathbb{N}\big\}\cup\big\{\sqrt{2}\sin(2k\pi x)\colon k\in\mathbb{N}\big\}, each such multiplication operator can be represented by an infinite matrix. For a closed subspace \mathcal{H}\subseteq L^{2}[0,1] denote by P_{\mathcal{H}}:L^{2}[0,1]\to\mathcal{H} the orthogonal projection onto \mathcal{H} . Then for any f\in\mathcal{H}, the operator M_{f}^{\mathcal{H}}:=P_{\mathcal{H}}M_{f}P_{\mathcal{H}} is in fact a multiplication operator on \mathcal{H} and can be as well represented by a (possibly infinite) matrix. Our idea is to find an infinite dimensional \mathcal{H} and an f\in\mathcal{H} such that M_{f}^{\mathcal{H}} has all finite principal submatrices \DNN but not \CP . 1.3.1. Construction of exceptional DNN matrices of all sizes \geq 5 The setting in which we work is the following: (1.7) \displaystyle f\text{ is of the form }1+2\sum_{k=1}^{m}a_{k}\cos(2k\pi x),\quad m\in\mathbb{N},\;a_{1}\geq 0,\ldots,a_{m}\geq 0, \displaystyle\mathcal{H}\subseteq L^{2}[0,1]\text{ is spanned by the functions }\cos(2k\pi x),k\in\mathbb{N}_{0}. For n\in\mathbb{N} , let \mathcal{H}_{n} be the finite-dimensional subspace of \mathcal{H} spanned by the functions 1,\sqrt{2}\cos(2\pi x),\ldots,\sqrt{2}\cos(2(n-1)\pi x) and let P_{n}:\mathcal{H}\to\mathcal{H}_{n} the orthogonal projection onto \mathcal{H}_{n} . Clearly, all the matrices (1.8) A^{(n)}:=P_{n}M_{f}^{\mathcal{H}}P_{n},\;n\in\mathbb{N} are \nn since f has positive Fourier coefficients. To certify that they are \psd , we impose the condition that f is a sum of squares ( \Sos ) of trigonometric polynomials, i.e., (1.9) f=v^{T}Bv,\quad\text{where}\quad B\in\psd_{m^{\prime}+1} and v^{T}=\begin{pmatrix}1&\cos(2\pi x)&\cdots&\cos(2m^{\prime}\pi x)\end{pmatrix}\quad\text{for some }m^{\prime}\leq m. Finally, to achieve that A^{(n)}\not\in\CP_{n} for n\geq 5 , we demand that (1.10) \langle A^{(5)},H\rangle<0, where H is the Horn matrix of ( 1.5 ) and \langle\cdot,\cdot\rangle is the usual Frobenius inner product on symmetric matrices, i.e., \langle A,B\rangle=\Tr(AB) . Since CP matrices are dual to the COP matrices w.r.t. the Frobenius inner product, this condition indeed certifies that A^{(n)}\not\in\CP_{n} for all n as we explain in Subsection 2.1 . Now let m=6 . The above construction can be implemented via the following feasibility SDP (1.11) \begin{split}&\Tr(A^{(5)}H)=-\epsilon,\\ &f=v^{\text{T}}Bv\quad\text{with}\quad B\succeq 0,\\ &a_{i}\geq 0,\quad i=1,\ldots,6,\end{split} where \epsilon>0 is predetermined (small enough). Solving ( 1.11 ) for different values of \epsilon and m^{\prime}\leq 6, Mathematica’s semidefinite optimization solver gives an exceptional DNN matrix A^{(5)} (see Subsection 2.3 for an explicit example). We remark that the idea is to search for an f as in 1.7 with the smallest m as possible to reduce the complexity of the SDP 1.11 . The choice of m=6 seemed optimal from our experiments. 1.3.2. Construction of exceptional copositive matrices of all sizes n\geq 5 To construct exceptional copositive matrices of arbitrary size we proceed as follows. For n\geq 5 let A^{(n)} be a DNN matrix constructed by the above procedure. To obtain an exceptional copositive matrix C of size n\times n we impose the conditions (1.12) \displaystyle\begin{split}&\langle A^{(n)},C\rangle<0,\\ &\big(\sum_{i=1}^{n}x_{i}^{2}\big)^{k}q_{C}\text{ is SOS for some }k\in\mathbb{N}\end{split} with q_{C} as in ( 1.2 ). Searching for C satisfying ( 1.12 ) for fixed k can again be formulated as a feasibility SDP. For an explicit example obtained in this way see Subsection 2.3 . 1.3.3. Second main result Let V be a finite-dimensional Hilbert space equipped with the pushforward measure of the Lebesgue measure \mu on \mathbb{R}^{\dim V} . A natural way to compare the volumes of two cones K_{1} , K_{2} in V is to compare the compact sections of both cones when intersected with some “fair” subset of V . A seemingly fair choice is the unit ball B of V . In this case the task is to derive an estimate for the so–called ball-truncated volume of K_{i} [ ST15a ] \btv(K_{i}):=\Vol(K_{i}\cap B), where the volume \Vol is computed with respect to \mu . If one is interested only in the asymptotical behaviour of the volume difference, then comparing volume radii \vrad(K_{i}\cap B) , defined by \vrad(K_{i}\cap B)=\left(\frac{\btv(K_{i}\cap B)}{\Vol(B)}\right)^{1/\dim V}, is equally informative (see also [ KŠZ24 , Remark 2.4] for a detailed discussion on the ratio of volumes versus the ratio of volume radii). Let B_{n}\subseteq\mathbb{S}_{n} be the unit ball w.r.t. the Frobenius inner product. Our second main result compares the sizes of the convex cones K from Definition 1.1 by comparing the volumes of their intersections with B_{n} , i.e., K^{(B_{n})}:=K\cap B_{n} . Theorem 3.1 . We have that \displaystyle\frac{1}{8\sqrt{2}} \displaystyle\leq\vrad(\CP^{(B_{n})}_{n})\leq\vrad(\nn^{(B_{n})}_{n})=\frac{1}{2}\leq\vrad(\COP^{(B_{n})}_{n})\leq 1. In particular, \frac{1}{8\sqrt{2}}\leq\frac{\vrad(K^{(B_{n})}_{n})}{\vrad(\COP^{(B_{n})}_{n})}\leq 1, where K\in\{\CP,\DNN,\psd,\nn,\SPN\} . Remark 1.2 . (1) Deriving tight estimates for the ball-truncated volume \btv(K^{(B)}) of a cone K is very demanding and infeasible for most cones in dimensions beyond 3. This is due to the fact that the conditions defining the section K^{(B)} are quadratic in the coordinates of \mathbb{R}^{\dim V} . To compensate on this problem one approach is to compare the cones when intersected with a suitably chosen half-space or equivalently, a hyperplane. For x\in V let H_{x}:=\{u\in V\colon\langle x,u\rangle\leq 1\} be a closed halfspace and \partial H_{x}:=\{u\in V\colon\langle x,u\rangle=1\} its boundary hyperplane. (a) A comparison of the sizes of the cones can be done in terms of their least partial volumes [ ST15a , Definition 1.1] . The least partial volume of a cone K is the smallest volume of K\cap H_{x} , where x runs over the unit sphere in V . (b) When we want to compare the cones K_{1} , K_{2} that are dual to each other in the inner product on V , i.e., K_{2}=K_{1}^{\ast}=\{u\in V\colon\langle x,u\rangle\geq 0\text{ for all }x\in K_{1}\}, a “fair” choice of x in H_{x} is the so-called volumetric center \rho(K_{1}) of K_{1} [ ST15a , Definition 1.2] . This is because \rho(K_{1}) is the centroid of K_{2}\cap\partial H_{\rho(K_{1})} (see [ ST15b , p. 2 and Lemma 5.2] ), which is equivalent to the fact that \rho(K_{1}) is the so–called Santaló point of K_{1}\cap\partial H_{\rho(K_{1})} , for which the Blaschke–Santalo inequality [ MP90 , p. 90] can be applied. (2) In our previous work [ KŠZ24 ] on estimating the quantitative gap between \COP_{n} and \CP_{n} we used the identification with quartic even forms ( 1.2 ) and then compared volumes of the corresponding cones in positive even quartics. The inner product is taken to be the L^{2} norm, i.e., \langle f,g\rangle=\int_{S^{n-1}}fg\;{\rm d}\sigma , where \sigma is the rotation invariant probability measure on the unit sphere S^{n-1}\subset\mathbb{R}^{n}. In this context, determining conclusive ball-truncated volumes is challenging. Therefore, we selected an appropriate hyperplane H_{x} , where x is a multiple of x_{1}^{2}+\ldots+x_{n}^{2} , and then derived volume estimates for the intersections of all the cones with \partial H_{x} . For a detailed discussion on the choice of x see [ KŠZ24 , Section 2.2] . (3) The proof of Theorem Theorem is significantly less demanding than the proof of the corresponding result in [ KŠZ24 ] , namely Theorem 1.4. To establish the latter, we had to use two distinct inner products: in addition to the L^{2} inner product, we also employed the so-called differential inner product on even quartics, which resembles the Frobenius inner product on matrices. The main observations for deriving the estimates relied on the differential inner product, while the connection between the volumes of the sets in both inner products, developed by Blekherman in [ Ble04 , Ble06 ] , was crucial. Proving Theorem Theorem closely follows the observations regarding the differential inner product from [ KŠZ24 ] . 2. Construction of exceptional doubly nonnegative and exceptional copositive matrices In this section we describe the details of the bootstrap method outlined in Subsection 1.3 to find exceptional doubly nonnegative (e-DNN) and exceptional copositive (e-COP) matrices. The idea is to find a seed e-DNN matrix of size 5\times 5 that is the compression of a multiplication operator M_{f} for a sum of squares cosine trigonometric polynomial f using a semidefinite optimization program (SDP). From the seed matrix we then read off the (finitely many) Fourier coefficients of f. Finally, we argue that all the larger finite compressions (principal submatrices) of M_{f} are e-DNN as well. Using the constructed e-DNN matrices we produce a corresponding family of exceptional copositive matrices. 2.1. Justification of the construction of a family of e-DNN matrices from a seed e-DNN matrix of size 5\times 5 Recall that the function f we are looking for is of the form f(x)=1+2\sum_{k=1}^{6}a_{k}\cos(2k\pi x) with a_{1},\ldots,a_{6}\geq 0 (here we immediately set m=6 as in ( 1.7 )). Also, in ( 1.8 ), we defined A^{(n)}=(A^{(n)}_{jk})_{j,k} to be the n\times n principal submatrix of the infinite matrix pertaining to the multiplication operator M_{f}^{\mathcal{H}} on \mathcal{H}. Here \mathcal{H} is the closed subspace of L^{2}[0,1] spanned by the \cos(2k\pi x) , k\in\mathbb{N}_{0}. The technical reasons why we restrict to \mathcal{H} instead of considering the entire L^{2}[0,1] are discussed in Remark 2.1 . The restriction to matrices of size n\geq 5 is clear from the introduction since \DNN_{n}=\cp_{n} for n\leq 4. To find the general form of A^{(n)} note that \displaystyle A_{jk}^{(n)} \displaystyle=\int_{0}^{1}f(x)\cos(2(j-1)\pi x)\cos(2(k-1)\pi x)\,dx\quad\text{for}\ \ j,k=1,\ldots,n, where the integration is with respect to the Lebesgue measure on [0,1]. Using the well-known trigonometry formula involving the cosine product identity, the products of different cosine functions can be replaced with linear combinations of cosine functions with higher and lower frequency, i.e., (2.1) \displaystyle\cos(2j\pi x)\cos(2k\pi x) \displaystyle=\frac{1}{2}\Big(\cos\big(2(j-k)\pi x)\big)+\cos\big(2(j+k)\pi x\big)\Big). From ( 2.1 ) it follows that (2.2) \int_{0}^{1}\cos(2j\pi x)\cos(2k\pi x)\cos(2\ell\pi x)dx=\left\{\begin{array}[]{rl}\frac{1}{2},&\text{if }j=\ell,k=0,\\[5.0pt] \frac{1}{4},&\text{if }k\neq 0\text{ and }j\in\{\ell+k,\ell-k\},\\[5.0pt] 0,&\text{otherwise}.\end{array}\right. Using ( 2.2 ) it is now easy to compute that for A^{(5)} to be the 5\times 5 compression of M_{f}^{\mathcal{H}}, it must be of the form (2.3) A^{(5)}=\begin{pmatrix}1&\sqrt{2}a_{1}&\sqrt{2}a_{2}&\sqrt{2}a_{3}&\sqrt{2}a_{4}\\ \sqrt{2}a_{1}&a_{2}+1&a_{1}+a_{3}&a_{2}+a_{4}&a_{3}+a_{5}\\ \sqrt{2}a_{2}&a_{1}+a_{3}&a_{4}+1&a_{1}+a_{5}&a_{2}+a_{6}\\ \sqrt{2}a_{3}&a_{2}+a_{4}&a_{1}+a_{5}&1+a_{6}&a_{1}\\ \sqrt{2}a_{4}&a_{3}+a_{5}&a_{2}+a_{6}&a_{1}&1\end{pmatrix}. Thus demanding that a_{i}\geq 0 for i=1,\ldots,6 certifies that A^{(5)} is \nn . By the same reasoning A^{(n)} is \nn for every n\geq 5 . Further on, f being of the form ( 1.9 ) is equivalent to f being a sum of squares of trigonometric polynomials [ Mar08 , Lemma 4.1.3] . This implies that all matrices A^{(n)}=P_{n}M_{f}^{\mathcal{H}}P_{n} as in ( 1.8 ) are PSD. Indeed, suppose f=\sum_{i=0}^{k}\big(\underbrace{\sum_{j=0}^{m^{\prime}}h_{ij}\cos(2j\pi x)}_{h_{i}}\big)^{2} for some k and h_{ij}\in\mathbb{R} . Since f and the h_{i} are in \mathcal{H}, clearly M_{f}^{\mathcal{H}} and the M^{\mathcal{H}}_{h_{i}} are multiplication operators on \mathcal{H} and M_{f}^{\mathcal{H}}=\sum_{i=1}^{k}\big(M^{\mathcal{H}}_{h_{i}}\big)^{2}. Here each M^{\mathcal{H}}_{h_{i}} is self-adjoint, from which the claim follows. Finally, we justify why ( 1.10 ) implies that P_{n}M_{f}^{\mathcal{H}}P_{n} is not \CP for any n\geq 5 . Since CP matrices are dual to copositive matrices in the usual Frobenius inner product, ( 1.10 ) certifies that A^{(5)} is not \CP . Now the equality (2.4) A^{(5)}=P_{5}(P_{n}M_{f}^{\mathcal{H}}P_{n})P_{5}=P_{5}A^{(n)}P_{5} for any n\geq 5 , implies that A^{(n)} is not \CP for any n\geq 5 . Indeed, suppose that A^{(n)}=BB^{\text{T}} for some n\geq 5 and (not necessarily square) matrix B with nonnegative entries. By ( 2.4 ), A^{(5)}=P_{5}B(P_{5}B)^{\text{T}} and since P_{5} only has 0,1 entries, this contradicts A^{(5)} not being \CP . 2.2. Justification of the construction of exceptional COP matrices from exceptional DNN matrices It remains to justify our procedure for constructing an exceptional copositive matrix C of size n\times n for any n\geq 5 from the obtained e-DNN matrix A^{(n)}. Since SPN matrices are dual to the DNN matrices in the Frobenius inner product, the first condition in ( 1.12 ), \langle A^{(n)},C\rangle<0, implies that C is not SPN. On the other hand, the second condition in ( 1.12 ), \big(\sum_{i=1}^{n}x_{i}^{2}\big)^{k}q_{C}\text{ is SOS for some }k\in\mathbb{N}, is a relaxation of the copositivity of C and it clearly implies that q_{C} is nonnegative on \mathbb{R}^{n}. Whence, C is COP. We remark that in practice, it suffices to consider only k=1 or k=2. Remark 2.1 . We explain the reason for restricting M_{f} to the closed subspace \mathcal{H} of L^{2}[0,1] generated by the cosine functions. As in Subsection 1.3.1 , with respect to the standard orthonormal basis for L^{2}[0,1] given by (2.5) 1,\ \sqrt{2}\cos\big(2k\pi x\big),\ \sqrt{2}\sin\big(2k\pi x\big) for k\in\mathbb{N}, each multiplication operator M_{f} for f\in L^{\infty}[0,1] can be represented by an infinite matrix. It seems natural to start by considering the entire space L^{2}[0,1] and compressions \widetilde{P}_{n}M_{f}\widetilde{P}_{n} of M_{f} for some trigonometric polynomial f and n\geq 2, onto the (2n+1) -dimensional span \widetilde{\mathcal{H}}_{n} of the functions in ( 2.5 ) for k=1,\ldots,n . Here \widetilde{P}_{n}:L^{2}[0,1]\to\widetilde{\mathcal{H}}_{n} are orthogonal projections. Suppose that A is the 5\times 5 compression of M_{f} and is given with respect to the ordered (orthonormal) basis consisting of the functions \displaystyle 1,\sqrt{2}\cos(2\pi x),\sqrt{2}\cos(4\pi x),\sqrt{2}\sin(2\pi x),\sqrt{2}\sin(4\pi x). Moreover, assume that the corresponding function f has finite Fourier series (2.6) f(x)=1+2\sum_{k=1}^{m}a_{k}\cos(2k\pi x)+2\sum_{k=1}^{m}b_{k}\sin(2k\pi x) for some m\in\mathbb{N} and real numbers a_{k},b_{k} with k=1,\ldots,m. Again, using well-known trigonometry formulas involving product identities, i.e., (2.7) \begin{split}\sin(2j\pi x)\sin(2k\pi x)&=\frac{1}{2}\Big(\cos\big(2(j-k)\pi x)\big)-\cos\big(2(j+k)\pi x\big)\Big),\\ \cos(2j\pi x)\sin(2k\pi x)&=\frac{1}{2}\Big(\sin\big(2(k-j)\pi x)\big)+\sin\big(2(j+k)\pi x\big)\Big)\end{split} in addition to ( 2.1 ), it is easy to compute that for A to be the 5\times 5 compression of a multiplication operator M_{f} for f as in ( 2.6 ) with m\geq 4 , it must be of the form A=\begin{pmatrix}1&\sqrt{2}a_{1}&\sqrt{2}a_{2}&\sqrt{2}b_{1}&\sqrt{2}b_{2}\\ \sqrt{2}a_{1}&a_{2}+1&a_{1}+a_{3}&b_{2}&b_{1}+b_{3}\\ \sqrt{2}a_{2}&a_{1}+a_{3}&a_{4}+1&b_{3}-b_{1}&b_{4}\\ \sqrt{2}b_{1}&b_{2}&b_{3}-b_{1}&1-a_{2}&a_{1}-a_{3}\\ \sqrt{2}b_{2}&b_{1}+b_{3}&b_{4}&a_{1}-a_{3}&1-a_{4}\end{pmatrix}. Note that since we want all the finite-dimensional compressions of M_{f} to be NN, f needs to have an infinite Fourier series. Indeed, suppose f has finite Fourier series as in ( 2.6 ) for some m\in\mathbb{N}. Then for all j,k with k