Obstructions to determinantal representability
By Petter Brand'en. 2010
92 citations recorded by the source corpus.
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. 1. Representing sets with linear matrix inequalities Motivated by powerful techniques commonly used in control theory, there has recently been considerable interest in the following question. Question 1. Which subsets of R can be represented by linear matrix inequalities (LMIs)? That is, which sets Y are of the form Y = {(x1, . . . , xn) ∈ R : A0 +A1x1 + · · ·+Anxn is positive semidefinite}, (1) where A0, . . . , An are real symmetric m×m matrices? In two variables such sets were characterized by Helton and Vinnikov [7] by so called rigidly convex sets, thereby answering a question posed by Parrilo and Sturmfels [14]. We will always assume that 0 is in the interior of Y and then the existence of a LMI representation of Y is equivalent to the existence of a monic LMI representation, i.e., a representation in which A0 is the identity matrix. A polynomial p ∈ R[x1, . . . , xn] is a real zero polynomial (RZ polynomial) if for each x ∈ R and μ ∈ C p(μx) = 0 implies μ is real. (2) A set Y ⊆ R is rigidly convex (at the origin) if there is a RZ polynomial p for which Y is equal to the closure of the connected component of {x ∈ R : p(x) > 0} containing the origin. 2000 Mathematics Subject Classification. 90C22, 90C25, 52B99.
Subfields: Computational Theory and Mathematics, Numerical Analysis
View Paper: https://www.semanticscholar.org/paper/3cc37acf432b1c8d8fb31d90dec118f2dbbb8810
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Numerical Analysis
Citations in the corpus
- Polynomials with and without determinantal representations (2010, methodology): “His work contains the following results: For a certain subclass of RZ-polynomials of degree d he first proves that the existence of a determinantal representation implies the existence of a representation of size d, both in the hermitian and symmetric case.”