Semidefinite Representation of the k-Ellipse 7 0 0 Jiawang Nie∗ Pablo A. Parrilo† Bernd Sturmfels‡ 2 n a February 2, 2008 J 1 3 Abstract ] G The k-ellipse is the plane algebraic curve consisting of all points whose sum A of distances from k given points is a fixed number. The polynomial equation h. defining the k-ellipse has degree 2k if k is odd and degree 2k− kk/2 if k is even. We express this polynomial equation as the determinant of a symmetric matrix t a (cid:0) (cid:1) of linear polynomials. Our representation extends to weighted k-ellipses and k- m ellipsoids in arbitrary dimensions, and it leads to new geometric applications of [ semidefinite programming. 1 v 5 1 Introduction 0 0 2 The circle is the plane curve consisting of all points (x,y) whose distance from a given 0 7 point (u1,v1) is a fixed number d. It is the zero set of the quadratic polynomial 0 h/ p1(x,y) = det d+x−u1 y −v1 . (1) t y −v1 d−x+u1 a (cid:20) (cid:21) m The ellipse is the plane curve consisting of all points (x,y) whose sum of distances from : v two given points (u1,v1) and (u2,v2) is a fixed number d. It is the zero set of i X d+2x−u1 −u2 y −v1 y −v2 0 ar y −v1 d+u1 −u2 0 y −v2 p2(x,y) = det . (2) y −v2 0 d−u1 +u2 y −v1  0 y −v2 y −v1 d−2x+u1 +u2     In this paper we generalize these determinantal formulas for the circle and the ellipse. Fix a positive real number d and fix k distinct points (u1,v1),(u2,v2),...,(uk,vk) in R2. The k-ellipse with foci (u ,v ) and radius d is the following curve in the plane: i i k (x,y) ∈ R2 : (x−u )2 +(y −v )2 = d . (3) i i ( ) i=1 Xp ∗Institute for Mathematics and its Applications, University of Minnesota †Laboratory for Information and Decision Systems, Massachusetts Institute of Technology ‡Department of Mathematics, University of California at Berkeley 1 Figure 1: A 3-ellipse, a 4-ellipse, and a 5-ellipse, each with its foci. The k-ellipse is the boundary of a convex set E in the plane, namely, the set of k points whose sum of distances to the k given points is at most d. These convex sets are of interest in computational geometry [Tra06] and in optimization, e.g. for the Fermat- Weber facility location problem [Baj88, CT90, Kul77, Sek99, Wei37]. In the classical literature (e.g. [Stu84]), k-ellipses are known as Tschirnhaus’sche Eikurven [Nagy50]. Indeed, they look like “egg curves” and they were introduced by Tschirnhaus in 1686. We are interested in the irreducible polynomial p (x,y) that vanishes on the k- k ellipse. This is the unique (up to sign) polynomial with integer coefficients in the unknowns x and y and the parameters d, u1,v1, ...,uk,vk. By the degree of the k- ellipse we mean the degree of p (x,y) in x and y. To compute it, we must eliminate k the square roots in the representation (3). Our solution to this problem is as follows: Theorem 1.1. The k-ellipse has degree 2k if k is odd and degree 2k− k if k is even. k/2 Its defining polynomial has a determinantal representation (cid:0) (cid:1) p (x,y) = det x·A +y ·B +C (4) k k k k where A ,B ,C are symmetric 2k×2k m(cid:0)atrices. The entries o(cid:1)f A and B are integer k k k k k numbers, and the entries of Ck are linear forms in the parameters d,u1,v1,...,uk,vk. For the circle (k = 1) and the ellipse (k = 2), the representation (4) is given by the formulas (1) and (2). The polynomial p3(x,y) for the 3-ellipse is the determinant of d+3x−u1−u2−u3 y−v1 y−v2 0 y−v3 0 0 0 2 y−v1 d+x+u1−u2−u3 0 y−v2 0 y−v3 0 0 3 6 y−v2 0 d+x−u1+u2−u3 y−v1 0 0 y−v3 0 7 66 0 y−v2 y−v1 d−x+u1+u2−u3 0 0 0 y−v3 77 66 y−v3 0 0 0 d+x−u1−u2+u3 y−v1 y−v2 0 77 66664 000 y−00v3 y−00v3 y−00v3 yy−−0vv12 d−x+uy1−−0vu22+u3d−x−uy1−+0vu12+u3d−3x+u1yy+−−uvv221+u377775 The full expansion of this 8×8-determinant has 2,355 terms. Next, the 4-ellipse is a curve of degree ten which is represented by a symmetric 16×16-matrix, etc.... Thispaperisorganizedasfollows. TheproofofTheorem1.1willbegiveninSection 2. Section 3 is devoted to geometric aspects and connections to semidefinite program- ming. While the k-ellipse itself is a convex curve, its Zariski closure { p (x,y) = 0} k 2 Figure 2: The Zariski closure of the 5-ellipse is an algebraic curve of degree 32. has many extra branches outside the convex set E . They are arranged in a beautiful k pattern known as a Helton-Vinnikov curve [HV03]. This pattern is shown in Figure 2 for k = 5 points. In Section 4 we generalize our results to higher dimensions and to the weighted case, and we discuss the computation of the Fermat-Weber point of the given points (u ,v ). A list of open problems and future directions is presented in Section 5. i i 2 Derivation of the Matrix Representation We begin with a discussion of the degree of the k-ellipse. Lemma 2.1. The defining polynomial of the k-ellipse has degree at most 2k in the variables (x,y) and it is monic of degree 2k in the radius parameter d. Proof. We claim that the defining polynomial of the k-ellipse can be written as follows: k p (x,y) = d − (−1)σi (x−u )2 +(y −v )2 . (5) k i i ! σ∈Y{0,1}k Xi=1 p 3 Obviously, the right hand side vanishes on the k-ellipse. The following Galois theory argument shows thatthisexpression isapolynomialandthatitisirreducible. Consider the polynomial ring R = Q[x,y,d,u1,v1,...,uk,vk]. The field of fractions of R is the field K = Q(x,y,d,u1,v1,...,uk,vk) of rational functions in all unknowns. Adjoining the square roots in (3) to K gives an algebraic field extension L of degree 2k over K. The Galois group of the extension L/K is (Z/2Z)k, and the product in (5) is over the orbit of the element d− k (x−u )2 +(y −v )2 of L under the action of the i=1 i i Galoisgroup. Thus this product in(5) lies inthegroundfield K. Moreover, each factor P p in the product is integral over R, and therefore the product lies in the polynomial ring R. To see that this polynomial is irreducible, it suffices to observe that no proper subproduct of the right hand side in (5) lies in the ground field K. The statement degree at most 2k is the crux in Lemma 2.1. Indeed, the degree in (x,y) and can be strictly smaller than 2k as the case of the classical ellipse (k = 2) demonstrates. When evaluating the product (5) some unexpected cancellations may occur. This phenomenon happens for all even k, as we shall see later in this section. We now turn to the matrix representation promised by Theorem 1.1. We recall the following standard definition from matrix theory (e.g., [HJ94]). Let A be a real m×m-matrix and B a real n×n-matrix. The tensor sum of A and B is the mn×mn matrix A⊕B := A⊗I +I ⊗B. The tensor sum of square matrices is an associative n m operation which is not commutative. For instance, for three matrices A,B,C we have A⊕B ⊕C = A⊗I ⊗I + I ⊗B ⊗I + I ⊗I ⊗C. Here ⊗ denotes the tensor product, which is also associative but not commutative. Tensor products andtensor sums of matrices arealso known as Kronecker products and Kronecker sums [Bel97,HJ94]. Tensor sums ofsymmetric matrices canbediagonalized by treating the summands separately: Lemma 2.2. Let M1,...,Mk be symmetric matrices, U1,...,Uk orthogonal matrices, and Λ1,...,Λk diagonal matrices such that Mi = Ui ·Λi ·UiT for i = 1,...,k. Then (U1 ⊗···⊗Uk)T ·(M1 ⊕···⊕Mk)·(U1 ⊗···⊗Uk) = Λ1 ⊕···⊕Λk. In particular, the eigenvalues of the tensor sum M1 ⊕ M2 ⊕ ··· ⊕ Mk are the sums λ1 +λ2 +···+λk where λ1 is any eigenvalue of M1, λ2 is any eigenvalue of M2, etc. The proof of this lemma is an exercise in (multi)-linear algebra. We are now pre- pared to state our formula for the explicit determinantal representation of the k-ellipse. Theorem 2.3. Given points (u1,v1),...,(uk,vk) in R2, we define the 2k ×2k matrix L (x,y) := d·I + x−u1 y −v1 ⊕ ··· ⊕ x−uk y −vk (6) k 2k y −v1 −x+u1 y −vk −x+uk (cid:20) (cid:21) (cid:20) (cid:21) 4 which is affine in x,y and d. Then the k-ellipse has the determinantal representation p (x,y) = detL (x,y). (7) k k The convex region bounded by the k-ellipse is defined by the following matrix inequality: E = (x,y) ∈ R2 : L (x,y) (cid:23) 0 . (8) k k Proof. Consider the 2×2 matr(cid:8)ix that appears as a tensor s(cid:9)ummand in (6): x−u y −v i i . y −v −x+u i i (cid:20) (cid:21) A computation shows that this matrix is orthogonally similar to (x−u )2 +(y −v )2 0 i i . 0 − (x−u )2 +(y −v )2 (cid:20)p i i (cid:21) These computations take place in the fieldpL which was considered in the proof of Lemma 2.1 above. Lemma 2.2 is valid over any field, and it implies that the matrix L (x,y) is orthogonally similar to a 2k ×2k diagonal matrix with diagonal entries k k d + (−1)σi (x−u )2 +(y −v )2, σ ∈ {0,1}. (9) i i i i=1 X p The desired identity (7) now follows directly from(5) andthe fact that thedeterminant of a matrix is the product of its eigenvalues. For the characterization of the convex set E , notice that positive semidefiniteness of L (x,y) is equivalent to nonnegativity k k of all the eigenvalues (9). It suffices to consider the smallest eigenvalue, which equals k d − (x−u )2 +(y −v )2. i i i=1 Xp Indeed, this quantity is nonnegative if and only if the point (x,y) lies in E . k Proof of Theorem 1.1. The assertions in the second and third sentence have just been proved in Theorem 2.3. What remains to be shown is the first assertion concerning the degree of p (x,y) as a polynomial in (x,y). To this end, we consider the univariate k polynomial g(t) := p (tcosθ,tsinθ) where θ is a generic angle. We must prove that k 2k if k is odd, deg g(t) = t 2k − k if k is even. ( k/2 (cid:0) (cid:1) The polynomial g(t) is the determinant of t(cid:0)he (cid:1)symmetric 2k ×2k-matrix cosθ sinθ cosθ sinθ L (tcosθ,tsinθ) = t· ⊕···⊕ + C . (10) k sinθ −cosθ sinθ −cosθ k (cid:18)(cid:20) (cid:21) (cid:20) (cid:21)(cid:19) 5 The matrix C does not depend on t. We now define the 2k ×2k orthogonal matrix k cos(θ/2) −sin(θ/2) U := V ⊗···⊗V where V := , sin(θ/2) cos(θ/2) ktimes (cid:20) (cid:21) and we note the mat|rix id{zentity} cosθ sinθ 1 0 VT · ·V = . sinθ −cosθ 0 −1 (cid:20) (cid:21) (cid:20) (cid:21) Pre- and post-multiplying (10) by UT and U, we find that 1 0 1 0 UT ·L (tcosθ,tsinθ)·U = t· ⊕···⊕ + UT ·C ·U. k 0 −1 0 −1 k (cid:18)(cid:20) (cid:21) (cid:20) (cid:21)(cid:19) Ek The determinant of this matrix is our u|nivariate pol{yznomial g(t). }The matrix E is a k diagonal matrix of dimension 2k ×2k. Its diagonal entries are obtained by summing k copies of −1 or +1 in all 2k possible ways. None of these sums are zero when k is odd, and precisely k of these sums are zero when k is even. This shows that the rank k/2 of E is 2k when k is odd, and it is 2k − k when k is even. We conclude that the k (cid:0) (cid:1) k/2 univariate polynomial g(t) = det t·E +UTC U has the desired degree. k (cid:0) (cid:1) k (cid:0) (cid:1) 3 More Pictures and Some Semidefinite Aspects In this section we examine the geometry of the k-ellipse, we look at some pictures, and we discuss aspects relevant to the theory of semidefinite programming. In Figure 1 several k-ellipses are shown, for k = 3,4,5. One immediately observes that, in contrast to the classical circle and ellipse, a k-ellipse does not necessarily contain the foci in its interior. The interior E of the k-ellipse is a sublevel set of the convex function k k (x,y) 7→ (x−u )2 +(y −v )2. (11) i i i=1 Xp This function is strictly convex in any region excluding the foci {(u ,v )}k , provided i i i=1 the foci are not collinear [Sek99]. This explains why the k-ellipse is a convex curve. In order for E to be nonempty, it is necessary and sufficient that the radius d be greater k than or equal to the global minimum d of the convex function (11). ⋆ The point (x ,y ) at which the global minimum d is achieved is called the Fermat- ⋆ ⋆ ⋆ Weber point of the foci. This point minimizes the sum of the distances to the k given points (u ,v ), and it is of importance in the facility location problem. See i i [Baj88, CT90, Kul77], and [Stu84] for a historical reference. For a given set of foci, we 6 Figure 3: A pencil of 3-ellipses with fixed foci (the three black dots) and different radii. These convex curves are always smooth unless they contain one of the foci. can vary the radius d, and this results in a pencil of confocal k-ellipses, as in Figure 3. The sum of distances function (11) is differentiable everywhere except at the (u ,v ), i i where the square root function has a singularity. As a consequence, the k-ellipse is a smooth convex curve, except when that curve contains one of the foci. An algebraic geometer would argue that there is more to the k-ellipse than meets the eye in Figures 1 and 3. We define the algebraic k-ellipse to be the Zariski closure of the k-ellipse, or, equivalently, the zero set of the polynomial p (x,y). The algebraic k k-ellipse is an algebraic curve, and it can be considered in either the real plane R2, in the complex plane C2, or (even better) in the complex projective plane P2. C Figure 2 shows an algebraic 5-ellipse. In that picture, the actual 5-ellipse is the tiny convex curve in the center. It surrounds only one of the five foci. For a less dizzying illustration see Figure 4. That picture shows an algebraic 3- ellipse. Thecurvehasdegreeeight, anditisgivenalgebraicallybythe8×8-determinant displayed in the Introduction. We see that the set of real points on the algebraic 3- ellipse consists of four ovals, corresponding to the equations (x−u1)2 +(y −v1)2 ± (x−u2)2 +(y −v2)2 ± (x−u3)2 +(y −v3)2 = d. Thpus Figure 4 visualizes thepGalois theory argument ipn the proof of Lemma 2.1. If we regard the radius d as an unknown, in addition to the two unknowns x and y, then the determinant in Theorem 1.1 specifies an irreducible surface {p (x,y,d) = 0} k 7 Figure 4: The Zariski closure of the 3-ellipse is an algebraic curve of degree eight. in three-dimensional space. That surface has degree 2k. For an algebraic geometer, this surface would live in complex projective 3-space CP3, but we are interested in its points in realaffine 3-space R3. Figure 5 shows this surface fork = 3. The bowl-shaped convex branch near the top is the graph of the sum of distances function (11), while each of the other three branches is associated with a different combination of signs in the product (5). The surface has a total of 2k = 8 branches, but only the four in the half-space d ≥ 0 are shown, as it is symmetric with respect to the plane d = 0. Note that the Fermat-Weber point (x ,y ,d ) is a highly singular point of the surface. ∗ ∗ ∗ The time has now come for us to explain the adjective “semidefinite” in the title of this paper. Semidefinite programming (SDP) is a widely used method in convex op- timization. Introductory references include [VB96, WSV00]. An algebraic perspective was recently given in [NRS06]. The problem of SDP is to minimize a linear functional over the solution set of a linear matrix inequality (LMI). An example of an LMI is x·A +y ·B +d·I +C˜ (cid:23) 0. (12) k k 2k k Here C˜ is the matrix gotten from C by setting d = 0, so that C = d·I +C˜ . If d is k k k 2k k a fixed positive real number then the solution set to the LMI (12) is the convex region E bounded by the k-ellipse. If d is an unknown then the solution set to the LMI (12) k is the epigraph of (11), or, geometrically, the unbounded 3-dimensional convex region interior to thebowl-shaped surfaceinFigure5. The bottompoint ofthat convex region is the Fermat-Weber point (x ,y ,d ), and it can be computed by solving the SDP ∗ ∗ ∗ Minimize d subject to (12). (13) 8 Figure 5: The irreducible surface {p3(x,y,d) = 0}. Taking horizontal slices gives the pencil of algebraic 3-ellipses for fixed foci and different radii d, as shown in Figure 3. Similarly, for fixed radius d, the k-ellipse is the set of all solutions to Minimize αx+βy subject to (12) (14) where α,β run over R. This explains the term semidefinite representation in our title. While the Fermat-Weber SDP (13) has only three unknowns, it has the serious dis- advantagethatthematrices areexponentially large(size2k). Forcomputing (x ,y ,d ) ∗ ∗ ∗ in practice, it is better to introduce slack variables d1,d2,...,dk, and to solve k d +x−a y −b Minimize d subject to i i i (cid:23) 0 (i = 1,...,k). (15) i y −b d −x+a i i i i=1 (cid:20) (cid:21) X This system can be written as single LMI by stacking the 2×2-matrices to form a block matrix of size 2k×2k. The size of the resulting LMI is linear in k while the size of the LMI (13) is exponential in k. If we take the LMI (15) and add the linear constraint d1 +d2 +···+dk = d, for some fixed d > 0, then this furnishes a natural and concise lifted semidefinite representation of our k-ellipse. Geometrically, the representation expresses E as the projection of a convex set defined by linear matrix inequalities in a k higher-dimensional space. Theorem 1.1 solves the algebraic LMI elimination problem corresponding to this projection, but at the expense of an exponential increase in size, which is due to the exponential growing of degrees of k-ellipses. 9 Our last topic in this section is the relationship of the k-ellipse to the celebrated work of Helton and Vinnikov [HV03] on LMI representations of planar convex sets, which led to the resolution of the Lax conjecture in [LPR05]. A semialgebraic set in the plane is called rigidly convex if its boundary has the property that every line passing through its interior intersects the Zariski closure of the boundary only in real points. Helton and Vinnikov [HV03, Thm. 2.2] proved that a plane curve of degree d has an LMI representation by symmetric d × d matrices if and only if the region bounded by this curve is rigidly convex. In arbitrary dimensions, rigid convexity holds for every region bounded by a hypersurface that is given by an LMI representation, but the strong form of the converse, where the degree of the hypersurface precisely matches the matrix size of the LMI, is only valid in two dimensions. It follows from the LMI representation in Theorem 1.1 that the region bounded by a k-ellipse is rigidly convex. Rigid convexity can be seen in Figures 4 and 2. Every line that passes through the interior of the 3-ellipse intersects the algebraic 3-ellipse in eight real points, and lines through the 5-ellipse meet its Zariski closure in 32 real points. Combining our Theorem 1.1 with the Helton-Vinnikov Theorem, we conclude: Corollary 3.1. The k-ellipse is rigidly convex. If k is odd, it can be represented by an LMI of size 2k, and if k is even, it can be represented as by LMI of size 2k − k . k/2 (cid:0) (cid:1) Wehavenotfoundyetanexplicit representation ofsize2k− k whenk iseven and k/2 k ≥ 4. For the classical ellipse (k = 2), the determinantal representation (2) presented (cid:0) (cid:1) in the Introduction has size 4×4, while Corollary 3.1 guarantees the existence of a 2×2 representation. One such representation of the ellipse with foci (u1,v1) and (u2,v2) is: 2 x−u2 y−v2 d +(u1−u2)(2x−u1−u2)+(v1−v2)(2y−v1−v2) ·I2 + 2d· (cid:23) 0. y−v2 −x+u2 (cid:20) (cid:21) (cid:0) (cid:1) Notice that in this LMI representation of the ellipse, the matrix entries are linear in x and y, as required, but they are quadratic in the radius parameter d and the foci u ,v . i i What is the nicest generalization of this representation to the k-ellipse for k even ? 4 Generalizations The semidefinite representation of the k-ellipse we have found in Theorem 1.1 can be generalizedinseveraldirections. Ourfirstgeneralizationcorrespondstotheinclusionof arbitrarynonnegativeweightsforthedistances, whilethesecondoneextendstheresults from plane curves to higher dimensions. The resulting geometric shapes are known Tschirnhaus’sche Eifl¨achen (or “egg surfaces”) in the classical literature [Nagy50]. 10