# How many tests to prove quadratic form is positive definite

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

• What exactly is a question? Do you mean how many points we can sample? – Osama Ghani Jun 5 '18 at 15:16
• One: is this positive definite? – Joel Jun 5 '18 at 15:18
• Ask for the values at a basis of eigenvectors. – user564402 Jun 5 '18 at 15:18
• 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. – Calculon Jun 5 '18 at 15:18
• 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. – Yves Daoust Jun 5 '18 at 15:26

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)$$