When a system of real quadratic equations has a solution
When a system of real quadratic equations has a solution
复制标题
DOI：
10.1016/j.aim.2022.108391
复制
发表时间：
2022-04-15
影响因子：
1.7
通讯作者：
Rudelson, Mark
中科院分区：
文献类型：
--
作者：
Barvinok, Alexander;Rudelson, Mark
给出了实二次方程组pi(X)=yi，i=1，…，m可解的一个充分条件，其中pi：Rn-+R是二次型。通过求解一个正半定规划，我们可以将它归结为另一个类型为q_i(X)=a_i，i=1，…，m的系统，其中q_i：Rn-+R为二次型，a_i=迹q_i。证明了后一类系统有解x Ern，如果对任意(等价)正交基A1，…，Am，在由齐形矩阵构成的空间中，A21+…+A2m的算子范数对某一绝对常数Eta&Gt；0不超过Eta/m.该条件可以在多项式时间内检查，并且例如对于给定绝对常数γ0的随机q1，满足该条件。我们证明了齐次二次方程组有非平凡解的一个类似的充分条件。虽然我们得到的条件是代数性质的，但证明依赖于分析工具，包括傅立叶分析和测量集中。
We provide a sufficient condition for solvability of a system of real quadratic equations pi(x) = yi, i = 1, ... , m, where pi : Rn -+ R are quadratic forms. By solving a positive semidefinite program, one can reduce it to another system of the type qi(x) = alpha i, i = 1, ... , m, where qi : Rn -+ R are quadratic forms and alpha i = trace qi. We prove that the latter system has solution x E Rn if for some (equivalently, for any) orthonormal basis A1, ... , Am in the space spanned by the matrices of the forms qi, the operator norm of A21 + ... + A2m 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 qi provided m < gamma.',/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.