Quadratic Forms (positive definite matrix)

Question

How can I show that

$900x_{1}^{2}+900x_{1}x_{2}+744x_{1}x_{3}+625x_{2}^{2}+620x_{2}x_{3}+961x_{3}^{2}>0$

for any $\left(x_{1},x_{2},x_{3}\right)\neq0$? I know that I should try to write this as a completed quadratic form but I can't find the right one.

Any help?

Answer 1

Added: you can also write the form as $$ (26x_1 + 5 x_2 )^2 + (12 x_1 + 10 x_2 + 31 x_3)^2 + 5 (4 x_1 + 10 x_2)^2 $$

ORIGINAL: If you wish, you can just find the eigenvalues of the Hessian matrix of second partials, or half the Hessian... Just checked, the eigenvalues will be really ugly, as the characteristic polynomial is irreducible (and has enormous entries). So, you are better off doing "congruence diagonalization"

$$ Q^T D Q = H $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 \\ \frac{ 31 }{ 75 } & \frac{ 31 }{ 100 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 900 & 0 & 0 \\ 0 & 400 & 0 \\ 0 & 0 & \frac{ 3844 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & \frac{ 31 }{ 75 } \\ 0 & 1 & \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961 \\ \end{array} \right) $$

Algorithm discussed at http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr
https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia
$$ H = \left( \begin{array}{rrr} 900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961 \\ \end{array} \right) $$ $$ D_0 = H $$ $$ 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 = Q_j P_j = I $$ $$ P_j^T H P_j = D_j $$ $$ Q_j^T D_j Q_j = H $$

$$ H = \left( \begin{array}{rrr} 900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961 \\ \end{array} \right) $$

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

$$ E_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 1 }{ 2 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 1 }{ 2 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrr} 900 & 0 & 372 \\ 0 & 400 & 124 \\ 372 & 124 & 961 \\ \end{array} \right) $$

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

$$ E_{2} = \left( \begin{array}{rrr} 1 & 0 & - \frac{ 31 }{ 75 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{2} = \left( \begin{array}{rrr} 1 & - \frac{ 1 }{ 2 } & - \frac{ 31 }{ 75 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & \frac{ 31 }{ 75 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrr} 900 & 0 & 0 \\ 0 & 400 & 124 \\ 0 & 124 & \frac{ 20181 }{ 25 } \\ \end{array} \right) $$

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

$$ E_{3} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & - \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{3} = \left( \begin{array}{rrr} 1 & - \frac{ 1 }{ 2 } & - \frac{ 31 }{ 120 } \\ 0 & 1 & - \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{3} = \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & \frac{ 31 }{ 75 } \\ 0 & 1 & \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{3} = \left( \begin{array}{rrr} 900 & 0 & 0 \\ 0 & 400 & 0 \\ 0 & 0 & \frac{ 3844 }{ 5 } \\ \end{array} \right) $$

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

$$ P^T H P = D $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 1 }{ 2 } & 1 & 0 \\ - \frac{ 31 }{ 120 } & - \frac{ 31 }{ 100 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 1 }{ 2 } & - \frac{ 31 }{ 120 } \\ 0 & 1 & - \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 900 & 0 & 0 \\ 0 & 400 & 0 \\ 0 & 0 & \frac{ 3844 }{ 5 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 \\ \frac{ 31 }{ 75 } & \frac{ 31 }{ 100 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 900 & 0 & 0 \\ 0 & 400 & 0 \\ 0 & 0 & \frac{ 3844 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & \frac{ 31 }{ 75 } \\ 0 & 1 & \frac{ 31 }{ 100 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961 \\ \end{array} \right) $$

Answer 2

If you find the matrix associated with the quadratic form, you just have to prove that that matrix is positive semidefinite.

What we have is the following: Let $$\mathbf x = \left(\begin{matrix} x_1\\x_2\\x_3\end{matrix}\right)$$ then there'll be a $3\times 3$ symmetric matrix $A$ such that $$\mathbf x^T A \mathbf x = 900x_1^2+900x_1x_2+744x_1x_3+625x_2^2+620x_2x_3+961x_3^2 \tag 1$$ To construct this matrix is really simple. A key fact is that the matrix should be symmetric!

First of all it is clear that the elements on the diagonal have to be the coefficients of $x_1^2,x_2^2,x_3^2$ elements: that is all because of the definition given in $(1)$. You should try to make an example with a general $2\times 2$ matrix to see that this is the case.

Then for the off diagonal elements we just take half of every other coefficients. Their position in the matrix will be given by the indices on the variable that they multiplay. For example: the elements $a_{12} = a_{21}$ should be half of the coefficient of the term of $x_1x_2$, so in our case $a_{12} = a_{21}=300$ and so on. The sign of the coefficients of the matrix is given by the sign of the coefficients of the quadratic form.

Le us now calculate our matrix $A$ $$a_{11} = 900 \\a_{22} = {625} \\ a_{33} = {961} \\ a_{12}=a_{21} = 450 \\ a_{13}=a_{31} = 372 \\ a_{23} = a_{32} = 310$$ so then $$A = \left(\begin{matrix} 900 & 450 & 372 \\ 450 & {625} & 310 \\ 372 &310 & {961} \end{matrix}\right)$$

We could try and see if formula $(1)$ holds

$$ \left(\begin{matrix} x_1&x_2&x_3\end{matrix}\right)\left(\begin{matrix} 900 & 450 & 372 \\ 450 & {625} & 310 \\ 372 &310 & {961} \end{matrix}\right)\left(\begin{matrix}x_1\\x_2\\x_3\end{matrix}\right) =\\ =\left(\begin{matrix} 900x_1+450x_2+372x_3 &450x_1+{625}x_2+310x_3&372x_1+310x_2+{961}x_3\end{matrix}\right)\left(\begin{matrix}x_1\\x_2\\x_3\end{matrix}\right)= \\ = 900x_1^2+\color{red}{450x_1x_2}+\color{blue}{372x_1x_3} + \color{red}{450x_1x_2} + 625x_2^2 + \color{orange}{310 x_2x_3} + \color{blue}{372x_1x_3}+\color{orange}{310x_2x_3}+961x_3^2 = \\ =900x_1^2+625x_2^2+961x_3^2+\color{red}{900x_1x_2}+\color{blue}{744x_2x_3}+\color{orange}{620x_2x_3} $$ Which is exactly your quadratic form! Hurray!

Now to see if the matrix $A$ is positive semidefinite, we can look at it's eigenvalues, for example but there're many ways, and see if they are all strictly positive. Indeed they are! I'll let you evaluate them!

So in the end the answer to your question is that

yes, that quadratic form is strictly positive $\forall\mathbf x$

Answer 3

The eigenvalues of the associated matrix look like they’re going to be ugly, so I recommend the diagonalization method in Will Jagy’s answer for completing the squares. However, for this problem I think using Sylvester’s criterion might be simpler: a symmetric matrix is positive-definite iff all of its leading principal minors are positive.

Form the associated matrix $$Q = \begin{bmatrix}900 & 900/2 & 744/2 \\ 900/2 & 625 & 620/2 \\ 744/2 & 620/2 & 961\end{bmatrix} = \begin{bmatrix}900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961\end{bmatrix}.$$ We then have $$900 \gt 0 \\ \begin{vmatrix}900&450\\450&625\end{vmatrix} = 360000 \gt 0 \\ \begin{vmatrix}900 & 450 & 372 \\ 450 & 625 & 310 \\ 372 & 310 & 961\end{vmatrix} = 276768000 \gt 0,$$ so the matrix and quadratic form are indeed positive-definite.

You don’t even need to compute these determinants explicitly. It’s easy to see that the $2\times2$ determinant is positive: both diagonal elements are greater than the off-diagonal elements. For the $3\times3$ matrix, you can perform a few row operations to make it upper-triangular and see that the diagonal elements are all positive, so the determinant is also positive.

---

Added: Now that I’ve though about it a bit, examining the eigenvalues isn’t so bad after all, though it’s still a bit more work than applying Sylvester’s criterion. We don’t need to know the exact values of the eigenvalues, only that they’re all positive. Determining that is a lot easier than completely solving the cubic equation. The characteristic polynomial of $Q$ is $$\lambda^3-2486\lambda^2+1591041\lambda-276768000.$$ Descartes’ rule of signs tells us that there are no negative roots and, since the matrix is real symmetric, all of the roots of this polynomial are real, so they’re all positive, as we’d like.

Answer 4

To find the maximum/minimum of $$ \small f(x_1,x_2,x_3)=900x_1^2+900x_1x_2+744x_1x_3+625x_2^2+620x_2x_3+961x_3^2 $$ given that $$ \small x_1^2+x_2^2+x_3^2=1 $$ we need to find $(x_1,x_2,x_3)$ so that for all $(\delta x_1,\delta x_2,\delta x_3)$ where $$ \small x_1\,\delta x_1+x_2\,\delta x_2+x_3\,\delta x_3=0 $$ we also have $$ \small(1800x_1+900x_2+744x_3)\,\delta x_1+(900x_1+1250x_2+620x_3)\,\delta x_2+(744x_1+620x_2+1922x_3)\,\delta x_3=0 $$ Orthogonality (see the Lemma in this answer) requires a $\lambda$ so that $$ \begin{align} 1800x_1+900x_2+744x_3&=\lambda x_1\\ 900x_1+1250x_2+620x_3&=\lambda x_2\\ 744x_1+620x_2+1922x_3&=\lambda x_3 \end{align} $$ That is, we want a unit column eigenvector of $$ \begin{bmatrix} 1800&900&744\\ 900&1250&620\\ 744&620&1922 \end{bmatrix} $$ The unit column eigenvectors are $$ \begin{bmatrix}0.6328898029682876399\\0.48441630123754085059\\0.6039795893853550811\end{bmatrix}\stackrel{f}\mapsto1599.4388924139868484 $$ $$ \begin{bmatrix}-0.5281093736430693063\\-0.30035435346657937794\\0.7942844275346194339\end{bmatrix}\stackrel{f}\mapsto596.4372230755582424 $$ $$ \begin{bmatrix}0.5661722235937463083\\-0.8216617974866624983\\0.06573358184291923328\end{bmatrix}\stackrel{f}\mapsto290.1238845104549091 $$ Thus, scaling, we get $$ 290\,\|v\|^2\le f(v)\le1600\,\|v\|^2 $$