Computing symmetric determinantal representations
Justin Chen, Papri Dey · Journal of Software for Algebra and Geometry · 2020
We introduce the DeterminantalRepresentations package for Macaulay2, which computes definite symmetric determinantal representations of real polynomials.We focus on quadrics and plane curves of low degree (i.e., cubics and quartics).Our algorithms are geared towards speed and robustness, employing linear algebra and numerical algebraic geometry, without genericity assumptions on the polynomials. INTRODUCTION.The problem of representing a polynomial as the determinant of a linear matrix pencil is classical; see [Beauville 2000;Buckley and Košir 2007; Dickson 1921;Dixon 1902;Helton and Vinnikov 2007].A polynomial f ∈ [ޒx 1 , . . ., x n ] of degree d (not necessarily homogeneous) is called determinantal if f is the determinant of a matrix with linear entries; i.e., there exist matricesto give a determinantal representation of f of size d.If the matrices A i can be chosen to be all symmetric (resp., hermitian), then the determinantal representation is called symmetric (resp., hermitian).The determinantal representation is called definite if A 0 is definite, and monic if A 0 = I d is the identity matrix.Computing definite symmetric (resp., hermitian) determinantal representations of a polynomial is known as the determinantal representation problem in convex algebraic geometry [Parrilo 2013].It has generated interest in the optimization community due to its connection with the problem of determining definite linear matrix inequality (LMI) representable sets ([Helton and Vinnikov 2007;Vinnikov 2012]).The problem of characterizing the LMI-representable subsets of ޒ n (i.e., spectrahedra) can be solved by characterizing determinantal polynomials, which leads to the generalized Lax conjecture [Lewis et al. 2005].Throughout this article we focus mainly on homogeneous polynomials, typically in three variables, corresponding to projective plane curves (though internally via dehomogenization, it suffices to compute determinantal representations for bivariate polynomials).By a celebrated theorem of Helton and Vinnikov [2007] (see also [Lewis et al. 2005]), all hyperbolic polynomials in three variables admit definite symmetric determinantal representations.When n ≥ 4, a general homogeneous polynomial of degree d in n variables does not admit any determinantal representation of size d (except for (n, d) = (4, 3)).We abbreviate the terms "monic symmetric (resp., hermitian) determinantal representation" to MSDR (resp., MHDR).