When is a quadratic form a bowl?

Two expressions in two real variables $x_1$ and $x_2$ look almost the same:

!Two forms that differ only in the coefficient of $x_2^2$. On the left the eigenvalues are 13.32 and 0.68, the level sets close into ovals, and the form is a bowl. On the right they are 12.71 and $-0.71$, the level sets open into hyperbolas, and the form reaches $-9$ at $(2,-3)$. Status: re-simulated.

!The signs of the eigenvalues name the shape. Two positive eigenvalues give a bowl, one of each sign gives a saddle, and one zero gives a trough with a flat direction. The curvature along each eigenaxis is its eigenvalue. Status: schematic.

The first is a sum of two squares, so it can never be negative. The second is a square minus a square, so it can. At $x_1=2$ and $x_2=-3$ the first expression is $0+9=9$, and the second is $0-9=-9$ [S:27:80]. One expression is a bowl with a single bottom. The other is a saddle: it curves up in some directions and down in others.

The two expressions differ only in the coefficient of $x_2^2$, which is five in the first and three in the second. The cross term, $12x_1{x}_2$, is the same in both. That small change is enough to turn a sum of two squares into a difference of squares, and the next paragraphs show that it also moves one eigenvalue across zero.

Both are quadratic forms, expressions of the shape $x^{\top }Ax$ for a symmetric matrix $A$. When you multiply out $x^{\top }Ax$, the two off-diagonal entries each contribute one copy of the cross term, so an off-diagonal entry of $6$ produces the coefficient $12$. That is why the matrix for the first expression is $\left(\begin{array}{cc}9& 6\\ 6& 5\end{array}\right)$ and the matrix for the second is $\left(\begin{array}{cc}9& 6\\ 6& 3\end{array}\right)$. A symmetric matrix is positive definite when its quadratic form is positive for every nonzero vector [S:27:80]. That is exactly the bowl condition.

The eigenvalues decide which case you are in. Change to the eigenbasis of $A$, which exists by the spectral theorem [S:27:117], and call the new coordinates $y_1$ and $y_2$. In those coordinates the cross terms disappear, and the form becomes a weighted sum of squares with weights ${\lambda }_1$ and ${\lambda }_2$:

Each eigenvalue is the curvature along one perpendicular axis. The curvature is how quickly the slope changes as you move away from the origin along that axis: a large eigenvalue means a steeply bending direction, and a small one means a flat direction.

Two positive eigenvalues give a bowl. One positive and one negative give a saddle point. A zero eigenvalue gives a flat direction, and the shape is a trough rather than a bowl. A positive definite matrix always has positive eigenvalues [S:27:112].

Three dimensions work the same way, with three eigenvalues and a list of signs. Three positive numbers give a bowl. Two positive and one negative give a saddle with one downhill direction, and two negative with one positive give a saddle with two downhill directions. A zero makes a flat direction and a trough.

Worked example. For the first matrix, the trace is $14$ and the determinant is $9$, so the eigenvalues solve ${\lambda }^2-14\lambda +9=0$. They are $7+\sqrt{40}$ and $7-\sqrt{40}$, about $13.32$ and $0.68$. Both are positive, so the form is a bowl.

For the second matrix, the trace is $12$ and the determinant is $-9$, so the eigenvalues solve ${\lambda }^2-12\lambda -9=0$. They are $6+\sqrt{45}$ and $6-\sqrt{45}$, about $12.71$ and $-0.71$. The negative eigenvalue is the downhill direction, and the value $-9$ at $(2,-3)$ is that direction made concrete.

The eigenvalue test is the same test as the completed square, read in a different language. Completing the square means rewriting the expression as a square plus a leftover, as the opening lines do: $9x_1^2+12x_1{x}_2+5x_2^2=(3x_1+2x_2{)}^2+x_2^2$. The square shows the sign directly for a two-by-two form. The eigenvalues show it in any dimension, and they also tell you how steep each direction is. The smallest eigenvalue is the curvature of the flattest direction; the largest is the curvature of the steepest one.

The signs can also be read without solving the polynomial. The trace is the sum of the eigenvalues, and the determinant is their product [S:27:118][S:27:119]. A negative determinant already proves that the two eigenvalues have opposite signs, so the form is a saddle. That is how the second matrix is caught in one line.

The idea has a limit. It describes one fixed quadratic form. It says nothing about where the bottom of the bowl is, how far away it lies, or what happens to a function that is not quadratic at all. The eigenvalue test also asks about every nonzero vector at once, so checking a few directions proves nothing.

The test can also be expensive. For a large matrix, deciding positive definiteness is a computation in its own right, and the eigenvalues are one route to the answer rather than the only one. Finally, a bowl can be extremely elongated. If one eigenvalue is $13.32$ and the other is $0.68$, the curvature differs by a factor of about twenty, and gradient descent, which steps along the negative gradient, will crawl along the flat one.

The formal statement. Let $A$ be a real symmetric $n\times n$ matrix and let $q(x)=x^{\top }Ax$. Then $q(x)>0$ for every nonzero $x$ exactly when every eigenvalue of $A$ is positive [S:27:80]. More generally, the signs of the eigenvalues give the shape. All positive is a bowl, all negative is a downward bowl, mixed signs give a saddle, and a zero eigenvalue gives a flat direction. A positive definite matrix always has positive eigenvalues [S:27:112].

The derivation. By the spectral theorem, $A$ has an orthonormal eigenbasis $u_1,\dots ,u_n$ with real eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ [S:27:117]. Write $x={\sum }_i{y}_i{u}_i$. Orthonormality gives $q(x)={\sum }_i{\lambda }_i{y}_i^2$. Each $y_i^2$ is nonnegative, and the $y_i$ are not all zero when $x$ is nonzero. If every ${\lambda }_i$ is positive, every term is nonnegative and at least one is positive, so $q(x)>0$. If some ${\lambda }_j\le 0$, take $x=u_j$. Then $q(x)={\lambda }_j\le 0$, and the form is not positive definite. That proves both directions, and no step is omitted.

The edge case. The core writes the form with a symmetric $A$. Take instead the non-symmetric matrix $L=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$. Then $x^{\top }Lx=x_1{x}_2$, which is positive at $(1,1)$ and negative at $(1,-1)$, so the form is a saddle. Both eigenvalues of $L$ are zero. A reader who applies the eigenvalue test to $L$ concludes "flat in every direction", which is wrong. Only the symmetric part $(L+L^{\top })/2$ enters a quadratic form, so you must symmetrize before you read eigenvalues.

What the core hid. The core checked the sign by completing the square in two variables. That trick is special to two dimensions and to a form with no linear term. The eigenbasis argument works in any dimension and needs only the spectral theorem. Completing the square was safe in the example because the example was two-by-two and had no linear term.

Where the analogy breaks. A bowl has a bottom, and $q(x)=x^{\top }Ax$ has its bottom at the origin only because no linear term is present. The general quadratic $x^{\top }Ax+b^{\top }x+c$ has the same curvature and a different bottom, at the solution of $2Ax+b=0$ when $A$ is invertible. The eigenvalues describe the shape, not the location. A second limit: "bowl" suggests one lowest point, but a positive semidefinite form with a zero eigenvalue has a whole flat trough. The core says this. The analogy does not.

Original sources. The definition of a symmetric positive definite matrix is Definition 3.4 in MML, and the two two-by-two examples are the ones in the core [S:27:80]. The step from a quadratic form to a general function is the second-order condition: a twice differentiable function is convex exactly when its Hessian is positive semidefinite at every point, and strictly convex when the Hessian is positive definite [S:63:310]. The same condition is Proposition 15.4 in the differentiable-programming text [S:72:423].

An open question. For a quadratic form the test is finite: list the eigenvalues, or factor the matrix. For a loss surface that is not quadratic, the test asks for the Hessian at every point, and the field has not settled how to certify a bowl over a whole region at a cost that scales. Evidence that would settle a given case: a certificate that holds on the region, checked against a dense grid of Hessian eigenvalues, including points the certificate was not fitted to. A local test on a grid is evidence, not a proof.

A frontier result. Strong convexity is the quantitative form of the bowl condition: the Hessian satisfies ${\nabla }^{2}f⪰\mu I$ for some positive $\mu$ [S:72:424]. It is not enough on its own for a rate. The linear bound needs a second hypothesis, $\beta$-smoothness, which says the gradient changes no faster than $\beta$, together with a step $\gamma \le 1/\beta$: under both, gradient descent satisfies $L(w_T)-L^{\star }\le (1-\gamma \mu {)}^T(L(w_0)-L^{\star })$ [S:72:433-434]. Without smoothness the gradient can change arbitrarily fast, and without the step bound the iteration can diverge. For a quadratic form the ratio $\beta /\mu$ is the ratio of the largest eigenvalue to the smallest, which is the condition number you read from the same eigendecomposition. The eigenvector for the smallest eigenvalue points along the flattest direction, which is the one a descent method crosses most slowly.

What to read next. Read MML 3.2.3 for the definition and the two examples [S:27:80], Murphy 8.1.3 for the Hessian test and the four surfaces [S:63:310], and Blondel and Roulet 15.4 for strong convexity and the rate it buys [S:72:424].