## D. Henrion - S. Naldi - M. Safey El Din

# Real root finding for determinants of linear matrices

created by naldi on 16 Mar 2018

modified on 18 May 2020

[

BibTeX]

*Published Paper*

**Inserted:** 16 mar 2018

**Last Updated:** 18 may 2020

**Journal:** J. Symb. Comput.

**Volume:** 74

**Pages:** 205-238

**Year:** 2016

**Doi:** https://doi.org/10.1016/j.jsc.2015.06.010

**Links:**
Publisher page

**Abstract:**

Let $A_0, A_1, \ldots, A_n$ be given square matrices of size $m$ with
rational coefficients. The paper focuses on the exact computation of one point
in each connected component of the real determinantal variety $\{X \in\mathbb{R}^n \:
:\: \det(A_0+x_1A_1+\cdots+x_nA_n)=0\}$. Such a problem finds applications
in many areas such as control theory, computational geometry, optimization,
etc. Using standard complexity results this problem can be solved using
$m^{O(n)}$ arithmetic operations. Under some genericity assumptions on the
coefficients of the matrices, we provide an algorithm solving this problem
whose runtime is essentially quadratic in ${{n+m}\choose{n}}^{3}$. We also
report on experiments with a computer implementation of this algorithm. Its
practical performance illustrates the complexity estimates. In particular, we
emphasize that for subfamilies of this problem where $m$ is fixed, the
complexity is polynomial in $n$.