When a system of real quadratic equations has a solution (Q2143674)

Let for \(i=1,\dots, m,\) \(Q_i\) be real symmetric \(n\times n\) matrices, \(q_i(x)=\langle Q_i x,x\rangle=x^{\mathsf{t}} Q_i x\) be the associated quadratic forms and \(\alpha_i\) be real numbers. The authors establish sufficient conditions in order that the system of \(m\) real quadratic equations \(q_i(x)=\alpha_i,\) has a real solution. By solving for \(X\) the equation \(\text{trace }Q_iX=\alpha_i\) subject to \(X\succeq 0\) -- this can be done rapidly by semidefinte programming -- it is elementary to show that it is sufficient to establish sufficient conditions for solvability of systems of equations of the form \(q_i(x)=\text{trace }Q_i.\) It is not hard to see that such a criterion should not so much depend on the \(Q_i\) per se but rather on the space only which the \(Q_i\) (supposed to be linearly independent) generate; and that the sum of the squares of the elements of an orthonormal basis with respect to the Frobenius inner product of that space is independent of the choice of the basis. The main theorem is formulated accordingly: Theorem 1.1: Assuming the above notations and supposing that for some (equivalently, for any) orthonormal basis \(A_1,\dots,A_m\) of the subspace \(\text{span}(Q_1,\dots, Q_m)\) there holds the operator norm inequality \(\|\sum_{i=1}^m A_i^2 \|_{\mathrm{op}}\leq \frac{10^{-6}}{m},\) the system of quadratic equations \(q_i(x)=\text{trace }Q_i,\) \(i=1,\dots, m\) has a solution \(x\in \mathbb{R}^n.\) (The real \(10^{-6}\) can probably be replaced by a better value but this problem is not investigated.) The condition of Theorem 1.1 can be checked in polynomial time and is satisfied for example for random \(q_i,\) provided \(m\leq \gamma \sqrt{n},\) for some absolute constant \(\gamma.\) The authors also give sufficient conditions, similar to the above, and with similar proof for the nontrivial solvability of homogeneous systems \(q_i(x)=0,\) \(i=1,\dots,m\) of quadratic equations, so we concentrate on giving details for the proof of T1.1. Theorem 1.1 is deduced from the following theorem where \(t\) is short for \((\tau_1,\dots,\tau_m),\) \(Q(t)= I- \mathbf i\sum_{i=1}^m \tau_i Q_i,\) and \(\det^{-1/2} Q(t)\) is a branch that has value 1 at \(t=0.\) (\(\mathbf i =\sqrt{-1}\)) Theorem 2.1: Let \(\alpha_1,\dots,\alpha_m\) be real numbers and \(q_i(x)=\frac{1}{2}\langle Q_i x, x\rangle \) quadratic forms. Provided that \( \int_{\mathbb R^m} \det^{-1/2} Q(t) \exp(-\mathbf i\sum_{i=1}^m \alpha_i \tau_i) dt\) is nonzero and absolutely convergent, the system \(q_i(x)=\alpha_i\) has a solution. The connection between the hypothesis and the conclusion of this theorem can be glimpsed at via Lemma 3.1 which says that for \(\sigma>0,\) \(\sigma^m \int_{\mathbb R^m} \exp(-\frac{\sigma^2}{2} \sum_{i=1}^m (q_i(x)-\alpha_i)^2) e^{-\frac{\|x\|^2}{2}} dx = (2\pi)^{\frac{n-m}{2}} \int_{\mathbb R^m} \det^{-1/2} Q(t) \exp(-\mathbf i\sum_{i=1}^m \alpha_i \tau_i) e^{-\frac{\|t\|^2}{2\sigma^2}} dt.\) The hypothesis of Theorem 2.1 tells us that as \(\sigma \rightarrow \infty\) the right hand side goes to a value \(\neq 0.\) Supposing the system \(q_i(x)=\alpha_i\) has no solution it is shown that the left hand side goes to 0. So the proof is by contradiction and thus we have the interesting case of a paper which proves that the existence of a solution can (in favorable circumstances) be rapidly established while it gives no clue of where to find the solution (rapidly). For the deduction of Theorem 1.1 from 2.1 a translation of Theorem 2.1 to polar coordinates is made: Let \(w=(w_1,\dots,w_m)\in \mathbb S^{m-1}\) and define \(A(w)=\sum_{i=1}^m w_i A_i,\) where \(A_1,.\dots,A_m\) is an orthonormal basis of \(\text{span}(Q_1,\dots, Q_m)\) and denote by \(\lambda_j(w)\) the eigenvalues of of \(A(w)\) for \(w\in \mathbb S^{m-1}.\) For getting to Theorem 1.1 it is sufficient to show that \(\int_{\mathbb S^{m-1}} ( \int_0^\infty \tau^{m-1} \det^{-1/2}(I-\mathbf i\tau A(w)) \exp(-\frac{\mathbf i\tau}{2} \text{trace} A(w)) d\tau )dw\neq 0. \) This is done by splitting the inner integral into two parts as \(\int_{5\sqrt{m}}^\infty \dots\) and \(\int_0^{5\sqrt{m}} \dots\) and showing that the contribution of the first part is negligible, while the contribution of the second part follows from eigenvalue estimates. The possibility of such an approach comes from noting that \(\det^{-1/2}(I-\mathbf i\tau A(w)) \exp(-\frac{\mathbf i\tau}{2} \text{trace} A(w))= \exp ( \frac{1}{2}\sum_{k=2}^\infty \frac{(\tau \mathbf i )^k}{k} \sum_{j=1}^n \lambda_j^k(w)).\) For carrying out this program, in Section 4 many eigenvalue estimates are given. As an example we mention the expectation inequality \(\mathbb E(\sum_{j=1}^n \lambda_j^3(w))^2 \leq \frac{120}{(m+2)(m+4)}\|\sum_{i=1}^m A_i^2\|_{\mathrm{op}}.\) Relationships between the operator norm, the Hilbert Schmidt or Frobenius norm and the Schatten 4 norm are also presented. In Section 5 a number of integrals are estimated, and in the final Section 6 the non-zeroness of above integral is obtained by applying probabilistic language, viewing the integral above essentially as an expectation value, and using the Markov inequality and a concentration inequality adapted for the Schatten 4 norm. In Section 2 an outline of the proof of Theorem 1.1 is given, facilitating thus following the rather involved ideas, but in Section 6 the reviewer thinks to have spotted a number of mathematically significant typos. For example in both equations (6.2) and (6.5) and after (6.7) the factor \(\tau^{m-1}\) in the inner integrals seems to be missing and the symbol \(\sum_{i=1}^m\) should be cancelled. In (6.7) \(A\) should be replaced by \(A(w).\) Well, refereeing never was nor ever will be a glamorous activity \ldots\ in particular as long as it remains anonymous. For the `well-known' facts used in Lemma 3.1 the reviewer relegates the reader e.g. to Chapter 2 of \textit{E. F. Beckenbach} and \textit{R. Bellman} [Inequalities. Berlin-Göttingen-Heidelberg: Springer-Verlag (1961; Zbl 0097.26502)] and to \textit{M. J. Lighthill} [Introduction to Fourier analysis and generalised functions. Cambridge: At the University Press (1958; Zbl 0078.11203)] or \textit{S. Lang} [Real and functional analysis. 3. ed. New York: Springer-Verlag (1993; Zbl 0831.46001)], respectively.