Positive Definite Matrices and Minima

Four tests for one property

This lecture, Strang says, “brings the whole course together” — pivots, determinants, eigenvalues — plus something new: the expression $\mathbf{x}^T A \mathbf{x}$, “the guy to watch in this lecture.” Two goals. First: given a matrix — say five by five — how can you tell whether it’s positive definite? Second, and more important: what does the property mean, and why do we care? At the end comes geometry — ellipses go with positive definite matrices; hyperbolas do not.

Throughout, every matrix is symmetric — that’s understood. For a symmetric $2 \times 2$ matrix

$$A = \begin{bmatrix} a & b \\ b & c \end{bmatrix}$$

each of the following is a complete test for positive definiteness:

1. Eigenvalue test: $\lambda_1 > 0$ and $\lambda_2 > 0$.
2. Determinant test: $a > 0$ and $ac - b^2 > 0$ — all the leading determinants positive. (For an $n \times n$ matrix, the determinants of all the upper-left submatrices — the “northwest, Seattle submatrices” — must be positive.)
3. Pivot test: the first pivot $a > 0$, and the second pivot $\dfrac{ac - b^2}{a} > 0$, since the pivots multiply to the determinant.
4. The energy test ★: $\mathbf{x}^T A \mathbf{x} > 0$ for every $\mathbf{x} \neq \mathbf{0}$.

Test 4 gets the star. In most presentations it’s the definition of positive definiteness, and tests 1–3 are the ways to check it. It’s the new idea of the lecture.

A family of examples: 2, 6, 6, and what?

Start with

$$A = \begin{bmatrix} 2 & 6 \\ 6 & \ast \end{bmatrix}$$

and ask: what number in the corner makes it positive definite? Don’t find eigenvalues — use the determinant test. The first entry $2$ is positive, fine. The determinant $2c - 36$ must be positive, so the corner had better be more than eighteen. Put $19$ there: determinant $38 - 36 = 2 > 0$ — positive definite.

Now play it really close and put $18$ there:

$$\begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix}$$

Not quite. This matrix is on the borderline — Strang calls it positive semi-definite. It’s singular: the second row $(6, 18)$ is a multiple of the first, so it’s a rank-one matrix with one eigenvalue $0$, and from the trace the other eigenvalue is $20$. Eigenvalues $\geq 0$ — it’s that “equal to” that brings in the word semi-definite. And the pivots? The first pivot is $2$; there is no second pivot — a singular matrix only has one.

What is $\mathbf{x}^T A \mathbf{x}$? Take $\mathbf{x} = (x_1, x_2)$ and multiply it out for the matrix with $18$:

$$\begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = 2x_1^2 + 12x_1x_2 + 18x_2^2.$$

The $2$ comes from the diagonal, the $18$ from the diagonal, and the cross term collects $6$ from each side — twelve $x_1x_2$‘s in all. In general $\mathbf{x}^T A \mathbf{x} = ax^2 + 2bxy + cy^2$: a quadratic form. $A\mathbf{x}$ was linear; with an $\mathbf{x}^T$ on the left we’re up to degree two — purely degree two, no linear part, no constant, no cubes. The question of positive definiteness is: is that quantity positive for every $x_1, x_2$?

When it fails: the saddle

Push the corner entry all the way down to $7$ — “such a total disaster.” The determinant is $14 - 36 = -22$, the pivots are $2$ and $-11$, and one eigenvalue is certainly negative. The quadratic form is

$$f(x, y) = 2x^2 + 12xy + 7y^2,$$

and there must be inputs that make it negative. Try $x = 1$, $y = -1$: the squares give $2 + 7$, but the cross term gives $-12$, and $2 - 12 + 7 = -3 < 0$.

What does the graph of $f$ look like? It goes through the origin. Along the $x$-axis it climbs like $2x^2$; along the $y$-axis it climbs like $7y^2$; along the forty-five degree line it climbs too. Going up in some directions — but we just checked it goes down along the direction $x = -y$. The surface is a saddle: up one way, down the other, like the way a saddle drops for your legs and rises fore and aft. The origin is a saddle point — a maximum in some directions and a minimum in others. And the perfect directions to look, it will turn out, are the eigenvector directions.

When it works: the bowl, and the calculus of minima

Now raise the corner to $20$ and make the matrix really positive definite:

$$A = \begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}, \qquad f(x, y) = 2x^2 + 12xy + 20y^2.$$

Check the tests without finding the eigenvalues. The determinant is $40 - 36 = 4$, so $\lambda_1\lambda_2 = 4 > 0$: both eigenvalues have the same sign. The trace is $22$, so they can’t both be negative — both positive. The pivots are $2$ and $4/2 = 2$: positive. And the function should be positive everywhere except at $(0,0)$ — “I don’t expect miracles.”

The graph is now a bowl (the long word is paraboloid), with its minimum at the origin. Here is where linear algebra meets calculus. In first-year calculus, a minimum required the first derivative to be zero — but that alone couldn’t distinguish minimum from maximum. The second derivative had to be positive: the slope increasing, the curvature upward. For a pure quadratic, the first derivatives automatically vanish at the origin (each term of $\partial f/\partial x$ or $\partial f/\partial y$ still carries an $x$ or a $y$). It’s the second derivatives that control everything — and the second derivatives are exactly what the matrix holds.

That matrix of second derivatives, in two variables, is

$$\begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix}$$

— symmetric, because the beautiful fact about mixed second derivatives is that $f_{xy} = f_{yx}$ in either order. The pure second derivatives $f_{xx}$ and $f_{yy}$ must be positive, but that’s not enough: they have to be big enough to overcome the cross derivative. You may remember, tucked in near the end of 18.02, the condition $f_{xx}f_{yy} > f_{xy}^2$ — that’s just our $2 \times 2$ determinant test.

Completing the square is elimination

How do you see that $2x^2 + 12xy + 20y^2$ is always positive? Squares are what we know to be nonnegative — so write it as a sum of squares. Start the square: $2(x + 3y)^2$ gets the $2x^2$ and the $12xy$ right, and produces $18y^2$; two more $y^2$‘s are left over:

$$2x^2 + 12xy + 20y^2 = 2(x + 3y)^2 + 2y^2.$$

Two squares added together — it couldn’t go negative. With the marginal $18$ in the corner, nothing is left over: $2(x+3y)^2 + 0 \cdot y^2$, positive semi-definite. With the disastrous $7$, you’d have to remove eleven: $2(x+3y)^2 - 11y^2$ — the indefinite case, the saddle.

Now look hard at the numbers $2$, $3$, $2$. They are no accident.

And elimination works for $m \times m$ matrices — which is how the whole story scales past two by two: $m$ pivots outside $m$ squares.

Three by three: the favorite matrix

The graph of this $f$ lives in four dimensions — $x_1, x_2, x_3$ in the base and $f$ going up — “I’m asking you to stretch your visualization here.” But slice it at height one, taking all points where

$$2x_1^2 + 2x_2^2 + 2x_3^2 - 2x_1x_2 - 2x_2x_3 = 1,$$

and you get an ellipsoid — a lopsided football (closer to a rugby ball). In the $2 \times 2$ bowl, the slice at $z = 1$ was an ellipse; slicing through a saddle would give a hyperbola instead.

A general ellipsoid has a center and three principal directions: a major axis, a middle axis, and a minor axis. A sphere is the case of the identity — all eigenvalues equal; a rugby ball has two eigenvalues repeated and one different; our matrix, with three different eigenvalues, gives three different axis lengths.

Problems

Work these with the four tests and the completing-the-square trick from the lecture.

Problem 27.1 Threshold for definiteness

For which values of $c$ is

$$A = \begin{bmatrix} 3 & 4 \\ 4 & c \end{bmatrix}$$

positive definite? For the borderline value of $c$, find both eigenvalues and the pivots, and classify the matrix.

Show solution

Determinant test: $3 > 0$ ✓ and $3c - 16 > 0$, so $A$ is positive definite exactly when $c > \frac{16}{3}$.

At the borderline $c = \frac{16}{3}$ the determinant is zero, so the matrix is singular: one eigenvalue is $0$, and from the trace the other is $3 + \frac{16}{3} = \frac{25}{3}$. The pivots: the first is $3$; there is no second pivot (rank one — the second row $\left(4, \frac{16}{3}\right)$ is $\frac{4}{3}$ times the first). Eigenvalues $\geq 0$ but not all $> 0$: positive semi-definite.

Problem 27.2 Quadratic form and its graph

Write out $f(x, y) = \mathbf{x}^T A \mathbf{x}$ for

$$A = \begin{bmatrix} 1 & 4 \\ 4 & 5 \end{bmatrix},$$

decide whether the graph of $f$ is a bowl or a saddle, and exhibit a specific $(x, y)$ where $f$ is negative if one exists.

Show solution

The form is $f(x, y) = x^2 + 8xy + 5y^2$ (the off-diagonal $4$ doubles into $8xy$).

Determinant test: the first entry $1 > 0$, but $\det A = 5 - 16 = -11 < 0$. The eigenvalues multiply to $-11$, so one is negative: $A$ is indefinite and the graph is a saddle.

A negative direction: try $x = 1$, $y = -1$: $f = 1 - 8 + 5 = -2 < 0$. (Completing the square shows the same thing: $f = (x + 4y)^2 - 11y^2$ — a negative number, $-11$, appears outside the second square, matching the second pivot $-11$.)

Problem 27.3 Completing the square = elimination

For

$$A = \begin{bmatrix} 4 & 8 \\ 8 & 25 \end{bmatrix},$$

find the pivots and the multiplier by elimination, then use them to write $\mathbf{x}^T A \mathbf{x}$ as a sum of squares. Confirm the matrix is positive definite.

Show solution

Elimination: the first pivot is $4$, the multiplier is $\ell = \frac{8}{4} = 2$; subtracting $2 \times$ row one from row two leaves $\begin{bmatrix} 4 & 8 \\ 0 & 9 \end{bmatrix}$, so the second pivot is $9$ (check: $4 \cdot 9 = 36 = \det A = 100 - 64$).

Pivots outside, multiplier inside:

$$\mathbf{x}^T A \mathbf{x} = 4x^2 + 16xy + 25y^2 = 4(x + 2y)^2 + 9y^2.$$

Check: $4(x + 2y)^2 = 4x^2 + 16xy + 16y^2$, and $16y^2 + 9y^2 = 25y^2$ ✓. Both coefficients outside the squares are positive, so $f > 0$ for every $(x, y) \neq (0, 0)$: positive definite, and the graph is a bowl.

Problem 27.4 Second-derivative test

Does $f(x, y) = x^2 + 6xy + 2y^2$ have a minimum at the origin? Write down the matrix of second derivatives and apply the positive definiteness test.

Show solution

The first derivatives $f_x = 2x + 6y$ and $f_y = 6x + 4y$ are both zero at the origin, so the origin is a critical point. The matrix of second derivatives is

$$\begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix} = \begin{bmatrix} 2 & 6 \\ 6 & 4 \end{bmatrix}.$$

Determinant test: $2 > 0$ but $\det = 8 - 36 = -28 < 0$. Not positive definite — indefinite. The origin is a saddle point, not a minimum: $f$ rises along the axes ($f_{xx}$ and $f_{yy}$ are positive) but the cross term overwhelms them; for instance $f(1, -1) = 1 - 6 + 2 = -3 < 0$.

Problem 27.5 A 3-by-3 by all tests

Show that

$$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}$$

is positive definite using the determinant test, find its pivots, and write out $\mathbf{x}^T A \mathbf{x}$. What surface do you get by setting $\mathbf{x}^T A \mathbf{x} = 1$, and which directions are its principal axes?

Show solution

Leading determinants: $2$, then $4 - 1 = 3$, then $3 \cdot 3 = 9$. All positive: positive definite.

Pivots: $2$, then $\frac{3}{2}$ (ratio of the first two determinants), then $\frac{9}{3} = 3$.

The quadratic form: the diagonal gives $2x_1^2 + 2x_2^2 + 3x_3^2$, and the $-1$ pair gives one cross term:

$$\mathbf{x}^T A \mathbf{x} = 2x_1^2 + 2x_2^2 + 3x_3^2 - 2x_1x_2.$$

Setting it equal to $1$ gives an ellipsoid centered at the origin. By the principal axis theorem $A = Q\Lambda Q^T$, its axes point along the eigenvectors. The block structure makes them visible: in the $x_1x_2$-plane the eigenvectors of $\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$ are $(1, 1, 0)$ with $\lambda = 1$ and $(1, -1, 0)$ with $\lambda = 3$; the third axis is $(0, 0, 1)$ with $\lambda = 3$. All eigenvalues positive (as they must be), the longest axis along $(1, 1, 0)$ — the smallest eigenvalue gives the longest half-length.