Waste less time on Facebook — follow Brilliant.
×

Quadratic Forms and Completing the Square

This note is inspired by the discussion in The King needs your help.

Prove that for any real numbers,

\[ 5a^2 + 4b^2 + 3c^2 \geq 6ab + 4ac + 2bc .\]

Solution: Observe that \[ \frac{1}{3} \left[ (a+b-2c)^2 + 2 ( a+c - 2b)^2 + 3 ( b+c - 2a)^2 \right] = 5a^2 + 4b^2 + 3c^2 - 6ab - 4ac - 2bc .\] Since this is a sum of squares, by the Trivial Inequality, the result follows.


How could we solve a problem like this? As the problem creator, I could randomly write the sum of squares to form the inequality. Does this mean that the only way to solve this problem is to somehow magically guess at what the random combination of variables are? Is there a better approach to solving these types of problems?

In this note, I will show an approach that can be used to deal with all quadratic polynomial inequalities. We will use some results in Linear Algebra, and the most important of which is to know how to diagonalize a matrix.


A quadratic form refers to a homogenous polynomial of degree 2. Such a polynomial can be written in the from \( \sum_{i,j} a_{ij} x_i x_j. \) We can write it in matrix form in the following way:

\[ M = \begin{pmatrix} a_{11} & \frac{a_{12}}{2} & \ldots \frac{ a_{1n} } { 2} \\ \frac{a_{21}}{2} & a_{22} & \ldots \frac{ a_{2n} } { 2} \\ \vdots \\ \frac{a_{n1}}{2} & \frac{a_{nn}}{2} & \ldots a_{nn} \\ \end{pmatrix}, X = \begin{pmatrix} x_1 & x_2 & \cdots x_n \\ \end{pmatrix}. \]

Then, we have

\[ \sum_{i,j} a_{ij} x_i x_j = X M X^T\]

For example, the equation that we started out with is

\[ 5a^2 + 4b^2 + 3c^2 - 6ab - 4ac - 2bc = \begin{pmatrix} a & b & c \end{pmatrix} \begin{pmatrix} 5 & -3 & -2 \\ -3 & 4 & -1 \\ -2 & -1 & 3 \\ \end{pmatrix} \begin{pmatrix} a \\ b \\ c\\ \end{pmatrix} \]

What can we gain from writing it in matrix form? Well, we have numerous ways of understanding a matrix. Since \(M\) is a symmetric matrix, hence by the finite-dimensional spectral theorem, there exists a real orthogonal matrix \(Q\) such that \( M = Q D Q^T \), where \(D\) is a diagonal matrix. In other words, every symmetric matrix is, up to choice of an orthonormal basis, a diagonal matrix. This gives us:

\[ X M X^T = X Q D Q^T X^T = (XQ) D (XQ)^T \]

Hence we can conclude that

\[ \sum_{i,j} a_{ij} x_i x_j = (XQ) D (XQ)^T = \sum d_I (Q X_I) ^2, \]

where \( QX_I = \sum q_{Ij} x_j \).

This gives us an easy way of completing the square.

Let's refer back to the example.

\[ M = \begin{pmatrix} 5 & -3 & -2 \\ -3 & 4 & -1 \\ -2 & -1 & 3 \\ \end{pmatrix} . \]

First, we find the eigenvalues.
\( \det ( x I -M ) = x^3 - 12x^2 + 33x = x ( x - ( 6 + \sqrt{3}) )( x - ( 6 - \sqrt{3})) \).
Hence, the eigenvalues are \( \lambda_1 = 0, \lambda_2 = 6 + \sqrt{3} , \lambda_3 = 6 - \sqrt{3} \).

We then find the eigenvectors by solving \( Mv_i = \lambda_i v_i \), and normalize them. We obtain
\( v_1 = \begin{pmatrix} \frac{ \sqrt{3} } { 3} \\ \frac{ \sqrt{3} } { 3} \\ \frac{ \sqrt{3} } { 3} \end{pmatrix}, v_2 = \begin{pmatrix} \frac{ 3 + \sqrt{3} } {6} \\ - \frac{\sqrt{3}}{3} \\ - \frac{ 3 - \sqrt{3} } { 6} \end{pmatrix}, v_3 = \begin{pmatrix} \frac{ 3 - \sqrt{3} } { 6} \\ \frac{\sqrt{3}}{3} \\ - \frac{ 3 + \sqrt{3} } {6} \end{pmatrix} \).

Thus, this gives us

\[ D = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 6 + \sqrt{3} & 0 \\ 0 & 0 & 6 - \sqrt{3} \\ \end{pmatrix}, \quad Q = \begin{pmatrix} \frac{\sqrt{3}}{3} & \frac{ 3 + \sqrt{3} } {6} & \frac{ 3 - \sqrt{3} } { 6} \\ \frac{\sqrt{3}}{3} & - \frac{\sqrt{3}}{3} & \frac{\sqrt{3}}{3} \\ \frac{\sqrt{3}}{3} & - \frac{ 3 - \sqrt{3} } { 6} & - \frac{ 3 + \sqrt{3} } {6} \\ \end{pmatrix} . \]

Hence, this allows us to conclude that

\[ 5a^2 + 4b^2 + 3c^2 - 6ab - 4ac - 2bc \\ = ( 6 + \sqrt{3} ) \left[ \frac{ 3 + \sqrt{3}}{6} a - \frac{ \sqrt{3}}{3} b - \frac{ 3 - \sqrt{3} } { 6} c \right]^2 + ( 6 - \sqrt{3} ) \left[ \frac{ 3 - \sqrt{3}}{6} a + \frac{ \sqrt{3}}{3} b - \frac{ 3 + \sqrt{3}} { 6} c \right]^2 \]

Now, it's not as pretty as the equation that we started out with, but that was with a lot of magical foresight, where we knew how to obtain it. If you do not trust the work that has been done, we can always Wolfram verify it.


Follow up questions:

  1. Did we actually need to find \(Q\) in order to prove the inequality?
    Hint: No! What was the actual work that we needed?
    Hint: Under what conditions on \( \{ d_i \} \) can we conclude that \( \sum d_i x_i ^2 \geq 0 \) for all real values of \( x_i \).

  2. Prove that for all real \(a, b, c, \) \[ 3a^2 + 3b^2 + 7c^2 \geq 4ab + 4ac - 4bc. \]

  3. Prove that for all real \(a, b, c, \) \[ 29 a^2-31 a b-27 a c+18 b^2-5 b c+16 c^2 \geq 0 \]

  4. Prove that \[ 43-62 x - 22 y + 31 x^2+2xy+11 y^2 \geq 0\]

  5. Prove that if \( Q \) is an orthonormal matrix (each row is a vector of norm 1, and every two distinct rows are orthogonal), then \( Q Q ^T = I = Q^T Q \).
    Hence, conclude that \( Q^T = Q^{-1} \).

  6. Understand / prove the statement

    Since \(M\) is a symmetric matrix, hence by the finite-dimensional spectral theorem, there exists a real orthogonal matrix \(Q\) such that \( M = Q^{-1} D Q \), where \(D\) is a diagonal matrix. Note: This requires a firm grasp of Linear Algebra.

Note by Calvin Lin
2 years, 2 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

@Prasun Biswas I had the wrong matrix earlier. While the equations were correct, they could not have been obtained through this process. Calvin Lin Staff · 2 years, 2 months ago

Log in to reply

@Calvin Lin Didn't notice that earlier! Thanks for informing. :) Prasun Biswas · 2 years, 2 months ago

Log in to reply

What topic does this come under? Vishnu C · 2 years, 2 months ago

Log in to reply

@Vishnu C Linear Algebra. Calvin Lin Staff · 2 years, 2 months ago

Log in to reply

@Calvin Lin Quadratic forms under linear algebra! Never would've made the correlation by myself. Talk about misnomers. Vishnu C · 2 years, 2 months ago

Log in to reply

@Vishnu C The sarcasm is strong with this one! :D Prasun Biswas · 2 years, 2 months ago

Log in to reply

Comment deleted Nov 15, 2015

Log in to reply

@Prasun Biswas After I made the correction, they were no longer relevant so I removed them to avoid future confusion. Calvin Lin Staff · 2 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...