When a system of real quadratic equations has a solution

Abstract

We provide a sufficient condition for solvability of a system of real quadratic equations $p_i(x)=y_i$, $i=1,\dots ,m$, where $p_i:{\mathbb{R}}^n⟶\mathbb{R}$ are quadratic forms. By solving a positive semidefinite program, one can reduce it to another system of the type $q_i(x)={\alpha }_i$, $i=1,\dots ,m$, where $q_i:{\mathbb{R}}^n⟶\mathbb{R}$ are quadratic forms and ${\alpha }_i=\mathrm{tr}{q}_i$. We prove that the latter system has solution $x\in {\mathbb{R}}^n$ if for some (equivalently, for any) orthonormal basis $A_1,\dots ,A_m$ in the space spanned by the matrices of the forms $q_i$, the operator norm of $A_1^2+\dots +A_m^2$ does not exceed $\eta /m$ for some absolute constant $\eta >0$. The condition can be checked in polynomial time and is satisfied, for example, for random $q_i$ provided $m\le \gamma \sqrt{n}$ for an absolute constant $\gamma >0$. We prove a similar sufficient condition for a system of homogeneous quadratic equations to have a non-trivial solution. While the condition we obtain is of an algebraic nature, the proof relies on analytic tools including Fourier analysis and measure concentration.

Results are substantially strengthened, 35 pages