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,

5a2+4b2+3c26ab+4ac+2bc. 5a^2 + 4b^2 + 3c^2 \geq 6ab + 4ac + 2bc .

Solution: Observe that 13[(a+b2c)2+2(a+c2b)2+3(b+c2a)2]=5a2+4b2+3c26ab4ac2bc. \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 i,jaijxixj. \sum_{i,j} a_{ij} x_i x_j. We can write it in matrix form in the following way:

M=(a11a122a1n2a212a22a2n2an12ann2ann),X=(x1x2xn). 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

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

For example, the equation that we started out with is

5a2+4b2+3c26ab4ac2bc=(abc)(532341213)(abc) 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 MM is a symmetric matrix, hence by the finite-dimensional spectral theorem, there exists a real orthogonal matrix QQ such that M=QDQT M = Q D Q^T , where DD is a diagonal matrix. In other words, every symmetric matrix is, up to choice of an orthonormal basis, a diagonal matrix. This gives us:

XMXT=XQDQTXT=(XQ)D(XQ)T X M X^T = X Q D Q^T X^T = (XQ) D (XQ)^T

Hence we can conclude that

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

where QXI=qIjxj 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=(532341213). M = \begin{pmatrix} 5 & -3 & -2 \\ -3 & 4 & -1 \\ -2 & -1 & 3 \\ \end{pmatrix} .

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

We then find the eigenvectors by solving Mvi=λivi Mv_i = \lambda_i v_i , and normalize them. We obtain
v1=(333333),v2=(3+3633336),v3=(336333+36) 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=(00006+300063),Q=(333+36336333333333363+36). 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

5a2+4b2+3c26ab4ac2bc=(6+3)[3+36a33b336c]2+(63)[336a+33b3+36c]2 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 QQ in order to prove the inequality?
    Hint: No! What was the actual work that we needed?
    Hint: Under what conditions on {di} \{ d_i \} can we conclude that dixi20 \sum d_i x_i ^2 \geq 0 for all real values of xi x_i .

  2. Prove that for all real a,b,c,a, b, c, 3a2+3b2+7c24ab+4ac4bc. 3a^2 + 3b^2 + 7c^2 \geq 4ab + 4ac - 4bc.

  3. Prove that for all real a,b,c,a, b, c, 29a231ab27ac+18b25bc+16c20 29 a^2-31 a b-27 a c+18 b^2-5 b c+16 c^2 \geq 0

  4. Prove that 4362x22y+31x2+2xy+11y20 43-62 x - 22 y + 31 x^2+2xy+11 y^2 \geq 0

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

  6. Understand / prove the statement

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

Note by Calvin Lin
4 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

What topic does this come under?

vishnu c - 4 years, 5 months ago

Log in to reply

Linear Algebra.

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

Quadratic forms under linear algebra! Never would've made the correlation by myself. Talk about misnomers.

vishnu c - 4 years, 5 months ago

Log in to reply

@Vishnu C The sarcasm is strong with this one! :D

Prasun Biswas - 4 years, 5 months ago

Log in to reply

@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 - 4 years, 5 months ago

Log in to reply

Didn't notice that earlier! Thanks for informing. :)

Prasun Biswas - 4 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...