Solving determinantal systems using homotopy techniques (Q2229744)

Let \(R=K[x_1,\ldots,x_n]\) be the ring of polynomials with coefficients in the field \(K\) where \(K\) has characteristic zero. Let also \(\overline{K}\) be the algebraic closure of \(K\). Suppose that \(\mathbf{F}=[f_{i,j}]_{p\times q}\) is a polynomial matrix over \(R\) with \(p\le q\) and \(G=\{g_1,\ldots ,g_t\}\) is a set of non-zero polynomials in \(R\). Let us define \[V_p(\mathbf{F},G)=\{\mathbf{x}\in \overline{K} \ | \ \mathrm{ rank }(\mathbf F(x)) < p \ \text{ and } \ g_1(\mathbf{x})=\cdots = g_t(\mathbf{x})=0\}.\] The main interest behind the study of this algebraic set lies in the fields of polynomial optimization and computational geometry. In the paper under review, the authors provide bounds on the number of isolated points in \(V_p(\mathbf{F},G)\) depending on the maxima of the degrees in rows (resp. columns) of \(\mathbf{F}\) and design probabilistic homotopy algorithms for computing those points. These algorithms have been implemented in Magma and their performance has been evaluated via a set of benchmark polynomials.