Obstructions to determinantal representability
arXiv:1004.1382 · doi:10.1016/j.aim.2010.08.003
Abstract
There has recently been ample interest in the question of which sets can be represented by linear matrix inequalities (LMIs). A necessary condition is that the set is rigidly convex, and it has been conjectured that rigid convexity is also sufficient. To this end Helton and Vinnikov conjectured that any real zero polynomial admits a determinantal representation with symmetric matrices. We disprove this conjecture. By relating the question of finding LMI representations to the problem of determining whether a polymatroid is representable over the complex numbers, we find a real zero polynomial such that no power of it admits a determinantal representation. The proof uses recent results of Wagner and Wei on matroids with the half-plane property, and the polymatroids associated to hyperbolic polynomials introduced by Gurvits.
10 pages. To appear in Advances in Mathematics
References in corpus (4)
Cited by in corpus (37)
- Hyperbolic polynomials, interlacers, and sums of squares
- Geometry of free loci and factorization of noncommutative polynomials
- Extreme points of matrix convex sets, free spectrahedra and dilation theory
- Representing some non-representable matroids
- Livsic-type Determinantal Representations and Hyperbolicity
- Determinantal Representations and Bézoutians
- Real Fibered Morphisms and Ulrich Sheaves
- Bianalytic Maps Between Free Spectrahedra
- Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits
- Regular and positive noncommutative rational functions
- The Chow form of a reciprocal linear space
- A Note on the Hyperbolicity Cone of the Specialized Vámos Polynomial
- Spectral linear matrix inequalities
- Bianalytic free maps between spectrahedra and spectraballs
- Hyperbolic polynomials and the Kadison-Singer problem
- Determinantal representations of semi-hyperbolic polynomials
- A real stable extension of the Vamos matroid polynomial
- Hyperbolic polynomials and the Marcus-Spielman-Srivastava theorem
- Noncommutative polynomials describing convex sets
- Symmetric Determinantal Representations in Characteristic 2
- Positive Polynomials and Projections of Spectrahedra
- A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming
- A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
- Hyperbolic Secant Varieties of M-Curves
- Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations
- Smooth Hyperbolicity Cones are Spectrahedral Shadows
- Determinantal Representations and the Hermite Matrix
- A Study on a New Method of Dynamic Aperture Enlargement
- Hyperbolic plane curves near the non-singular tropical limit
- Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
- Highly symmetric matroids, the strong Rayleigh property, and sums of squares
- Extreme points of matrix convex sets and their spanning properties
- Positive Ulrich Sheaves
- Matroids on Eight Elements with the Half-plane Property and Related Concepts
- Matroids in OSCAR
- Hyperbolic Polynomials and Generalized Clifford Algebras
- Spectrahedral relaxations of hyperbolicity cones