The Algebraic Boundary of Graph Elliptopes Monique Laurent, Francesco Maria Mascarin, Simon Telen Abstract This paper studies the algebraic boundary of the elliptope ℰ ⁡ ( G ) {\mathcal{E}}(G) of a graph G G . In particular, we completely characterize the algebraic boundary of ℰ ⁡ ( G ) {\mathcal{E}}(G) when G G is cycle completable. In this case, the boundary is a union of determinantal hypersurfaces and Lissajous varieties, i.e., images of rational linear subspaces under the coordinatewise cosine map. As an application, we show that the algebraic boundary of ℰ ⁡ ( G ) {\mathcal{E}}(G) is disjoint from its interior precisely when ℰ ⁡ ( G ) {\mathcal{E}}(G) is a spectrahedron or, equivalently, when G G is a chordal graph. A central ingredient for the defining equation of the boundary hypersurface is the cycle polynomial, which captures the algebraic boundary of the elliptope ℰ ⁡ ( C n ) {\mathcal{E}}(C_{n}) of the n n -th cycle graph C n C_{n} . We show that the cycle polynomial of C n C_{n} is the resultant of two smaller cycle polynomials. Via this result, Sylvester’s determinantal formula offers an inductive method for computing the cycle polynomial which mirrors a geometric property of metric polytopes. We also determine the degree of the homogeneous cycle polynomial, settling an open question of Sturmfels and Uhler (2010). 1 Introduction Given a (simple undirected) graph G=(V=[n],E) , its elliptope {\mathcal{E}}(G) is defined as the projection onto \mathbb{R}^{E} of the set {\mathcal{E}}_{n} of correlation matrices. In symbols, we have \displaystyle{\mathcal{E}}_{n} \displaystyle\,=\,\{X\in{\mathcal{S}}^{n}_{+}:X_{ii}=1\text{ for }i\in[n]\}, \displaystyle{\mathcal{E}}(G) \displaystyle\,=\,\{x\in\mathbb{R}^{E}:\exists X\in{\mathcal{E}}_{n}\text{ such that }X_{ij}=x_{ij}\text{ for }\{i,j\}\in E\}. Here, {\mathcal{S}}^{n}_{+} is the cone of n\times n real symmetric matrices X\in{\mathcal{S}}^{n} that are positive semidefinite, denoted as X\succeq 0 . The elliptope {\mathcal{E}}(K_{n})\simeq{\mathcal{E}}_{n} of the complete graph G=K_{n} is a spectrahedron. It is the convex semialgebraic set consisting of the matrices X\in{\mathcal{S}}^{n} with ones on the diagonal and with non-negative principal minors. By the Tarksi-Seidenberg theorem, any graph elliptope {\mathcal{E}}(G) is semialgebraic as well, and {\mathcal{E}}(G) is a spectrahedral shadow by definition. Moreover, {\mathcal{E}}(G)\subseteq\mathbb{R}^{E} is convex and it has non-empty interior: {\rm int}({\mathcal{E}}(G))\neq\emptyset . In this paper we investigate graph elliptopes from an algebraic geometry perspective. More precisely, we study their algebraic boundary \partial_{a}{\mathcal{E}}(G) , which is the Zariski closure of the euclidean boundary \partial{\mathcal{E}}(G)={\mathcal{E}}(G)\setminus{\rm int}({\mathcal{E}}(G)) in \mathbb{C}^{E} . For instance, the algebraic boundary of {\mathcal{E}}_{n} is given by the polynomial equation \det(X)=0 . The paper [ 27 ] discusses the algebraic boundary of elliptopes of chordal graphs and cycles. It is stated in [ 27 , Proposition 4.1] that, if G is chordal, then \partial_{a}{\mathcal{E}}(G) is defined by the determinantal equations corresponding to the maximal cliques of G . In [ 27 , Section 4.2] it is stated (without proof) that, if G is a cycle C_{n} , then \partial_{a}{\mathcal{E}}(C_{n}) is defined by the so-called n -th cycle polynomial \Gamma_{n} . One of our main results (Theorem 4.5 ) is that determinantal equations and cycle polynomials suffice to describe the algebraic boundary \partial_{a}{\mathcal{E}}(G) for any cycle completable graph G . This includes chordal graphs and graphs with no K_{4} -minor, as well as any clique sum of such graphs (see Theorem 2.4 ). As a byproduct, we show that the elliptope {\mathcal{E}}(G) is a spectrahedron if and only if its algebraic boundary does not intersect its interior, which holds precisely when G is chordal (Corollary 4.10 ). In particular, the elliptope of a cycle C_{n} with length n\geq 4 is not a spectrahedron, which rectifies a claim made in [ 27 , Section 4.2] . The affine hypersurface defined by \Gamma_{n}=0 ( n\geq 3 ) is the image of a rational hyperplane under the coordinatewise cosine map. Here “rational” means defined over \mathbb{Q} . Such varieties were recently studied in [ 4 , 23 ] . In particular, [ 23 ] introduces the name “Lissajous variety” for the cosine of a rational affine space L . If L is the row space of the incidence matrix of the cycle C_{n} , then one obtains the Lissajous variety {\mathcal{L}}_{n}=\cos(L)=V(\Gamma_{n}) . So, Lissajous hypersurfaces defined by cycle polynomials play a central role in describing algebraic boundaries of graph elliptopes. This connection is readily seen from the well-known result from [ 3 ] : the elliptope of a cycle is the image of a convex polytope, namely the metric polytope, under the cosine map. Cycle polynomials have remarkable properties. They are symmetric and, as shown in [ 23 ] , their associated Lissajous hypersurface {\mathcal{L}}_{n} admits a determinantal representation using multiplication matrices in a suitable polynomial algebra. For n=3 , {\mathcal{E}}(C_{3})\simeq{\mathcal{E}}_{3} and \Gamma_{3} recovers the polynomial \det(X) for X\in{\mathcal{E}}_{3} . For n\geq 4 , we show that the cycle polynomial \Gamma_{n} can be obtained by computing the resultant of two smaller cycle polynomials \Gamma_{p} and \Gamma_{q} where n=p+q-2 and p,q\geq 3 . In a nutshell, one should think of adding a chord to C_{n} , which creates two smaller cycles sharing the chord as a common edge. The cycle polynomial of C_{n} is obtained by eliminating the variable associated to the new chord from the two cycle polynomials of the smaller cycles. Example 1.1 . The elliptope {\mathcal{E}}_{3}={\mathcal{E}}(C_{3})={\mathcal{E}}(K_{3})\subseteq\mathbb{R}^{3} is the semialgebraic set \Big\{(x_{1},x_{2},y)\in\mathbb{R}^{3}\,:\,X\,=\,\left(\begin{smallmatrix}1&x_{1}&x_{2}\\ x_{1}&1&y\\ x_{2}&y&1\end{smallmatrix}\right)\succeq 0\Big\}. Its algebraic boundary is Cayley’s cubic surface, given by f(x_{1},x_{2},y)=\det(X)=0 , with f(x_{1},x_{2},y)=-\Gamma_{3}(x_{1},x_{2},y) (see Example 3.3 ). This surface is shown at the bottom-right of Figure 1 (rightmost picture in the third row). The elliptope {\mathcal{E}}(C_{4}) of the cycle C_{4} consists of all points (x_{1},x_{2},x_{3},x_{4})\in\mathbb{R}^{4} for which the partially filled matrix \left(\begin{smallmatrix}1&x_{1}&?&x_{2}\\ x_{1}&1&x_{3}&?\\ ?&x_{3}&1&x_{4}\\ x_{2}&?&x_{4}&1\end{smallmatrix}\right) admits a positive semidefinite completion. Its algebraic boundary is given by the polynomial (1-x_{1}^{2})(1-x_{2}^{2})(1-x_{3}^{2})(1-x_{4}^{2})\cdot\Gamma_{4} , where the fourth cycle polynomial \Gamma_{4} is the resultant \Gamma_{4}\,=\,{\rm Res}_{y}(f(x_{1},x_{2},y),f(x_{3},x_{4},y)). The expansion of \Gamma_{4} is displayed in Example 3.3 . The four factors (1-x_{i}^{2}) come from the maximal cliques of C_{4} , i.e., from the four edges. The point x={\bf 0} is an interior point of {\mathcal{E}}(C_{4}) , and a zero of \Gamma_{4} , i.e., \Gamma_{4}({\bf 0})=0 . The algebraic boundary of a spectrahedron does not intersect the interior, which shows that {\mathcal{E}}(C_{4}) is not a spectrahedron (see Corollary 4.10 ). The second row of Figure 1 shows three different slices in \mathbb{R}^{3} of the elliptope {\mathcal{E}}(C_{4})\subseteq\mathbb{R}^{4} , obtained by setting x_{4}=0,\tfrac{1}{2},1 , respectively, and its third row shows the corresponding slices of the real variety V_{\mathbb{R}}(\Gamma_{4})=V(\Gamma_{4})\cap\mathbb{R}^{4} . The first row of Figure 1 shows the corresponding slices of the metric polytope \text{\rm MET}(C_{4})=\tfrac{1}{\pi}\arccos({\mathcal{E}}(C_{4})) , obtained by setting \tfrac{1}{\pi}\arccos x_{4}=\tfrac{1}{2},\tfrac{1}{3},0 . See Section 2.1 for details on the metric polytope. Figure 1 : Three slices of {\mathcal{E}}(C_{4}) (second row) and the corresponding slices of V_{\mathbb{R}}(\Gamma_{4}) (third row) at x_{4}=0,\tfrac{1}{2},1 , together with the matching slices of \text{\rm MET}(C_{4}) at {1\over\pi}\arccos x_{4}=\tfrac{1}{2},\tfrac{1}{3},0 (first row). In [ 23 ] the authors compute the degree of \Gamma_{n} . Here, we prove that the degree of its homogeneous analog \Gamma_{n}^{h} is n\cdot 2^{n-3} (Theorem 3.20 ), answering an open question posed in [ 27 , Conjecture 4.9] . The polynomial \Gamma_{n}^{h} arises as follows: for the cycle C_{n}=(V=[n],E_{n}) , the cone {\mathscr{C}}(C_{n})=\pi_{V\cup E_{n}}({\mathcal{S}}^{n}_{+})\subseteq\mathbb{R}^{V\cup E_{n}} is the image of the positive semidefinite cone under the projection \pi_{V\cup E_{n}}(X)=(\pi_{V}(X),\pi_{E_{n}}(X))\in\mathbb{R}^{V\cup E_{n}} , where \pi_{V}(X)=(X_{11},\ldots,X_{nn}) is the diagonal of X . The algebraic boundary of {\mathscr{C}}(C_{n}) involves the polynomial \Gamma_{n}^{h} . Our strategy for computing the degree of \Gamma_{n}^{h} implies a stronger result, which states the multidegree of \Gamma_{n}^{h} with respect to a natural \mathbb{Z}^{n} -grading (Theorem 3.21 ). We now give an overview of relevant background literature and applications. Some background literature and applications. Graph elliptopes {\mathcal{E}}(G) arise in several different contexts. First, as we saw in Example 1.1 , they are directly connected to the positive semidefinite (PSD) completion problem. Given a partially filled correlation matrix whose (i,j) -th entries are known for \{i,j\}\in E , the PSD completion problem asks whether it can be completed to a positive (semi)definite matrix by filling in the missing (i,j) -th entries for \{i,j\}\notin E . There is a vast literature on this problem, starting with the seminal paper [ 15 ] , which answers the problem for chordal graphs. The case of cycles is settled in [ 3 ] , where positive (semi)definite completability is characterized using a cosine parametrization. The larger class of graphs with no K_{4} -minors is treated in [ 20 ] and cycle completable graphs are covered in [ 2 ] . The main results are recalled in Section 2.1 . Graph elliptopes are also used within combinatorial optimization. Indeed, the set {\mathcal{E}}_{n} of correlation matrices defines a natural semidefinite programming relaxation for the maximum cut problem, which has been used by Goemans and Williamson [ 14 ] for their celebrated 0.878 -approximation algorithm. In the same way, {\mathcal{E}}(G) provides a relaxation for the maximum cut problem on G . For details see, e.g., [ 19 , 17 ] and references therein. The PSD matrix completion problem where one does not fix the diagonal entries to be 1 is also widely investigated, see [ 15 , 22 ] and references therein. This leads to the cone {\mathscr{C}}(G)\subseteq\mathbb{R}^{V\cup E} obtained by projecting the cone {\mathcal{S}}^{n}_{+} onto the subspace indexed by the vertices and edges of G . The elliptope {\mathcal{E}}(G) is an affine section of this cone. There are tight links with the distance geometry problem and Euclidean distance matrix completion problems, see [ 21 , 22 ] . In addition, the cone {\mathscr{C}}(G) is used in algebraic statistics, where it is directly relevant to the cone of sufficient statistics for the undirected Gaussian graphical model of G , as explained in [ 27 ] . In this context, the existence of a maximum likelihood estimate is equivalent to the condition that the set \pi_{V\cup E}^{-1}(\mathbb{S}){\cap}{\cal S}^{n}_{+} is non-empty, where \mathbb{S} is the sample covariance matrix. The close relation between {\mathscr{C}}(G) and {\mathcal{E}}(G) leads the authors of [ 27 ] to consider the algebraic boundary of {\mathscr{C}}(C_{n}) in [ 27 , Section 4.2] , invoking results from [ 3 ] . In [ 8 ] the authors investigate the quality of the outer approximation of the cone {\mathscr{C}}(G) obtained by requiring positive semidefiniteness of the fully specified submatrices supported on the cliques of G (the conic analog of the set S(G) in ( 2 )); they give an explicit analysis for cycle completable graphs and their suspensions. The problem of finding positive semidefinite matrix completions of low rank has been investigated in [ 12 , 13 , 18 ] ; this connects to low dimensional Euclidean embeddings [ 6 , 5 ] and falls within the broader context of low rank solutions to semidefinite programs (see, e.g., [ 24 ] and references therein). It is known that any point x\in{\mathcal{E}}(C_{n}) has a positive semidefinite completion of rank at most 3 and a characterization is given for the points admitting such a completion of rank at most 2 (see [ 12 , Section 2.2] , or [ 8 , Lemma 4.6] ). We come back to this in Remark 2.7 . Geometric results on graph elliptopes and their polar bodies are presented in [ 26 ] . In particular, for a graph G with no K_{5} -minor, a connection is established between the facets of its cut polytope and the extreme rays of the polar body of {\mathcal{E}}(G) . For such graphs it is known that the cut polytope coincides with the metric polytope and thus its facets arise from edge inequalities and cycle inequalities, as recalled in Section 2.1 . Finding the algebraic boundary \partial_{a}S of a convex semialgebraic set S is a standard task in convex algebraic geometry, see [ 25 ] for details and applications. There, it is shown that the algebraic boundary of a full-dimensional convex semialgebraic set S is a hypersurface, i.e., its irreducible components have codimension one (see Proposition 4.7 ). So, the hypersurface \partial_{a}S can be seen as a nonlinear generalization of the facet hyperplane arrangement for a convex polytope. As mentioned above, the cycle polynomial \Gamma_{n} is an important ingredient for describing the algebraic boundary \partial_{a}{\mathcal{E}}(G) of the elliptope {\mathcal{E}}(G) , when G is cycle completable. This polynomial turns out to be interesting in its own right and, in fact, we have dedicated Section 3 to proving several of its remarkable properties. This part of the project was facilitated by recent results in [ 23 ] on the above mentioned class of varieties called Lissajous varieties, of which the zero locus of \Gamma_{n} is an example (see Section 2.2 ). Lissajous varieties arising from graphs are investigated in [ 23 , Section 4] , where they are used for computing equilibria in Kuramoto dynamics. Organization of the paper. Section 2 contains preliminaries on graph elliptopes and Lissajous varieties, and introduces notation used throughout the paper. Section 3 proves our new results related to cycle polynomials. The main theorems provide a resultant construction (Theorem 3.12 ) and the degree of the homogeneous cycle polynomial (Theorem 3.20 ). Section 4 includes our main results on the algebraic boundary of {\mathcal{E}}(G) . The main result is Theorem 4.5 , which characterizes the algebraic boundary of {\mathcal{E}}(G) for cycle completable graphs (as a consequence of a more general result). This allows us to characterize the graph elliptopes that are spectrahedra (Corollary 4.10 ). In addition, when G is cycle completable, we derive the algebraic boundary of the cone {\mathscr{C}}(G) (Corollary 4.11 ) and the algebraic boundaries of {\mathscr{C}}(\nabla G) , {\mathcal{E}}(\nabla G) of the suspension graph \nabla G , obtained by adding a new node adjacent to all nodes of G (Proposition 4.14 ). 2 Preliminaries 2.1 Preliminaries on elliptopes A correlation matrix is a (real symmetric) positive semidefinite matrix whose diagonal entries are all equal to one. We denote by \mathcal{E}_{n} the set of all n\times n real correlation matrices. Let G=(V=[n],E) be a simple, undirected graph; it is sometimes convenient to let V(G) and E(G) denote the vertex set and the edge set of G . The elliptope of G , denoted by \mathcal{E}(G) , is defined as the projection of \mathcal{E}_{n} onto the subspace \mathbb{R}^{E} indexed by the edge set of G , i.e., \mathcal{E}(G)=\pi_{E}({\cal E}_{n})=\{x\in\mathbb{R}^{E}:\exists X\in\mathcal{E}_{n}\text{ such that }X_{ij}=x_{ij}\text{ for }\{i,j\}\in E\}. Throughout, \pi_{E} denotes the projection onto the subspace indexed by the edge set E of G . In particular, {\mathcal{E}}_{n} corresponds to the elliptope of the complete graph K_{n} (after identifying a correlation matrix with the vector consisting of its off-diagonal entries). Deciding whether a vector x\in\mathbb{R}^{E} belongs to {\mathcal{E}}(G) is an instance of the positive semidefinite completion problem , which asks to determine whether the partially filled matrix with ones on the diagonal and entries x_{e} at the positions indexed by the edges of G can be completed to a positive semidefinite matrix. This problem has been widely studied, starting with the work of Grone et al. [ 15 ] which proves the following necessary condition: If x\in{\mathcal{E}}(G) , then \displaystyle x[K]\succeq 0\text{ for all cliques }K\text{ of }G. (1) This is known as the clique condition . Recall that a clique of G is a set K\subseteq V of vertices that are pairwise connected by an edge in G . In ( 1 ), x[K] denotes the symmetric matrix indexed by K with an all-ones diagonal and whose off-diagonal entries are provided by the entries of x . The vertices of each edge in E form a clique, so the clique condition implies that {\mathcal{E}}(G) is contained in the hypercube [-1,1]^{E} . Clearly, in ( 1 ), it suffices to consider the maximal cliques of G . Let {\mathcal{K}}_{G} denote the set of maximal cliques of G . Grone et al. [ 15 ] show that the clique condition ( 1 ) is necessary and sufficient for membership in {\mathcal{E}}(G) if and only if the graph G is chordal. Theorem 2.1 . [ 15 ] For a graph G=(V,E) , define the spectrahedron \displaystyle S(G)\,=\,\{x\in\mathbb{R}^{E}:x[K]\succeq 0\ \text{ for all }K\in{\mathcal{K}}_{G}\}. (2) We have the inclusion {\mathcal{E}}(G)\subseteq S(G) , and equality holds if and only if G is a chordal graph. One of the many equivalent definitions of G being chordal is that G does not contain a chordless cycle of length at least 4 (i.e., every cycle of length at least 4 has a chord). Here, a cycle C in G of length p\geq 3 is a subgraph of G whose vertices can be ordered as v_{1},\ldots,v_{p} in such a way that the pairs \{v_{1},v_{2}\},\ldots,\{v_{p-1},v_{p}\},\{v_{p},v_{1}\} are all edges in G ; the cycle is then also denoted as C=(v_{1},\ldots,v_{p}) . Any other edge of G of the form \{v_{i},v_{j}\} with j\neq i-1,i+1 (modulo p ) is called a chord of C , and C is chordless if no such a chord exists. A cycle of length n is denoted by C_{n} and its edge set is denoted by E_{n} . The inclusion {\mathcal{E}}(G)\subseteq S(G) is strict when G=C_{n}=(1,\ldots,n) is a cycle with n\geq 4 ; indeed, the vector x\in\mathbb{R}^{E_{n}} with entries x_{12}=\ldots=x_{n-1,n}=1 and x_{1n}=-1 satisfies ( 1 ), but x\not\in{\mathcal{E}}(C_{n}) as x is not completable to a positive semidefinite matrix. When G contains (chordless) cycles, another necessary condition was introduced by Barrett et al. [ 3 ] : If x\in{\mathcal{E}}(G) , then it can be parametrized as x=\cos(\pi a) for some a\in[0,1]^{E} (since x\in[-1,1]^{E} ), and the vector a={1\over\pi}\arccos(x) satisfies \displaystyle a(F)-a(C\setminus F)\leq|F|-1\text{ for all cycles }C\text{ in }G,F\subseteq C,|F|\text{ odd}. (3) These are called the cycle inequalities . Here, for a subset F\subseteq E , we set a(F)=\sum_{e\in F}a_{e} . Let \text{\rm MET}(G) denote the polytope in \mathbb{R}^{E} consisting of the vectors a\in\mathbb{R}^{E} satisfying 0\leq a_{e}\leq 1 for e\in E and the cycle inequalities ( 3 ). This polytope is known as the metric polytope of G . It is well-known that the inequalities 0\leq a_{e}\leq 1 define facets of \text{\rm MET}(G) only for the edges e\in E that are not contained in a larger clique of G . Moreover, only the chordless cycles are needed in ( 3 ) since these are precisely the ones that induce facets of \text{\rm MET}(G) (see [ 1 ] , or [ 11 , Chap. 27] ). Indeed, if the edge e_{0}\in E is a chord of a cycle C in G , then one can cover the edge set of C with two smaller cycles (call them C^{\prime} , C^{\prime\prime} ) sharing only the edge e_{0} , and one can easily see that the cycle inequality ( 3 ) obtained from C is implied by the cycle inequalities obtained from C^{\prime} and C^{\prime\prime} by eliminating the variable x_{e_{0}} . This idea of eliminating the variable attached to a chord of a cycle will be used again in Section 3.2 when dealing with the resultant of cycle polynomials. The result of Barrett et al. [ 3 ] can be expressed as \displaystyle{\mathcal{E}}(G)\subseteq\cos(\pi\text{\rm MET}(G)), (4) where the cosine map is applied entrywise. The paper [ 3 ] also shows that equality holds in ( 4 ) when G is a cycle. In [ 20 ] , Laurent characterizes all graphs for which equality holds. Theorem 2.2 . [ 20 ] For a graph G , equality {\mathcal{E}}(G)=\cos(\pi\text{\rm MET}(G)) holds if and only if G has no K_{4} -minor (equivalently, G is series-parallel). By the above discussion, the facets of \text{\rm MET}(K_{n}) are defined by the cycle inequalities ( 3 ) for all triplets \{i,j,k\}\subseteq V(K_{n}) . These are also known as the triangle inequalities . Moreover, the metric polytope of a graph G=(V,E) with n vertices is obtained as a projection of \text{\rm MET}(K_{n}) : \displaystyle\text{\rm MET}(G)=\pi_{E}(\text{\rm MET}(K_{n})), (5) see [ 1 ] , or [ 11 , Chap. 27] . The inclusion \pi_{E}(\text{\rm MET}(K_{n}))\subseteq\text{\rm MET}(G) is clear since each cycle inequality is implied by triangle inequalities. The first row in Figure 1 shows three different sections of the metric polytope \text{\rm MET}(C_{4}) , obtained by setting a variable to \tfrac{1}{2},\tfrac{1}{3},0 , respectively. As C_{3}=K_{3} , we have {\mathcal{E}}(K_{3})=\cos(\pi\text{\rm MET}(K_{3})) . Combining this with ( 5 ), it follows that \cos(\pi\text{\rm MET}(G)) is a spectrahedral shadow for any graph G . Lemma 2.3 . For any graph G , the set \cos(\pi\text{\rm MET}(G)) is the projection of a spectrahedron. In particular, \cos(\pi\text{\rm MET}(G)) is convex and semialgebraic. Proof. Since \text{\rm MET}(K_{3}) is defined by the triangle inequalities that are based on three point-sets and the equality \cos(\pi\text{\rm MET}(K_{3}))={\mathcal{E}}(K_{3}) holds by Theorem 2.2 , one obtains that \cos(\pi\text{\rm MET}(K_{n}))=\{x\in\mathbb{R}^{E(K_{n})}:x[K]\succeq 0\text{ for all }K\subseteq V,|K|=3\}. Hence, the set \cos(\pi\text{\rm MET}(K_{n})) is a spectrahedron, so it is convex and semialgebraic. Since the projection of a convex set is convex, and the projection of a semialgebraic set is semialgebraic by Tarski-Seidenberg, the projection \pi_{E}(\cos(\pi\text{\rm MET}(K_{n}))) is convex semialgebraic too. Using ( 5 ), we have \pi_{E}(\cos(\pi\text{\rm MET}(K_{n})))=\cos(\pi_{E}(\pi\text{\rm MET}(K_{n})))=\cos(\pi\text{\rm MET}(G)) .∎ Theorem 2.1 and Equation ( 4 ) provide two convex semialgebraic sets containing {\mathcal{E}}(G) . We combine them to obtain a sharper outer approximation \widetilde{\mathcal{E}}(G)=S(G)\cap\cos(\pi\text{\rm MET}(G)) , \displaystyle\begin{split}\widetilde{\mathcal{E}}(G)=\Big\{x\in\mathbb{R}^{E}:x[K]\succeq 0\text{ for all }K\in{\mathcal{K}}_{G}\text{ and }{1\over\pi}\arccos(x)\in\text{\rm MET}(G)\Big\},\end{split} (6) of the elliptope {\mathcal{E}}(G) : we have the inclusion {\mathcal{E}}(G)\subseteq\widetilde{\mathcal{E}}(G) . Notice that \widetilde{\mathcal{E}}(G) is full-dimensional since the zero vector lies in its interior. It is convex and semialgebraic, as these properties are preserved when taking intersections. Following Barrett et al. [ 2 ] , a graph G is said to be cycle completable when membership in the elliptope {\mathcal{E}}(G) is characterized by both conditions ( 1 ) and ( 3 ) combined, i.e., when the equality {\mathcal{E}}(G)=\widetilde{\mathcal{E}}(G) holds. The following characterization of cycle completable graphs follows from results in [ 2 , 16 ] . Theorem 2.4 . [ 2 , 16 ] A graph G is cycle completable, i.e., equality {\mathcal{E}}(G)=\widetilde{\mathcal{E}}(G) holds with \widetilde{\mathcal{E}}(G) as in ( 6 ), if and only if G satisfies any of the following equivalent conditions: (i) G is a subgraph of a chordal graph, all of whose cliques of size 4 are contained in G . (ii) G can be obtained as a clique sum of chordal graphs and graphs with no K_{4} -minors. (iii) No induced subgraph of G is a wheel W_{k} ( k\geq 5 ) or an iterated splitting of W_{k} ( k\geq 4 ). We refer to [ 2 , 16 ] for details on clique sums and splittings. We will consider elliptopes of wheels later in Section 4.3 . 2.2 Preliminaries on Lissajous varieties In this section we discuss Lissajous varieties, a class of algebraic varieties that was recently introduced and investigated by Mascarin and Telen [ 23 ] . We refer to the textbooks [ 9 , 10 ] for basic facts about algebraic varieties and polynomial ideals. In what follows, for a set {\mathcal{F}}\subseteq\mathbb{C}[x_{1},\ldots,x_{n}] of polynomials, V({\mathcal{F}})=\{x\in\mathbb{C}^{n}:f(x)=0\text{ for all }f\in{\mathcal{F}}\} denotes the associated complex affine variety. The vanishing ideal of a set S\subseteq\mathbb{C}^{n} is denoted by I(S)\,=\,\{f\in\mathbb{C}[x_{1},\ldots,x_{n}]\,:\,f(x)=0\text{ for all }x\in S\} . We use the notation u\cdot v for the euclidean inner product of two vectors u,v\in\mathbb{C}^{n} , and u\circ v=(u_{i}v_{i})_{i=1}^{n} for their Hadamard product. We let \mathbf{1} and \mathbf{0} denote the all-ones vector and the zero vector (of appropriate size), and I_{n} is the n\times n identity matrix. Parametric and determinantal representations of Lissajous varieties Let A\in\mathbb{Z}^{d\times n} be an integer-valued matrix and let {\rm Row}(A)\subseteq\mathbb{C}^{n} denote the \mathbb{C} -linear span of its rows. Given a vector b\in\mathbb{C}^{n} , let {\cal L}_{A,b} be the image of the affine space \displaystyle L_{A,b}={\rm Row}(A)-\frac{b\pi}{2}=\Big\{x-\frac{b\pi}{2}\,:\,x\in{\rm Row}(A)\Big\}\subseteq\mathbb{C}^{n} under the componentwise cosine map. That is, define \displaystyle{\cal L}_{A,b}\,=\,{\rm cos}(L_{A,b})=\{(\cos(z_{1}),\dotsc,\cos(z_{n})):z\in L_{A,b}\}\subseteq\mathbb{C}^{n}, called the Lissajous variety associated to the pair (A,b) . Then, {\mathcal{L}}_{A,b} is an irreducible affine algebraic variety of dimension {\rm rank}(A) [ 23 , Lemma 2.1] . The case where b={\bf 0}\in\mathbb{C}^{n} first appeared in [ 4 , Section 5] . We shall use the short-hand notation {\cal L}_{A}={\cal L}_{A,{\bf 0}}=\cos({\text{\rm Row}}(A)) . Let a_{1},\ldots,a_{n}\in\mathbb{Z}^{d} denote the columns of matrix A . Choosing coordinates t\in\mathbb{C}^{d} on {\rm Row}(A) , one can obtain the Lissajous variety {\cal L}_{A,b} as the image of \mathbb{C}^{d} under the map \phi_{A,b}\,:\,\mathbb{C}^{d}\longrightarrow\mathbb{C}^{n},\quad t=(t_{1},\ldots,t_{d})\longmapsto({\rm cos}(a_{1}\cdot t-b_{1}\tfrac{\pi}{2}),\ldots,{\rm cos}(a_{n}\cdot t-b_{n}\tfrac{\pi}{2})), (7) which gives a trigonometric parametrization of {\mathcal{L}}_{A,b}=\phi_{A,b}(\mathbb{C}^{d}) . The integer matrix A defines an affine toric variety Y_{A}\subseteq\mathbb{C}^{n} , obtained as the closure of the image of the Laurent monomial map v\in(\mathbb{C}^{*})^{d}\mapsto(v^{a_{1}},\ldots,v^{a_{n}}) , i.e., \displaystyle Y_{A}\,=\,\overline{\{v^{a_{1}},\ldots,v^{a_{n}}):v\in(\mathbb{C}^{*})^{d}\}}\,\subseteq\,\mathbb{C}^{n}. A scaled toric variety Y_{A,\beta} is obtained from A\in\mathbb{Z}^{d\times n} and \beta\in(\mathbb{C}^{*})^{n} as follows: Y_{A,\beta}\,=\,\{(\beta_{1}\,y_{1},\ldots,\beta_{n}\,y_{n})\,:\,y\in Y_{A}\}\,\subseteq\,\mathbb{C}^{n}. The vanishing ideal I(Y_{A,\beta}) is generated by binomials: \displaystyle I(Y_{A,\beta})\,=\,\langle\beta^{w}y^{u}-\beta^{u}y^{w}\,:\,u,w\in\mathbb{N}^{n}\,\,\text{and}\,\,A(u-w)=0\rangle\,\subseteq\,\mathbb{C}[y]=\mathbb{C}[y_{1},\ldots,y_{n}]. (8) For instance, the vanishing ideal I(Y_{A}) is obtained by setting \beta={\mathbf{1}} . The following characterization, shown in [ 23 , Theorem 2.2] , immediately yields a rational parametrization of {\cal L}_{A,b} . Theorem 2.5 . Let A\in\mathbb{Z}^{d\times n} , b\in\mathbb{C}^{n} , and set \beta=(e^{-ib_{1}\tfrac{\pi}{2}},\ldots,e^{-ib_{n}\tfrac{\pi}{2}})\in(\mathbb{C}^{*})^{n} . Then, the Lissajous variety {\cal L}_{A,b}\subseteq\mathbb{C}^{n} is equal to the image of the variety {\cal Y}_{A,b}\,=\,\{(x,y)\in\mathbb{C}^{n}\times(\mathbb{C}^{*})^{n}\,:\,y\in Y_{A,\beta}\text{ and }x_{j}\,=\,\tfrac{1}{2}(y_{j}+y_{j}^{-1})\text{ for }j=1,\ldots,n\}, under the coordinate projection \pi_{A,b}\colon(x,y)\in{\cal Y}_{A,b}\mapsto x\in\mathbb{C}^{n} . That is, {\mathcal{L}}_{A,b}=\pi_{A,b}({\cal Y}_{A,b}). This characterization can be used to derive a determinantal representation of the Lissajous variety {\mathcal{L}}_{A,b} , as shown in [ 23 , Theorem 3.1] . For simplicity, and since this is the relevant case for our paper, we present this determinantal representation in the case when A has rank n-1 and b=\mathbf{0} , i.e., \beta={\mathbf{1}} . The kernel of A is spanned by a vector u-w with u,w\in\mathbb{N}^{d} and I(Y_{A})=\langle g_{A}\rangle , where g_{A}=y^{u}-y^{w}\in\mathbb{C}[y] . Given x\in\mathbb{C}^{n} , consider the ideal J_{x}=\langle 2x_{i}-y_{i}-y_{i}^{-1}:i\in[n]\rangle\subseteq\mathbb{C}[y,y^{-1}]=\mathbb{C}[y_{i},y_{i}^{-1}:i\in[n]]. As the equation 2x_{i}-y_{i}-y_{i}^{-1}=0 is equivalent to y_{i}^{2}-2x_{i}y_{i}+1=0 , the variety V(J_{x}) is a finite set, consisting of 2^{n} points, \displaystyle V(J_{x})=\Big\{\big(x_{i}+\epsilon_{i}\sqrt{x_{i}^{2}-1}\big)_{i=1}^{n}:\epsilon\in\{\pm 1\}^{n}\Big\}. (9) Consider the quotient algebra R_{x}=\mathbb{C}[y,y^{-1}]/J_{x} . Hence, R_{x}\simeq\otimes_{i=1}^{n}\mathbb{C}[y_{i}]/\langle y_{i}^{2}-2x_{i}y_{i}+1\rangle has finite dimension 2^{n} , since \mathbb{C}[y_{i}]/\langle y_{i}^{2}-2x_{i}y_{i}+1\rangle is spanned by the cosets of 1,y_{i} . For any polynomial g\in\mathbb{C}[y] , consider the associated “multiplication by g ” linear map M_{g}:R_{x}\to R_{x} that maps the coset of f to the coset of fg . It follows from the well-known eigenvalue method for polynomial root finding (see, e.g., [ 9 , Chapter 4, Proposition 2.7] ) that the eigenvalues of M_{g} are the evaluations g(\xi) of g at the roots \xi\in V(J_{x}) . In particular, we have \displaystyle\det(M_{g})=\prod_{\xi\in V(J_{x})}g(\xi). (10) The matrix M_{g} is obtained as M_{g}=g(M_{y_{1}},\ldots,M_{y_{n}}) , a polynomial in the pairwise commuting matrices M_{y_{i}} . In [ 23 , Section 3] , it is explained in detail that the matrix M_{y_{i}} is the following Kronecker product of n matrices of size 2\times 2 : I_{2}\otimes\cdots\otimes I_{2}\otimes\left(\begin{smallmatrix}0&-1\cr 1&2x_{i}\end{smallmatrix}\right)\otimes I_{2}\otimes\cdots\otimes I_{2}, where the only non-identity matrix appearing in the product is placed at the i -th position. Hence, M_{g} is a 2^{n}\times 2^{n} matrix with polynomial entries in \mathbb{Z}[x] . By Theorem 2.5 , x\in{\mathcal{L}}_{A,b} if and only if there exists y\in V(J_{x}) such that y\in Y_{A}=V(g_{A}) ; equivalently, x\in{\mathcal{L}}_{A,b} if and only if \prod_{y\in V(J_{x})}g_{A}(y)=0 . Therefore, using ( 10 ) for the polynomial g=g_{A} , we obtain the following determinantal representation of {\mathcal{L}}_{A,b} , \displaystyle{\mathcal{L}}_{A,b}=\{x\in\mathbb{C}^{n}:\det(M_{g_{A}})=0\}. (11) Lissajous varieties of graphs An important class of Lissajous varieties arises from graphs in the following way. Let G=(V,E) be a simple, connected graph. We define an incidence matrix A_{G}\in\mathbb{Z}^{V\times E} of G as follows. Select an ordering and orientation of the edges in E , and an ordering of the vertices in V . The rows of A_{G} are indexed by V and its columns are indexed by E . If (j,k) is the l -th edge of G (oriented from j to k ), then the l -th column of A_{G} is the vector a_{l}=e_{j}-e_{k} , where e_{k} is the k -th standard basis vector of \mathbb{R}^{V} . That is, (A_{G})_{i,(j,k)} is equal to 1 (resp., -1 , 0) if i=j (resp., i=k , i\in V\setminus\{j,k\} ). Since G is connected, the rank of A_{G} is |V|-1 . The Lissajous variety associated to G is \displaystyle{\mathcal{L}}_{G}={\mathcal{L}}_{A_{G},{\bf 0}}=\cos({\text{\rm Row}}(A_{G})). Reordering the edges simply amounts to permuting the coordinates in the ambient space \mathbb{C}^{n} and \mathcal{L}_{G} does not depend on the selected orientation of the edges. Indeed, reversing the edge (j,k) amounts to replacing the associated column a_{l}=e_{j}-e_{k} of A_{G} by its negation -a_{l}=e_{k}-e_{j} ; as \cos(-a_{l}\cdot t)=\cos(a_{l}\cdot t) , the variety \mathcal{L}_{G} remains unchanged. The Lissajous variety of the cycle graph G=C_{n}=(1,2,\ldots,n) plays a central role in this paper. For a cycle of length n , we simplify the notation further to \mathcal{L}_{n}={\mathcal{L}}_{C_{n}}. Let us order and orient the edges of C_{n} as (1,n),(1,2),\ldots,(n-1,n) . Since A_{C_{n}} has rank n-1 and the Lissajous variety \mathcal{L}_{n} depends only on the row span of A_{C_{n}} , one can delete a row of A_{C_{n}} and apply row transformations so that its row space is equal to that of A_{n}\,=\,\begin{pmatrix}1&1&0&\cdots&0\\ 1&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&0&0&\cdots&1\end{pmatrix}\quad\in\,\,\mathbb{Z}^{(n-1)\times n}. (12) The associated Lissajous variety \mathcal{L}_{n}\subseteq\mathbb{C}^{n} is \mathcal{L}_{n}\,=\,\cos({\text{\rm Row}}(A_{n}))\,=\,\{(\cos(t_{2}+\dotsc+t_{n}),\cos(t_{2}),\dotsc,\cos(t_{n})):t\in\mathbb{C}^{n-1}\}. (13) A Lissajous variety depends only on the linear space {\rm Row}(A)\subseteq\mathbb{C}^{n} , and not on the particular choice of the matrix A\in\mathbb{Z}^{d\times n} . This correspondence is still not one-to-one, as multiple affine spaces may define the same Lissajous variety. The following result provides such an observation, which we will use for the case of {\cal L}_{n} . Lemma 2.6 . Consider a matrix A\in\mathbb{Z}^{d\times n} of rank d . Let \{v_{j}\}_{j=1}^{n-d}\subseteq\mathbb{Z}^{n} be a basis of the lattice \ker(A)\cap\mathbb{Z}^{n}=\{z\in\mathbb{Z}^{n}\,:\,A\,z=0\} . For the Lissajous variety {\cal L}_{A}=\cos({\text{\rm Row}}(A)) , we have {\mathcal{L}}_{A}=\cos(H_{s,k}) for any affine space H_{s,k}\subseteq\mathbb{C}^{n} of the form H_{s,k}=\{t\in\mathbb{C}^{n}:(s\circ v_{j})\cdot t=2\pi k_{j}\text{ for all }j=1,\dotsc,n-d\}, where s\in\{\pm 1\}^{n} and k\in\mathbb{Z}^{n-d} . Moreover, we have the equality \cos^{-1}({\mathcal{L}}_{A})=\bigcup_{s\in\{\pm 1\}^{n},k\in\mathbb{Z}^{n-d}}H_{s,k}. Proof. Let s\in\{\pm 1\}^{n} and k\in\mathbb{Z}^{n-d} . Assume that x\in\cos(H_{s,k}) , i.e., x=\cos(t) for some t\in\mathbb{C}^{n} with (s\circ v_{j})\cdot t=2k_{j}\pi for all j=1,\dotsc,n-d . Choose z\in\mathbb{Z}^{n} such that k_{j}=v_{j}\cdot z for j=1,\ldots,n-d . We perform the linear change of variables t_{i}\mapsto t^{\prime}_{i}=s_{i}t_{i}-2z_{i}\pi,\text{ for }i=1,\dotsc,n. Then, we obtain v_{j}\cdot t^{\prime}=(v_{j}\circ s)\cdot t-2\pi v_{j}\cdot z=0 for 1\leq j\leq n-d , showing t^{\prime}\in{\text{\rm Row}}(A) . Then, \cos(t^{\prime})=\cos(t)=x , and thus x\in{\cal L}_{A} . The inclusion {\mathcal{L}}_{A}\subseteq\cos(H_{s,k}) is proved analogously, by inverting the change of variables. It remains to prove that \cos^{-1}({\mathcal{L}}_{A})\subseteq\bigcup_{s,k}H_{s,k} . Let t\in\mathbb{C}^{n} be such that \cos(t)\in{\mathcal{L}}_{A} . By definition, we have \cos(t)=\cos(t^{\prime}) , for some t^{\prime}\in{\text{\rm Row}}(A) . This means that there exist some s\in\{\pm 1\}^{n} and k^{\prime}\in\mathbb{Z}^{n} such that t=s\circ t^{\prime}+2k^{\prime}\pi . In particular, (s\circ v_{j})\cdot t=2\pi(s\circ v_{j})\cdot k^{\prime} for j=1,\dotsc,n-d . Set k=(v_{1}\cdot(s\circ k^{\prime}),\dotsc,v_{n-d}\cdot(s\circ k^{\prime})) . Then (s\circ v_{j})\cdot t=2\pi k_{j} for j=1,\dotsc,n-d , which shows that t\in H_{s,k} . ∎ Remark 2.7 . As an application of Lemma 2.6 , the Lissajous variety of the cycle C_{n} is given by {\mathcal{L}}_{n}=\cos(H_{s,k}),\text{ where }H_{s,k}=\Big\{t\in\mathbb{C}^{n}:s\cdot t=2k\pi\Big\},\ s\in\{\pm 1\}^{n}\text{ and }\ k\in\mathbb{Z}, and we have \displaystyle\cos^{-1}({\mathcal{L}}_{n})=\bigcup_{s\in\{\pm 1\}^{n},k\in\mathbb{Z}}H_{s,k}=\{t\in\mathbb{C}^{n}:s\cdot t=2k\pi\}. (14) In particular, {\mathcal{L}}_{n}={\mathcal{L}}_{A^{\prime}_{n}} , where A^{\prime}_{n} is obtained from A_{n} in ( 12 ) by changing the signs in its first column. Indeed, the kernel of A_{n} is spanned by v=(1,-1,\ldots,-1) , and selecting s=\mathbf{1} , k=0 gives the hyperplane H_{{\bf 1},0}=\ker(A^{\prime}_{n})=\{t\in\mathbb{C}^{n}\,:\,t_{1}+\cdots+t_{n}=0\} . The intersection {\mathcal{L}}_{n}\cap[-1,1]^{n} is particularly relevant to our treatment as well as its preimage {1\over\pi}\cos^{-1}({\mathcal{L}}_{n})\cap[0,1]^{n} under the componentwise cosine map, which can in fact be covered by a union of finitely many hyperplanes since one can restrict to |k|\leq n/2 in ( 14 ). Let us comment briefly on the relation to elliptopes. A point x\in{\mathcal{E}}(C_{n}) has a PSD completion of rank at most 2 if and only if \arccos x lies in the union of hyperplanes in ( 14 ) (see [ 12 , Section 2.2] , or [ 8 , Lemma 4.6] ), which is equivalent to x\in{\mathcal{L}}_{n} . Thus, the hypersurface {\cal L}_{n} is the Zariski closure of the part of the boundary of {\mathcal{E}}(C_{n}) consisting of the points that admit a PSD completion of rank at most 2 . On the other hand, the Zariski closure of the full boundary of {\mathcal{E}}(C_{n}) consists of {\mathcal{L}}_{n} together with the coordinate hyperplanes x_{e}=\pm 1 for e\in E_{n} (see Proposition 4.3 ). 3 Cycle polynomials In [ 27 , Section 4.2] the authors define the n -th cycle polynomial \Gamma_{n} as the unique (up to scaling) n -variate irreducible polynomial obtained by rationalizing the equation x_{1}=\cos\Big(\sum_{i=2}^{n}\arccos(x_{i})\Big). (15) Here, it is meant that \Gamma_{n} is the defining polynomial of the hypersurface obtained by applying the coordinatewise cosine map to the hyperplane t_{1}=t_{2}+\cdots+t_{n} . As this hyperplane is the row span of the matrix A_{n} from ( 12 ) this means that V(\Gamma_{n})=\cos({\text{\rm Row}}(A_{n}))={\mathcal{L}}_{n} . The identity V(\Gamma_{n})={\cal L}_{n} determines \Gamma_{n} up to scaling. We shall now present a new definition (Definition 3.2 ), consistent with V(\Gamma_{n})={\cal L}_{n} , which uniquely fixes this scaling. Let C_{n}=(1,\ldots,n) be the cycle graph with n vertices and E_{n}=E(C_{n}) be its set of edges, denoted \{1,2\},\ldots,\{n-1,n\},\{1,n\} . It is convenient to use variables indexed by the edges of C_{n} , so \Gamma_{n}\in\mathbb{C}[x_{e}:e\in E_{n}] . When C is a cycle in a graph G=(V,E) , we also denote the corresponding cycle polynomial as \Gamma_{C}\in\mathbb{R}[x_{e}:e\in E(C)] . It is convenient to use the alternative, equivalent definition of the Lissajous variety {\mathcal{L}}_{n} as {\mathcal{L}}_{n}={\mathcal{L}}_{A^{\prime}_{n}} , where A^{\prime}_{n} is obtained by changing the signs in the first column of A_{n} . The matrix A^{\prime}_{n} defines a different toric variety Y_{A_{n}^{\prime}} but the same Lissajous variety {\cal L}_{A_{n}}={\cal L}_{A_{n}^{\prime}}={\cal L}_{n} (recall Remark 2.7 ). The kernel of A_{n}^{\prime} is spanned by the all-ones vector, which has the advantage that the defining equation of Y_{A_{n}^{\prime}} is more symmetric than that of Y_{A_{n}} . Concretely, as explained in Section 2.2 , Y_{A_{n}^{\prime}}=V(g_{n}) , where g_{n}(y)\,=\,\prod_{e\in E_{n}}y_{e}-1 . Using relations ( 10 ) and ( 11 ), we obtain {\mathcal{L}}_{n}=\Big\{x\in\mathbb{C}^{E_{n}}:\prod_{\xi\in V(J_{x})}g_{n}(\xi)=0\Big\}=\left\{x\in\mathbb{C}^{E_{n}}:h_{n}(x)=0\right\}, where V(J_{x}) is as in ( 9 ) and the function h_{n} is defined as h_{n}(x)\,=\,\prod_{\xi\in V(J_{x})}g_{n}(\xi)\,=\,\prod_{\epsilon\in\{-1,1\}^{E_{n}}}\Big[\prod_{e\in E_{n}}(x_{e}+\epsilon_{e}\sqrt{x_{e}^{2}-1})-1\Big]. (16) By the discussion in Section 2.2 , h_{n}=\det(M_{g_{n}}) is a polynomial in \mathbb{Z}[x] . It follows from results in [ 23 ] that h_{n} is, in fact, the square of a polynomial. Theorem 3.1 . For n\geq 3 , the polynomial h_{n} from ( 16 ) is the square of an irreducible polynomial and the degree of h_{n} is equal to n\binom{n-1}{\lfloor(n-1)/2\rfloor} . Proof. By [ 23 , Proposition 3.5] , the determinant of M_{g_{n}} is f^{w} , where f\in\mathbb{C}[x] is a defining equation of {\cal L}_{n} and w is a positive integer (the degree of the map \pi_{A,b} from Theorem 2.5 ). For the Lissajous hypersurface {\mathcal{L}}_{n} , this integer is shown to be equal to 2 in the proof of [ 23 , Proposition 2.6] . The same proposition states the degree of f , which is 1/2 times the stated degree of h_{n} . ∎ Definition 3.2 . Let h_{n} be as in Theorem 3.1 . The n -th cycle polynomial \Gamma_{n} is the unique polynomial in \mathbb{C}[x_{e}:e\in E_{n}] that satisfies 2^{-2^{n-1}}h_{n}=\Gamma_{n}^{2} and whose leading coefficient is equal to 1 when viewed as a univariate polynomial in any variable x_{e_{0}} . In Proposition 3.6 we will show that, when viewing h_{n} as a univariate polynomial in a variable x_{e_{0}} , its leading coefficient is 2^{2^{n-1}} , which motivates the scaling in the above definition. Example 3.3 . We mention the cycle polynomials \Gamma_{n} for small n and will come back later to them in Examples 3.8 and 3.14 . For n=3 , the polynomial \Gamma_{3} reads \Gamma_{3}\,=\,-1+x_{12}^{2}+x_{23}^{2}+x_{13}^{2}-2\,x_{12}x_{23}x_{13}=-\det\left(\begin{smallmatrix}1&x_{12}&x_{13}\cr x_{12}&1&x_{23}\cr x_{13}&x_{23}&1\end{smallmatrix}\right), hence it defines the Cayley cubic surface. Its square is a product of eight factors, each corresponding to a sign vector \epsilon=(\epsilon_{12},\epsilon_{23},\epsilon_{13})\in\{\pm 1\}^{E_{3}} : \displaystyle h_{3}\,=\,16\cdot\Gamma_{3}^{2} \displaystyle\,=\,\prod_{\epsilon\in\{\pm 1\}^{E_{3}}}\,\Big(x_{12}+\epsilon_{12}\sqrt{x_{12}^{2}-1}\Big)\Big(x_{23}+\epsilon_{23}\sqrt{x_{23}^{2}-1}\Big)\Big(x_{13}+\epsilon_{13}\sqrt{x_{13}^{2}-1}-1\Big). The 4-th cycle polynomial \Gamma_{4} is given by \begin{matrix}\Gamma_{4}\,=\,x_{12}^{4}-4x_{12}^{3}x_{23}x_{34}x_{14}+4x_{12}^{2}x_{23}^{2}x_{34}^{2}+4x_{12}^{2}x_{23}^{2}x_{14}^{2}-2x_{12}^{2}x_{23}^{2}+4x_{12}^{2}x_{34}^{2}x_{14}^{2}-2x_{12}^{2}x_{34}^{2}\\ \quad-2x_{12}^{2}x_{14}^{2}-4x_{12}x_{23}^{3}x_{34}x_{14}-4x_{12}x_{23}x_{34}^{3}x_{14}-4x_{12}x_{23}x_{34}x_{14}^{3}+8x_{12}x_{23}x_{34}x_{14}+x_{23}^{4}\\ +4x_{23}^{2}x_{34}^{2}x_{14}^{2}-2x_{23}^{2}x_{34}^{2}-2x_{23}^{2}x_{14}^{2}+x_{34}^{4}-2x_{34}^{2}x_{14}^{2}+x_{14}^{4}.\end{matrix} Finally, \Gamma_{5} has degree 15 and it has 339 terms. We display a few of them for concreteness: \Gamma_{5}\,=\,x_{12}^{8}-8x_{12}^{7}x_{23}x_{34}x_{45}x_{15}+16x_{12}^{6}x_{23}^{2}x_{34}^{2}x_{45}^{2}+16x_{12}^{6}x_{23}^{2}x_{34}^{2}x_{15}^{2}-\cdots-4x_{15}^{2}+1. 3.1 Properties of the cycle polynomial A first observation is that h_{n} and \Gamma_{n} enjoy the following symmetry properties. Lemma 3.4 . The polynomial h_{n} is symmetric, i.e., it is invariant under any permutation of the variables. Moreover, if \tilde{x} is obtained from x\in\mathbb{C}^{E_{n}} by an even sign flip, i.e., by replacing an even number of entries x_{e} by \tilde{x}_{e}=-x_{e} , then h_{n}(x)=h_{n}(\tilde{x}) holds. The same properties hold for the cycle polynomial \Gamma_{n} . Proof. This follows easily using the definition of h_{n} in ( 16 ) and of \Gamma_{n} in Definition 3.2 . ∎ Hence, contrary to what the name suggests, the cycle polynomial has more than only cyclic symmetry. This is also reflected in the symmetry of the row span of A_{n}^{\prime} and of the toric variety Y_{A_{n}^{\prime}} . The next result follows directly from the invariance under even sign flips. Corollary 3.5 . Let E^{\prime}\subseteq E be a subset of edges with even cardinality. The cycle polynomial \Gamma_{n} , viewed as a polynomial in x_{e} for e\in E^{\prime} , is even. In other words, if we expand \displaystyle\Gamma_{n}\,=\,\sum_{\alpha\in\mathbb{N}^{E^{\prime}}}c_{\alpha}(x_{E\setminus E^{\prime}})\,\prod_{e\in E^{\prime}}x_{e}^{\alpha_{e}}, (17) where the coefficients c_{\alpha} are polynomials in the variables x_{E\setminus E^{\prime}}=(x_{e}\,:\,e\in E\setminus E^{\prime}) , then \sum_{e\in E^{\prime}}\alpha_{e} is even for each \alpha such that c_{\alpha}\neq 0 . To simplify the exposition, we introduce some notation that we will also use in the next sections. Recall that E_{n}=E(C_{n}) . We define the following algebraic functions of x : \displaystyle z_{\epsilon}=\prod_{e\in E_{n}}\left(x_{e}+\epsilon_{e}\sqrt{x_{e}^{2}-1}\right)^{|\epsilon_{e}|}\ \text{ for any }\epsilon\in\{\pm 1,0\}^{E_{n}}. (18) For convenience we may also index z by \{\pm,0\} instead of \{\pm 1,0\} , e.g., writing z_{+-0} for z_{1,-1,0} . Note that z_{\epsilon}\cdot z_{-\epsilon}=1 and z_{\epsilon}=\prod_{i=1}^{n}z_{\mathbf{0},\epsilon_{i},\mathbf{0}} , where \epsilon_{i} is placed at the i -th position and \mathbf{0} denotes a zero vector of appropriate length. If \delta , \delta^{\prime} are sequences whose concatenation (\delta,\delta^{\prime}) lies in \{\pm 1,0\}^{E_{n}} , then z_{\delta,\delta^{\prime}}=z_{\delta,\mathbf{0}}\cdot z_{\mathbf{0},\delta^{\prime}} holds. Using ( 18 ), we can rewrite h_{n} from ( 16 ) compactly as \displaystyle h_{n}=\prod_{\epsilon\in\{\pm 1\}^{E_{n}}}(z_{\epsilon}-1). (19) The next proposition motivates the factor 2^{-2^{n-1}} in Definition 3.2 : this scaling makes \Gamma_{n} monic when viewed as a univariate polynomial in any of its variables. Proposition 3.6 . Consider two distinct edges e_{0},e_{1}\in E_{n} . When viewed as a univariate polynomial in x_{e_{0}} , the polynomial h_{n} has degree 2^{n-1} with leading coefficient 2^{2^{n-1}} , and its roots are given by the following algebraic functions of x_{e} (for e\in E_{n}\setminus\{e_{0}\} ): \displaystyle r_{\delta}\,=\,\frac{z_{0,\delta}+z_{0,-\delta}}{2}\quad\text{ for }\delta\in\{-1,1\}^{E_{n}\setminus\{e_{0}\}}, (20) where z_{0,\delta}\,=\,\prod_{e\in E\setminus\{e_{0}\}}(x_{e}+\delta_{e}\,\sqrt{x_{e}^{2}-1}) as in ( 18 ), with the first zero entry in the subscript corresponding to the variable x_{e_{0}} . Moreover, we have \displaystyle h_{n}=2^{2^{n-1}}\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}z_{0,\delta}(x_{e_{0}}-r_{\delta})=2^{2^{n-1}}\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}:\delta_{e_{1}}=1}(x_{e_{0}}-r_{\delta})^{2}. (21) Proof. Starting with the definition of h_{n} in ( 19 ), we obtain \displaystyle h_{n}(x) \displaystyle=\prod_{\epsilon\in\{-1,1\}^{E_{n}}}(z_{\epsilon}-1)=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}\prod_{\epsilon_{0}\in\{\pm 1\}}(z_{\epsilon_{0},\delta}-1) \displaystyle=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}\prod_{\epsilon_{0}\in\{\pm 1\}}(z_{\epsilon_{0},\mathbf{0}}z_{0,\delta}-1)=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}(z_{+\mathbf{0}}z_{0,\delta}-1)\cdot(z_{-\mathbf{0}}z_{0,\delta}-1) \displaystyle=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}(z_{0,\delta}^{2}-z_{0,\delta}(z_{+\mathbf{0}}+z_{-\mathbf{0}})+1)=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}(z_{0,\delta}^{2}-2x_{e_{0}}z_{0,\delta}+1) \displaystyle=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}\Big[2z_{0,\delta}\cdot(x_{e_{0}}-r_{\delta})\Big]. In this derivation, we used the fact that z_{+\mathbf{0}}z_{-\mathbf{0}}=1 , z_{+\mathbf{0}}+z_{-\mathbf{0}}=2x_{e_{0}} , and the identities z_{0,\delta}^{2}-2x_{e_{0}}z_{0,\delta}+1=-2z_{0,\delta}(x_{e_{0}}-{1\over 2}(z_{0,\delta}+z_{0,\delta}^{-1}))=-2z_{0,\delta}(x_{e_{0}}-r_{\delta}) . This gives the first representation of h_{n} in ( 21 ). To get the second one, consider the partition of \{\pm 1\}^{E_{n}\setminus\{e_{0}\}} as \Delta\cup(-\Delta) , where \Delta=\{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}:\delta_{e_{1}}=1\} and -\Delta=\{-\delta:\delta\in\Delta\} . Then, using the fact that z_{0,\delta}z_{0,-\delta}=1 and r_{\delta}=r_{-\delta} , we obtain \prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}}z_{0,\delta}(x_{e_{0}}-r_{\delta})=\prod_{\delta\in\Delta}z_{0,\delta}(x_{e_{0}}-r_{\delta})\cdot z_{0,-\delta}(x_{e_{0}}-r_{-\delta})=\prod_{\delta\in\Delta}(x_{e_{0}}-r_{\delta})^{2}, which settles ( 21 ). So, the degree of h_{n} in x_{e_{0}} is 2^{n-1} , with leading coefficient 2^{2^{n-1}} . ∎ Proposition 3.6 has the following implication for the cycle polynomial \Gamma_{n} (Definition 3.2 ). Corollary 3.7 . Consider two distinct edges e_{0},e_{1}\in E_{n} . Let r_{\delta} be as in ( 20 ). When viewed as a univariate polynomial in x_{e_{0}} , \Gamma_{n} is a monic polynomial of degree 2^{n-2} , and it reads \displaystyle\Gamma_{n}=\prod_{\delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}}:\delta_{e_{1}}=1}(x_{e_{0}}-r_{\delta}). (22) Example 3.8 . Let n=3 . Let us order the edges in E_{3}=E(C_{3}) as \{1,2\},\{2,3\},\{1,3\} and set e_{0}=\{1,2\} , e_{1}=\{2,3\} . Equation ( 22 ) in this example reads \Gamma_{3}=(x_{12}-r_{++})(x_{12}-r_{-+})=x_{12}^{2}-x_{12}(r_{++}+r_{-+})+r_{++}r_{-+}. One can easily verify that r_{++}+r_{-+}={1\over 2}(z_{++}+z_{--}+z_{-+}+z_{+-})=2x_{13}x_{23} and that r_{++}r_{-+}={1\over 4}(z_{++}+z_{--})(z_{-+}+z_{+-})=x_{13}^{2}+x_{23}^{2}-1 . Hence we get, as mentioned Example 3.3 , \displaystyle\Gamma_{3}=x_{12}^{2}-2x_{12}x_{13}x_{23}+x_{13}^{2}+x_{23}^{2}-1. As an application of Corollary 3.7 , the Lissajous variety {\mathcal{L}}_{n}=V(\Gamma_{n}) does not contain any affine subspace obtained by fixing a strict subset of coordinates. This will be useful in Section 4.4 . Lemma 3.9 . Consider a strict subset J\subsetneq[n] and z=(z_{j})_{j\in J}\in\mathbb{C}^{J} . Define the (n-|J|) -variate polynomial f\in\mathbb{C}[x_{i}:i\in[n]\setminus J] , obtained by setting x_{j}=z_{j} for j\in J , in the cycle polynomial \Gamma_{n}(x) . Then, the polynomial f is not identically zero. Proof. This follows from Corollary 3.7 , which states that \Gamma_{n} is monic when viewed as a univariate polynomial in any of its variables x_{i} . In particular, we may pick i\in[n]\setminus J .∎ Next, we compute the degree of \Gamma_{n} as a bivariate polynomial in two selected variables, since we will need this result later in Section 3.3 . Proposition 3.10 . Viewed as a bivariate polynomial in any two distinct edge variables x_{e_{0}},x_{e_{1}} , the cycle polynomial \Gamma_{n} has degree 2^{n-2} . Proof. By Lemma 3.4 , it suffices to show that the degree of h_{n} as a bivariate polynomial in x_{e_{0}},x_{e_{1}} is equal to 2^{n-1} . The proof is analogous to that of Proposition 3.6 , only a bit more technical. Set F=E_{n}\setminus\{e_{0},e_{1}\} and assume that e_{0},e_{1} come first and second in the ordering of E_{n} used in the subscript of z_{\epsilon} . We start from the definition ( 19 ) for h_{n} , which we now rewrite as \displaystyle h_{n} \displaystyle=\prod_{\delta\in\{\pm 1\}^{F}}\prod_{\epsilon_{0},\epsilon_{1}\in\{\pm 1\}}(z_{\epsilon_{0},\epsilon_{1},\delta}-1)=\prod_{\delta\in\{\pm 1\}^{F}}\prod_{\epsilon_{0},\epsilon_{1}\in\{\pm 1\}}(z_{\epsilon_{0},\epsilon_{1},\mathbf{0}}z_{0,0,\delta}-1) \displaystyle=\prod_{\delta\in\{\pm 1\}^{F}}(z_{++\mathbf{0}}z_{0,0,\delta}-1)(z_{+-\mathbf{0}}z_{0,0,\delta}-1)(z_{-+\mathbf{0}}z_{0,0,\delta}-1)(z_{--\mathbf{0}}z_{0,0,\delta}-1) \displaystyle=\prod_{\delta\in\{\pm 1\}^{F}}[(z_{0,0,\delta})^{4}\sigma_{4}-(z_{0,0,\delta})^{3}\sigma_{3}+(z_{0,0,\delta})^{2}\sigma_{2}-z_{0,0,\delta}\sigma_{1}+1], where \sigma_{k} is the sum of the products of k factors among z_{++\mathbf{0}},z_{+-\mathbf{0}},z_{-+\mathbf{0}},z_{--\mathbf{0}} for k=1,2,3,4 . We have \sigma_{4}=z_{++\mathbf{0}}z_{+-\mathbf{0}}z_{-+\mathbf{0}}z_{--\mathbf{0}}=1 , \sigma_{3}=\sigma_{1}=z_{++\mathbf{0}}+z_{+-\mathbf{0}}+z_{-+\mathbf{0}}+z_{--\mathbf{0}}=4x_{e_{0}}x_{e_{1}} , and \sigma_{2}=4x_{e_{0}}^{2}+4x_{e_{1}}^{2}-2 . Hence, for any \delta , the inner summation has degree 2 in x_{e_{0}},x_{e_{1}} , and thus h_{n} has degree 2\cdot 2^{n-2}=2^{n-1} in x_{e_{0}},x_{e_{1}} , as desired. ∎ We will also need the following property of the roots r_{\delta} in ( 20 ). Lemma 3.11 . For \delta\in\{\pm 1\}^{E_{n}\setminus\{e_{0}\}} and \epsilon_{0}\in\{\pm 1\} , there exists \eta_{\delta}\in\{\pm 1\} such that r_{\delta}+\epsilon_{0}\sqrt{r_{\delta}^{2}-1}=z_{0,\epsilon_{0}\cdot\eta_{\delta}\cdot\delta}. Proof. As r_{\delta}={1\over 2}(z_{0,\delta}+z_{0,-\delta}) , we get r_{\delta}^{2}-1={1\over 4}(z_{0,\delta}-z_{0,-\delta})^{2} . This uses z_{0,\delta}z_{0,-\delta}=1 . Hence, for some \eta_{\delta}\in\{\pm 1\} , \sqrt{r_{\delta}^{2}-1}=\eta_{\delta}{1\over 2}(z_{0,\delta}-z_{0,-\delta}) . Thus, r_{\delta}+\epsilon_{0}\sqrt{r_{\delta}^{2}-1}={1\over 2}z_{0,\delta}(1+\epsilon_{0}\eta_{\delta})+{1\over 2}z_{0,-\delta}(1-\epsilon_{0}\eta_{\delta})=z_{0,\epsilon_{0}\cdot\eta_{\delta}\cdot\delta}, as desired. ∎ 3.2 Cycle polynomials and resultants Here, we show yet another (recursive) representation for the cycle polynomial \Gamma_{n} , as the resultant of two ‘smaller’ cycle polynomials \Gamma_{p} and \Gamma_{q} , where n=p+q-2 and p,q\geq 3 . Figure 2 : The cycle C_{n} is obtained by deleting the common edge e_{0} from C_{p} and C_{q}^{\prime} . The construction goes as follows. Consider the n -th cycle C_{n}=(1,\ldots,n) for n\geq 4 . For 3\leq p\leq n-1 , consider the graph C_{n}+e_{0} obtained by adding the edge e_{0}=\{1,p\} to C_{n} , so that e_{0} is a chord of C_{n} in this graph. Then, consider the cycles C_{p}=(1,2,\ldots,p) and C^{\prime}_{q}=(p,p+1,\ldots,n,1) with respective lengths p and q=n+2-p . The graphical picture to keep in mind is shown in Figure 2 : by adding a chord e_{0} to the cycle C_{n} , one gets two smaller cycles C_{p} and C_{q}^{\prime} that share this chord as a unique common edge. In Figure 3 below, we also see an illustration for C_{4} , where C_{4}+e_{0} is the union of two 3-cycles, and for C_{5} , where C_{5}+e_{0} is the union of a 3-cycle and a 4-cycle. For convenience, set F_{p}=\{\{1,2\},\ldots,\{p-1,p\}\} , so that the edge set of C_{p} is E(C_{p})=F_{p}\cup\{e_{0}\} , and set F^{\prime}_{q}=\{\{p,p+1\},\ldots,\{n-1,n\},\{n,1\}\} , so that the edge set of C_{q}^{\prime} is E(C_{q}^{\prime})=F^{\prime}_{q}\cup\{e_{0}\} . Then, the cycle polynomials \Gamma_{n}=\Gamma_{C_{n}},\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}} belong to \mathbb{R}[x_{e}:e\in E_{n}\cup\{e_{0}\}] , depending on the variables \{x_{e}:e\in E_{n}\} , \{x_{e}:e\in F_{p}\cup\{e_{0}\}\} , and \{x_{e}:e\in F_{q}^{\prime}\cup\{e_{o}\}\} , respectively. We similarly define the polynomials h_{n}=h_{C_{n}} , h_{C_{p}} and h_{C^{\prime}_{q}} . The construction of the cycle polynomial \Gamma_{n} from \Gamma_{C_{p}} and \Gamma_{C^{\prime}_{q}} mimics the geometric observation that the elliptope {\mathcal{E}}(C_{n}) can be obtained from the elliptopes {\mathcal{E}}(C_{p}) and {\mathcal{E}}(C^{\prime}_{q}) by projecting out the variable corresponding to the chord e_{0} . On the algebraic side, we will show that \Gamma_{n} is obtained by eliminating x_{e_{0}} from the equations \Gamma_{C_{p}}=\Gamma_{C_{q}^{\prime}}=0 . We make this precise using resultants . The theory we need and more can be found in [ 9 , Chapter 3, §1] . We introduce our notation and recall some facts. For two univariate polynomials f=a_{0}+a_{1}\,y+\cdots+a_{d_{f}}\,y^{d_{f}} and g=b_{0}+b_{1}\,y+\cdots+b_{d_{g}}\,y^{d_{g}} in K[y] , with coefficients a_{k},b_{\ell} in a field K and respective degrees d_{f} and d_{g} , their Sylvester matrix {\rm Syl}_{y}(f,g) is the (d_{f}+d_{g})\times(d_{f}+d_{g}) matrix \mathrm{Syl}_{y}(f,g)=\begin{pmatrix}S_{f}\\ S_{g}\end{pmatrix},\quad\text{where}\quad S_{f}\,=\,\begin{pmatrix}a_{0}&a_{1}&\cdots&a_{d_{f}}&&\\ &a_{0}&a_{1}&\cdots&a_{d_{f}}&\\ &&\ddots&&&\ddots\\ &&&a_{0}&a_{1}&\cdots&a_{d_{f}}\end{pmatrix}\,\in\,K^{d_{g}\times(d_{f}+d_{g})} and S_{g} is constructed analogously. The resultant {\rm Res}_{y}(f,g) is defined as the determinant of the Sylvester matrix: \displaystyle{\rm Res}_{y}(f,g)=\det{\rm Syl}_{y}(f,g). (23) In particular, {\rm Res}_{y}(f,g) is a polynomial in the coefficients a_{i},b_{j} with integer coefficients. An alternative formula for the resultant, called Poisson’s formula , will be useful. Let r_{1},\ldots,r_{d_{f}}\in\bar{K} be the roots of f\in K[y] (listed with the appropriate multiplicity) in the algebraic closure \bar{K} of K . The resultant {\rm Res}_{y}(f,g) in ( 23 ) can be equivalently expressed as {\rm Res}_{y}(f,g)\,=\,a_{d_{f}}^{d_{g}}\,\prod_{i=1}^{d_{f}}g(r_{i}). (24) This highlights a crucial property of the resultant: it vanishes precisely when f and g have a common root. Using ( 23 ) and ( 24 ), one can easily check the following properties of the resultant: for f_{1},f_{2},f,g\in K[y] and \lambda\in K , \displaystyle{\rm Res}_{y}(f_{1}f_{2},g)={\rm Res}_{y}(f_{1},g){\rm Res}_{y}(f_{2},g), (25) \displaystyle{\rm Res}_{y}(g,f)=(-1)^{d_{f}d_{g}}{\rm Res}_{y}(f,g), (26) \displaystyle{\rm Res}_{y}(\lambda\,f,g)=\lambda^{d_{g}}{\rm Res}_{y}(f,g). (27) Here, we will use the resultant for (f,g)=(\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}}) and (h_{C_{p}},h_{C_{q}^{\prime}}) , y=x_{e_{0}} , and K is the field of rational functions in the variables (x_{e}\,:\,e\in E_{n}) . Our main result is: Theorem 3.12 . {\rm Res}_{x_{e_{0}}}(\Gamma_{C_{p}},\Gamma_{C_{q}^{\prime}})=\Gamma_{n} for any n=p+q-2 with p,q\geq 3 . Our strategy to prove Theorem 3.12 is to first compute the resultant of the polynomials h_{C_{p}} and h_{C_{q}^{\prime}} and then to apply properties ( 25 )-( 27 ) to obtain the resultant of \Gamma_{C_{p}} and \Gamma_{C_{q}^{\prime}} . First, we show that the resultant of h_{C_{p}} and h_{C_{q}^{\prime}} is a scaling of h_{n}^{2} . Proposition 3.13 . With the above notation, consider the polynomials h_{n}\in\mathbb{C}[x_{e}:e\in E_{n}] , h_{C_{p}}\in\mathbb{C}[x_{e}:e\in F_{p}\cup\{e_{0}\}] , and h_{C^{\prime}_{q}}\in\mathbb{C}[x_{e}:e\in F_{q}^{\prime}\cup\{e_{0}\}] , where E_{n}=F_{p}\cup F^{\prime}_{q} . We have the identity: {\rm Res}_{x_{e_{0}}}(h_{C_{p}},h_{C^{\prime}_{q}})=(2^{2^{n-1}}\,h_{n})^{2} . Proof. We compute the resultant using relation ( 24 ) applied to f=h_{C_{p}} and g=h_{C^{\prime}_{q}} , viewed as univariate polynomials in x_{e_{0}} . By Proposition 3.6 , the roots of h_{C_{p}} are given by r_{\delta}={1\over 2}(z_{0,\delta,\mathbf{0}}+z_{0,-\delta,\mathbf{0}}) for \delta\in\{-1,1\}^{F_{p}}. Here, the subscript of z uses the ordering of \{e_{0}\}\cup E_{n} as e_{0},F_{p},F_{q}^{\prime} . By Poisson’s formula ( 24 ), the resultant is given by the following expression: {\rm Res}_{x_{e_{0}}}(h_{C_{p}},h_{C_{q}^{\prime}})=(2^{2^{p-1}})^{2^{q-1}}\,\prod_{\delta\in\{-1,1\}^{F_{p}}}h_{C^{\prime}_{q}}(r_{\delta})=2^{2^{n}}\prod_{\delta\in\{-1,1\}^{F_{p}}}h_{C^{\prime}_{q}}(r_{\delta}), where we used p+q-2=n . Using the definition ( 19 ) for the polynomial h_{C_{q}^{\prime}} , we get \displaystyle h_{C_{q}^{\prime}}=\prod_{\delta^{\prime}\in\{\pm 1\}^{F_{q}^{\prime}}}\prod_{\epsilon_{0}\in\{\pm 1\}}(z_{\epsilon_{0},\mathbf{0},\delta^{\prime}}-1)=\prod_{\delta^{\prime}\in\{\pm 1\}^{F_{q}^{\prime}}}\prod_{\epsilon_{0}\in\{\pm 1\}}(z_{\epsilon_{0},\mathbf{0},\mathbf{0}}\cdot z_{0,\mathbf{0},\delta^{\prime}}-1). By Lemma 3.11 , evaluating z_{\epsilon_{0},\mathbf{0},\mathbf{0}} at x_{e_{0}}=r_{\delta} gives: (z_{\epsilon_{0},\mathbf{0},\mathbf{0}})_{|x_{e_{0}}=r_{\delta}}\,=\,r_{\delta}+\epsilon_{0}\sqrt{r_{\delta}^{2}-1}\,=\,z_{0,\epsilon_{0}\cdot\eta_{\delta}\cdot\delta,\mathbf{0}}\ \text{ for some }\eta_{\delta}\in\{\pm 1\}. Then, viewing h_{C_{q}^{\prime}} as a polynomial in x_{e_{0}} and evaluating it at x_{e_{0}}=r_{\delta} , we obtain \displaystyle\prod_{\delta\in\{-1,1\}^{F_{p}}}h_{C^{\prime}_{q}}(r_{\delta}) \displaystyle=\prod_{\delta\in\{-1,1\}^{F_{p}}}\prod_{\delta^{\prime}\in\{\pm 1\}^{F_{q}^{\prime}}}\prod_{\epsilon_{0}\in\{\pm 1\}}(z_{0,\epsilon_{0}\cdot\eta_{\delta}\cdot\delta,\mathbf{0}}\cdot z_{0,\mathbf{0},\delta^{\prime}}-1) \displaystyle=\prod_{\delta\in\{-1,1\}^{F_{p}}}\prod_{\delta^{\prime}\in\{\pm 1\}^{F_{q}^{\prime}}}(z_{0,\delta,\delta^{\prime}}-1)^{2} \displaystyle=\prod_{\epsilon\in\{\pm 1\}^{E_{n}}}(z_{0,\epsilon}-1)^{2} \displaystyle=h_{n}^{2}. Here, we use the identity \prod_{\delta}\prod_{\epsilon_{0}}(z_{0,\epsilon_{0}\cdot\eta_{\delta}\cdot\delta,\mathbf{0}}\cdot z_{0,\mathbf{0},\delta^{\prime}}-1)=\prod_{\delta}(z_{0,\delta,\mathbf{0}}\cdot z_{0,\mathbf{0},\delta^{\prime}}-1)^{2} for the second equality, combined with z_{0,\delta,\mathbf{0}}\cdot z_{0,\mathbf{0},\delta^{\prime}}=z_{0,\delta,\delta^{\prime}} . The last equality follows using relation ( 16 ) and the fact that E_{n}=F_{p}\cup F_{q}^{\prime} . So, we have proved that {\rm Res}_{x_{e_{0}}}(h_{C_{p}},h_{C_{q}^{\prime}})=2^{2^{n}}h_{n}^{2} , as desired. ∎ Proof of Theorem 3.12 . Using Definition 3.2 and ( 25 )-( 27 ), we have the chain of equalities: {\rm Res}(h_{C_{p}},h_{C_{q}^{\prime}})\,=\,{\rm Res}(2^{2^{p-1}}\Gamma_{C_{p}}^{2},2^{2^{q-1}}\Gamma_{C_{q}^{\prime}}^{2})\,=\,2^{2^{n+1}}{\rm Res}(\Gamma_{C_{p}}^{2},\Gamma_{C_{q}^{\prime}}^{2})\,=\,2^{2^{n+1}}{\rm Res}(\Gamma_{C_{p}},\Gamma_{C_{q}^{\prime}})^{4}. where the resultant is always taken with respect to the common edge variable x_{e_{0}} . By Proposition 3.13 (combined with Definition 3.2 ), {\rm Res}(h_{C_{p}},h_{C_{q}^{\prime}})=2^{2^{n}}h_{n}^{2}=2^{2^{n+1}}\Gamma_{n}^{4} . This implies {\rm Res}(\Gamma_{C_{p}},\Gamma_{C_{q}^{\prime}})^{4}=\Gamma_{n}^{4} , and thus {\rm Res}(\Gamma_{C_{p}},\Gamma_{C_{q}^{\prime}})=\alpha\Gamma_{n} for some \alpha=\pm 1 . Now, we argue that \alpha=1 , i.e., \Gamma_{n}=R_{p,q} , setting R_{p,q}={\rm Res}(\Gamma_{C_{p}},\Gamma_{C_{q}^{\prime}}) for compact notation. Let us write \Gamma_{C_{p}}=a_{0}+a_{1}x_{e_{0}}+\ldots+a_{d_{p}}x_{e_{0}}^{d_{p}} and \Gamma_{C^{\prime}_{q}}=b_{0}+b_{1}+\ldots+b_{d_{q}}x_{e_{0}}^{d_{q}} , where d_{p}=2^{p-2} , d_{q}=2^{q-2} , the a_{i} ’s involve the variables x_{e} for e\in F_{p} , and the b_{i} ’s involve the variables x_{e} for e\in F^{\prime}_{q} . Consider a variable x_{e_{1}} with e_{1}\in F_{p} , so that x_{e_{1}} occurs only in \Gamma_{C_{p}} and not in \Gamma_{C^{\prime}_{q}} . By relation ( 22 ), \Gamma_{n} has leading coefficient 1 when viewed as univariate polynomial in any given variable, and the same holds for \Gamma_{C_{p}} and \Gamma_{C^{\prime}_{q}} . Considering the variable x_{e_{0}} , this implies a_{d_{p}}=b_{d_{q}}=1 . Moreover, by considering the variable x_{e_{1}} , this implies that the leading term in x_{e_{1}} within \Gamma_{C_{p}} occurs in the coefficient a_{0} (the only coefficient without a factor x_{e_{0}} ). We now compute the leading coefficient of the resultant R_{p,q} , viewed as a polynomial in x_{e_{1}} . For this we use the formula for R_{p,q} given by the determinant of the Sylvester matrix \text{\rm Syl}_{x_{e_{0}}}(\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}}) as in ( 23 ). The term in the expansion of this determinant which has the highest degree in x_{e_{1}} is obtained by picking all d_{q} occurrences of a_{0} on the nonzero lower diagonal of the submatrix S_{\Gamma_{C_{p}}} and all d_{p} occurrences of b_{d_{q}} on the nonzero upper diagonal of S_{\Gamma_{C^{\prime}_{q}}} . In other words, x_{e_{1}} appears with highest degree in the term (a_{0})^{d_{p}}\cdot(b_{d_{q}})^{d_{p}}=(a_{0})^{d_{p}} , and thus its leading coefficient is positive. On the other hand, as R_{p,q}=\alpha\Gamma_{n} , the leading coefficient in x_{e_{1}} is equal to \alpha . This implies \alpha=1 , as desired. ∎ Example 3.14 . For p=q=3 , n=4 , the graph C_{4}+e_{0} is obtained by gluing two 3 -cycles along the edge e_{0}=\{1,3\} , see Figure 3 (left). 1 2 3 4 4 3 2 1 5 Figure 3 : With e_{0}=\{1,3\} , the graph C_{4}+e_{0} is the union of C_{3}=(1,2,3) and C_{3}^{\prime}=(3,4,1) , while C_{5}+e_{0} is the union of C_{3}=(1,2,3) and C_{4}^{\prime}=(3,4,5,1) . Theorem 3.12 gives the following way to obtain \Gamma_{4} as a 4\times 4 Sylvester determinant, using \Gamma_{3} (which was computed in Example 3.8 ): \Gamma_{4}\,=\,\det\begin{pmatrix}-1+x_{12}^{2}+x_{23}^{2}&-2x_{12}x_{23}&1&0\\ 0&-1+x_{12}^{2}+x_{23}^{2}&-2x_{12}x_{23}&1\\ -1+x_{14}^{2}+x_{34}^{2}&-2x_{14}x_{34}&1&0\\ 0&-1+x_{14}^{2}+x_{34}^{2}&-2x_{14}x_{34}&1\end{pmatrix}. Similarly, for p=3 , q=4 , n=5 , C_{5}+e_{0} is obtained by gluing a 3-cycle and a 4-cycle along the edge e_{0}=\{1,3\} , as shown in Figure 3 (right). By Theorem 3.12 , the polynomial \Gamma_{5} can be obtained from \Gamma_{3} and \Gamma_{4} as a 6\times 6 Sylvester determinant. Remark 3.15 . Observe that the result in Theorem 3.12 offers a new proof of the fact that \Gamma_{n} is a multivariate polynomial, as we already established in Theorem 3.1 . Indeed, its proof relies only on the fact that \Gamma_{C_{p}} and \Gamma_{C_{q}^{\prime}} are univariate polynomials in the variable x_{e_{0}} . Then, using the definition ( 23 ) of the resultant via the Sylvester matrix, the identity \Gamma_{n}=\text{\rm Res}_{x_{e_{0}}}(\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}}) shows by induction that \Gamma_{n} is a multivariate polynomial. The base case is for \Gamma_{3} , which is indeed a multivariate polynomial as we saw in Example 3.8 . In addition, the same argument shows that \Gamma_{n} is a multivariate polynomial with integer coefficients for all n\geq 3 . Remark 3.16 . Using the definition ( 23 ) of the resultant via the Sylvester matrix, the identity \Gamma_{n}=\text{\rm Res}_{x_{e_{0}}}(\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}}) shows by induction that \Gamma_{n} is a multivariate polynomial with integer coefficients . The base case is for \Gamma_{3} , which satisfies this property by Example 3.8 . Moreover, one can use \Gamma_{n}=\text{\rm Res}_{x_{e_{0}}}(\Gamma_{C_{p}},\Gamma_{C^{\prime}_{q}}) as an alternative definition of \Gamma_{n} , avoiding the use of square roots as is now done in Definition 3.2 . Via Theorem 3.12 , Sylvester’s formula gives several determinantal expressions for \Gamma_{n} , one for each pair (p,q) such that p+q=n+2 and p,q\geq 3 , in which case \Gamma_{n} is the determinant of a Sylvester matrix of size 2^{p-2}+2^{q-2} . One can check that the smallest size is equal to \sqrt{2^{n}} , obtained with p=q={n\over 2}+1 if n is even, and equal to {3\over 2}\sqrt{2^{n-1}} , obtained with p={n+1\over 2} , q={n+3\over 2} if n is odd. In comparison, the determinantal represention of \Gamma_{n} obtained from the multiplication matrix M_{g_{n}} in ( 16 ), involves a matrix of size 2^{n} , and its determinant is h_{n}=2^{2^{n-1}}\Gamma_{n}^{2} . On the other hand, that 2^{n}\times 2^{n} -matrix has significantly simpler entries. The preferred representation may depend on the precise application. Compact representations and efficient evaluation of \Gamma_{n} form an interesting topic for further research. 3.3 Homogeneous cycle polynomials Recall that the elliptope {\cal E}(G) consists of partially filled correlation matrices which allow a positive semidefinite completion. Replacing correlation matrices by semidefinite matrices in this definition gives the cone {{\mathscr{C}}}(G) . We think of a partially filled matrix as a point s\in\mathbb{R}^{E\cup V}=\mathbb{R}^{E}\times\mathbb{R}^{V} , where the coordinates on the first factor are s_{ij} , indexed by the edges \{i,j\}\in E , and the coordinates on the second factor are s_{kk} for k\in V . Define \displaystyle{\mathscr{C}}(G)\,=\,\{s\in\mathbb{R}^{E\cup V}:\exists X\in{\cal S}^{n}_{+}\text{ such that }X_{ij}=s_{ij}\text{ for }\{i,j\}\in E,\ X_{kk}=s_{kk}\text{ for }k\in V\}. (28) A point s\in\mathbb{R}^{E\cup V} lies in {\mathscr{C}}(G) if and only if the point x\in\mathbb{R}^{E} with entries x_{ij}\,=\,\frac{s_{ij}}{\sqrt{s_{ii}s_{jj}}}\ \text{ for }\{i,j\}\in E (29) lies in {\cal E}(G) (setting x_{ij}=0 if s_{ii}s_{jj}=0 ). For this reason, the authors of [ 27 ] are interested in a homogeneous version of the cycle polynomial expressed in the variables s_{ij},s_{kk} . In this section, we prove Conjecture 4.9 in [ 27 ] , which pertains to the degree of that homogeneous polynomial. To define it, we substitute ( 29 ) in \Gamma_{n} . The resulting function of the s -variables is denoted by R_{n} . Proposition 3.17 . The function R_{n} , obtained by substituting x_{ij}=\tfrac{s_{ij}}{\sqrt{s_{ii}s_{jj}}} in the cycle polynomial \Gamma_{n} , is a rational function in the s -variables. Its denominator is s_{11}^{2^{n-3}}\cdots s_{nn}^{2^{n-3}} . Proof. Notice that R_{n} is a fraction whose numerator is a polynomial in s , and whose denominator is a product of powers of s_{11},\ldots,s_{nn} . A priori, these are fractional powers. We must show that each of the variables s_{11},\ldots,s_{nn} appears in the denominator with an integer exponent. Fix i\in[n] and let x_{i-1,i} and x_{i,i+1} be the edge variables of the two edges containing i (taking indices modulo n ). We set E^{\prime}=\{\{i-1,i\},\{i,i+1\}\} and we expand \Gamma_{n} as in relation ( 17 ): \Gamma_{n}\,=\,\sum_{(\alpha,\beta)\in\mathbb{N}^{2}}c_{\alpha,\beta}(x_{E\setminus E^{\prime}})\,x_{i-1,i}^{\alpha}\,x_{i,i+1}^{\beta}. The substitution x_{ij}=\frac{s_{ij}}{\sqrt{s_{ii}s_{jj}}} leads to the expression \sum_{(\alpha,\beta)\in\mathbb{N}^{2}}\tilde{c}_{\alpha,\beta}\,\frac{s_{i-1,i}^{\alpha}\,s_{i,i+1}^{\beta}}{(s_{i-1,i-1})^{\alpha\over 2}(s_{i+1,i+1})^{\beta\over 2}(s_{ii})^{\alpha+\beta\over 2}} where \tilde{c}_{\alpha,\beta} is obtained from c_{\alpha,\beta} after the substitution. Note that \tilde{c}_{\alpha,\beta} does not involve the variable s_{ii} . Moreover, by Corollary 3.5 , each \alpha+\beta for which \tilde{c}_{\alpha,\beta}\neq 0 is an even integer. Therefore, s_{ii} appears with an integer exponent in each term for all i . By Proposition 3.10 , \Gamma_{n} has degree 2^{n-2} when viewed as a bivariate polynomial in x_{i-1,i} and x_{i,i+1} . Hence, the exponent of s_{ii} in the common denominator is 2^{n-3} . ∎ Example 3.18 . For n=4 , the rational function R_{4} is given by \begin{matrix}s_{12}^{2}\,s_{23}^{2}\,s_{34}^{2}\,s_{14}^{2}\cdot R_{4}\,=\,s_{14}^{4}s_{22}^{2}s_{33}^{2}-4s_{12}s_{14}^{3}s_{22}s_{23}s_{33}s_{34}+4s_{11}s_{14}^{2}s_{22}s_{23}^{2}s_{34}^{2}+4s_{12}^{2}s_{14}^{2}s_{22}s_{33}s_{34}^{2}\\ -2s_{11}s_{14}^{2}s_{22}^{2}s_{33}s_{34}^{2}-4s_{11}s_{12}s_{14}s_{22}s_{23}s_{34}^{3}+s_{11}^{2}s_{22}^{2}s_{34}^{4}+4s_{12}^{2}s_{14}^{2}s_{23}^{2}s_{33}s_{44}\\ -2s_{11}s_{14}^{2}s_{22}s_{23}^{2}s_{33}s_{44}-2s_{12}^{2}s_{14}^{2}s_{22}s_{33}^{2}s_{44}-4s_{11}s_{12}s_{14}s_{23}^{3}s_{34}s_{44}-4s_{12}^{3}s_{14}s_{23}s_{33}s_{34}s_{44}\\ +8s_{11}s_{12}s_{14}s_{22}s_{23}s_{33}s_{34}s_{44}+4s_{11}s_{12}^{2}s_{23}^{2}s_{34}^{2}s_{44}-2s_{11}^{2}s_{22}s_{23}^{2}s_{34}^{2}s_{44}-2s_{11}s_{12}^{2}s_{22}s_{33}s_{34}^{2}s_{44}\\ +s_{11}^{2}s_{23}^{4}s_{44}^{2}-2s_{11}s_{12}^{2}s_{23}^{2}s_{33}s_{44}^{2}+s_{12}^{4}s_{33}^{2}s_{44}^{2}.\end{matrix} Each term on the righthand side corresponds to a term of \Gamma_{4} , see Example 3.3 . Definition 3.19 . The homogeneous cycle polynomial is \Gamma_{n}^{h}=s_{11}^{2^{n-3}}\cdots s_{nn}^{2^{n-3}}\cdot R_{n} . We note that our notation differs slightly from [ 27 ] , where the cycle polynomial \Gamma_{n} and the homogeneous cycle polynomial \Gamma_{n}^{h} are denoted by \Gamma_{n}^{\prime} and \Gamma_{n} respectively. The following theorem settles Conjecture 4.9 in [ 27 ] . Theorem 3.20 . The polynomial \Gamma_{n}^{h} is homogeneous and its degree is n\cdot 2^{n-3} . Proof. By construction, the rational function R_{n} is homogeneous of degree zero. Multiplying with the denominator s_{11}^{2^{n-3}}\cdots s_{nn}^{2^{n-3}} , which is homogeneous of degree n\cdot 2^{n-3} , gives a homogeneous polynomial of degree n\cdot 2^{n-3} . ∎ In fact, the homogeneous cycle polynomial is homogeneous with respect to a multigrading by the group \mathbb{Z}^{n} . We define the multidegree of s_{ij} as \deg_{n}(s_{ij})={\bf e}_{i}+{\bf e}_{j} . Here, {\bf e}_{j} is the j -th standard basis vector of \mathbb{Z}^{n} . Note that R_{n} is homogeneous of multidegree {\bf 0}\in\mathbb{Z}^{n} . Theorem 3.21 . The homogeneous cycle polynomial \Gamma^{h}_{n} is homogeneous with respect to the multigrading \deg_{n} . We have \deg_{n}(\Gamma_{n}^{h})=(2^{n-2},\ldots,2^{n-2}) . Theorem 3.21 can be equivalently expressed as follows. For any \lambda\in(\mathbb{C}^{*})^{n} , we have \Gamma_{n}^{h}(\lambda_{1}\lambda_{2}\,s_{12},\ldots,\lambda_{1}\lambda_{n}\,s_{1n},\lambda_{1}^{2}\,s_{11},\ldots,\lambda_{n}^{2}s_{nn})\,=\,\lambda_{1}^{2^{n-2}}\cdots\lambda_{n}^{2^{n-2}}\cdot\Gamma_{n}^{h}(s_{12},\ldots,s_{1n},s_{11},\ldots,s_{nn}). 4 The algebraic boundary of the elliptope of a graph Recall that the Zariski closure \overline{S}^{z} of a set S\subseteq\mathbb{R}^{n} is the smallest (with respect to inclusion) affine variety in \mathbb{C}^{n} that contains S , and the algebraic boundary \partial_{a}S=\overline{\partial S}^{z}\subseteq\mathbb{C}^{n} is the Zariski closure of its euclidean boundary \partial S . In this section we investigate the algebraic boundary of the elliptope {\mathcal{E}}(G) and of its outer approximation \widetilde{\mathcal{E}}(G) for a graph G . Recall the definition of the semialgebraic sets S(G) and \widetilde{\mathcal{E}}(G)=S(G)\cap\cos(\pi\text{\rm MET}(G)) in Equations ( 2 ) and ( 6 ). Our main result is that the algebraic boundary of \widetilde{\mathcal{E}}(G) is given by the cycle polynomials \Gamma_{C} for the chordless cycles C of G and the determinantal polynomials \det(x[K]) for the maximal cliques K (see Theorem 4.5 ). This directly provides the algebraic boundary of the elliptope {\mathcal{E}}(G) when G is cycle completable, in which case {\mathcal{E}}(G)=\widetilde{\mathcal{E}}(G) . We also characterize the graphs whose elliptope {\mathcal{E}}(G) is a spectrahedron (Corollary 4.10 ). In addition, we extend the results to the cone {\mathscr{C}}(G) from ( 28 ) (Corollary 4.11 ) and to the graphs obtained by adding an apex node to a cycle completable graph (Proposition 4.14 ). 4.1 Some geometric properties of graph elliptopes We begin with some preliminary geometric results on the elliptope of a graph. Proposition 4.1 . Let G=(V=[n],E) be a graph. We have {\rm int}({\cal E}(G))=\pi_{E}({\rm int}({\cal E}_{n})) and \partial{\cal E}(G)\subseteq\pi_{E}(\partial{\cal E}_{n}) . Proof. Let x_{E}\in\pi_{E}({\rm int}({\cal E}_{n})) , i.e., there exists X\in{\rm int}({\cal E}_{n}) such that x_{E}=\pi_{E}(X) . Since X\in{\rm int}({\cal E}_{n}) , there exists a ball B_{\epsilon}(X)\subset{\cal E}_{n} for some small \epsilon>0 . This means that small perturbations of the entries of X result in a positive definite matrix. This clearly holds if we restrict only to the variables labeled with E . This implies that there exists a small ball around x_{E} consisting of points x\in\mathbb{R}^{E} that can be completed to positive semidefinite matrices, thus showing x_{E}\in{\rm int}({\cal E}(G)) . This shows the inclusion \pi_{E}({\rm int}({\cal E}_{n}))\subseteq{\rm int}({\cal E}(G)) . Then, the following chain of inclusions holds: \partial{\cal E}(G)={\cal E}(G)\setminus{\rm int}({\cal E}(G))\subseteq\pi_{E}({\cal E}_{n})\setminus\pi_{E}({\rm int}({\cal E}_{n}))\subseteq\pi_{E}({\cal E}_{n}\setminus{\rm int}({\cal E}_{n}))=\pi_{E}(\partial{\cal E}_{n}). We now show the reverse inclusion {\rm int}({\cal E}(G))\subseteq\pi_{E}({\rm int}({\cal E}_{n})) . Equivalently, we show that if x_{E}\in{\cal E}(G) with x_{E}\not\in\pi_{E}({\rm int}({\cal E}_{n})) , then x_{E}\not\in\text{ int}({\mathcal{E}}(G)) . By assumption, the system \left\{\begin{aligned} &X\succeq 0,\\ &\langle E_{ii},X\rangle=1,\text{ for }i\in V,\\ &\langle E_{ij},X\rangle=x_{ij},\text{ for }\{i,j\}\in E,\end{aligned}\right. admits a solution X , but it does not admit a positive definite solution. Here, the matrices E_{ij}=(e_{i}e_{j}^{T}+e_{j}e_{i}^{T})/2 are the elementary matrices for 1\leq i\leq j\leq n . By the Theorem of Alternatives for semidefinite programming (see, e.g., [ 18 , Lemma 3.6] ), there exist scalars y_{i} ( i\in V ) and y_{ij} ( \{i,j\}\in E ) satisfying the system \left\{\begin{aligned} &\Omega=\sum_{i\in V}y_{i}E_{ii}+\sum_{\{i,j\}\in E}y_{ij}E_{ij}\succeq 0,\ \Omega\neq 0,\\ &\sum_{i\in V}y_{i}+\sum_{\{i,j\}\in E}y_{ij}x_{ij}\leq 0.\end{aligned}\right. (30) Observe that \sum_{i\in V}y_{i}+\sum_{\{i,j\}\in E}y_{ij}z_{ij}\geq 0 holds for any z\in{\cal E}(G) . Indeed, if z\in{\mathcal{E}}(G) , there exists Z\in{\cal E}_{n} such that z=\pi_{E}(Z) . Since Z,\Omega\succeq 0 , we have \langle Z,\Omega\rangle\geq 0 , and expanding the scalar product proves the claim. Moreover, by Equation 30 , we derive that x_{E} satisfies the above inequality at equality, which implies that x_{E}\in\partial{\cal E}(G) , and thus x_{E}\not\in{\rm int}({\cal E}(G) ). So, we have shown equality {\rm int}({\cal E}(G))=\pi_{E}({\rm int}({\cal E}_{n})) . ∎ Proposition 4.2 . For any graph G=(V,E) , the following assertions hold. (i) \text{\rm int}(\cos(\pi\text{\rm MET}(G)))=\cos(\pi\text{\rm int}(\text{\rm MET}(G))) and \partial(\cos(\pi\text{\rm MET}(G)))=\cos(\pi\partial\text{\rm MET}(G)) . (ii) \text{\rm int}(S(G))=\{x\in\mathbb{R}^{E}:x[K]\succ 0\text{ for all }K\in{\mathcal{K}}_{G}\} . (iii) \text{\rm int}(\widetilde{\mathcal{E}}(G))=\text{\rm int}(S(G))\cap\cos(\pi\text{\rm int}(\text{\rm MET}(G))) . Proof. For (i), it suffices to show the claim about the interiors since the claim about the euclidean closures then follows from the fact that the map \cos:[0,\pi]^{n}\rightarrow[-1,1]^{n} is one-to-one; the claim about the interiors follows easily using Lipschitz continuity of the cosine and arccosine maps. The proof of (ii) is easy, and (iii) directly follows from (i),(ii), using the fact that the interior of an intersection equals the intersection of the interiors. ∎ Proposition 4.3 . For a graph G=(V,E) , define the polynomial \displaystyle P_{G}(x)=\prod_{K\in{\mathcal{K}}_{G}}\det x[K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma_{C}(x), (31) where {\mathcal{K}}_{G} is the set of maximal cliques and {\mathcal{C}}_{G} is the set of chordless cycles of length at least 4 in G . We have \partial\widetilde{\mathcal{E}}(G)\subseteq\widetilde{\mathcal{E}}(G)\cap V(P_{G}). Proof. By Proposition 4.2 (iii), \partial\widetilde{\mathcal{E}}(G)=\widetilde{\mathcal{E}}(G)\setminus\text{\rm int}(\widetilde{\mathcal{E}}(G))\subseteq\partial S(G)\cup\partial(\cos(\pi\text{\rm MET}(G))) . Let x=\cos(\pi a)\in\partial\widetilde{\mathcal{E}}(G) with a\in[0,1]^{E} . If x\in\partial S(G) then, by Proposition 4.2 (ii), we have \det x[K]=0 for some K\in{\mathcal{K}}_{G} , and thus P_{G}(x)=0 . If x\in\partial\widetilde{\mathcal{E}}(G)\setminus\partial S(G) , then we have x\in(-1,1)^{E} . Moreover, x\in\partial(\cos(\pi\text{\rm MET}(G)))=\cos(\pi\partial\text{\rm MET}(G)) , and thus a\in\partial\text{\rm MET}(G) with a\in(0,1)^{E} by Proposition 4.2 (i). Hence, there exists C\in{\mathcal{C}}_{G} for which a satisfies a cycle inequality ( 3 ) at equality. From Remark 2.7 , we obtain that \Gamma_{C}(x)=0 , which implies P_{G}(x)=0 . ∎ Remark 4.4 . For G=C_{3} , the polynomial P_{C_{3}} has a single factor corresponding to the (unique) maximal clique K=[3] and equal to the irreducible cubic \Gamma_{3} . The equality \partial{\mathcal{E}}(C_{3})={\mathcal{E}}(C_{3})\cap V(P_{C_{3}}) holds. For the cycle G=C_{n} with n\geq 4 , we have P_{C_{n}}=(1-x_{12}^{2})\cdots(1-x_{n-1,n}^{2})(1-x_{1n}^{2})\cdot\Gamma_{n}. So, P_{C_{n}} has n factors corresponding to the maximal cliques (i.e., the edges of C_{n} ), and one factor \Gamma_{n} corresponding to the unique chordless cycle in {\cal C}_{C_{n}}=\{C_{n}\} . As we now observe, the inclusion \partial{\mathcal{E}}(C_{n})\subsetneq{\mathcal{E}}(C_{n})\cap V(P_{C_{n}}) is strict for n\geq 4 . For this, consider the vector x=\cos(\pi a)\in\mathbb{R}^{n} , with a={n-2\over n}{\mathbf{1}} for n even, and a={n-3\over n}{\mathbf{1}} for n odd. Then, one can check that the point a belongs to the interior of the metric polytope \text{\rm MET}(C_{n}) since it satisfies all cycle inequalities ( 3 ) strictly. Hence, by Proposition 4.2 (i), x\in{\rm int}({\mathcal{E}}(C_{n})) . On the other hand, we have x\in V(P_{C_{n}}) . Indeed, x satisfies \Gamma_{n}(x)=0 , which follows from Remark 2.7 since a\cdot{\mathbf{1}}\in 2\mathbb{Z} . In other words, for the cycle C_{n} of length n\geq 4 , we have \text{\rm int}({\mathcal{E}}(C_{n}))\cap V(\Gamma_{n})\neq\emptyset . The fact that V(\Gamma_{4}) intersects the interior of {\mathcal{E}}(C_{4}) can be seen from the first two plots in the last row of Figure 1 . 4.2 The algebraic boundary of the elliptope for cycle completable graphs In this section we describe the algebraic boundary of the elliptope {\mathcal{E}}(G) when the graph G is cycle completable (Theorem 4.5 ). In fact, we show a stronger result and characterize the algebraic boundary of the larger set \widetilde{\mathcal{E}}(G) from ( 6 ) for any graph G . Recall that {\mathcal{K}}_{G} is the set of maximal cliques of G . To avoid trivialities we assume G has no isolated nodes, so each maximal clique has size at least 2. Hence, {\mathcal{K}}_{G}={\mathcal{K}}_{G,2}\cup{\mathcal{K}}_{G,\geq 3} , where {\mathcal{K}}_{G,2} denotes the set of maximal cliques of size 2 (i.e., the set of edges e\in E that are not contained in a larger clique), and {\mathcal{K}}_{G,\geq 3}=\{K\in{\mathcal{K}}_{G}:|K|\geq 3\} . Let {\mathcal{C}}_{G} denote the set of chordless cycles of G of length at least 4. Since a clique K of size 3 can also be viewed as a (chordless) cycle and \det x[K]=-\Gamma_{K}(x) , we also define the set {\mathcal{C}}_{G,\geq 3} as the set of chordless cycles of length at least 3. The following is the main result of this section. Theorem 4.5 . For any graph G , the algebraic boundary of the set \widetilde{\mathcal{E}}(G) is the hypersurface defined by the polynomial P_{G} from ( 31 ), i.e., \partial_{a}\widetilde{\mathcal{E}}(G)=V(P_{G}). In particular, if G is cycle completable, then \partial_{a}{\mathcal{E}}(G)=V(P_{G}). We begin with proving Theorem 4.5 for graphs with no K_{4} -minors. For this, we describe the algebraic boundary of the set \cos(\pi\text{\rm MET}(G)) for any graph G , in which case the arguments are simpler and exploit the description of the euclidean boundary in Proposition 4.2 (i). Proposition 4.6 . For any graph G=(V,E) , we have \partial_{a}\cos(\pi\text{\rm MET}(G))=V(Q_{G}) , where the polynomial Q_{G} is defined by Q_{G}(x)=\prod_{e\in{\mathcal{K}}_{G,2}}(x_{e}-1)(x_{e}+1)\cdot\prod_{C\in{\mathcal{C}}_{G,\geq 3}}\Gamma_{C}(x). Therefore, if G has no K_{4} -minor, then we have \partial_{a}{\mathcal{E}}(G)=V(P_{G}) . Proof. If G has no K_{4} -minor, then {\mathcal{E}}(G)=\cos(\pi\text{\rm MET}(G)) , and P_{G}=Q_{G} since G has no clique of size 4. Hence, it suffices to show that \partial_{a}\cos(\pi\text{\rm MET}(G))=V(Q_{G}) for any graph G . We begin with the explicit description of the facets of \text{\rm MET}(G) . For each edge e\in{\mathcal{K}}_{G,2} and \alpha\in\{0,1\} , the set {\mathcal{F}}_{e,\alpha}=\text{\rm MET}(G)\cap\{a\in\mathbb{R}^{E}:a_{e}=\alpha\} is a facet of \text{\rm MET}(G) and, for each C\in{\mathcal{C}}_{G,\geq 3} and F\subseteq E(C) with |F| odd, also the set {\mathcal{F}}_{C,F}=\text{\rm MET}(G)\cap\{a\in\mathbb{R}^{E}:a(F)-a(E(C)\setminus F)=|F|-1\} is a facet, and these are all the facets of \text{\rm MET}(G) . That is, \partial\text{\rm MET}(G)=\bigcup_{e\in{\mathcal{K}}_{G,2},\alpha\in\{0,1\}}{\mathcal{F}}_{e,\alpha}\ \cup\bigcup_{C\in{\mathcal{C}}_{G,\geq 3},\ F\subseteq E(C),\ |F|\text{\rm odd}}{\mathcal{F}}_{C,F}. Applying the componentwise cosine map to both sides one obtains that \cos(\pi\partial\text{\rm MET}(G))=\bigcup_{e,\alpha}\cos(\pi{\mathcal{F}}_{e,\alpha})\cup\bigcup_{C,F}\cos(\pi{\mathcal{F}}_{C,F}). (32) It is clear that \cos(\pi{\mathcal{F}}_{e,\alpha})\subseteq V(x_{e}-\cos(\pi\alpha)) , and \cos(\pi{\mathcal{F}}_{C,F})\subseteq V(\Gamma_{C}) holds by Remark 2.7 . By taking the Zariski closure on both sides of these two inclusions, we obtain \overline{\cos(\pi{\mathcal{F}}_{e,\alpha})}^{z}\subseteq V(x_{e}-\cos(\pi\alpha)) and \overline{\cos(\pi{\mathcal{F}}_{C,F})}^{z}\subseteq V(\Gamma_{C}) . Here, \overline{\cdot}^{z} is the Zariski closure. The key observation is that the latter two inclusions are in fact equalities, which we prove below using a dimension argument. Once we establish this claim, Proposition 4.6 follows directly from ( 32 ) using the fact that the closure of the union is the union of closures. Let {\mathcal{F}} denote one of the facets {\mathcal{F}}_{e,\alpha} or {\mathcal{F}}_{C,F} . Both the relative interior {\rm relint}(\pi{\mathcal{F}}) of {\mathcal{F}} and its image {\rm cos}({\rm relint}(\pi{\mathcal{F}})) are real analytic manifolds of dimension |E|-1 , since the cosine map is one-to-one and thus preserves the dimension. Therefore, the smallest variety containing {\rm cos}({\rm relint}(\pi{\mathcal{F}})) must have dimension at least |E|-1 . The varieties V(x_{e}-\cos(\pi\alpha)) and V(\Gamma_{C}) have dimension |E|-1 and they are irreducible. Hence, the equalities \overline{\cos(\pi{\mathcal{F}}_{e,\alpha})}^{z}=V(x_{e}-\cos(\pi\alpha)) and \overline{\cos(\pi{\mathcal{F}}_{C,F})}^{z}=V(\Gamma_{C}) hold, as desired. The correspondence between facets of \text{\rm MET}(G) and their images under the cosine map is nicely seen, for G=C_{4} , from the color coding in Figure 1 . ∎ For the description of the algebraic boundary of the set \widetilde{\mathcal{E}}(G) , there are additional determinantal hypersurfaces \det(K)=0 (for the cliques of G ) that need to be added to the hypersurfaces that form part of the algebraic boundary boundary of \cos(\pi\text{\rm MET}(G)) . We need some additional technical arguments in order to show Theorem 4.5 . We state three auxiliary results that will be key ingredients in the proof. The first key ingredient is the fact that each irreducible component of the algebraic boundary of a full-dimensional convex semialgebraic set has codimension 1. Proposition 4.7 . [ 25 , Lemma 2.5] Let S\subsetneq\mathbb{R}^{n} be a convex semialgebraic set with non-empty interior. Each irreducible component of the algebraic boundary of S has codimension 1 in \mathbb{C}^{n} , i.e., \partial_{a}S is a hypersurface. A second key ingredient is that the determinant of a correlation matrix of size at least 3 is an irreducible polynomial. For lack of a precise reference, we include a proof. Lemma 4.8 . The determinant \det(X_{n})\in\mathbb{C}[x_{ij}:1\leq iL . Pick an index k such that L+1\leq k\leq M . Now, we use Proposition 4.9 applied to the set \widetilde{\mathcal{E}}(G) : there exists a point x\in\partial\widetilde{\mathcal{E}}(G)\cap{\mathcal{Y}}_{k} such that x\not\in{\mathcal{Y}}_{j} for all j\in[M]\setminus\{k\} . But, x\in\partial\widetilde{\mathcal{E}}(G)\subseteq{\mathcal{X}} , which implies x\in\bigcup_{l=1}^{L}{\mathcal{X}}_{l}=\bigcup_{l=1}^{L}{\mathcal{Y}}_{l} , yielding a contradiction. ∎ 4.3 Applications We mention here some applications and extensions of the above results about algebraic boundaries of graph elliptopes. Which graph elliptopes are spectrahedra? As a first application, we investigate when the elliptope of a graph is a spectrahedron. Clearly, any graph elliptope {\mathcal{E}}(G) is a spectrahedral shadow , i.e., the projection of a spectrahedron. However, {\mathcal{E}}(G) is in general not a spectrahedron. As we observe below, the elliptope of a cycle {\mathcal{E}}(C_{n}) ( n\geq 4 ) is not a spectrahedron, thus rectifying a claim in [ 27 , Section 4.2] . As an application of Theorem 4.5 , we shall prove that {\mathcal{E}}(G) is a spectrahedron precisely when G is chordal; moreover, we show that this is equivalent to requiring that the algebraic boundary of the elliptope {\mathcal{E}}(G) does not intersect its interior (Corollary 4.10 ). We begin with recalling some well-known facts about spectrahedra (see, e.g., [ 7 ] for more information). A spectrahedron is a set of the form \displaystyle{\mathcal{K}}=\Big\{x\in\mathbb{R}^{n}:B(x)=B_{0}+\sum_{i=1}^{n}x_{i}B_{i}\succeq 0\Big\}, (33) where B_{0},B_{i}\in{\mathcal{S}}^{N} for some N\geq 1 . If there exists x\in\mathbb{R}^{n} such that B(x)\succ 0 , then {\mathcal{K}} is full-dimensional and its interior is \text{\rm int}({\mathcal{K}})=\{x\in\mathbb{R}^{n}:B(x)\succ 0\} . Hence, its boundary is given by \partial{\mathcal{K}}=\{x\in{\mathcal{K}}:\det(B(x))=0\} , and thus its algebraic boundary satisfies: \partial_{a}{\mathcal{K}}\subseteq\{x\in\mathbb{C}^{n}:\det(B(x))=0\} . Therefore, we have \displaystyle\text{If }{\mathcal{K}}\text{ is a spectrahedron, then }\text{\rm int}({\mathcal{K}})\cap\partial_{a}{\mathcal{K}}=\emptyset. (34) Note that the inclusion \partial{\mathcal{K}}\subseteq\{x\in\mathbb{R}^{n}:\det(B(x))=0\} can be strict. As an example, the one-dimensional spectrahedron defined by \left(\begin{smallmatrix}1&x&0\\ x&1&0\\ 0&0&x\end{smallmatrix}\right)\succeq 0 is given by the line segment [0,1] . Its associated determinantal hypersurface is given by the polynomial equation x(1-x^{2})=0 , while the algebraic boundary is given by x(1-x)=0 . By the above discussion, we obtain that {\mathcal{E}}(C_{n}) is not a spectrahedron, and more generally we can characterize the graphs G for which {\mathcal{E}}(G) is a spectrahedron. Corollary 4.10 . For a graph G=(V,E) the following assertions are equivalent: (i) G is chordal. (ii) The elliptope {\mathcal{E}}(G) is a spectrahedron. (iii) \partial_{a}{\mathcal{E}}(G)\cap\text{\rm int}({\mathcal{E}}(G))=\emptyset . Proof. The implication (i) \Longrightarrow (ii) follows using Theorem 2.1 , and (ii) \Longrightarrow (iii) follows from the above discussion, see relation ( 34 ). Now we show (iii) \Longrightarrow (i), using contradiction. Assume that G is not chordal. We show that \partial_{a}{\mathcal{E}}(G)\cap\text{\rm int}({\mathcal{E}}(G))\neq\emptyset . By assumption, G contains a chordless cycle C of length at least 4. Observe that the elliptope {\mathcal{E}}(C) can be obtained as an affine section of the elliptope of G . Indeed, for y\in\mathbb{R}^{E(C)} , consider the point x=(y,\mathbf{0})\in\mathbb{R}^{E} obtained by padding y with zero entries at the positions of the edges in E\setminus E(C) . Then, y\in{\mathcal{E}}(C) if and only if x\in{\mathcal{E}}(G) . Set {\mathcal{H}}=\{x\in\mathbb{R}^{E}:x_{e}=0\text{ for }e\in E\setminus E(C)\} . The map y\mapsto(y,\mathbf{0}) establishes a one-to-one correspondence between {\mathcal{E}}(C) and {\mathcal{E}}(G)\cap{\mathcal{H}} , between \text{\rm int}({\mathcal{E}}(C)) and \text{\rm int}({\mathcal{E}}(G))\cap{\mathcal{H}} , and between \partial{\mathcal{E}}(C) and \partial{\mathcal{E}}(G)\cap{\mathcal{H}} , which implies \displaystyle\partial_{a}{\mathcal{E}}(C)\,\simeq\,\overline{\partial{\mathcal{E}}(G)\cap{\mathcal{H}}}^{z}\,\subseteq\,\partial_{a}{\mathcal{E}}(G)\cap{\mathcal{H}}. By Remark 4.4 , there exists a point y\in\text{\rm int}({\mathcal{E}}(C)) such that \Gamma_{C}(y)=0 . Thus, y\in\partial_{a}{\mathcal{E}}(C) . Hence, the point x=(y,\mathbf{0}) belongs to \text{\rm int}({\mathcal{E}}(G))\cap\partial_{a}{\mathcal{E}}(G) , as desired. ∎ The algebraic boundary of the cone \mathscr{C}(G) As a direct application of Theorem 4.5 , one can compute the algebraic boundary of the cone \mathscr{C}(G) in ( 28 ) when G is cycle completable. It is provided by the analog of the polynomial P_{G} in ( 31 ), where we now replace the cycle polynomial \Gamma_{C} by the homogeneous one \Gamma_{C}^{h} (introduced in Definition 3.19 ). For \mathscr{C}(C_{n}) the next result recovers Theorem 4.8 in [ 27 ] . Corollary 4.11 . If G is cycle completable, then the algebraic boundary of the cone \mathscr{C}(G) is the hypersurface defined by the polynomial equation \prod_{K\in{\mathcal{K}}_{G}}\det s[K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma_{C}^{h}(s)=0, in the variables s=(s_{kk}:k\in V;s_{ij}:\{i,j\}\in E) . Proof. We use the analog of Proposition 4.1 stating that {\rm int}(\mathscr{C}(G))=\pi_{V\cup E}({\rm int}({\cal S}_{+}^{n})) . Assume that s\in\mathbb{R}^{V\cup E} belongs to \mathscr{C}(G) . Then, s\in\partial\mathscr{C}(G) precisely when s_{kk}=0 for some k\in V , or the point x\in\mathbb{R}^{E} from ( 29 ) belongs to \partial{\mathcal{E}}(G) . By Theorem 4.5 , we have that \partial_{a}({\mathcal{E}}(G))=V(P_{G})=V(\prod_{K\in{\mathcal{K}}_{G}}\det x[K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma_{C}(x)) . The result now follows after applying the change of variables and using the definition of \Gamma_{C}^{h} . We also use the fact that \mathscr{C}(G)\cap\{s:s_{kk}=0\}\subseteq\mathscr{C}(G)\cap\{s:\det s[K]=0\} if K\in{\mathcal{K}}_{G} contains the vertex k\in V . ∎ The elliptope of a suspension graph As another application, we indicate how to compute the algebraic boundary for the elliptope of a suspension graph. Given a graph G=(V=[n],E) , its suspension graph \nabla G is obtained by adding a new node to G , called an apex node and denoted by 0 , which is adjacent to all nodes of G . So, V(\nabla G)=V\cup\{0\} and E(\nabla G)=E\cup\{\{0,i\}:i\in V\} . As an example, the wheel graph W_{k}=\nabla C_{k-1} on k vertices is obtained by adding an apex node to the cycle C_{k-1} . So, W_{4}=K_{4} is cycle completable, but the wheel W_{k} is not cycle completable for any k\geq 5 , see Theorem 2.4 . To compute the algebraic boundary of the elliptope of a suspension graph \nabla G in terms of the algebraic boundary of the elliptope of G , we proceed as in [ 27 , Sec. 4.3] . We first pass to the cones {\mathscr{C}}(\nabla G) and {\mathscr{C}}(G) to allow for arbitrary diagonal entries. We use coordinates s=(s_{ii},i\in V(\nabla G);s_{ij},(i,j)\in E(\nabla G))\in\mathbb{R}^{V(\nabla G)\cup E(\nabla G)} . The next observation will be useful. Lemma 4.12 . Let G=(V=[n],E) be any graph and \nabla G its suspension graph. The semialgebraic set {\mathscr{C}}(\nabla G)\cap\{s:s_{00}=0\} has codimension at least n+1 in \mathbb{R}^{V(\nabla G)\cup E(\nabla G)} . Proof. If s\in{\mathscr{C}}(\nabla G) , then s admits a positive semidefinite completion. In particular, the specified 2\times 2 minors s_{00}s_{ii}-s_{0i}^{2} are nonnegative for i=1,\ldots,n . If, in addition to s\in{\mathscr{C}}(\nabla G) , the entry s_{00} is zero, we must have s_{0i}=0 for i=1,\ldots,n . Therefore, {\mathscr{C}}(\nabla G)\cap\{s:s_{00}=0\} is contained in the coordinate subspace s_{00}=s_{01}=\cdots=s_{0n}=0 of codimension n+1 . ∎ Since the entries s_{0i} are specified for all i\in V=V(G) , the key idea is to check membership of s in {\mathscr{C}}(\nabla G) by taking the Schur complement w.r.t. the entry s_{00} . Restricted to the entries indexed by V\cup E , the Schur complement is represented by a map \varphi:\mathbb{R}^{V(\nabla G)\cup E(\nabla G)}\rightarrow\mathbb{R}^{V\cup E} : \displaystyle t=\varphi(s)=\Big(s_{ij}-{s_{0i}s_{0j}\over s_{00}}\Big)_{\{i,j\}\in V\cup E} (35) (setting \tfrac{s_{0i}s_{0j}}{s_{00}}=0 if s_{00}=0 ). Proposition 4.13 . Let G be any graph. If the algebraic boundary of {\mathscr{C}}(G) is given by the polynomial B_{G}(t)=0 , then the algebraic boundary of {\mathscr{C}}(\nabla G) is the zero locus of the numerator of the rational function B_{G}(\varphi(s)) . Moreover, each irreducible factor f(t) of B_{G}(t) pulls back to an irreducible factor of B_{G}(\varphi(s)) , namely the numerator of f(\varphi(s)) . Proof. Write \mathbb{C}^{V(\nabla G)\cup E(\nabla G)} as \mathbb{C}\times\mathbb{C}^{V}\times\mathbb{C}^{V\cup E} , where we use the coordinates s=(s_{00};s_{0i},i\in V;s_{ij},\{i,j\}\in V\cup E) on the individual factors. Consider the map \displaystyle\psi: \displaystyle\ \mathbb{C}^{*}\times\mathbb{C}^{V}\times\mathbb{C}^{V\cup E}\to\mathbb{C}^{*}\times\mathbb{C}^{V}\times\mathbb{C}^{V\cup E} \displaystyle\ s\mapsto(s_{00};s_{0i},i\in V;\varphi(s)), where \mathbb{C}^{*}=\mathbb{C}\setminus\{0\} and \varphi(s) is as in ( 35 ). The map \psi is an isomorphism of affine varieties. A standard property of the Schur complement implies that, if s_{00}\neq 0 , then \varphi(s)\in{\mathscr{C}}(\nabla G)\Longleftrightarrow s\in{\mathscr{C}}(G) . Therefore, the image of \mathscr{C}(\nabla G)\setminus\{s:s_{00}=0\} under \psi is \psi(\mathscr{C}(\nabla G)\setminus\{s:s_{00}=0\})=\mathbb{R}_{>0}\times\mathbb{R}^{V}\times\mathscr{C}(G). An irreducible component {\cal Y}_{j} of the algebraic boundary of {\mathscr{C}}(G) gives an irreducible component \overline{\psi^{-1}({\cal Y}_{j})}^{z} of the algebraic boundary of {\mathscr{C}}(\nabla G) , not contained in s_{00}=0 . Here the Zariski closure is taken in \mathbb{C}\times\mathbb{C}^{V}\times\mathbb{C}^{V\cup E} . If {\cal Y}_{j} is defined by f(t)=0 , then \psi^{-1}({\cal Y}_{j}) is defined by f(\varphi(s))=0 , and its Zariski closure is defined by the numerator of this rational function. The only components of the algebraic boundary of {\mathscr{C}}(\nabla G) that are not obtained in this way must be contained in \{s\,:\,s_{00}=0\} . By Proposition 4.7 and Lemma 4.12 , there is no such component. ∎ Proposition 4.14 . Assume G=(V,E) is cycle completable. The algebraic boundary of the cone {\mathscr{C}}(\nabla G) is given by the zero locus of the polynomial \prod_{K\in{\mathcal{K}}_{G}}\det s[\nabla K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma^{h}_{C}(\tilde{s})\in\mathbb{R}[s_{00};s_{0i},i\in V;s_{ij},\{i,j\}\in V\cup E] where we set \tilde{s}_{ij}=s_{ij}s_{00}-s_{0i}s_{0j} for \{i,j\}\in V\cup E and where \Gamma^{h}_{C} is the homogeneous cycle polynomial from Definition 3.19 . Therefore, the algebraic boundary of the elliptope {\mathcal{E}}(\nabla G) is given by the zero locus of the polynomial \displaystyle P^{\nabla}_{G}(x)=\prod_{K\in{\mathcal{K}}_{G}}\det x[\nabla K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma^{\nabla}_{C}(x)\in\mathbb{R}[x_{ij}:\{i,j\}\in E(\nabla G)], (36) where \Gamma^{\nabla}_{C}(x)=\Gamma^{h}_{C}(\tilde{x}) , with \tilde{x}_{ii}=1-x_{0i}^{2} for i\in V and \tilde{x}_{ij}=x_{ij}-x_{0i}x_{0j} for \{i,j\}\in E . Proof. We combine Corollary 4.11 and Proposition 4.13 . By Corollary 4.11 , the algebraic boundary of \mathscr{C}(G) is the vanishing set of the polynomial \prod_{K\in{\mathcal{K}}_{G}}\det t[K]\cdot\prod_{C\in{\mathcal{C}}_{G}}\Gamma_{C}^{h}(t)\in\mathbb{R}[t_{ij}:\{i,j\}\in V\cup E]. By Proposition 4.13 , we must compute the numerator of f(\varphi(s)) for each irreducible factor f(t) of this polynomial. First, consider a factor f(t)=\det t[K] for a clique K\in{\mathcal{K}}_{G} . Then, \nabla K=K\cup\{0\} is a clique of \nabla G and \det s[\nabla K]=s_{00}\cdot\det t[K] (by taking a Schur complement). So, the component \det t[K]=0 of \partial_{a}{\mathscr{C}}(G) contributes the component \det s[\nabla K]=0 of \partial_{a}{\mathscr{C}}(\nabla G) . Second, consider a factor f(t)=\Gamma_{C}^{h}(t) for a cycle C\in{\mathcal{C}}_{G} . Using Theorem 3.21 (and the comment therefater with all \lambda_{i}=s_{00}^{1/2} ), we obtain that \Gamma^{h}_{C}(\tilde{s})=s_{00}^{d}\cdot\Gamma_{C}^{h}(t) , where d=|C|\cdot 2^{|C|-3} and \tilde{s}_{ij}=s_{00}s_{ij}-s_{0i}s_{0j} for \{i,j\}\in V\cup E . So, the component \Gamma_{C}^{h}(t)=0 of \partial_{a}{\mathscr{C}}(G) pulls back to the component \Gamma^{h}_{C}(\tilde{s})=0 of \partial_{a}{\mathscr{C}}(\nabla G) . ∎ Example 4.15 . The wheel graph W_{k}=\nabla C_{k-1} on k vertices is the suspension graph of the cycle C_{k-1}=(1,2,\ldots,k-1) , obtained by adding an apex node 0 to C_{k-1} . By Proposition 4.14 , the algebraic boundary of its elliptope {\mathcal{E}}(W_{k}) is given by the polynomial \Gamma^{\nabla}_{C_{k-1}}(x)\cdot\prod_{\{i,j\}\in E_{k-1}}\det x[\{0,i,j\}]. Comparing with the polynomial P_{W_{k}}(x)=\Gamma_{C_{k-1}}(x)\cdot\prod_{\{i,j\}\in E_{k-1}}\det x[\{0,i,j\}] , i.e., the algebraic boundary of \tilde{\mathcal{E}}(W_{k}) , it is clear that these two polynomials only differ in one factor. In other words, we have \partial_{a}{\mathcal{E}}(W_{k})\neq V(P_{W_{k}}) for any k\geq 5 . To give a concrete example, consider the wheel W_{5} . The polynomial \Gamma_{4}^{\nabla} has degree 16 and depends on all variables \{x_{e}:e\in E(W_{5})\} , while \Gamma_{4} has degree 8 and only depends on the variables x_{e} indexed by e\in E(C_{4}) . Figure 4 on the left shows the intersections of V(\Gamma_{4}) (in yellow) and V(\Gamma_{4}^{\nabla}) (in red) with the three-dimensional affine space defined by x_{01}=x_{02}=x_{03}=x_{04}=x_{14}=\tfrac{1}{2} . The first slice is a Lissajous hypersurface, while the second one is the same algebraic variety scaled by a factor smaller than 1 and tangent to the former. The right part of Figure 4 compares the 2-dimensional slices of {\mathcal{E}}(W_{5}) (in red) and of \widetilde{\mathcal{E}}(W_{5}) (in yellow), where the slice is now obtained by setting x_{01}=x_{02}=x_{03}=x_{04}=x_{14}=\tfrac{1}{2} and x_{12}=x_{23} . Figure 4 : On the left, the 3-D slices of V(\Gamma_{4}) (in yellow) and V(\Gamma_{4}^{\nabla}) (in red) at x_{01}=\dotsc=x_{04}=x_{14}=\tfrac{1}{2} ; on the right, the 2-D slices of {\mathcal{E}}(W_{5}) (in red) and its superset \widetilde{\mathcal{E}}(W_{5}) (in yellow) at x_{01}=\dotsc=x_{04}=x_{14}=\tfrac{1}{2} and x_{12}=x_{23} (discussed in Example 4.15 ). As just observed in Example 4.15 , we have \partial_{a}{\mathcal{E}}(W_{k})\neq V(P_{W_{k}}) for any k\geq 5 . In [ 27 , Example 4.10] the authors observe that \partial_{a}{\mathcal{E}}(H)\neq V(P_{H}) if H=\widetilde{W}_{4} is the graph on 5 nodes obtained by splitting one vertex in W_{4}=K_{4} . We expect that the same holds for all iterated splittings of W_{k} ( k\geq 5 ) and \widetilde{W}_{4} , and that this can be used to show the converse implication: if \partial_{a}{\mathcal{E}}(G)=V(P_{G}) then G is cycle completable. We leave this as future work. 4.4 Proof of Proposition 4.9 Here, we show Proposition 4.9 . Recall that V({\mathcal{F}})=\{x\in\mathbb{C}^{n}:f(x)=0\text{ for }f\in{\mathcal{F}}\} is the complex affine variety defined by {\mathcal{F}}\subseteq\mathbb{R}[x_{1},\ldots,x_{n}] . We write V_{\mathbb{R}}({\mathcal{F}})=V({\mathcal{F}})\cap\mathbb{R}^{n} for its real points, i.e., the set of all common real roots of {\mathcal{F}} . We begin with showing the result for the elliptope {\mathcal{E}}(G) . After that, we will derive the result for the superset \widetilde{\mathcal{E}}(G) from it. Let us fix some notation. Let G=(V,E) be a graph. Let V=U\cup W , where W=V\setminus U and U=K for some K\in{\mathcal{K}}_{G} , or U=V(C) for some C\in{\mathcal{C}}_{G} , depending whether we wish to prove property (PK) or (PC). Let H=G[W]=(W,E(H)) denote the subgraph of G induced by W . Our proof strategy is to construct a matrix X\in{\mathcal{E}}_{V} with block-form \displaystyle X=Z\oplus Y=\begin{pmatrix}Z&\mathbf{0}\cr\mathbf{0}&Y\end{pmatrix}, (37) where Z\in{\mathcal{E}}_{U} , Y\in{\mathcal{E}}_{W} are indexed by U,W, respectively. Then, the point x=\pi_{E}(X) belongs to {\mathcal{E}}(G) and the goal is to select the matrices Z,Y in such a way that x satisfies property (PK) or (PC). We treat these two cases separately. We first show that (PK) holds. Consider a clique K\in{\mathcal{K}}_{G} , set p=|K| and U=K . Define the matrix Z={1\over p-1}(pI_{p}-J_{p})\in{\mathcal{E}}_{U} , where J_{p} is the all-ones p\times p matrix. Then, Z\succeq 0 with zero eigenvalue for the all-ones eigenvector and eigenvalue p\over p-1 with multiplicity p-1 ; hence, each strict principal submatrix of Z is positive definite. By construction, x[K]=Z , so \det x[K]=0 . We now need to select the matrix Y\in{\mathcal{E}}_{W} . We will choose Y to be positive definite. This guarantees that \det x[K^{\prime}]\neq 0 for all cliques K^{\prime}\in{\mathcal{K}}_{G}\setminus\{K\} . Indeed, we have x[K^{\prime}]=Z[K^{\prime}\cap K]\oplus Y[K^{\prime}\cap W] , and both direct summands are positive definite by construction. We must also ensure that \Gamma_{C}(x)\neq 0 for all C\in{\mathcal{C}}_{G} . We claim that this is satisfied for all choices of Y such that y=\pi_{E(H)}(Y)\in\mathbb{R}^{E(H)} avoids a hypersurface {\cal H}\subseteq\mathbb{R}^{E(H)} . Then, a point y\in{\rm int}({\cal E}(H))\setminus{\cal H} exists, because {\cal E}(H) is full-dimensional in \mathbb{R}^{E(H)} while {\mathcal{H}} has codimension one. To prove our claim, we describe the hypersurface {\cal H} explicitly. For each cycle C\in{\cal C}_{G} , let f_{C}\in\mathbb{R}[y_{e}\,:\,e\in E(C)\cap E(H)] be the polynomial obtained by substituting x_{e}\,=\,\begin{cases}y_{e}&e\in E(C)\cap E(H)\\ \frac{-1}{p-1}&e\in E(C)\cap E(K)\\ 0&e\in E(C)\setminus(E(K)\cup E(H))\end{cases} in the cycle polynomial \Gamma_{C}\in\mathbb{Z}[x_{e}\,:\,e\in E(C)] . By construction, we have \Gamma_{C}(x)=0 if and only if f_{C}(y)=0 . Since C is a chordless cycle with at least four edges, we have |E(C)\cap E(K)|\leq 1 and thus the set E(C)\cap E(H) is non-empty. Hence, by Lemma 3.9 , the polynomial f_{C} is not identically zero. We now define the hypersurface {\cal H}\subseteq\mathbb{R}^{E(C)} as {\mathcal{H}}=\Big\{y\in\mathbb{R}^{E(C)}:\prod_{C\in{\mathcal{C}}_{G}}f_{C}(y)=0\Big\}. In summary, as \text{\rm int}({\mathcal{E}}(H))\not\subseteq{\mathcal{H}} , one can pick y\in{\rm int}({\cal E}(H))\setminus{\cal H} and a positive definite matrix Y\in{\mathcal{E}}_{W} such that \pi_{E(H)}(Y)=y . Then, one constructs X as in ( 37 ) and the point x=\pi_{E}(X)\in{\mathcal{E}}(G) satisfies the assertions of property (PK) for the clique K . It is clear that x\in\partial{\mathcal{E}}(G) , since it admits no positive definite completion (because \det x[K]=0 ). Now, we show property (PC). Consider a cycle C\in{\mathcal{C}}_{G} and set U=V(C) . Again, we want to find matrices Z\in{\mathcal{E}}_{U} and Y\in{\mathcal{E}}_{W} so that, for the block-matrix X in ( 37 ), the point x=\pi_{E}(X) satisfies (PC), i.e., x\in\partial{\mathcal{E}}(G) , \Gamma_{C}(x)=0 , \Gamma_{D}(x)\neq 0 for D\in{\mathcal{C}}_{G}\setminus\{C\} , and \det x[K]\neq 0 for K\in{\mathcal{K}}_{G} . We first indicate conditions that we need to impose on Z,Y . By Proposition 4.2 (i), \partial{\mathcal{E}}(C)=\cos(\pi\partial\text{\rm MET}(C)) holds. Consider an edge e_{0}\in E(C) and the hyperplane H_{e_{0}}=\{a\in\mathbb{R}^{E(C)}:a_{e_{0}}=\sum_{e\in E(C)\setminus\{e_{0}\}}a_{e}\} . This hyperplane defines the facet {\mathcal{F}}_{e_{0}}=H_{e_{0}}\cap\text{\rm MET}(C) of \text{\rm MET}(C) , and the relative interior of {\mathcal{F}}_{e_{0}} satisfies \text{\rm relint}({\mathcal{F}}_{e_{0}})\subseteq(0,1)^{E(C)}\cap\partial\text{\rm MET}(C) . Define the semialgebraic set S_{C}=\cos(\pi\ \text{\rm relint}({\mathcal{F}}_{e_{0}})) . Then, S_{C}\subseteq(-1,1)^{E(C)}\cap V_{\mathbb{R}}(\Gamma_{C}) (recall Remark 2.7 ). Moreover, S_{C} has dimension |C|-1 : the facet \text{\rm relint}({\mathcal{F}}_{e_{0}}) and its image under the cosine map, which is one-to-one, have the same dimension. The matrix Z will be chosen in order to ensure that the point z=\pi_{E(C)}(Z) lies in the set S_{C} , but not in a real variety {\cal H} of dimension at most |C|-2 . This variety {\mathcal{H}} will be described below. Its dimension ensures that S_{C}\setminus{\cal H}\neq\emptyset . So, one can pick z\in S_{C}\setminus{\cal H} and Z\in{\mathcal{E}}_{U} such that z=\pi_{E(C)}(Z) , which guarantees that \Gamma_{C}(z)=0 . Once we have fixed Z such that z=\pi_{E(C)}(Z)\in S_{C}\setminus{\cal H} , we shall pick Y\in{\mathcal{E}}_{W} positive definite such that y=\pi_{E(H)}(Y)\in{\rm int}({\mathcal{E}}_{W})\setminus{\cal H}_{z} . Here, {\cal H}_{z} is a hypersurface in \mathbb{R}^{E(H)} that depends on z , to be described explicitly below. Note that if \pi_{E(C)}(Z)\in S_{C} and Y\succ 0 in ( 37 ), then it is guaranteed that \det x[K]\neq 0 for all K\in{\mathcal{K}}_{G} . Indeed, we have x[K]=Z[K\cap U]\oplus Y[K\cap W] , with Y[K\cap W]\succ 0 since Y\succ 0 . Moreover, |K\cap U|\leq 2 as C is chordless with at least 4 edges. So, Z[K\cap U] is either the scalar 1 if |K\cap U|=1 , or the matrix \left(\begin{smallmatrix}1&z_{uv}\cr z_{uv}&1\end{smallmatrix}\right)\succ 0 if K\cap U=\{u,v\} (since z_{uv}\neq\pm 1 ). The varieties {\cal H}\subseteq\mathbb{R}^{E(C)} and {\cal H}_{z}\subseteq\mathbb{R}^{E(H)} are determined by the conditions \Gamma_{D}(x)\neq 0 for all cycles D\in{\cal C}_{G}\setminus\{C\} . We first define {\cal H} . Write {\cal C}_{G}^{C} for the set of cycles D\in{\cal C}_{G}\setminus\{C\} with E(D)\cap E(H)=\emptyset . Let D\in{\cal C}_{G}^{C} . Consider the polynomial g_{D}\in\mathbb{R}[z_{e}\,:\,e\in E(D)\cap E(C)] obtained by specializing x_{e}\,=\,\begin{cases}z_{e}&e\in E(D)\cap E(C)\\ 0&e\in E(D)\setminus E(C)\end{cases} in the cycle polynomial \Gamma_{D}\in\mathbb{Z}[x_{e}\,:\,e\in E(D)] . By construction, we have that \Gamma_{D}(x)=0 if and only if g_{D}(z)=0 , where x=\pi_{E(D)}(X) with X as in ( 37 ). Consider the variety {\mathcal{H}}_{D}=V(\Gamma_{C})\cap V(g_{D}) . We have strict inclusion {\mathcal{H}}_{D}\subsetneq V(\Gamma_{C}) , because g_{D}(z) involves a strict subset of the variables of \Gamma_{C}(z) (since E(D)\not\subseteq E(C) ). As \Gamma_{C} is an irreducible polynomial, its variety V(\Gamma_{C}) is irreducible and thus the variety {\mathcal{H}}_{D} must have smaller dimension than V(\Gamma_{C}) . Hence, the dimension of {\mathcal{H}}_{D} is at most |C|-2 , and thus also the dimension of the real variety {\mathcal{H}}_{D}\cap\mathbb{R}^{E(C)} is at most |C|-2 . We now define the real variety {\mathcal{H}}\subseteq\mathbb{R}^{E(C)} as {\cal H}\,=\Big\{z\in V_{\mathbb{R}}(\Gamma_{C}):\prod_{D\in{\cal C}^{C}_{G}}g_{D}(z)=0\Big\}=\bigcup_{D\in{\mathcal{C}}^{C}_{G}}({\mathcal{H}}_{D}\cap\mathbb{R}^{E(C)}). By the above reasoning, \dim{\cal H}\leq|C|-2 , and thus S_{C}\setminus{\cal H}\neq\emptyset (since \dim S_{C}=|C|-1 ). The remaining cycles serve to specify the hypersurface {\cal H}_{z}\subseteq\mathbb{R}^{E(H)} . Let {\cal C}_{G}^{H}\subseteq{\mathcal{C}}_{G}\setminus\{C\} be the set of cycles D\in{\mathcal{C}}_{G} with |E(D)\cap E(H)|\geq 1 . For each D\in{\mathcal{C}}_{G}^{H} , define the polynomial h_{D,z}\in\mathbb{R}[y_{e}\,:\,e\in E(D)\cap E(H)] obtained by specializing x_{e}\,=\,\begin{cases}z_{e}&e\in E(D)\cap E(C)\\ y_{e}&e\in E(D)\cap E(H)\\ 0&e\in E(D)\setminus(E(C)\cup E(H))\\ \end{cases} in the cycle polynomial \Gamma_{D}\in\mathbb{Z}[x_{e}\,:\,e\in E(D)] . Here, z_{e} is the coordinate of \pi_{E(C)}(Z) labeled by e\in E(C) for our fixed matrix Z from above. By Lemma 3.9 , h_{D,z} is not the zero polynomial. The hypersurface {\cal H}_{z} is defined as {\cal H}_{z}\,=\,\Big\{y\in\mathbb{R}^{E(H)}\,:\,\prod_{D\in{\cal C}^{H}_{G}}h_{D,z}(y)=0\Big\}. The set {\rm int}({\mathcal{E}}(H))\setminus{\cal H}_{z} is non-empty, since {\mathcal{E}}(H) is full-dimensional while {\mathcal{H}}_{z} has codimension 1. So, pick y\in{\rm int}({\mathcal{E}}(H))\setminus{\cal H}_{z} , pick Y\in{\mathcal{E}}_{W} positive definite such that y=\pi_{E(H)}(Y) , and consider the matrix X from ( 37 ). Then, x=\pi_{E}(X)\in{\mathcal{E}}(G) satisfies the conditions from property (PC). Remains only to verify that x\in\partial{\mathcal{E}}(G) . Indeed, if x\in\text{\rm int}({\mathcal{E}}(G)) , then x=\pi_{E}(\widehat{X}) for some positive definite \widehat{X}\in{\mathcal{E}}_{n} . But then this would imply that z=\pi_{E(C)}(\widehat{X}) belongs to \text{\rm int}({\mathcal{E}}(C)) , contradicting the fact that we selected z\in S_{C}\subseteq\partial{\mathcal{E}}(C) . This concludes the proof of Proposition 4.9 for the case of the elliptope {\mathcal{E}}(G) , where we ask for a point x\in\partial{\mathcal{E}}(G) in properties (PK) and (PC). Consider now the case of the superset \widetilde{\mathcal{E}}(G) , where we ask for a point x\in\partial\widetilde{\mathcal{E}}(G) in properties (PK) and (PC). We use the fact that the boundary of \widetilde{\mathcal{E}}(G) is given by \partial\widetilde{\mathcal{E}}(G)=(\partial S(G)\cap\cos(\pi\text{\rm MET}(G)))\cup(S(G)\cap\cos(\pi\partial\text{\rm MET}(G))). We show that the point x\in\partial{\mathcal{E}}(G) constructed in the above proof, in fact, also belongs to \partial\widetilde{\mathcal{E}}(G) . First of all, x clearly belongs to \widetilde{\mathcal{E}}(G) . Moreover, for property (PK), x satisfies \det x[K]=0 for some K\in{\mathcal{K}}_{G} , implying x\in\partial S(G)\cap\widetilde{\mathcal{E}}(G)\subseteq\partial\widetilde{\mathcal{E}}(G) . For property (PC), x=\cos(\pi a) with a\in\partial\text{\rm MET}(G) , implying x\in\cos(\pi\partial\text{\rm MET}(G))\cap\widetilde{\mathcal{E}}(G)\subseteq\partial\widetilde{\mathcal{E}}(G) . This concludes the proof of Proposition 4.9 for the case of \widetilde{\mathcal{E}}(G) .