Let $Q$ an unknown quadratic form in an $n$-dimensional space. You can ask questions "What is $Q(v)$?"

What is the least number of questions you need to ask to check if $Q$ is positive definite?

Attempt Consider a quadratic form $$Q(x)=x_1^2+x_2^2+...+x_s^2-x_{s+1}^2-...-x_r^2$$ You need to ask at least $r$ questions to make a definite conclusion about $Q$. But how can I prove that $r$ is enough for any form? True that any quadratic form can be transformed into the form above, but we cannot make transformations

  • $\begingroup$ What exactly is a question? Do you mean how many points we can sample? $\endgroup$ – Osama Ghani Jun 5 '18 at 15:16
  • 3
    $\begingroup$ One: is this positive definite? $\endgroup$ – Joel Jun 5 '18 at 15:18
  • 1
    $\begingroup$ Ask for the values at a basis of eigenvectors. $\endgroup$ – user564402 Jun 5 '18 at 15:18
  • $\begingroup$ You need to compute $n$ leading principal minors. Would that be answering $n$ questions? Alternatively, you need to perform $n$ elementary row operations and check the sign of a number after each operation. I don't think the qualifier "at least" makes a lot of sense in this context. $\endgroup$ – Calculon Jun 5 '18 at 15:18
  • $\begingroup$ A quadratic form has $n(n+1)/2$ independent coefficients which you can compute from as many evaluations of $Q$, by solving a linear system. $\endgroup$ – Yves Daoust Jun 5 '18 at 15:26

Makes all the difference whether the answer for a vector is just (positive/negative) or if we are told a numeric value; looking at the wording again, apparently we get a numeric value.

My first guess is the triangular number $n(n+1)/2.$ ADDED: yes, that is correct. Take a standard basis. First check $Q$ at all points with just a single $1,$ other entries $0.$ This gives the diagonal of the Gram matrix. Then check $Q$ on all vectors with exactly two entries equal to $1$ and otherwise $0.$ Those give all the off diagonal entries of the Gram matrix.

in dimension 2. Suppose the actual form is $x^2 + 200 xy + 9999 y^2.$ I ask for the form at $(1,0)$ and am told $1.$ Good start. I ask for the form at $(0,1)$ and am told $9999.$ In order to find out the $200$ I can ask at $(1,1).$ I am told $10200.$ One version of the parallelogram law is $$ 2 \langle v,w \rangle = Q(v+w) - Q(v) - Q(w) $$ so i have, in this basis, Gram matrix $$ \left( \begin{array}{cc} 1 & 100 \\ 100 & 9999 \end{array} \right) $$
which is indefinite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.