Obstructions to determinantal representability (Q616881)

The paper addresses questions related to the algebraic and geometric structures of affine sections of the convex cone of positive semidefinite matrices, also called linear matrix inequalities (LMIs) in the engineering literature. A polynomial \(x \in {\mathbb R}^n \mapsto p(x) \in {\mathbb R}[x]\) is a real zero (RZ) polynomial if for each \(x \in {\mathbb R}^n\) and \(t \in {\mathbb C}\), the identity \(p(tx)=0\) implies that \(t\) is real. A set is called rigidly convex (at the origin) if there is a RZ polynomial \(p\) for which the set is equal to the closure of the connected component of \(\{x \in {\mathbb R}^n: p(x)>0\}\) containing the origin. The name rigid convexity is motivated by the property that convexity of the set is not affected by small perturbations on the coefficients of \(p\). In the early 2000s, Helton and Vinnikov proved the following remarkable result. When \(n=2\), if \(p\) is an RZ polynomial of degree \(d\) such that \(p(0)=1\), then there exist real symmetric matrices \(A_1\) and \(A_2\) of size \(d\) such that \(p(x)=\mathrm{det}(I+x_1A_1+x_2A_2)\), where \(I\) is the identity matrix. It follows that the rigidly convex set attached to \(p\) is the LMI set \(\{x \in {\mathbb R}^2 : I+x_1A_1+x_2A_2 \succeq 0\}\), where ``\(\succeq 0\)'' means ``positive semidefinite''. This result entirely characterizes the algebraic and geometric structures of affine planar sections of the semidefinite cone. When \(n>2\), it is tempting to conjecture that if \(p(x)\) is an RZ polynomial of degree \(d\) such that \(p(0)=1\), then there exist symmetric matrices \(A_1,\dots,A_n\) such that \(p(x)=\mathrm{det}(I+x_1A_1+\cdots+x_nA_n)\). In this paper, combinatorics arguments (polymatroids and subspace arrangements) are used in an elegant way to prove that there are whole families of RZ polynomials for which this is not the case. The author also disproves a weaker form of the conjecture which states that if \(p\) is an RZ polynomial of degree \(d\) such that \(p(0)=1\), then there exist symmetric matrices \(A_1,\dots,A_n\) and a (sufficiently large) positive integer \(N\) such that \(p(x)^N=\mathrm{det}(I+x_1A_1+\cdots+x_nA_n)\). At the time of writing this review, simple explicit examples of RZ polynomials with no real symmetric determinantal representations are available. However, the question of LMI representations of rigidly convex sets is still open. More generally, the geometry of affine sections of the semidefinite cone is not yet well understood for dimension three or higher.