Source author record

Cynthia Vinzant

Cynthia Vinzant appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

19works
15topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2022arXiv

Determinantal representations and the image of the principal minor map

In this paper we explore determinantal representations of multiaffine polynomials and consequences for the image of various spaces of matrices under the principal minor map. We show that a real multiaffine polynomial has a definite Hermitian determinantal representation if and only if all of its so-called Rayleigh differences factor as Hermitian squares and use this characterization to conclude that the image of the space of Hermitian matrices under the principal minor map is cut out by the orbit of finitely many equations and inequalities under the action of $({\rm SL}_2(\mathbb{R}))^{n} \rtimes S_{n}$. We also study such representations over more general fields with quadratic extensions. Factorizations of Rayleigh differences prove an effective tool for capturing subtle behavior of the principal minor map. In contrast to the Hermitian case, we give examples to show for any field $\mathbb{F}$, there is no finite set of equations whose orbit under $({\rm SL}_2(\mathbb{F}))^{n} \rtimes S_{n}$ cuts out the image of $n\times n$ matrices over $\mathbb{F}$ under the principal minor map for every $n$.

preprint2021arXiv

Positively Hyperbolic Varieties, Tropicalization, and Positroids

A variety of codimension $c$ in complex affine space is called positively hyperbolic if the imaginary part of any point in it does not lie in any positive linear subspace of dimension $c$. Positively hyperbolic hypersurfaces are defined by stable polynomials. We give a new characterization of positively hyperbolic varieties using sign variations, and show that they are equivalently defined by being hyperbolic with respect to the positive part of the Grassmannian, in the sense of Shamovich and Vinnikov. We prove that positively hyperbolic projective varieties have tropicalizations that are locally subfans of the type $A$ hyperplane arrangement defined by $x_i = x_j$, in which the maximal cones satisfy a non-crossing condition. This gives new proofs of some results of Choe--Oxley--Sokal--Wagner and Brändén on Newton polytopes and tropicalizations of stable polynomials. We settle the question of which tropical varieties can be obtained as tropicalizations of positively hyperbolic varieties in the case of tropical toric varieties, constant-coefficient tropical curves, and Bergman fans. Along the way, we also give a new characterization of positroids in terms of a non-crossing condition on their Bergman fans.

preprint2020arXiv

Sparse moments of univariate step functions and allele frequency spectra

We study the univariate moment problem of piecewise-constant density functions on the interval $[0,1]$ and its consequences for an inference problem in population genetics. We show that, up to closure, any collection of $n$ moments is achieved by a step function with at most $n-1$ breakpoints and that this bound is tight. We use this to show that any point in the $n$th coalescence manifold in population genetics can be attained by a piecewise constant population history with at most $n-2$ changes. Both the moment cones and the coalescence manifold are projected spectrahedra and we describe the problem of finding a nearest point on them as a semidefinite program.

preprint2018arXiv

Generalized eigenvalue methods for Gaussian quadrature rules

A quadrature rule of a measure $μ$ on the real line represents a convex combination of finitely many evaluations at points, called nodes, that agrees with integration against $μ$ for all polynomials up to some fixed degree. In this paper, we present a bivariate polynomial whose roots parametrize the nodes of minimal quadrature rules for measures on the real line. We give two symmetric determinantal formulas for this polynomial, which translate the problem of finding the nodes to solving a generalized eigenvalue problem.

preprint2016arXiv

Computing complex and real tropical curves using monodromy

Tropical varieties capture combinatorial information about how coordinates of points in a classical variety approach zero or infinity. We present algorithms for computing the rays of a complex and real tropical curve defined by polynomials with constant coefficients. These algorithms rely on homotopy continuation, monodromy loops, and Cauchy integrals. Several examples are presented which are computed using an implementation that builds on the numerical algebraic geometry software Bertini.

preprint2015arXiv

A small frame and a certificate of its injectivity

We present a complex frame of eleven vectors in 4-space and prove that it defines injective measurements. That is, any rank-one $4\times 4$ Hermitian matrix is uniquely determined by its values as a Hermitian form on this collection of eleven vectors. This disproves a recent conjecture of Bandeira, Cahill, Mixon, and Nelson. We use algebraic computations and certificates in order to prove injectivity.

preprint2015arXiv

Computing Hermitian determinantal representations of hyperbolic curves

Every real hyperbolic form in three variables can be realized as the determinant of a linear net of Hermitian matrices containing a positive definite matrix. Such representations are an algebraic certificate for the hyperbolicity of the polynomial and their existence has been proved in several different ways. However, the resulting algorithms for computing determinantal representations are computationally intensive. In this note, we present an algorithm that reduces a large part of the problem to linear algebra and discuss its numerical implementation.

preprint2014arXiv

A real stable extension of the Vamos matroid polynomial

In 2004, Choe, Oxley, Sokal and Wagner established a tight connection between matroids and multiaffine real stable polynomials. Recently, Branden used this theory and a polynomial coming from the Vamos matroid to disprove the generalized Lax conjecture. Here we present a 10-element extension of the Vamos matroid and prove that its basis generating polynomial is real stable (i.e. that the matroid has the half-plane property). We do this via large sums of squares computations and a criterion for real stability given by Wagner and Wei. Like the Vamos matroid, this matroid is not representable over any field and no power of its basis generating polynomial can be written as the determinant of a linear matrix with positive semidefinite Hermitian forms.

preprint2014arXiv

Quartic Spectrahedra

Quartic spectrahedra in 3-space form a semialgebraic set of dimension 24. This set is stratified by the location of its ten nodes. There are twenty maximal strata, identified recently by Degtyarev and Itenberg, via the global Torelli Theorem for real K3 surfaces. We here give a new proof that is self-contained and algorithmic. This involves extending Cayley's characterization of quartic symmetroids, by the property that the branch locus of the projection from a node consists of two cubic curves. This paper represents a first step towards the classification of all spectrahedra of a given degree and dimension.

preprint2013arXiv

An algebraic characterization of injectivity in phase retrieval

A complex frame is a collection of vectors that span $\mathbb{C}^M$ and define measurements, called intensity measurements, on vectors in $\mathbb{C}^M$. In purely mathematical terms, the problem of phase retrieval is to recover a complex vector from its intensity measurements, namely the modulus of its inner product with these frame vectors. We show that any vector is uniquely determined (up to a global phase factor) from $4M-4$ generic measurements. To prove this, we identify the set of frames defining non-injective measurements with the projection of a real variety and bound its dimension.

preprint2013arXiv

Computing Linear Matrix Representations of Helton-Vinnikov Curves

Helton and Vinnikov showed that every rigidly convex curve in the real plane bounds a spectrahedron. This leads to the computational problem of explicitly producing a symmetric (positive definite) linear determinantal representation for a given curve. We study three approaches to this problem: an algebraic approach via solving polynomial equations, a geometric approach via contact curves, and an analytic approach via theta functions. These are explained, compared, and tested experimentally for low degree instances.

preprint2013arXiv

Hyperbolic polynomials, interlacers, and sums of squares

Hyperbolic polynomials are real polynomials whose real hypersurfaces are nested ovaloids, the inner most of which is convex. These polynomials appear in many areas of mathematics, including optimization, combinatorics and differential equations. Here we investigate the special connection between a hyperbolic polynomial and the set of polynomials that interlace it. This set of interlacers is a convex cone, which we write as a linear slice of the cone of nonnegative polynomials. In particular, this allows us to realize any hyperbolicity cone as a slice of the cone of nonnegative polynomials. Using a sums of squares relaxation, we then approximate a hyperbolicity cone by the projection of a spectrahedron. A multiaffine example coming from the Vamos matroid shows that this relaxation is not always exact. Using this theory, we characterize the real stable multiaffine polynomials that have a definite determinantal representation and construct one when it exists.

preprint2013arXiv

The Entropic Discriminant

The entropic discriminant is a non-negative polynomial associated to a matrix. It arises in contexts ranging from statistics and linear programming to singularity theory and algebraic geometry. It describes the complex branch locus of the polar map of a real hyperplane arrangement, and it vanishes when the equations defining the analytic center of a linear program have a complex double root. We study the geometry of the entropic discriminant, and we express its degree in terms of the characteristic polynomial of the underlying matroid. Singularities of reciprocal linear spaces play a key role. In the corank-one case, the entropic discriminant admits a sum of squares representation derived from the discriminant of a characteristic polynomial of a symmetric matrix.

preprint2012arXiv

Determinantal representations of hyperbolic plane curves: An elementary approach

If a real symmetric matrix of linear forms is positive definite at some point, then its determinant is a hyperbolic hypersurface. In 2007, Helton and Vinnikov proved a converse in three variables, namely that every hyperbolic plane curve has a definite real symmetric determinantal representation. The goal of this paper is to give a more concrete proof of a slightly weaker statement. Here we show that every hyperbolic plane curve has a definite determinantal representation with Hermitian matrices. We do this by relating the definiteness of a matrix to the real topology of its minors and extending a construction of Dixon from 1902. Like Helton and Vinnikov's theorem, this implies that every hyperbolic region in the plane is defined by a linear matrix inequality.

preprint2011arXiv

Edges of the Barvinok-Novik orbitope

Here we study the k^th symmetric trigonometric moment curve and its convex hull, the Barvinok-Novik orbitope. In 2008, Barvinok and Novik introduce these objects and show that there is some threshold so that for two points on S^1 with arclength below this threshold, the line segment between their lifts on the curve form an edge on the Barvinok-Novik orbitope and for points with arclenth above this threshold, their lifts do not form an edge. They also give a lower bound for this threshold and conjecture that this bound is tight. Results of Smilansky prove tightness for k=2. Here we prove this conjecture for all k.

preprint2011arXiv

Lower Bounds for Optimal Alignments of Binary Sequences

In parametric sequence alignment, optimal alignments of two sequences are computed as a function of the penalties for mismatches and spaces, producing many different optimal alignments. Here we give a 3/(2^{7/3}π^{2/3})n^{2/3} +O(n^{1/3} \log n) lower bound on the maximum number of distinct optimal alignment summaries of length-n binary sequences. This shows that the upper bound given by Gusfield et. al. is tight over all alphabets, thereby disproving the "square root of n conjecture". Thus the maximum number of distinct optimal alignment summaries (i.e. vertices of the alignment polytope) over all pairs of length-n sequences is Theta(n^{2/3}).

preprint2011arXiv

Quartic Curves and Their Bitangents

A smooth quartic curve in the complex projective plane has 36 inequivalent representations as a symmetric determinant of linear forms and 63 representations as a sum of three squares. These correspond to Cayley octads and Steiner complexes respectively. We present exact algorithms for computing these objects from the 28 bitangents. This expresses Vinnikov quartics as spectrahedra and positive quartics as Gram matrices. We explore the geometry of Gram spectrahedra and we find equations for the variety of Cayley octads. Interwoven is an exposition of much of the 19th century theory of plane quartics.

preprint2011arXiv

Real radical initial ideals

We explore the consequences of an ideal I of real polynomials having a real radical initial ideal, both for the geometry of the real variety of I and as an application to sums of squares representations of polynomials. We show that if in_w(I) is real radical for a vector w in the tropical variety, then w is in the logarithmic set of the real variety. We also give algebraic sufficient conditions for w to be in the logarithmic limit set of a more general semialgebraic set. If in addition the entries of w are positive, then the corresponding quadratic module is stable. In particular, if in_w(I) is real radical for some positive vector w then the set of sums of squares modulo I is stable. This provides a method for checking the conditions for stability given by Powers and Scheiderer.

preprint2011arXiv

The central curve in linear programming

The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal of the central curve, thereby answering a question of Bayer and Lagarias. These invariants, along with the degree of the Gauss image of the curve, are expressed in terms of the matroid of the input matrix. Extending work of Dedieu, Malajovich and Shub, this yields an instance-specific bound on the total curvature of the central path, a quantity relevant for interior point methods. The global geometry of central curves is studied in detail.