From the series: Differential Equations and Linear Algebra
Gilbert Strang, Massachusetts Institute of Technology (MIT)
A positive definite matrix S has positive eigenvalues, positive pivots, positive determinants, and positive energy vTSv for every vector v. S = ATA is always positive definite if A has independent columns.
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.
1.1: Overview of Differential Equations Linear equations include dy/dt = y, dy/dt = –y, dy/dt = 2ty . The equation dy/dt = y *y is nonlinear.
1.2: The Calculus You Need The sum rule, product rule, and chain rule produce new derivatives from the derivatives of xn , sin(x ) and ex . The Fundamental Theorem of Calculus says that the integral inverts the derivative.
1.4b: Response to Exponential Input, exp(s*t) With exponential input, est , from outside and exponential growth, eat , from inside, the solution, y(t), is a combination of two exponentials.
1.4c: Response to Oscillating Input, cos(w*t) An oscillating input cos(ωt ) produces an oscillating output with the same frequency ω (and a phase shift).
1.4d: Solution for Any Input, q(t) To solve a linear first order equation, multiply each input q(s) by its growth factor and integrate those outputs.
1.4e: Step Function and Delta Function A unit step function jumps from 0 to 1. Its slope is a delta function: zero everywhere except infinite at the jump.
1.5: Response to Complex Exponential, exp(i*w*t) = cos(w*t)+i*sin(w*t) For linear equations, the solution for f = cos(ωt ) is the real part of the solution for f = eiωt . That complex solution has magnitude G (the gain).
1.6: Integrating Factor for a Constant Rate, a The integrating factor e-at multiplies the differential equation, y’=ay+q, to give the derivative of e-at y: ready for integration.
1.6b: Integrating Factor for a Varying Rate, a(t) The integral of a varying interest rate provides the exponent in the growing solution (the bank balance).
1.7: The Logistic Equation When –by2 slows down growth and makes the equation nonlinear, the solution approaches a steady state y( ∞) = a/b.
1.7c: The Stability and Instability of Steady States Steady state solutions can be stable or unstable – a simple test decides.
2.1: Second Order Equations For the oscillation equation with no damping and no forcing, all solutions share the same natural frequency.
2.1b: Forced Harmonic Motion With forcing f = cos(ωt ), the particular solution is Y *cos(ωt ). But if the forcing frequency equals the natural frequency there is resonance.
2.3: Unforced Damped Motion With constant coefficients in a differential equation, the basic solutions are exponentials est . The exponent s solves a simple equation such as As2 + Bs + C = 0 .
2.3c: Impulse Response and Step Response The impulse response g is the solution when the force is an impulse (a delta function). This also solves a null equation (no force) with a nonzero initial condition.
2.4: Exponential Response - Possible Resonance Resonance occurs when the natural frequency matches the forcing frequency — equal exponents from inside and outside.
2.4b: Second Order Equations With Damping A damped forced equation has a particular solution y = G cos(ωt – α). The damping ratio provides insight into the null solutions.
2.5: Electrical Networks: Voltages and Currents Current flowing around an RLC loop solves a linear equation with coefficients L (inductance), R (resistance), and 1/C (C = capacitance).
2.6: Methods of Undetermined Coefficients With constant coefficients and special forcing terms (powers of t , cosines/sines, exponentials), a particular solution has this same form.
2.6b: An Example of Method of Undetermined Coefficients This method is also successful for forces and solutions such as (at2 + bt +c) est : substitute into the equation to find a, b, c .
2.6c: Variations of Parameters Combine null solutions y1 and y2 with coefficients c1(t) and c2(t) to find a particular solution for any f(t).
2.7: Laplace Transform: First Order Equation Transform each term in the linear differential equation to create an algebra problem. You can then transform the algebra solution back to the ODE solution, y(t) .
2.7b: Laplace Transform: Second Order Equation The second derivative transforms to s2Y and the algebra problem involves the transfer function 1/ (As2 + Bs +C).
3.1: Pictures of the Solutions The direction field for dy/dt = f(t,y) has an arrow with slope f at each point t, y . Arrows with the same slope lie along an isocline.
3.2: Phase Plane Pictures: Source, Sink Saddle Solutions to second order equations can approach infinity or zero. Saddle points contain a positive and also a negative exponent or eigenvalue.
3.2b: Phase Plane Pictures: Spirals and Centers Imaginary exponents with pure oscillation provide a “center” in the phase plane. The point (y, dy/dt) travels forever around an ellipse.
3.2c: Two First Order Equations: Stability A second order equation gives two first order equations for y and dy/dt . The matrix becomes a companion matrix.
3.3: Linearization at Critical Points A critical point is a constant solution Y to the differential equation y’ = f(y) . Near that Y , the sign of df/dy decides stability or instability.
3.3b: Linearization of y'=f(y,z) and z'=g(y,z) With two equations, a critical point has f(Y,Z) = 0 and g(Y,Z) = 0. Near those constant solutions, the two linearized equations use the 2 by 2 matrix of partial derivatives of f and g .
3.3c: Eigenvalues and Stability: 2 by 2 Matrix, A Two equations y’ = Ay are stable (solutions approach zero) when the trace of A is negative and the determinant is positive.
5.1: The Column Space of a Matrix, A An m by n matrix A has n columns each in R m . Capturing all combinations Av of these columns gives the column space – a subspace of R m .
5.4: Independence, Basis, and Dimension Vectors v 1 to v d are a basis for a subspace if their combinations span the whole subspace and are independent: no basis vector is a combination of the others. Dimension d = number of basis vectors.
5.5: The Big Picture of Linear Algebra A matrix produces four subspaces – column space, row space (same dimension), the space of vectors perpendicular to all rows (the nullspace), and the space of vectors perpendicular to all columns.
5.6: Graphs A graph has n nodes connected by m edges (other edges can be missing). This is a useful model for the Internet, the brain, pipeline systems, and much more.
6.1: Eigenvalues and Eigenvectors The eigenvectors x remain in the same direction when multiplied by the matrix (A x = λx ). An n x n matrix has n eigenvalues.
6.2: Diagonalizing a Matrix A matrix can be diagonalized if it has n independent eigenvectors. The diagonal matrix Λis the eigenvalue matrix.
6.3: Solving Linear Systems d y /dt = A y contains solutions y = eλt x where λ and x are an eigenvalue / eigenvector pair for A .
6.4: The Matrix Exponential, exp(A*t) The shortest form of the solution uses the matrix exponential y = eAt y (0) . The matrix eAt has eigenvalues eλt and the eigenvectors of A.
6.4b: Similar Matrices, A and B=M^(-1)*A*M A and B are “similar” if B = M-1AM for some matrix M . B then has the same eigenvalues as A .
6.5: Symmetric Matrices, Real Eigenvalues, Orthogonal Eigenvectors Symmetric matrices have n perpendicular eigenvectors and n real eigenvalues.
7.2: Positive Definite Matrices, S=A'*A A positive definite matrix S has positive eigenvalues, positive pivots, positive determinants, and positive energy vT Sv for every vector v. S = AT A is always positive definite if A has independent columns.
7.2b: Singular Value Decomposition, SVD The SVD factors each matrix A into an orthogonal matrix U times a diagonal matrix Σ (the singular value) times another orthogonal matrix VT : rotation times stretch times rotation.
7.3: Boundary Conditions Replace Initial Conditions A second order equation can change its initial conditions on y(0) and dy/dt(0) to boundary conditions on y(0) and y(1) .
8.1: Fourier Series A Fourier series separates a periodic function F(x) into a combination (infinite) of all basis functions cos(nx) and sin(nx) .
8.1b: Examples of Fourier Series Even functions use only cosines (F(–x) = F(x) ) and odd functions use only sines. The coefficients an and bn come from integrals of F(x) cos(nx ) and F(x) sin(nx ).
8.1c: Fourier Series Solution of Laplace's Equation Inside a circle, the solution u (r , θ) combines rn cos(n θ) and rn sin(n θ). The boundary solution combines all entries in a Fourier series to match the boundary conditions.
8.3: Heat Equation The heat equation ∂u /∂t = ∂2u /∂x2 starts from a temperature distribution u at t = 0 and follows it for t > 0 as it quickly becomes smooth.