11
$\begingroup$

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

Say, for the quadratic inequality

$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 form is always greater than zero or has negative results or it is always negative for all non-zero values of the variables?

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

Thanks for any help.

  • 1
    If this is homework, haven't you covered such methods in class already? (Diagonalization or completing the squares, for example.)2011-08-17

5 Answers 5

10

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.

  • 0
    ohh ya...you are right. A singular first leading submatrix will not work. Actually, I tried a few and it seems like as long as the first $a_{11}$ entry is a $0$, chances are it will not allow the matrix to be formed into an triangular matrix and then the whole decomposition will not work. Thanks! :)2011-08-18
5

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

  • 0
    @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-matrix2011-08-17
1

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.

  • 0
    @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$.2011-08-18
1

The matrix $H$ is the Hessian matrix of second partial derivatives. We find from "congruence diagonalization" that the eigenvalues of $H$ are $++- \; \; .$ Of course, the diagonal entries of $D$ are not the eigenvalues themselves. This is about Sylvester's Law of Inertia.

Sylvester's law of inertia is a theorem in matrix algebra about certain properties of the coefficient matrix of a real quadratic form that remain invariant under a change of basis. Namely, if $A$ is the symmetric matrix that defines the quadratic form, and $S$ is any invertible matrix such that $D = SAS^T$ is diagonal, then the number of negative elements in the diagonal of $D$ is always the same, for all such $S \; ; \; $ and the same goes for the number of positive elements.

If I had the energy to find the eigenvectors, I could write $O^T H O = D_0$ with orthogonal $O$ and diagonal $D_0,$ at which point the diagonal entries of $D_0$ would be the eigenvalues. Sylvester says that my $ P^T H P = D $ gives the same number of positive diagonal entries and the same number of negative, also the same number of zero entries. For this example, two positive eigenvalues and one negative.

$ P^T H P = D $ $\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 4 }{ 3 } & 1 & 0 \\ - \frac{ 27 }{ 10 } & \frac{ 7 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 6 & 8 & 5 \\ 8 & 14 & 2 \\ 5 & 2 & 4 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & - \frac{ 27 }{ 10 } \\ 0 & 1 & \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 6 & 0 & 0 \\ 0 & \frac{ 10 }{ 3 } & 0 \\ 0 & 0 & - \frac{ 67 }{ 10 } \\ \end{array} \right) $

$ E_j^T D_{j-1} E_j = D_j $ $ P_{j-1} E_j = P_j $ $ E_j^{-1} Q_{j-1} = Q_j $ $ P_j Q_j = I $ $ P_j^T H P_j = D_j $ $ Q_j^T D_j Q_j = H $

$ H = \left( \begin{array}{rrr} 6 & 8 & 5 \\ 8 & 14 & 2 \\ 5 & 2 & 4 \\ \end{array} \right) $

==============================================

$ E_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $ $ P_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrr} 1 & \frac{ 4 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrr} 6 & 0 & 5 \\ 0 & \frac{ 10 }{ 3 } & - \frac{ 14 }{ 3 } \\ 5 & - \frac{ 14 }{ 3 } & 4 \\ \end{array} \right) $

==============================================

$ E_{2} = \left( \begin{array}{rrr} 1 & 0 & - \frac{ 5 }{ 6 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $ $ P_{2} = \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & - \frac{ 5 }{ 6 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrr} 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 6 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrr} 6 & 0 & 0 \\ 0 & \frac{ 10 }{ 3 } & - \frac{ 14 }{ 3 } \\ 0 & - \frac{ 14 }{ 3 } & - \frac{ 1 }{ 6 } \\ \end{array} \right) $

==============================================

$ E_{3} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) $ $ P_{3} = \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & - \frac{ 27 }{ 10 } \\ 0 & 1 & \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{3} = \left( \begin{array}{rrr} 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 6 } \\ 0 & 1 & - \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{3} = \left( \begin{array}{rrr} 6 & 0 & 0 \\ 0 & \frac{ 10 }{ 3 } & 0 \\ 0 & 0 & - \frac{ 67 }{ 10 } \\ \end{array} \right) $

==============================================

$ P^T H P = D $ $\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 4 }{ 3 } & 1 & 0 \\ - \frac{ 27 }{ 10 } & \frac{ 7 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 6 & 8 & 5 \\ 8 & 14 & 2 \\ 5 & 2 & 4 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 4 }{ 3 } & - \frac{ 27 }{ 10 } \\ 0 & 1 & \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 6 & 0 & 0 \\ 0 & \frac{ 10 }{ 3 } & 0 \\ 0 & 0 & - \frac{ 67 }{ 10 } \\ \end{array} \right) $ $ Q^T D Q = H $ $\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 4 }{ 3 } & 1 & 0 \\ \frac{ 5 }{ 6 } & - \frac{ 7 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 6 & 0 & 0 \\ 0 & \frac{ 10 }{ 3 } & 0 \\ 0 & 0 & - \frac{ 67 }{ 10 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 6 } \\ 0 & 1 & - \frac{ 7 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 6 & 8 & 5 \\ 8 & 14 & 2 \\ 5 & 2 & 4 \\ \end{array} \right) $

0

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.

  • 0
    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.2011-08-17