Noncommutative polynomials describing convex sets (Q2031064)

Given a matrix \(f = (f_{ij})_{i,j=1}^\delta\) of noncommutative \(*\)-polynomials \(f_{ij} \in \mathbb{C} \langle x_1, \ldots, x_g, x_1^*, \ldots, x_g \rangle\), one can evaluate it on any tuple of square matrices \(X = (X_1, \ldots, X_g) \in M_n(\mathbb{C})^g\), resulting in another matrix \[ f(X, X^*) \in M_{n \delta}(\mathbb{C}). \] Assuming \(f(0) \neq 0\), the \emph{free invertibility set} is the family of sets \(\mathcal{K}_f = (\mathcal{K}_f(n))_{n \in \mathbb{N}}\), where \(\mathcal{K}_f(n)\) is the connected component of \(0\) of \(\{X \in M_n(\mathbb{C}) \mid \det f(X,X^*) \neq 0\}\). A free invertibility set is considered convex if each of its levels \(\mathcal{K}_f(n)\) is convex. This paper is concerned with the question of when convexity holds and how to detect it algorithmically. It was already known that convexity holds if and only if \(\mathcal{K}_f\) is a free spectrahedron [\textit{J. W. Helton} and \textit{S. McCullough}, Ann. Math. (2) 176, No. 2, 979--1013 (2012; Zbl 1260.14011)]. The main result of the present paper (Theorem 1.1) sharpens this result by showing that if convexity holds, then a representing linear matrix inequality of minimal size can be constructed in terms of the matrix pencil appearing in the Fornasini-Marchesini realization of \(f\) [\textit{E. Fornasini} and \textit{G. Marchesini}, Math. Syst. Theory 12, 59--72 (1978; Zbl 0392.93034)]. A concrete algorithm for computing such a linear matrix inequality representation is then derived from that (Section 4.2). In combination with a new Nichtsingulärstellensatz for linear matrix polynomials (Theorem 1.5), the authors also obtain an algorithm for testing whether \(\mathcal{K}_f\) is convex to begin with (Section 4.3). These results are completed by some more concrete results and examples on the free semialgebraic sets associated to single-variable noncommutative \(*\)-polynomials. The appendix provides some extensions to the case of noncommutative rational functions.