Positive Definite Matrices and Minima

Positive definite matrices and minima Studying positive definite matrices brings the whole course together; we use pivots, determinants, eigenvalues and stability. The new quantity here is x T Ax; watch for it. This lecture covers how to tell if a matrix is positive definite, what it means for it to be positive definite, and some geometry. Positive definite matrices � Given a symmetric two by two matrix a b b c � , here are four ways to tell if it’s positive definite: 1. Eigenvalue test: λ1 > 0, λ2 > 0. 2. Determinants test: a > 0, ac − b2 > 0. 3. Pivot test: a > 0, ac − b2 > 0. a 4. x T Ax is positive except when x = 0 (this is usually the definition of posi­ tive definiteness). 2 by 2 � Using the determinants test, we know that 2 6 6 y � is positive definite when 2y − 36 > 0 or when y >�18. � 2 6 The matrix is on the borderline of positive definiteness and is 6 18 called a positive semidefinite matrix. It’s a singular matrix with eigenvalues 0 and 20. Positive semidefinite matrices have eigenvalues greater than or equal to 0. For a singular matrix, the determinant is 0 and it only has one pivot. � �� � � � 2 6 x1 x1 x2 x T Ax = 6 18 x2 � � � � 2x1 + 6x2 x1 x2 = 6x1 + 18x2 = 2x12 + 12x1 x2 + 18x22 = ax12 + 2bx1 x2 + cx22 . If this quadratic form is positive for every (real) x1 and x2 then the matrix is positive definite. In this positive semi-definite example, 2x12 + 12x1 x2 + 18x22 = 2( x1 + 3x2 )2 = 0 when x1 = 3 and x2 = −1. Tests for minimum � If we apply the fourth test to the matrix 2 6 6 7 � which is not positive defi­ nite, we get the quadratic form f ( x, y) = 2x2 + 12xy + 7y2 . The graph of this function has a saddle point at the origin; see Figure 1. Figure 1: The graph of f ( x, y) = 2x2 + 12xy + 7y2 . � � 2 6 The matrix is positive definite – its determinant is 4 and its trace 6 20 is 22 so its eigenvalues are positive. The quadratic form associated with this matrix is f ( x, y) = 2x2 + 12xy + 20y2 , which is positive except when x = y = 0. The level curves f ( x, y) = k of this graph are ellipses; its graph appears in Figure 2. If a > 0 and c > 0, the quadratic form ax2 + 2bxy + cy2 is only negative when the value of 2bxy is negative and overwhelms the (positive) value of ax2 + cy2 . The first derivatives f x and f y of this function are zero, so its graph is tan­ gent to the xy-plane at (0, 0, 0); but this was also true of 2x2 + 12xy + 7y2 . As in single variable calculus, we need to look at the second derivatives of f to tell whether there is a minimum at the critical point. We can prove that 2x2 + 12xy + 20y2 is always positive by writing it as a sum of squares. We do this by completing the square: 2x2 + 12xy + 20y2 = 2( x + 3y)2 + 2y2 . Note that 2( x + 3y)2 = 2x2 + 12xy + 18y2 , and 18 was the “borderline” between passing and failing the tests for positive definiteness. Figure 2: The graph of f ( x, y) = 2x2 + 12xy + 20y2 . When we complete the square for 2x2 + 12xy + 7y2 we get: 2x2 + 12xy + 7y2 = 2( x + 3y)2 − 11y2 which may be negative; e.g. when x = −3 and y = 1. The coefficients that appear when completing the square are exactly the entries that appear when performing elimination on the original matrix. The two pivots are multiplied by the squares, and the coefficient c in the term ( x − cy)2 is the multiple of the first row that’s subtracted from the second row. � � � � 2 6 2 6 subtract 3 times row 1 −−−−−−−−−−−−→ . 6 20 0 2 We can see the terms that appear when completing the square in: � � � � 2 6 1 0 U= , and L = . 0 2 3 1 When we complete the square, the numbers multiplied by the squares are the pivots; if the pivots are all positive then the sum of squares will always be positive. Hessian matrix The matrix of second derivatives of f ( x, y) is: � � f xx f xy . f yx f yy This matrix is symmetric because f xy = f yx . Its determinant is positive when 2 test for a mini­ the matrix is positive definite, which matches the f xx f yy > f xy mum that we learned in calculus. n by n A function of several variables f ( x1 , x2 , ..., xn ) has a minimum when its matrix of second derivatives is positive definite, and identifying minima of functions is often important. The tests we’ve just learned for 2 by 2 matrices also apply to n by n matrices. A 3 by 3 example: ⎡ 2 A = ⎣ −1 0 ⎤ −1 0 2 −1 ⎦ . −1 2 Is this matrix positive definite? Our tests will say yes. What’s the function x T Ax associated with this matrix? Does that function have a minimum at x = 0? What does the graph of its quadratic form look like? Looking at determinants we see: ⎡ ⎤ � � 2 −1 0 2 −1 2 −1 ⎦ = 4. det[ 2 ] = 2, det = 5, det ⎣ −1 −1 2 0 −1 2 These are all positive, so A is positive definite. The pivots of A are 2, 3/2 and 4/3 (all positive) because the products of the pivots equal the determinants. The eigenvalues of A √ their product is 4. It’s not difficult to √are positive and check that they are 2 − 2, 2 and 2 + 2 (all positive). Ellipsoids in Rn f (x) = x T Ax = 2x12 + 2x22 + 2x32 − 2x1 x2 − 2x2 x3 . Because A is positive definite, we expect f (x) to be positive except when x = 0. Its graph is a sort of four dimensional bowl or paraboloid. If we wrote f (x) as a sum of three squares, those squares would be multiplied by the (pos­ itive) pivots of A. Earlier, we said that a horizontal slice of our three di­ mensional bowl shape would be an ellipse. Here, a horizontal slice of the four dimensional bowl is an ellipsoid – a little bit like a rugby ball. For ex­ ample, if we cut the graph at height 1 we get a surface whose equation is: 2x12 + 2x22 + 2x32 − 2x1 x2 − 2x2 x3 = 1. Just as an ellipse has a major and minor axis, an ellipsoid has three axes. If we write A = QΛQ T , as the principal axis theorem tells us we can, the eigenvectors of A tell us the directions of the principal axes of the ellipsoid. The eigenvalues tell us the lengths of those axes.