In this manuscript, we provide foundations of properties of homogeneous polynomials such as the half-plane property, determinantal representability, being weakly determinantal, and having a spectrahedral hyperbolicity cone. One of the motivations for studying those properties comes from the ``generalized Lax conjecture'' stating that every hyperbolicity cone is spectrahedral. The conjecture has particular importance in convex optimization and has curious connections to other areas.
We take a combinatorial approach, contemplating the properties on matroids with a particular focus on operations that preserve these properties. We show that the spectrahedral representability of hyperbolicity cones and being weakly determinantal are minor-closed properties. In addition, they are preserved under passing to the faces of the Newton polytopes of homogeneous polynomials. We present a proved-to-be computationally feasible algorithm to test the half-plane property of matroids and another one for testing being weakly determinantal. Using the computer algebra system Macaulay2 and Julia, we implement these algorithms and conduct tests. We classify matroids on at most 8 elements with respect to the half-plane property and provide our test results on matroids with 9 elements. We provide 14 matroids on 8 elements of rank 4, including the Vámos matroid, that are potential candidates for the search of a counterexample for the conjecture.:1 Background 1
1.1 Some Properties of Homogeneous Polynomials . . . . . . . . . . 1
Hyperbolic Polynomials . . . . . . . . . . . . . . . . . . . . . . 1
The Half-Plane Property and Stability . . . . . . . . . . . . . . 8
Determinantal Representability . . . . . . . . . . . . . . . . . . 15
Spectrahedral Representability . . . . . . . . . . . . . . . . . . 19
1.2 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Some Operations on Matroids . . . . . . . . . . . . . . . . . . . 29
The Half-Plane Property of Matroids . . . . . . . . . . . . . . . 36
2 Some Operations 43
2.1 Determinantal Representability of Matroids . . . . . . . . . . . 43
A Criterion for Determinantal Representability . . . . . . . . . 46
2.2 Spectrahedral Representability of Matroids . . . . . . . . . . . 50
2.3 Matroid Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . 54
Newton Polytopes of Stable Polynomials . . . . . . . . . . . . . 59
3 Testing the Properties: an Algorithm 61
The Half-Plane Property . . . . . . . . . . . . . . . . . . . . . . 61
Being SOS-Rayleigh and Weak Determinantal Representability 65
4 Test Results on Matroids on 8 and 9 Elements 71
4.1 Matroids on 8 Elements . . . . . . . . . . . . . . . . . . . . . . 71
SOS-Rayleigh and Weakly Determinantal Matroids . . . . . . . 76
4.2 Matroids on 9 Elements . . . . . . . . . . . . . . . . . . . . . . 80
5 Conclusion and Future Perspectives 85
5.1 Spectrahedral Matroids . . . . . . . . . . . . . . . . . . . . . . 86
5.2 Non-negative Non-SOS Polynomials . . . . . . . . . . . . . . . 88
5.3 Completing the Classification of Matroids on 9 Elements and More 89
Bibliography 91
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:86685 |
| Date | 01 August 2023 |
| Creators | Sert, Büşra |
| Contributors | Kummer, Mario, Theobald, Thorsten, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds