Differential Equations and Linear Algebra, 7.2: Positive Definite Matrices, S=A'*A

OK. This is positive definite matrix day.

Our application was the second-order equation with a symmetric matrix, S. And we solved this equation. Second derivative, plus S times y, equals 0.

And you maybe remember how we solved it. We looked for an exponential solution. e to the I omega t, times a vector x. We substituted, and we discovered x had to be an eigenvector of S, as usual. And lambda, which was omega squared, is the eigenvalue.

But I didn't stop to point out that if we want lambda to be omega squared, we need to know lambda greater or equal to 0. So that is the best of the best matrices. Symmetric and positive definite, or positive semidefinite, which means the eigenvalues are not only real, they're real for symmetric matrices. They're also positive. Positive definite matrices-- automatically symmetric, I'm only talking about symmetric matrices-- and positive eigenvalues.

OK. There it is. Positive definite matrix. All the eigenvalues are positive. Positive semidefinite. That word semi allows lambda equal 0. The matrix could be singular, but all the eigenvalues have to be greater or equal to 0.

And let me show you exactly where those matrices come from. Those matrices come from A transpose A. If I take any matrix A, could be rectangular. And A transpose A will be square. A transpose A will be symmetric. And it will be at least positive semidefinite. Why is that?

This is the simple step that is worth remembering. What's special about A transpose A x equal lambda x? The good idea? Multiply both sides by x transpose. Take the inner product of both sides with x. Then I have x transpose times the left side, is x transpose times the right side.

I'm OK with equation 2. When my S is A transpose A, that's my S. OK.

But now I look at this. That is A x in a product with itself. That's the length of A x squared. Any time I have y transpose y, I'm getting the length of y squared. Here y is A x, so I'm getting the length of A x squared. Over here, y is x, so I'm getting the length of x squared.

And you see that number lambda is, in this equation, I have a number that can't be negative. A number that's positive, for sure. Because x is not the 0 vector. So lambda is never negative.

A x could be the 0 vector. If we were in a singular case, A x could be the 0 vector. In that case, I would only learn lambda equals 0, and I'd be in this semidefinite case.

So if I want to move from semidefinite to definite, then I must rule out A x equals 0 there. Because that's certainly a possibility. If I took the 0 matrix, all 0's, as A, A transpose A would be the 0 matrix. That would be symmetric. All its eigenvalues would be 0.

Would it be positive semidefinite? Yes. Yes. All its eigenvalues would actually be 0. Of course, that's not a case that we are really thinking about. More often we're in this good case where all the eigenvalues are above 0.

OK. So that's the meaning. And now the next job. How do we recognize a positive definite matrix? It has to be symmetric. That's easy to see.

But how can we tell if its eigenvalues are positive? That's not fun because computing eigenvalues is a big job. For a large matrix, we take time on that. We didn't know how to do it a little while ago. Now there are good ways to do it, but it's not for paper and pencil, and not for I.

So how can we tell that all the eigenvalues are positive? Well, we only want to know their sign. We don't have to know what they are. We don't know that we need the number, we just want to know is it a positive number.

And there are several neat tests. Can I show you them? I'm going to have five tests. Five equivalent tests. Any one of these tests is sufficient to make the matrix S positive definite.

There is a particular S there that I'll use as a test matrix. So there is a symmetric matrix S. And I know it is positive definite. But how do I know?

OK. Well. So can you take five things here? They connect all of linear algebra. It's really beautiful. That the eigenvalues, that's one chapter of linear algebra. The pivots are another chapter of linear algebra.

Do you remember about pivots? That's when you do elimination. So 4 is the first pivot. The first pivot. Pivot number 1 is the 4.

And then when I take a multiple of that away from that, I get a second pivot. And I'd see that that was positive. So what's that? Maybe I take 1 and 1/2 away of this. I multiply that by 1 and 1/2, 6, 9. Subtract from 6, 10. So I actually get a 1 down there.

So pivot number 2 is a 1 in that case. Right? 6, 9 taken away from 6, 10 leaves me 0, 1.

OK. It passed the pivot test. Notice I didn't compute the eigenvalues. I'm just doing other tests.

Now here's another beautiful test. It involves determinants. Now, I have to say upper. Upper left. Upper left determinants greater than 0.

What do I mean by an upper left determinant? I look at my matrix. That's a 1 by 1 determinant. Certainly positive. That determinant is 4.

Here is a 2 by 2 determinant. And that determinant is 40 minus 36, so happened to be 4 again. So the determinant of the matrix is 4.

But I also needed the ones on the way. I can't just find the determinant of the whole matrix. That's the last part of this test, but I have to do all the others as I get there.

So it passes that test. Check. It works. So that test is passed. I'm doing more work than I need to do because one test would have done the job.

Now here comes another one. S is A transpose A. That's what we looked at a minute ago. If S has this form A transpose A.

Oh, what did we convince ourselves? We said that this was sure to be semidefinite. And I needed some condition to avoid A x equals 0. There was the possibility of A x equals 0.

I'll just bring that down. You remember we started there and ended up here. And if A x was 0 then lambda was 0. We were in the semidefinite case. So I have to avoid that.

So I have to say when A has independent columns. And I think I could factor that matrix S into A transpose A. I'm sure I could. And get independent columns. And it would pass test 4.

I want to go on to test 5. Which really, in a way, is the definition, the best definition, of positive definite. So if I took number 5, it's the energy definition. So can I tell you what that means?

I mean that x transpose Sx. If I take my matrix S that I'm testing for positive definite, I multiply on the right by any vector x, any x, and on the left by x transpose. Well, I get a number. S is a matrix. Sx is a vector. Inner product with a vector. I get a number. And that number should be positive for all x.

Oh, I have to make one exception. If x is the 0 vector, then of course that answer is 0. All x except the 0 vector.

OK. So that would be a way to-- another test. And this is associated in applications with energy. So I call this the energy test, or really the energy definition, of positive definite. x transpose Sx.

I'd like to apply that test. So you'll see what does it mean. Now we're looking at all x to this particular example.

But I won't throw away this board here. You see eigenvalues, pivots, determinants, A transpose A, and energy. Really all the pieces of linear algebra.

A transpose A. We'll see it more and more. It comes up in least squares.

If I have a general matrix A, it's not even square. It doesn't have great properties. But when I compute A transpose A, then I get a symmetric matrix. And now I know also a positive semidefinite. And with a little bit more positive definite matrix. OK.

By the way, are there five tests for semidefinite matrices? Yes. There are five similar tests. All eigenvalues greater or equal to 0. All pivots greater or equal to 0. I can go down this and just allow that borderline case that brings in semidefinite. I won't do that.

Let me take my matrix S. That small, example matrix. And apply the energy test. OK. So I'm looking at energy.

So I'm looking at x. That's x1 x2, times my matrix 4, 6, 6, 10, times x1 x2. That's the energy. That's my x transpose Sx.

x transpose Sx. Is that what we wanted to compute? Yes. x transpose Sx.

Now, can I compute that? Yes. It's a matrix multiplication. Nothing magical here. But when I do, I'll show you the shortcut.

When I do that, a 4 x1 is going to appear, and it'll be multiplied by that x1 over there. I'll get a 4 x1 squared. And then I'll have a 6 x2 that's multiplying that x1. So there's a 6 x1 x2.

And now from this. That was the first component. And now I have 6 x1 and 10 x2. Multiply an x2. Well, that's another 6 x1 x2. And the 10, we'll multiply x2 and x2. x2 squared.

I did that quickly. But the result is just easy to see. The 4, 6, 6, 10 show up in the squares. The diagonal 4 and 10 show up in the squares. And the off diagonal 6, which doubles to 12, shows up in the x1 x2, the cross term.

OK. Now why should that-- so that's a number for every x1 and x2. Suppose x1 is 1 and x2 is 1. Then the number I get is 4, plus 6, plus 6, plus 10. That's probably 26. It's positive.

What if x1 is 1-- let me try this. x1 is 1 and x2 is minus 1. Do I still get a positive energy? So my vector is 1 minus 1. So I get 4. Now, because of that, I have minus 6, and minus 6, and 10, from the x2 squared. And that's 14 minus 12. That's 2. It's positive.

Well, I tested two vectors. I tested the 1, 1 vector and the 1, minus 1 vector. But you have to know that for every vector x, this does turn out to be positive. And I can show you that by something called completing the square. It's not what I plan to do.

But the beauty is we now understand this energy test. What it means to take x transpose Sx, write it out, and ask is it always positive. Is it always positive?

OK. So that's the fifth, number 5, test. But I think of it really as the definition. And it means-- can I draw a picture?

Here is x1. Here's x2. And now I'm going to-- this is my function. x transpose A x. My energy.

If I graph that, I have an x, and a y, and a function z. That function of x and y. What kind of a graph does it have? When x1 and x2 are 0, it's there. When x1 and x2 move away from 0, it goes positive. That graph is like that. It's sort of a bowl. And I have a minimum.

One of the main application of derivatives in calculus is to find the test for a minimum, and decide minimum or maximum. Minimum or maximum. And you remember the second derivative decides a minimum or maximum. Positive second derivative, minimum. Negative second derivative, maximum. It tells you about the bending of the curve.

Well, we're in two dimensions now, with a function of two variables. This is multivariable calculus. So what becomes positive second derivative, becomes positive definite matrix. A matrix of second derivatives. This is the whole subject of optimization. Maximizing, minimizing, comes here.

OK. That's for another day.

I just would like to tell you one more thing about positive definite matrices. I got a book in the mail which could be quite valuable. It's a little paperback, and the title is Frequently Asked Questions in Interviews for Financial Math.

Being a Quant. Going to Wall Street. Becoming rich. So they don't give you all the money right away. They make you show that you know something.

And so they ask a few math questions. And the first question was-- I was happy to see this. The first question asked, when is this matrix positive definite?

OK. Can you see that matrix? 1 is on the diagonal. Those are correlation. This is a correlation matrix. That's why it's important in finance.

It might be the three correlations of bonds, and stocks, and foreign exchange. So each one is correlated to itself with a full correlation of 1. But there'll be a correlation between bonds and stocks going up together, but not perfectly together, by some number a. And bonds and foreign exchange with some number b. Stocks and foreign exchange, some number c. So that's the matrix of correlations. And the key point is, it is positive definite.

So the question when you go to Wall Street to apply for the money. If you're asked what's the test on those numbers a, b, c, to have a positive definite, proper correlation matrix? I would suggest the determinant test.

The determinant test, if I'm given a small matrix, I'll just do the determinants. So that determinant is 1. No problem.

This determinant, what's the 2 by 2 determinant? 1 minus a squared. So 1 minus a squared has to be positive. I'm doing the determinant test.

And what's the 3 by 3 determinant? 1 from the diagonal. And I have an acb and an acb. I think I have two acb's from the three terms.

Now, those terms have the plus signs. And now I have some with a minus sign, which better not be too big. That's the whole point on positive definite matrices. The off diagonal is not allowed to overrun the diagonal. The diagonal should be the biggest numbers.

OK. So I saw that a squared had to be below 1. But now what's the determinant test? I think this has to be bigger than what I'm getting from this direction, which is a b squared, and a c squared, and an a squared. Oh, look at that. a squared, b squared, and c squared. That would be the answer.

That first test there. Second test there. Well, the easy test was just 1, is positive. So really, that's what they're looking for. That would be the test, those numbers. So abc can't be too large or that would begin to fail. Good.

So positive definite matrices have lots of applications. Here was minimum. Here was correlation matrices and finance. Many, many other places.

Let me just bring down the five tests. Eigenvalues, pivots, determinants, A transpose A, and energy. And I'll stop there. Thank you.