Positive definite: the shape of a bowl

There is a moment in every optimization story where someone says "and then we roll downhill to the minimum," and everyone nods, and nobody asks the awkward question: how do you know there's a bottom to roll to? A hill can dip and rise, a landscape can have a pass between two peaks, and "downhill" from where you're standing might lead you straight off a cliff or into a saddle that isn't a minimum at all. The thing that guarantees a genuine bowl — one lowest point, curving up in every direction — turns out to be a single algebraic property of a matrix. It's called being positive definite, and once you can see it, half of machine learning stops looking like luck.

The idea grows out of the nineteenth-century study of quadratic surfaces. Cauchy, rotating ellipsoids onto their principal axes in the 1820s, was already sorting quadratic forms by whether they curved up, down, or both ways. James Joseph Sylvester gave the classification its spine in 1852 with what he called the law of inertia: no matter how you change coordinates, the number of directions a form curves up in, and the number it curves down in, never changes. That invariant count is the whole subject. This essay is about the positive end of it — the forms that curve up everywhere — because those are the shapes optimization is allowed to promise you.

The quadratic form

Take a symmetric matrix A and a vector x, and sandwich the matrix between two copies of the vector:

q(x) = x^\top A x.

The result is a single number. Multiply it out for the 2\times2 case, with A = \begin{bmatrix} a & b \\ b & c \end{bmatrix} (symmetric, so the off-diagonal entry is shared), and you get

q(x) = a\,x_1^2 + 2b\,x_1 x_2 + c\,x_2^2.

This is a quadratic form: every term is degree two, a homogeneous mixture of squares and a cross-term. Why insist that A be symmetric? Because the antisymmetric part of any matrix contributes nothing to x^\top A x — the x_1 x_2 and x_2 x_1 pieces always pair up, so only the symmetric average (A + A^\top)/2 survives. Every quadratic form has a unique symmetric matrix behind it, and we lose nothing by always working with that one. This is the same symmetry that the spectral theorem loves, and that is not a coincidence — it's the hinge the whole essay turns on.

Now watch what q does as x ranges over the plane. It assigns a height to every direction, and the graph of that height is a surface sitting over the plane. There are exactly three shapes it can take.

Bowl, dome, saddle

If q(x) > 0 for every nonzero x, the surface is a bowl: it sits at zero at the origin and rises no matter which way you walk. That is the definition of positive definite. Flip every sign — q(x) < 0 for all x \neq 0 — and you have a dome, curving down in every direction: negative definite. And if q is positive along some directions and negative along others, the surface is a saddle: up if you walk one way, down if you walk the perpendicular way, like the seat that gives the shape its name. That mixed case is indefinite, and it is exactly the case where "roll downhill" betrays you, because the origin is a critical point that is a minimum in some directions and a maximum in others.

There are two borderline shapes worth naming. If q(x) \ge 0 always but equals zero for some nonzero direction — a bowl with a flat trough along one line, like a half-pipe — the matrix is positive semidefinite. Its negative twin, the flattened dome, is negative semidefinite. Semidefinite is the honest word for "curves up, but not strictly, everywhere," and it will matter the moment we talk about covariance.

Five tests that all say the same thing

The beautiful thing about positive-definiteness is how many disguises it wears. Here are five conditions on a symmetric A, and the theorem is that they are all equivalent — any one of them implies the other four.

The definition itself: q(x) = x^\top A x > 0 for all x \neq 0. Clean, but useless as a test — you can't check infinitely many vectors by hand.

All eigenvalues positive. This is the one that connects everything back to eigenvectors. Because A is symmetric, the spectral theorem hands us an orthonormal eigenbasis: A = Q\Lambda Q^\top. Substitute and let y = Q^\top x be x rewritten in that basis:

q(x) = x^\top Q \Lambda Q^\top x = y^\top \Lambda y = \lambda_1 y_1^2 + \lambda_2 y_2^2 + \cdots + \lambda_n y_n^2.

In the eigenbasis the cross-terms vanish and the form is a plain weighted sum of squares — the surface is an ellipsoid whose axes point along the eigenvectors. Each y_i^2 is nonnegative, so q is positive for every nonzero x if and only if every weight \lambda_i is positive. Positive definite means: all eigenvalues strictly positive. Semidefinite means: none negative, but some may be zero (a flat trough is a zero eigenvalue). This is the test the playground computes, and it's the one to keep in your head, because it says positive-definiteness is the statement that the map never flips or flattens any direction — it only stretches, and always outward.

Positive pivots. Run Gaussian elimination without row swaps, and the numbers you divide by — the pivots — come out all positive exactly when A is positive definite. This is elimination quietly confirming the same fact, and it's how a computer usually checks: no eigenvalue solve required.

Positive leading principal minors — Sylvester's criterion. Take the determinants of the top-left 1\times1, 2\times2, …, n\times n corners of A. If all of them are positive, A is positive definite; that's Sylvester's criterion, and it's the fastest hand-check there is. For our 2\times2 it reads: a > 0 and \det A = ac - b^2 > 0. The first says the surface curves up along the x_1-axis; the second says the cross-term b isn't strong enough to tip a saddle open. Two inequalities, and you know the shape.

A Cholesky factorization exists. A is positive definite precisely when it can be written A = LL^\top for a lower-triangular L with positive diagonal — a kind of "square root" of the matrix. We'll only tease this one here, because it's the workhorse of numerical linear algebra: solving Ax = b or sampling from a Gaussian both lean on Cholesky, and the factorization simply fails, halfway through, the moment the matrix isn't positive definite. The algorithm is its own certificate.

Five doors, one room. Which one you walk through depends on what you're holding — eigenvalues if you're theorizing, pivots or minors if you're computing, Cholesky if you're solving.

Why machine learning is soaked in this

Positive-definiteness is not a curiosity you meet once; it's structural, and it shows up in at least three load-bearing places.

Covariance matrices are positive semidefinite. The covariance matrix \Sigma of a random vector is built so that for any direction w, the number w^\top \Sigma w is the variance of the data projected onto w. Variance can't be negative — you can't have a spread of less than nothing — so w^\top \Sigma w \ge 0 for every w, which is precisely the semidefinite condition. It's definite (strictly) unless the data lie exactly in a lower-dimensional flat, which is what a zero eigenvalue detects: a direction of no variance. This is why the principal directions of data are eigenvectors of a matrix guaranteed to have real, nonnegative eigenvalues — the same guaranteed-positive structure the singular value decomposition exploits when it factors data.

The Hessian decides convexity. For a smooth loss function f, the matrix of second derivatives — the Hessian — plays the role of A in a local quadratic picture of the surface. Where the Hessian is positive definite, the function is locally a bowl and any critical point there is a genuine minimum. If the Hessian is positive definite everywhere, the function is convex: one basin, no false bottoms, and gradient descent cannot get trapped, because there is nowhere to get trapped. That single guarantee is the difference between an optimization you can trust and one you can only hope about.

Loss surfaces are bowls when you're lucky. We already saw one: the least-squares loss L(\beta) = \lVert X\beta - y\rVert^2 has Hessian 2X^\top X, and w^\top X^\top X w = \lVert Xw \rVert^2 \ge 0 makes it positive semidefinite — a bowl (flat-bottomed if X has dependent columns). That is why the least-squares minimum is unique and why "solve the normal equations" works. And it's why, when the bowl is too big to solve in one shot, you can instead roll downhill with confidence: on a positive-definite bowl, downhill genuinely reaches the bottom. The eigenvalues of that Hessian even set the pace — a bowl stretched long and thin (one big eigenvalue, one tiny) makes plain gradient descent zig-zag miserably, which is the exact pathology Adam and its cousins are built to fix. The curvature you're reading about here is the terrain those optimizers are trying to survive.

Where this goes

Positive-definiteness is the algebraic name for "curves up in every direction," and once you have it, a surprising amount of downstream machinery is just this fact wearing a hat. Ask what happens to a matrix that isn't symmetric or square, and the repair is to study the guaranteed-positive-semidefinite A^\top A instead — that detour is the singular value decomposition, where the eigenvalues of A^\top A become the squared singular values, nonnegative by construction. Ask how to actually optimize on these bowls at scale and you're back to gradient descent and Adam, whose whole job is to move sensibly across curvature that this essay taught you to read.

But the quickest way to feel the difference between a bowl and a saddle is to bend one into the other. The positive-definite playground lets you set the three entries of a symmetric matrix \begin{bmatrix} a & b \\ b & c \end{bmatrix} and draws the contour map of its quadratic form live. Nudge b upward past the point where Sylvester's criterion breaks — where ac - b^2 crosses zero — and watch the concentric ellipses of a bowl tear open into the hyperbolas of a saddle, while the readout flips the sign of an eigenvalue and the badge changes its verdict. It's one thing to read that a determinant controls the shape of a surface. It's another to slide it across zero and watch the bowl split.