Transcript
5 4 Okay, this is the lecture on positive definite matrices. I made a start on those briefly in a previous lecture and one point I wanted to make was the way that this topic brings the whole course together. Pivots, determinants, eigenvalues, and something new for and stability and then something new in this expression X transpose AX. Actually, that's the guy to watch in this lecture. So, so the topic is positive definite matrix and what what's my goal? First first goal is how can I tell if a matrix is positive definite? So, I would like to have tests to see if you give me a a 5 by 5 matrix, how do I tell if it's positive definite?
More important is what does it mean? Why are we so interested in this property of positive definiteness? And then at the end comes some geometry. Ellipses are connected with positive definite things. Hyperbolas are not connected with positive definite things. So, we it's this uh we there's a geometry, too, but mostly it's linear algebra and uh this this application of how do you recognize them when you have a minimum is pretty neat. Okay, I'm going to begin with 2 by 2. All matrices are symmetric, right? That's understood. The matrix is symmetric. Now, my question is is it positive definite? Now, here are here are some each one of these is a complete test for positive definiteness.
If I know the eigenvalues, my test is are they positive? Are they all positive? If I know the these So, A is really I I look at that number A here as the as the 1 by 1 determinant and here's the 2 by 2 determinant. So, this is the determinant test. This is the eigenvalue test. This is the determinant test. Are the determinants growing in of all of all n sort of could I call them leading submatrices? They're they're they're the first ones. They're the northwest Seattle submatrices coming down from from there. They all all those determinants have to be positive. And then another test is the pivots.
The pivots of a 2 by 2 matrix are that number A for sure. And uh since the product is the determinant, the second pivot must be the determinant divided by A. And then in here is going to come my favorite and my new idea, the the the the one to catch about X transpose AX being positive. But we'll have to look at this guy. This gets a like a star because for most uh presentations, the definition of positive definiteness would be this number four and these numbers 1 2 3 would be tests for it. Okay, maybe I'll tuck this wire in a little bit. Okay, so I have to look at this X transpose AX. Can you uh Can we just be sure how do we know that the eigenvalue test and the and the determinant test pick out the same matrices?
And and let me let's just do a few examples. So, examples. Let me let me pick the matrix two uh 6 6. Tell me what number do I have to put there for the matrix to be positive definite? Tell me a sufficiently large number that would would make it positive definite. Just just let's just practice with these conditions in the 2 by 2 case. Now, when I ask you that, you don't want to find the eigenvalues. You would use the determinant test for that. So, so the first or the pivot test, that that guy is certainly positive. That had to happen. And it's okay. How large a number here the number had better be more than what?
More than 18, right? Because if it's eight No. More than what? 19 is it? What If I have a 19 here, is that positive definite? Yeah, because the I get 38 minus 36. That's okay. If I had an 18, let me play it really close. If I have an 18 there, then am I positive definite? Not quite. I would call this guy positive. So, it's it's useful just to see that this is the borderline. That matrix is on the borderline. I would call that matrix positive semi-definite. And and what are the eigenvalues of that matrix? Just since we're good at eigenvalues of 2 by 2s, uh when it's semi-definite, but not definite, then the I'm squeezing this eigenvalue test down.
Tell what's the what's the what's the eigenvalue that I know this matrix has? What kind of a matrix have I got here? It's a singular matrix. One of its eigenvalues is zero. That has an eigenvalue zero and the other eigenvalue is from the trace, 20. Okay. So, that that matrix has eigenvalues greater than or equal to zero. And it's that equal to that brought this word semi-definite in. And the What are the pivots of that matrix? So, the pivots So, the eigenvalues are zero and 20. The pivots are well, the pivot is two and what's the next pivot? There isn't one. We got a singular matrix here. It'll only have one pivot.
You see that that's a rank one matrix. 2 6 is a 6 18 is a multiple of 2 6. The matrix is singular. It only has one pivot. So, uh the pivot test doesn't quite pass. The Let me do the X transpose AX. Now, this is this is the this is the uh the the novelty now. Okay. What am I looking at when I look at at this new combination X transpose AX? X is any vector now. So, let me compute So, any vector, let me call its components X1 and X2. So, that's X. And I put in here A. Let's let's use this example 2 6 6 18. And here's X transpose, so X1 X2. We're back to real matrices after that last lecture that that said what to do in the complex case, let's come back to real matrices.
So, here's X transpose AX and what I'm interested in is what do I get if I multiply those together? I get some function of X1 and X2. And what is it? Uh let's see. If I do this multiplication, should I do it? Let me I'll just do it slowly. X1 X2, if I multiply that matrix, this is 2 X1 and 6 X2s and the next row is 6 X1s and 18 X2s. And now I do this final step and what do I have? I've got 2 X1 squareds. That 2 X1 squareds is coming from this two. I've got this one gives me 18 Well, should I do the ones in the middle? How many How many X1 X2s do I have? Let's see. X1 times that 6 X2 will be six of them and then X2 times this one will be six more.
I get 12. So, in in here is going This is the This is the number A. This is the number 2 B. And in here is going to X2 times 18 X2 will be 18 X2 squareds and this is is number C. So, it's A X1 It's like AX squared, 2 BXY, and CY squared. So, my my first point that I wanted to make by just doing out a multiplication is that as soon as you give me the matrix, as soon as you give me the matrix, I can I Those are the numbers that appear in the I'll call this thing a quadratic. It You see, it's not linear anymore. AX is linear, but now I've got an X transpose coming in. I'm up to degree two. Up to degree two, maybe quadratic is the usual word, a quadratic form.
It's It's purely degree two. There's no linear part, there's no constant part, there certainly aren't any cubes or fourth powers. It's all second degree. And my question is, is it po- is that quantity positive or not? That's my It for every X1 and X2. That is my new definition. That's my definition of a positive definite matrix. If this quantity is positive, if if if it's positive for all X's and Y's, all X1 X2's, then I call them And then, that's the matrix is positive definite. Now, is this guy passing our test? Well, we had we anticipated the answer here by by asking first about eigenvalues and pivots.
And what happened? It failed. It barely failed. If I had made this 18 down to a seven, it would have totally failed. If I if I if I Can I do that with the eraser? And then, I'll put back 18 cuz I'm Seven is such a total disaster that if that Well, let me I'll keep seven for a second. Is that thing in any way positive definite? No, absolutely not. The I I don't know it's eigenvalues, but I know for sure one of them is negative. It's pivots are two, and then the next pivot would be the determinant over two, and the determinant is What's the determinant of this thing? 14 minus 36. I've got a determinant of minus 22.
The next pivot will be The pivots now of this thing are two and minus 11 or something. Their product being minus 22, the determinant. This thing is not positive definite. What would be What Let me look at the X transpose AX for this guy. What's If I do out this multiplication, this 18 is temporarily changing to a seven. This 18 is temporarily changing to a seven. And I know that there's some numbers X1 and X2 for which that thing that function is negative. And I'm desperately trying to think what they are. Okay, maybe you can see. Can you tell me a value of X1 and X2 that makes this quantity negative?
Oh, maybe one and minus one? Yeah, that's a that's a In this case, that uh will work, right? If I took X1 to be one and X2 to be minus one, then I always get something positive, the two and the seven minus one squared. But this would be minus 12, and the whole thing would be negative. I'd have two minus 12 plus seven, I'm negative. If I drew the graph, can I Can I get a little picture in here? If I draw the graph of this thing, so graph of the function F of XY or F of X, shall I say, or F of XY equal this It's this It's this X transpose AX. This This This AX squared, 2 BXY, and CY squared. And let's take the example with these numbers.
Okay, so here's the X axis. Here's the Y axis, but here's up is the function. Z, if you like, or F. I I I apologize. Let me just once in my life here put an arrow over these these axes, so you see that that's the vector, and I just Okay, instead of X1 and X2, I made them X the components X and Y. Okay. So, So, what's a graph of 2X squared, 12XY, and 7Y squared? I'd like to see So, to get some idea Actually, I'm not the greatest artist. But let's Tell me something about this graph of this function. Uh well, tell me one point it goes through. Uh the origin, right? Even this artist can get this thing to go through the origin.
At At When these are zero, I I certainly get zero. Okay, some more points. If X is one and Y is zero, then I'm going upwards. So, I'm going up this way. And I'm going up like 2X squared in that direction. So, that's meant to be a a parabola. And suppose X stays zero and Y increases. Well, Y could be positive or negative. It's 7Y squared. Is this function going upward? In the X direction, it's going upward. And in the Y direction, it's going upwards. And if X equals Y in the 45° direction, it's certainly going upwards. Cuz then we'd have What about Everything would be positive, but what? This function What What What's the graph of this function?
So, like tell me the Tell me the word that describes the graph of this function. This is the non-positive definite. You Everybody's with me here. I'm for some reason got started in a negative direction here, a case that isn't positive definite. And what's What's the graph look like? It goes up, but does it Do we have a minimum here? Does it go up from the from the origin? Completely? No, because we just checked that this thing failed. It failed along the direction when X was minus Y. We have a saddle point. Let me Let me put myself Let me at least tell you the word. This thing goes up in some directions, but down in other directions.
And if we actually knew what a saddle looked like, I think saddle do that. Like Am I right? I I mean, like the way your legs go like down. I And the way you And looking like forward and uh the And drawing the thing is even worse than describing. I'm just going to say, in some directions we go up, and in other directions there is um a saddle. Now, I'm sorry I put that on the front board cuz I've no way to to cover it. But it's a saddle. Okay. And And this is a saddle point. It's the It's a point that's at the maximum in some directions and at the minimum in other directions. And actually, the perfect directions to look are the eigenvector directions.
We'll see that. So, this is um not a positive definite matrix. Okay. Now, I'm coming back to this example. Getting rid of this seven, let's move it up to 20. Let's Let's Let's make the thing really positive definite. Okay. So, this is This number is now 20. C is now 20. Okay. Now, that passes the test, which I haven't proved, of course. It passes the test for positive pivots. It passes the test for positive eigenvalues. How How can you tell that the eigenvalues of that matrix are positive without actually finding them? Of course, two by two, I could find them. But can you see How do I know they're positive?
I know that their product is I know that lambda one times lambda two is positive. Why? Because that's the determinant, right? Lambda one times lambda two is the determinant, which is 40 minus 36 is four. So, the determinant is four. And the trace the sum down the diagonal is 22. So, they multiply to give four. So, that leaves the possibility they're either both positive or both negative. But, if they're both negative, the trace couldn't be 22. So, they're both positive. So, both of the eigenvalues there are positive, both of the pivots are positive, the the determinants are positive, and I believe that this function is positive everywhere except at 0 0, of course.
When I write down this condition. I So, I believe that X transpose Let me copy X transpose AX is positive except, of course, at the minimum point at the zero vector. Of course, I don't expect miracles. So, what does its graph look like? And how do I check and how do I check that this really is positive? So, we take its graph for a minute. What would be the graph of that function? It does not have a saddle point. Let me I'll raise the board here and stay with this example for a while. So, I want to do the graph of Here's my function. 2 X squared 12 XY's, that could be positive or negative, and 20 Y squared.
My My point is so I mean, you're seeing the underlying point is that the things are positive definite when when in some way these these pure squares, squares we know to be positive. And when those kind of overwhelm this guy who could be positive or negative cuz X and Y could have same or different signs. When when these are big enough, they overwhelm this guy and make the total thing positive. And what would the graph now look like? Let me draw the X Well, let me draw the X direction, the Y direction, and the origin. At 0 0, I'm there. Where do I go as I move away from the origin? Where do I go as I move away from the origin?
I'm sure that I go up. The origin, the center point here, is a minimum because this thing I believe, and we better see why, it's the graph is like a bowl. The graph is like a bowl shaped. It's it's it's Here's the minimum. And because we've got a pure quadratic, we know it sits at the origin, we know it's tangent plane, the first derivatives are zero. So, so we know we know first derivatives first derivatives are all zero. But, that's not enough for a minimum. Its first derivatives were zero here. So, the the partial derivatives, the first derivatives are zero. Again. Cuz first derivatives are going to have an X or an a Y or a Y in them, they'll be zero at the origin.
It's the second derivatives that control everything. It's the second derivatives that this matrix is telling us. And somehow second So, here here's my point. You remember in calculus how did you decide on a minimum? First requirement was that the derivative had to be zero. But, then you didn't know if you had a minimum or a maximum. To know that you had a minimum, you had to look at the second derivative. The second derivative had to be positive. The the the slope had to be increasing as you went through the minimum point. The curvature had to go upwards. And that's what we're doing now in two dimensions and in N dimensions.
So, we're doing what we did in calculus. Second derivative positive will now become that the matrix of second derivatives is positive definite. Can I just So, this is the like the translation of of this is how minimum is coming in. In in in in in begin in in the beginning of calculus the we had a minimum was associated with second derivative being positive and first derivative zero, of course. Derivative first derivative. But, it was the second derivative that told us we had a minimum. And now in 1806 in linear algebra we'll have a minimum for our function now our function will have be a function not of just X, but several variables the way functions really are in real life.
The minimum will be when the matrix of second derivatives The matrix here was one by one. There was just one second derivative. Now, we've got lots. is positive definite. So, positive for a number translates into positive definite for a matrix. And it just brings everything together. You check You check pivots, you check determinants, you check eigenvalues, or you check this minimum stuff. Okay, let me come back to this graph. That graph goes upwards. And I have to see why. How do I know that this that this function is always positive? Can you look at that and tell that it's always positive? Maybe two by two you could feel pretty sure, but the What's the good way to show that this thing is always positive?
If we can express it as in terms of squares because that's what we know for any X and Y, whatever, if we're squaring something, we certainly are not negative. So, I believe that this expression, this function, could be written as a sum of squares. Can Can you tell me It See, because all the problems the headaches are coming from this XY term. If we can get expressions if we can get that inside a square. So, actually we're what we're doing is something called that you've seen called completing the square. Let me Let me Let me start the square and you complete it. Okay, I think we have two of X plus Now, I don't know how many Y's we need, but you'll figure it out squared.
How many Y's should I put in here to make What do I want to do? The two X squareds will be correct, right? What I want to do is put in the right number of Y's to get the 12 XY correct. And what is that number of Y's? Let's see. I've got two times it, so I really want six XY's to come out of here. I think maybe if I put three there. Does that look right to you? I have two This is we can mentally multiply that out. That's X squared, that's right. That's six XY times the two gives this one right. And how many Y squareds have I now got? How many Y squareds have I got from this term? 18. 18 was the key number, remember?
Now, if I want to make it 20, then I've got two left. Two Y squareds. That's completed the square. And it's Now, I can see that that that function is positive because it's a it's all squares. I've got two squares added together. I couldn't go negative. What if What if I went back to that seven? If instead of 20, that number was a seven, then what would happen? This would still be correct. I'd still have this square to get the 2x squared and the 12xy, and I'd have 18y squared, and then what would I do here? I'd have to remove 11 y squared, right? If I If I only had a seven here, then instead of when I had a 20, I had two more to to put in.
When I had an 18, which was the marginal case, I had no more to put in. When I had a seven, which was the case below zero, the the the indefinite case, I had minus 11. Okay. Now, so you you can see now that this thing is a bowl. It's going upwards. Uh if I cut it at at a plane z equal to one, say, I would get uh I would get a curve. What would be the equation for that curve? If I cut it at at height one, the equation would be this thing equal to one. And that curve would be an ellipse. So actually already I've brought into the into the lecture the different pieces that we're aiming for. We're aiming for the tests, which this passed.
We're aiming for the connection to a minimum, which this which we see in the in the graph. And if we chop it at if we set this thing equal to one, if I set that thing equal to one, that what that gives me is the cross section. It gives me this this curve, and its equation is this thing equals one, and that's an ellipse. Whereas if I cut through a saddle point, I'll get a hyperbola. Okay. But this minimum stuff is is really what I'm I'm most interested in. Okay. Uh but I I just have to ask, do you recognize I mean, these numbers here, the two that appeared outside, the three that appeared inside, the two that appeared there.
Actually, those numbers come from elimination. Completing the square is our good old method of Gaussian elimination in for expressed in terms of these squares. The the uh let me show you what I mean. I I I just think those numbers are no accident. If I take my matrix 2 6 6 and 20, and I do elimination, then the pivot is two. And I take three Oh, yeah, what's the multiplier? How much of row one do I take away from row two? Three. So what you're seeing in this completing the square is the pivot's outside and the multiplier inside. To To just do that again, the the pivot is two. Three of Three of those away from that gives me 2 6 0, and what's the second pivot?
Three of this away from this, three sixes will be 18, and the second pivot will also be a two. So that's the that's the U. This is the A, and of course the L was 1 0 1, and the multiplier was three. So, completing the square is elimination. Why am I happy to see to see that coming together? Because I know about elimination for n by n matrices. I just started talking about completing the square here for two by twos. But now I see what's going on. Completing the square really amounts to splitting this thing into a sum of squares. So what's the critical thing? I have a lot of squares, and in inside those squares are multipliers, but they're squares.
And And the question is, what's outside these squares? When I complete the square, what are the numbers that go outside? They're the pivots. They're the pivots, and that's why positive pivots give me sum of squares. Positive pivots, those pivots are the numbers that go outside the squares, so positive pivots, sum of squares, everything positive, graph goes up, a minimum at the origin. It's all connected together. All connected together, and in the two by two case, you can see those connections. But linear algebra now can go up to three by three, n by n. And let's do that next. Can I just before I leave two by two, I've written this expression matrix of second derivatives.
What's the matrix of second derivatives? It's that's one second derivative now, but if I'm in if I'm in two dimensions, I have a two by two matrix. It's the second x derivative is the second x derivative goes there. D Shall I write it? Yeah, I better use the This is f fxx, if you like. fxx, that means the second derivative of f in the x direction. fyy second derivative in the y direction. Those are the pure derivative second derivatives. They have to be positive for a minimum. This number has to be positive for a minimum. That number has to be positive for a minimum. But that's not enough. They Those numbers have to somehow be big enough to to overcome this cross derivative.
Why is the matrix symmetric? Because the second derivative of f with respect to x and y is equal to I can That's the beautiful fact about second derivatives is I could do those in either order, and I get the same thing. So this is the same as that. And uh so uh that's the matrix of second derivatives. And the test is it has to be positive definite. You might remember from from uh tucked in somewhere near the end of 1802, or at least in the book, was the condition for a minimum for a function of two variables. What's When do you have a minimum for a function of two variables? And believe me, that's what calculus is for.
The condition is first derivatives have to be zero. And the matrix of second derivatives has to be positive definite. So you may be remember there was an fxx times an fyy that had to be bigger than an fxy squared. That's just our determinant two by two. But now we now know the answer for three by three, n by n, because we can do elimination on n by n matrices. We can connect to eigenvalues of n by n matrices. We can do sum of squares, sum of n squares instead of only two squares. And so let's take a uh Let me go over here to do a three by three example. So three by three example. Okay. Oh, let me make Let me use Hmm, shall I use my favorite matrix?
You've seen this matrix before. Uh let me Uh yeah, let me Yes, let's let's use the good matrix. What the Why not? That's Okay. Is that matrix positive definite? What's Uh so I'm going to ask questions about this matrix. Is it positive definite, first of all? What's the function associated with that matrix? What's the x transpose Ax? Is Do Do we have a minimum for that function at zero? And then even what's the geometry? Okay. First of all, is the matrix positive definite? I've given you the numbers there, so you can take determinants. Maybe that's the quickest. Is that what you would do mentally?
If If I give you a matrix on a quiz and say, "Is it positive definite or not?" I would take that determinant and I'd get the answer two. I would take that determinant and I would get the answer for that two by two determinant. I get the answer three. And anybody remember the answer for the three by three determinant? It was four. Do you remember for these special matrices when we did determinants they went up two, three, four, five, six. They just went up linearly. So that matrix has the determinants are two, three, and four. Pivots. What are the pivots for that matrix? I'll tell you. They're The first pivot is two.
The next pivot is three over two. The next pivot is four over three. Because the product of the pivots has to give me those determinants. The product of these two pivots gives me that determinant. The product of all the pivots gives me that determinant. What are the eigenvalues? Oh, I don't know. Um Yeah, the eigenvalues I've got What do I have? A cubic equation, a degree three equation. There are three eigenvalues to find. If I believe what I've said today, what do I know about these eigenvalues? Even so I don't know the exact numbers. I I might actually I I I think I remember the numbers. Because these matrices are so important that people figured them out.
Uh but what do you What do you believe to be true about these three eigenvalues? You believe that they are all positive They're all positive. I think that they are two minus square root of two two and two plus the square root of two. I think. Uh let me just I I can't write those numbers down without checking the simple checks. What's the first simple check is the trace. So if I add those numbers, I get six. Then if I add those numbers, I get six. The other simple test is the determinant. If I Am I going to do this? Can you multiply those numbers together? I guess we can multiply by two, okay. Uh what's two minus square root of two times two plus square root of two?
That's That'll be four minus two. That'll be two. Yeah, two times two. That That's got the determinant right. So it's got a it's got a chance of being correct and I think it is. Now, what's the X transpose AX? I better give myself enough room for that. X transpose AX for this guy. It's two X1 squared and two X2 squared and two X3 squared. Those Those come from the diagonal. Those were easy. Now off the diagonal, there's a minus and a minus. They come together. There'll be minus two and then minus two what's are coming from this one two and two one position is is the X1 X2. I'm I'm doing mentally a multiplication of this matrix times a row vector on the left times a column vector on the right and I know that these numbers show up in the answer.
The diagonal is the perfect squares. This off diagonal is a minus 2 X1 X2 and there are no X1 X3s and there are minus 2 X2 X3s. And I believe that that expression is always positive. I believe that that curve that graph of the of this function. This is my function F. And I'm in more dimensions now than I can draw. It It but the graph of that function goes upwards. It's a bowl. Or maybe the right word is uh is forgotten. Um What's a long word for a bowl? Uh Hm. Maybe a paraboloid? I think paraboloid comes in. I'll I'll edit the tape and get that word in. Bowl, let's say. is Uh that So that And if I can I could complete the squares.
I could write that as a sum of three squares. And those three squares would get multiplied by the three pivots. And the pivots are all positive. So I would have positive pivots times squares. The net result would be a positive function and a bowl that goes upwards. And then finally, if I cut If I slice through this bowl If I Now I'm asking you to stretch your visualization here. Cuz I'm in four dimensions. I've got X1 X2 X3 in the base and this function is Z or F or something. And the its graph is going up. But I'm in four dimensions cuz I've got three in the base and then the upward direction.
But now if I cut through this four dimensional picture at level one So suppose I cut through this thing at height one. So I take all the points that are at height one. That gives me It gave me an ellipse over there. In that In that two by two case in this case this will be the equation of an ellipsoid. A football in other words. Well, not quite a football. A lopsided football. What What will be Can I Can I try to describe to you what the ellipsoid will look like? This ellipsoid. I'm sorry that the that I've ended the matrix right at the point. Let's Let me Let me be sure you see the the equation.
2 X1 squared, 2 X2 squared, 2 X3 squared minus two of the cross products equal one. That is the equation of of a football. So what do I mean by a football or an ellipsoid? I mean that Well, I'll draw it here. It's like that. And like that. It's got a center. And it's got um It's got three principal directions. This this ellipsoid. So You see what I'm saying? If we had a sphere, then all directions would be the same. If we had a true football or it's closer to a rugby ball really cuz it's more curved than a football. It would be It would have one long direction and the other two would be equal.
That would be like having a matrix that had one eigenvalue repeated. And then one other different. So the sphere comes from like the identity matrix. All eigenvalues the same. Uh rugby ball comes from a case where uh three the three I two of the three eigenvalues are the same. But we now have a case where the typical case where the three eigenvalues are all different. So this will have How do I say it? If I If I look at this ellipsoid correctly, it'll have a major axis. It'll have a middle axis. And it'll have a minor axis. And those three axes will be in the direction of the eigenvectors. And the length of those axes will be determined by the eigenvalues.
It It I can get turn this all into linear algebra. Cuz we have the right we the right thing we know about eigenvectors and eigenvalues for that matrix is what? Let me just tell you the repeat the main linear algebra point. How could we turn what I said into into into algebra? We would write this A as Q the eigenvector matrix times lambda the eigenvalue matrix times Q transpose. The principal axis theorem, we'll call it now. The eigenvectors tell us the directions of the principal axes. The eigenvalues tell us the lengths of those axes. Actually, the lengths are the half lengths are one over the eigenvalues, it turns out.
And that is the matrix factorization, which is the which is the most important matrix factorization in in our eigenvalue material so far. That's diagonalization for a symmetric matrix, so instead of the inverse, I can write the transpose. Okay, I've I've So, what I've tried today is to tell you the what's going on with positive definite matrices. Uh you see all how all these pieces are there, and linear algebra connects them. Okay. Um see you on Friday.