When the positive semidefinite relaxation guarantees a solution to a system of real quadratic equations
share
By solving a positive semidefinite program, one can reduce a system of real quadratic equations to a system of the type q_i(x)=α_i, i=1, …, m, where q_i: R^n ⟶ R are quadratic forms and α_i=trace q_i. We prove a sufficient condition for the latter system to have a solution x ∈ R^n: assuming that the operator norms of the n × n matrices Q_i of q_i do not exceed 1, the smallest eigenvalue the m × m matrix with the (i,j)-th entry equal tr (Q_i Q_j) is at least γ n^2/3 m^2 ln n for an absolute constant γ >0. In particular, this happens when n ≫ m^6 and the forms q_i are sufficiently generic. We prove a similar sufficient condition for a homogeneous system of quadratic equations to have a non-trivial solution.
READ FULL TEXT