As per request from Comrade Pi Han Goh

Algebra Level 5

$\begin{aligned} f_a(x,y,z)&=&ax^2+(a+1)y^2+(a+2)z^2 \\ && -4xy-4yz+2x-3y+4z-5 \end{aligned}$

Find the smallest real number $a$ such that the function $f_a(x,y,z)$ has a (global) minimum.

The Topic is Algebra ; calculus solutions will be frowned upon.

2 1 3 4 There is no such minimal

a

2 solutions

Otto Bretscher
Apr 3, 2016

Let me get started on a solution. The matrix of the quadratic part of the function $f_a(x,y,z)$ (the first five terms) is

$A_a=\begin{bmatrix} a & -2 & 0 \\ -2 & a+1 & -2 \\ 0 & -2 & a+2\end{bmatrix}=aI_3+\begin{bmatrix} 0 & -2 & 0 \\ -2 & 1 & -2 \\ 0 & -2 & 2\end{bmatrix}=aI_3+B$

A straightforward computation shows that the eigenvalues of $B$ are $-2,1,4$ , so that the eigenvalues of $A_a$ are $a-2,a+1$ and $a+4$ .

Now we need to consider three cases, with the smallest eigenvalue being positive, negative, or zero.

Please take it from here, Comrade @Pi Han Goh !

This is not an easy question for me. I'll have to work on this question on the weekends.

Pi Han Goh - 5 years, 2 months ago

Take your time, Comrade!

Otto Bretscher - 5 years, 2 months ago

Sorry. I appreciate everything that you wrote for me, but I don't see how it helps by splitting $A_a = a I_3 + B$ . Yes, I've verified by hand that the eigenvalues you've listed are indeed correct.

Why split them up? Or what three cases to consider?

I apologize, but you need to spoonfeed this nitwit (me) once more.

(And yes, I've already read your comments in the solution discussion below)

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – The splitting is no big deal; you can skip that step if you wish. The eigenvalues of $aI_3+B$ are $a$ plus the eigenvalues of $B$ , by definition of an eigenvector, so that the splitting makes things a big easier.

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Ughhhhhh?? I know that already, so we got eigenvalue (LHS) = eigenvalue (RHS). What about the splitting part?

If you're looking for anti-solutions, then we can definitely rule out the values of 1,2,3,4 based on your working. But I don't think that's the solution you're looking for.

But I don't see anything that needs/should be split into, or even how to be splitting into something else.

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – Ok then, let's forget about the splitting part and move on. So, the eigenvalues of $A_a$ are $a-2, a+1$ and $a+4$ . Where do we go from here? For which $a$ does the function $f_a(x,y,z)$ have a minimum?

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Hmm I don't know where this is going, but here's my answer to the question "For which $a$ does the function $f_a(x,y,z)$ have a minimum?"

For it to have a minimum, all its eigenvalues have to be positive, so $a-1>0, a+2>0, a+4> 0$ , and thus the intersection of these inequalities is $a>1$ . That's all I have.

To be honest, I don't know what you (we?) are doing, it appears (to me) that you want me to find some random value/expression, and somehow, it will miraculously tell me the answer. I've read all your comments past the few days already, and I'm still very clueless on what is going on.

You even said

The matrix of the quadratic part of the function $f_a(x,y,z)$ (the first five terms) is...

Then what about the linear and constant terms? Are they not important anymore? And yes, I have indeed read your comment below and don't see the importance of your comment.

Here is a simple analogy: When does the function $f(x)=ax^2+bx+c$ have a minimum? The answer is trivial, of course: ...

Looking at your matrix $B$ and comparing it with your solution here tells us that want to find the determinant of matrix $B$ , which is equal to $(a-2)(a+1)(a+4)$ . And since it is a cubic polynomial with real coefficients, then by intermediate value theorem , the cubic polynomial can never be strictly positive, so $\det(B) > 0$ can never be true for all real $a$ , so there's no such $a$ ? Hence the answer? I'm not sure whether I'm talking gibberish or not...

I have plenty of other questions with regards to why my solution is wrong, but I hope you can (still) steer me to the right direction. As of now, I'm aimlessly looking at random numbers and theorems just to see any of them is about this question.

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – You are asking exactly the right question: "Then what about the linear and constant term?"

In the example $ax^2+bx+c$ , the quadratic term dominates as long as $a\neq 0$ : In that case, we dont need to know $b$ and $c$ to determine whether the function has a global minimum. The linear term $bx$ plays a rôle in the "border line case" $a=0$ only. (Obviously, the constant term $c$ is irrelevant.)

Similarly, the linear terms in $f_a(x,y,z)$ play a rôle only in the border line case when the smallest eigenvalue is 0, that is, when $a=2$ .

In my solution here , the logic was this: Since the determinant of the matrix $Q$ of the quadratic form is negative, there is a negative eigenvalue, and therefore the function (including the linear terms) fails to be bounded below. But keep in mind that there may be negative eigenvalues even if the determinant is positive.

To fully and conceptually understand this problem, I suggest that you focus on the central rôle of the eigenvalues.

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – I don't know what I'm supposed to search for. I only have 2 linear algebra textbooks: this one and this one . Both of them barely touches on quadratic forms. The latter book tells us that (page 437) we need to find a new orthonormal basis $\gamma$ for $\mathbb R^3$ , whatever that means, and it tells us that we need to find some symmetric bilinear form as well, whatever that means.

And of course, Wikipedia is not user-friendly at all, so I don't know what I'm supposed to do.

In other words, I can't solve this question and your comments are too ambiguous for me to understand.

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – Friedberg-Insel-Spence is a good text (I don't know the other). My FIS is at the office, and it's Sunday ;) Another great text is Strang (an MIT guy); he has an excellent chapter on "positive definite matrices." You might want to get an old edition. Strang is not an easy read, but he is "deep." My text also goes over these issues in detail.

The key fact here is the Spectral Theorem which, in its simplest form (real and finite dimensional), states that any real symmetric matrix $A$ is "orthogonally diagonalizable", meaning that there exists an orthonormal basis consisting of eigenvectors. An orthonormal basis is a basis consisting of orthogonal (perpendicular) unit vectors. In the language of matrices, this means that there exists an orthogonal matrix $S$ such that $S^{-1}AS=S^{T}AS$ is diagonal.

If $q(\textbf{x})=\textbf{x}\cdot A\textbf{x}$ is a quadratic form and if $c_1,c_2,c_3$ are the coordinates of $\mathbf{x}$ with respect to an orthonormal basis of eigenvectors of $A$ , then we can write the quadratic form as $\lambda_1 c_1^2+\lambda_2c_2^2+\lambda_3c_3^2.$ This shows that the quadratic form is positive definite if all eigenvalues are positive, and the quadratic form is positive semidefinite if all eigenvalues are non-negative.

Before we move on, let me check that this all makes good sense to you.

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Awhhhh dang it. I didn't expect some super duper fancy theorem to appear. Your previous comments did not give the slightest hint on this theorem at all. Give me a few months (years?) to understand what you said.

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – Well, we can do without this theorem, but I thought you wanted to get to the bottom of it ;)

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Lay it on me. I got nothing new right now.

EDIT: you need to spell it out for me. Your hints are too obscure.

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – You see, when I explain things I try to do it more with questions than with answers, in a kind of Socratic way.... it often drives my students nuts, particularly when they are in a hurry, but in the long run they learn more that way ;)

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – It's been over a week now. I'm fairly sure nobody is as patient as me. I told you I'm out of insights already. If you're not telling me, then I have to figure it out some other time.

Plus, I assume you're moderator now? Why were you editing my comments?

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – I was not editing your comments at all, I promise. I was cost hitting "edit" instead of "reply" first, by mistake. I told you, I'm not good with technology.

Otto Bretscher - 5 years, 2 months ago

@Pi Han Goh – Let's go over it step by step.

Does it make sense that we can write a quadratic function in $n$ variables $x_1,...,x_n$ as $\mathbf{x}\cdot A\mathbf{x}+\mathbf{b}\cdot\mathbf{x}+c$ where $A$ is the symmetric matrix of the quadratic form and $\mathbf{b}$ collects the coefficients of the linear terms.

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Yep. It makes sense so far. No idea where we're heading but go on...

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – Great! Now, if $\mathbf{v}$ is a unit eigenvector with eigenvalue $\lambda$ and we let $\mathbf{x}=k\mathbf{v}$ , then the quadratic function takes the value $\lambda k^2+(\mathbf{b}\cdot\mathbf{v})k+c$ . If $\lambda<0$ , this proves that the function fails to be bounded below; just let $k$ grow without bound.

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – That's your reasoning to your previous problem . Now, how do you prove that $\lambda < 0$ is indeed true?

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – I'm saying if there is a negative eigenvalue, then the function fails to be bounded below. In the given problem, this is the case when $a<2$ .

Now we need to think about the cases $a>2$ , when all eigenvalues are positive, and $a=2$ , when 0 is the smallest eigenvalue.

When all eigenvalues are positive, it turns out that the function does have a minimum; why?

Otto Bretscher - 5 years, 2 months ago

Pi Han Goh
Apr 2, 2016

The matrix of the quadratic part of the function $f_a(x,y,z)$ can be expressed as

$A_a=\begin{bmatrix} a & -2 & 0 \\ -2 & a+1 & -2 \\ 0 & -2 & a+2\end{bmatrix}=aI_3+\underbrace{\begin{bmatrix} 0 & -2 & 0 \\ -2 & 1 & -2 \\ 0 & -2 & 2\end{bmatrix}}_{:=\; B} \; .$

The eigenvalues of the matrix $B$ satisfy the equation, $| \lambda I_3 - B | = 0$ . Solving this equation gives

$0 = \begin{bmatrix} \lambda & 2 & 0 \\ 2 & \lambda-1 & 2 \\ 0 & 2 & \lambda-2\end{bmatrix} = \lambda [ (\lambda-1)(\lambda-2) - 4 ] - 2 [ 2(\lambda-2)-2(0) ] \quad \Leftrightarrow \quad 0= (\lambda +2)(\lambda -1)(\lambda -4) \; .$

Or equivalently, $\lambda = -2, 1,4$ . So the eigenvalues of $B$ are $-2, 1,4$ , and the eigenvalues of $A_a$ are $a-2,a+1,a+4$ .

$A_a$ to have a minimum value, all its eigenvalues must be non-negative, so $a-2, a+1,a+4 \geq 0 \Rightarrow a \geq 2$ .

We are left to check for the borderline case for $a=2$ , then $f_2(x,y,z) = 2x^2 + 3y^2 + 4z^2-4xy -4yz+ 2x - 3y + 4z - 5$ . Let's find the kernel of this matrix:

$\left [ \begin{array} { c c c | c } 2 & -2 & 0 & 0 \\ -2 & 3 & -2 & 0 \\ 0 & -2 & 4 & 0 \end{array} \right ] \stackrel{R_2 \to R_2+ R_1}{\huge \longrightarrow} \left [ \begin{array} { c c c | c } 2 & -2 & 0 & 0 \\ 0 & 1 & -2 & 0 \\ 0 & -2 & 4 & 0 \end{array} \right ] \stackrel{R_3 \to R_3+ 2R_2}{\huge \longrightarrow} \left [ \begin{array} { c c c | c } 2 & -2 & 0 & 0 \\ 0 & 1 & -2 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right ] \; .$

So $x:y: z = 1: 1: \dfrac12 \Leftrightarrow (x,y,z) = (2t,2t,t), t \in \mathbb R$ . Now $f_2(2t,2t,t) = 2t - 5$ showing that $f_2(x,y,z)$ is a straight line thus has no minimum value. In other words, for $a=2$ , the function $f_2(x,y,z)$ does not have a minimum value either.

Thus the minimum value of $f_a(x,y,z)$ occurs when $a>2$ . Hence, $2$ is the infimum of $a$ only, but not the minimum value of $a$ . Therefore, there is no minimum value of $a$ satisfying this condition.

What is the point of the first sentence being seperated from the rest of the proof?

Note that it follows directly from looking at the $1 \times 1$ principal minor. In fact, saying "Setting $y = z = 0$ " means you are looking at the principal minor formed by the first and fourth columns.

Calvin Lin Staff - 5 years, 2 months ago

Oh haha! You're right. I didn't think of it that way. I'm still a newbie in this. Any other improvements? For example, I couldn't motivate why I choose a certain minor (the partially red matrix) to do the calculation. What I've done is I experiment with a couple of minors and this minor produces "the best result".

Pi Han Goh - 5 years, 2 months ago

I'm afraid that this is not quite correct yet.... but you will figure it out.

You cannot apply Sylvester's criterion to the big matrix, the $E$ in your link . For example, consider $f(x,y,z)=x^2+y^2+z^2-1$ , which certainly has a minimum, but the $E$ has lots of negative principal minors.

The discussion of eigenvalues, definiteness, and Sylvester's criterion is confined to the $3\times 3$ matrix $e$ , the matrix of the "underlying quadratic form".

When I learned this, long ago, we never looked at the matrix $E$ ; it is a weird hybrid construct.

Otto Bretscher - 5 years, 2 months ago

That leaves me with little options other than brute force , which is plain tedious, or (first establish the fact at $a>0$ ) by finding the characteristic polynomial of the $4\times4$ matrix and show that by Descartes' rule of signs , there are always negative eigenvalues, which is far more tedious.

Both of these solutions are super long (yes, I've tried it), so I'll refrain from posting an updated solution for now. Unless of course, there is some new insights/tricks that you have?

Pi Han Goh - 5 years, 2 months ago

The problem isn't tedious; I don't post (or solve) tedious problems, as you know ;)

My hint is to forget about the $4\times4$ matrix (until the very end) and work with the $3\times 3$ , the matrix of the quadratic form. The eigenvalues of that one are easy to find (or I can tell them to you, if you wish). You want to write that matrix as $aI_3+B$ , of course, and find the eigenvalues of $B$ .

Otto Bretscher - 5 years, 2 months ago

@Otto Bretscher – Awhhh curses! I thought Calvin's solution is the only way to go! Let me put on my thinking cap on again. Be right back! Stay tuned.

In the meantime, can you explain to me what do you mean by "it is a weird hybrid construct."? And where exactly in the Wikipedia page did it say that it only works for small square matrices?

Pi Han Goh - 5 years, 2 months ago

@Pi Han Goh – In your link they talk about the matrix $e$ , the matrix of the quadratic form, and the matrix $E$ that contains the linear and constant terms in the last row and column. That one is a "weird hybrid construct" in that the last row and column play quite a different role. Note that we work with the eigenvalues of $e$ only (denoted by $k_1,k_2,k_3$ ), not those of $E$ . The eigenvalues of $E$ are irrelevant for our problem.

Otto Bretscher - 5 years, 2 months ago

@Pi Han Goh – Let me try to help you along a little more..

Here is a simple analogy: When does the function $f(x)=ax^2+bx+c$ have a minimum? The answer is trivial, of course:

There is a minimum if $a$ is positive, regardless of the linear and constant terms.

There is no minimum if $a$ is negative, again, regardless of the linear and constant terms.

If $a=0$ , then there is a minimum iff $b=0$ .

In several variables, the situation is analogous:

If all the eigenvalues of the quadratic part are positive, then there is a minimum.

If the quadratic part has a negative eigenvalue, then there is no minimum.

If the smallest eigenvalue is 0, then we have to look at the linear part.

Otto Bretscher - 5 years, 2 months ago

@Pi Han Goh Sorry for confusing you. I take back what I said about creating the matrix with a 1 in it. That doesn't help.

You should only look at the matrix $E_{xyz}$ and then

Verify that it has non-negative principal minors
If there are non-zero linear terms, verify that any principal minors that involve these variables have a positive minor.

See Otto's comment for more information.

Calvin Lin Staff - 5 years, 2 months ago

@Otto Bretscher I've fixed my solution.

@Calvin Lin , one Challenge Master Note please.

Pi Han Goh - 5 years, 1 month ago

As per request from Comrade Pi Han Goh

The Topic is Algebra ; calculus solutions will be frowned upon.

2 solutions

0 pending reports