Determining if a quadratic is always positive

Is there a quick and systematic method to find out if a quadratic equation is always positive or may have positive and negative or always negative for all values to its variables?

Say for a quadratic equation: $3x^{2}+8xy+5xz+2yz+7y^{2}+2z^{2}>0$, without drawing a graph to look at its shape, how can I find out if this equation is always more than zero or does it have negative results or is it always negative for all non-zero values into the variables?

I tried randomly substituting values into the variables but I can never be sure if I had covered all cases.

Thanks for any help.

-
If this is homework, haven't you covered such methods in class already? (Diagonalization or completing the squares, for example.) – Hans Lundmark Aug 17 '11 at 10:12

This is what Sylvester's criterion is for. Write your quadratic as $v^T A v$ where $v$ is a vector of variables $(x_1\ x_2\ \cdots\ x_n)$ and $A$ is a matrix of constants. For example, in your case, you are interested in $$\begin{pmatrix} x & y & z \end{pmatrix} \begin{pmatrix} 3 & 4 & 5/2 \\ 4 & 7 & 1 \\ 5/2 & 1 & 2 \end{pmatrix}\begin{pmatrix} x \\ y \\ z \end{pmatrix}$$ Observe that the off diagonal entries are half the coefficients of the quadratic.

The standard terminology is that $A$ is "positive definite" if this quantity is positive for all nonzero $v$. Sylvester's criterion says that $A$ is positive definite if and only if the determinants of the top-left $k \times k$ submatrix are positive for $k=1$, $2$, ..., $n$. In our case, we need to test $$\det \begin{pmatrix} 3 \end{pmatrix} =3 \quad \det \begin{pmatrix}3 & 4 \\ 4 & 7\end{pmatrix} = 5 \quad \det \begin{pmatrix} 3 & 4 & 5/2 \\ 4 & 7 & 1 \\ 5/2 & 1 & 2 \end{pmatrix} = -67/4.$$ Since the last quantity is negative, Sylvester's criterion tells us that this quadratic is NOT positive definite.

-
Just an offhand remark: from a computational perspective, you probably would not want to use Sylvester's criterion - assuming each determinant is computed in $O(n^3)$ operations, this involves doing $O(n^4)$ operations total. I'm not a hundred percent sure what the best algorithm is - perhaps someone more knowledgeable can pipe in - but I'm guessing its Cholesky decomposition, which can be performed in $O(n^3)$ operations total through a variant of Gaussian elimination. – alexx Aug 17 '11 at 19:42
Good point. I also don't know. I would guess that the best idea would be to slightly modify Cholesky decomposition to get a decomposition of the form $M D M^*$ where $M$ is lower triangular with ones on the diagonal, and $D$ is diagonal. This will avoid having to compute square roots. In particular, if your input is integer like the above, then you won't have to go to floating point. But one of the big things I have learned from talking to numerical analysts is that you shouldn't try to guess what a good algorithm will be; you need to actually test your ideas on data. – David Speyer Aug 17 '11 at 19:48
@alex is right on the nose; Cholesky is a very computationally efficient way to test for positive definiteness. The $M D M^*$ (more conventionally denoted $LDL^T$) decomposition mentioned by David has both the advantage of not needing square roots and being able to give information on the inertia. On the other hand, there are symmetric matrices that do not have an $LDL^T$ decomposition, and pivoting may be necessary... (of course, I still gave a +1!) – J. M. Aug 18 '11 at 10:24
@J.M. You brought up something interesting. Actually, is the $LDL^{T}$ same as Cholesky if the pivots are positive then $L\sqrt{D}(L\sqrt{D})^{T}$? But this only works if the pivots are positive; matrix is positive definite. For the symmetric matrices that don't work with $L\sqrt{D}(L\sqrt{D})^{T}$ due to negative pivots, it still has $LDL^{T}$, wouldn't it? And even singular matrices would have $LDL^{T}$ decomposition just that $D$ is singular too. Then what are the symmetric matrices that don't have $LDL^{T}$? – xenon Aug 18 '11 at 15:14
@xEnOn: Very perceptive of you! :) Most people unfortunately do not realize that relationship between $LDL^T$ and Cholesky. If any element of $D$ is negative, the original matrix cannot have a Cholesky decomposition since one of the underlying assumptions is that the diagonal elements ought to be real. As for matrices that do not possess an $LDL^T$ decomposition, if the leading submatrix of your symmetric matrix is singular, then you cannot outright compute the decomposition, e.g. $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ will not have that decomposition. – J. M. Aug 18 '11 at 15:23

One of the methods when you don't know necessary and sufficient condition for the minimum of function of several variables - consider other as parameters. You know that for a function $$a_1x^2+b_1(y,z)x+c(y,z)$$ the minimum is attained at $\frac{-b_1(y,z)}{2a_1}$ for $a_1>0$ and any fixed $y,z$. Then you should just substitute this into your equation and solve the minimum problem w.r.t. $y$ and then, on the third step, for $z$.

In your case: $a_1 = 3, b_1 = 8y+5z$, so you put $$x = -\frac{1}{6}(8y+5z)$$ and obtain a function $$\frac{1}{12}(20 y^2-56 y z-z^2)$$ which certainly can go below zero due to the negativity of the coefficient with $z^2$.

Finally, the strict inequality never holds, since any quadratic function is equal to zero in the origin.

-
At the point after obtaining the function $\frac{1}{12}(20 y^2-56 y z-z^2)$, can I only through observation on the square amount from $y^2$ and $z^2$ to see if they can over come the middle term $56yz$ to know if it is positive? Thanks! – xenon Aug 17 '11 at 12:41
@xEnOn: sure, you can take $y=0$. So in overall you take $y=0,z=1$ and $x = -5/6$ to obtain $-1/12$ as a value. – Ilya Aug 17 '11 at 13:31
So the only way is through observation and no formal ways to "squeeze out a value" that can determine if the equation is always positive or negative? – xenon Aug 18 '11 at 1:42
@xEnOn: I think from the other answers you see that the problem is equivalent to sign-definiteness of the matrix. So, the fastest way is to use Sylvester's criteria. The are two reasons why I presented here another method. 1) I didn't know if you already studied Sylvester's criteria, while my method you can simply apply based on the school program. 2) it also works if you have terms $\alpha x+\beta y+\gamma z$. – Ilya Aug 18 '11 at 7:03
Thanks Gortaur! :) – xenon Aug 18 '11 at 16:04

My approach of this is like this:

For a regular one variable quadratic, $ax^2+bx+c$ you can find its sign like this: solve $ax^2+bx+c=0$, and after that

• between the roots (if any) the sign is opposite to the sign of $a$

• outside the roots the sign is the sign of $a$.

In your case you want to see if a quadratic is positive all the time, and this means it has no roots, i.e. the determinant $\Delta=b^2-4ac<0$.

You can now solve your problem: Consider the equation as a quadratic in $x$, and suppose the condition $\Delta_x<0$ is true. Now you arrive at a quadratic in $y,z$ which should be negative all the time. Consider this second quadratic as a one variable quadratic in $y$, and suppose the condition $\Delta_y<0$ is again true. Next you arrive at a quadratic in $z$, and if $\Delta_z<0$ all the time you are done.

The other method, as the previous answer stated is to form squares. This is always possible, and if the signs of the three squares formed are not all plus, then the quadratic isn't always positive.

The third method uses linear algebra, and you can search for positive definitness of the matrix of your quadratic. This can be done pretty fast, but it uses determinants. If you are interested I will present this method.

-
Thanks! Although the determinant $b^{2}-4ac<0$ does not have real roots, could the graph be totally above or below the axis? Do I have to then substitute any random number into the equation to find if it is above(always positive) or below(always negative) the axis? If there're more than 1 variable like the example I wrote, I'm still not sure how I could get it into $\Delta$. For $\Delta_x$, I group it into $3x^{2}+[8y]x+[5z]x+2yz+7y^{2}+2z^{2}>0$ and so $a=3$, $b=8y$ & $c=2yz+5z+y^{2}$, then I put them into $\Delta_x=(8y)^{2}-4(3)(2yz+5z+y^{2})$, is this right? But they're all variables only. – xenon Aug 17 '11 at 12:28
Actually, I came about this question because I was thinking about one of the properties of or test for positive definite with $x^{T}Ax>0$. But at the same time, was wondering how I could find out if the quadratic equation is always positive, negative or both when the number of variables gets more. – xenon Aug 17 '11 at 12:29

Rewrite your expression as a bilinear form with a symmetric matrix in-between. This can always be done. For instance, in your case, your expression is $$3x^{2}+8xy+5xz+2yz+7y^{2}+2z^{2} = \begin{pmatrix} x & y & z \end{pmatrix} \begin{pmatrix} 3 & 4 & 5/2 \\ 4 & 7 & 1 \\ 5/2 & 1 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix}$$ Now all you need to check is that the matrix is positive definite. A nice property of the positive definite matrix is that every diagonal sub-matrix must be positive definite. However, note that the matrix $$\begin{pmatrix} 3 & 5/2 \\ 5/2 & 2 \end{pmatrix}$$ is not positive definite. Hence, it is not possible that $$3x^{2}+8xy+5xz+2yz+7y^{2}+2z^{2}$$ is always positive $\forall x,y,z \in \mathbb{R}$

-
Thanks. But how was the matrix $\begin{pmatrix} 3 & 5/2 \\ 5/2 & 2 \end{pmatrix}$ derived? By diagonal sub-matrix, I thought it referred to the submatrix from the top left corner of the main matrix? But $\begin{pmatrix} 3 & 5/2 \\ 5/2 & 2 \end{pmatrix}$ doesn't look like that. – xenon Aug 17 '11 at 17:25
@xEnOn: By diagonal submatrix I mean $A(n1,n2,\ldots,nk;n1,n2,\ldots,nk)$ where $n1,n2,\ldots,nk \in \{1,2,\ldots,n\}$ or you can think of symmetric permutation i.e. in this case swap rows 2 and 3 and columns 2 and 3 and then look at the top left sub-matrix – user17762 Aug 17 '11 at 17:50