14
$\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.

$\endgroup$
1
  • 1
    $\begingroup$ If this is homework, haven't you covered such methods in class already? (Diagonalization or completing the squares, for example.) $\endgroup$ Aug 17, 2011 at 10:12

5 Answers 5

12
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – morgan
    Aug 17, 2011 at 19:42
  • $\begingroup$ 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. $\endgroup$ Aug 17, 2011 at 19:48
  • 1
    $\begingroup$ @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!) $\endgroup$ Aug 18, 2011 at 10:24
  • 1
    $\begingroup$ @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}$? $\endgroup$
    – xenon
    Aug 18, 2011 at 15:14
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 18, 2011 at 15:23
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – xenon
    Aug 17, 2011 at 17:25
  • $\begingroup$ @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 $\endgroup$
    – user17762
    Aug 17, 2011 at 17:50
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – xenon
    Aug 17, 2011 at 12:41
  • $\begingroup$ @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. $\endgroup$
    – SBF
    Aug 17, 2011 at 13:31
  • $\begingroup$ 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? $\endgroup$
    – xenon
    Aug 18, 2011 at 1:42
  • $\begingroup$ @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$. $\endgroup$
    – SBF
    Aug 18, 2011 at 7:03
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – xenon
    Aug 17, 2011 at 12:28
  • $\begingroup$ 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. $\endgroup$
    – xenon
    Aug 17, 2011 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .