The signs no completion can change

Completing the square in one variable has exactly one way to go. The quadratic $ax^2 + bx + c$ has one square term, the missing corner is forced, and the answer $a(x + b/2a)^2 + (c - b^2/4a)$ is the only one there is. Nothing about the method invites a choice.

In two variables the choice appears at the first step. The quadratic $2x^2 + 6xy + 3y^2$ has two square terms and a cross term, and the cross term can be swallowed by either of them. Gather everything containing $x$ into a square and the leftover is a multiple of $y^2$:

$$2x^2 + 6xy + 3y^2 = 2\left(x + \tfrac32 y\right)^2 - \tfrac32 y^2.$$

Gather everything containing $y$ instead and the leftover is a multiple of $x^2$:

$$2x^2 + 6xy + 3y^2 = 3(y + x)^2 - x^2.$$

Both are correct, both are completions in exactly the sense the one-variable method taught, and they disagree about the coefficients: $2$ and $-\tfrac32$ against $3$ and $-1$. Neither is the “real” answer, because there is no real answer — a quadratic in two variables can be written as a sum of two squares in infinitely many ways, and each pair of new variables is as good as any other.

And yet something is shared. Each completion has one positive coefficient and one negative one. That is not a coincidence of this example, and the theorem that says so — Sylvester’s law of inertia, published by James Joseph Sylvester in 1852 — is the subject of this essay. It says that however a quadratic in any number of variables is completed into a sum of squares, the number of positive squares, the number of negative squares and the number of missing ones never change. The coefficients are opinions. Their signs are facts.

What a completion actually names #

The two completions above are not merely two rearrangements of symbols. Each one is a change of coordinates, and each change of coordinates is a statement about directions in the plane.

Take the first, $2u^2 - \tfrac32 v^2$ with $u = x + \tfrac32 y$ and $v = y$. Setting $v = 0$ means walking along the $x$-axis, where only $u$ changes; there the quadratic is $2u^2$, positive. Setting $u = 0$ means walking along the line $x = -\tfrac32 y$, where only $v$ changes; there it is $-\tfrac32 v^2$, negative. So the completion names one positive direction and one negative direction, and its two coefficients measure how steeply the quadratic grows along each.

The second completion, $3w^2 - z^2$ with $w = y + x$ and $z = x$, names two other directions: the $y$-axis, positive, and the line $y = -x$, negative. A third natural completion is the one along the eigenvectors of the symmetric matrix $\begin{pmatrix} 2 & 3 \\ 3 & 3\end{pmatrix}$, whose coefficients are the eigenvalues $\tfrac{5 \pm \sqrt{37}}{2}$, about $5.541$ and $-0.541$; its two directions are at right angles, which is the only thing that makes it special.

The hero figure draws all three pairs on the sign pattern of the quadratic, and the pattern is the point. The quadratic is zero on two lines through the origin — the dashed ones — and they cut the plane into four wedges, positive and negative alternately. Every completion puts exactly one of its directions in a positive wedge and one in a negative wedge. No completion can put both in the positive wedges, because then the quadratic would be positive on a whole plane’s worth of directions, and the negative wedges are not empty.

That is the whole proof in two dimensions, and it is a proof about the wedges rather than about any formula. The coefficients came from arithmetic that could have gone a hundred ways. The wedges came from the quadratic itself, before any coordinates were chosen, and they decide the signs.

One more thing the coefficients agree on #

The three completions disagree about the size of their coefficients and agree about something besides the signs. Multiply the two coefficients of each completion together:

$$2 \times \left(-\tfrac32\right) = -3, \qquad 3 \times (-1) = -3, \qquad 5.541 \times (-0.541) = -3.$$

Each product is the determinant of the matrix, $2 \cdot 3 - 3 \cdot 3 = -3$. That is not a second law, and it is worth seeing why it is weaker than the first. Completing the square one variable at a time is a substitution like $u = x + \tfrac32 y$, $v = y$ — a shear, which preserves area and so leaves the determinant alone. The eigenvector completion is a rotation, which preserves it too. But a general change of variables stretches as well, and stretching $u$ by a factor of $k$ divides its coefficient by $k^2$. The product of the coefficients changes by a square, and the only thing a square cannot change is a sign.

So the determinant’s sign is invariant under every change of variables and its size is invariant only under the area-preserving ones. Inertia generalises the first statement and not the second. In two variables the sign of the determinant already decides the signs of both coefficients when one of them is known — a negative product means one of each — which is why the two-variable case looks almost too easy. The content of the law appears with a third variable.

Six orders, six answers, one count #

With three variables there are six orders in which to complete, one for each ordering of the three letters. The figure below does all six for one form, with every coefficient computed exactly as a fraction.

The procedure in each row is the one the single-variable method would recognise. Take the first variable in the order; collect every term containing it into a square, which uses up its coefficient as the first pivot; what is left is a quadratic in the remaining variables with no trace of the first. Repeat. The coefficient set $\{-2, \tfrac32, \tfrac73\}$ is what the order $x, y, z$ produces, and $\{1, 1, -7\}$ is what $y, z, x$ produces. Not only the values differ but where the negative one falls: first, second or third, according to which variable was completed when.

The rows have two things in common. Each has two positive coefficients and one negative one. And the three coefficients in each row multiply to $-7$, the determinant, for the reason given above — every step is a shear. The eigenvalues, $\sqrt 7$, $1$ and $-\sqrt7$, multiply to $-7$ as well and carry the same signs.

The census under the table is the reason to believe this is a theorem and not a pattern in one example. Two thousand symmetric matrices of size four were drawn with whole entries from $-3$ to $3$; thirty-six of them had a zero eigenvalue and were set aside, leaving 1,964. Each of those was completed in every one of its 24 orders that did not run into a zero pivot — an order that meets a zero pivot needs a substitution before it can go on, and is simply skipped. That is 36,844 completions, and not one of them has a count of signs that differs from the eigenvalues’. Ten thousand orders were blocked by a zero, which is worth saying because it is the one place the plain procedure fails. A form like $xy$ has no square term to start from at all, and must first be rewritten with $x = u + v$, $y = u - v$ into $u^2 - v^2$; the law of inertia covers that route as well, since it is a statement about every change of variables, not about the one-at-a-time procedure.

Why no order can disagree #

Sylvester’s proof replaces the coefficients with something that has no coordinates in it.

Call a positive subspace of a quadratic form any collection of directions — a line, a plane, a three-dimensional slice — on which the form is positive at every point except the origin. In the two-variable hero figure the positive subspaces are the lines inside the positive wedges; there is no positive plane, because the whole plane includes negative directions.

Now suppose a completion has $p$ positive squares. Hold the other new variables at nought and let the $p$ positive ones vary freely: that is a $p$-dimensional slice of space on which the form is a sum of $p$ positive squares, positive everywhere but the origin. So every completion exhibits a positive subspace of dimension $p$. In the same way, holding the positive variables at nought exhibits a subspace of dimension $n - p$ on which the form is never positive.

Two completions disagreeing would mean one has $p$ positive squares and the other $p' < p$. The first supplies a positive subspace of dimension $p$; the second supplies a never-positive subspace of dimension $n - p'$. Their dimensions add to $p + n - p'$, which is more than $n$, and two subspaces of $n$-dimensional space whose dimensions add to more than $n$ must share a nonzero direction. Along that direction the form would be positive by the first and not positive by the second, which is impossible.

So the number of positive squares in any completion is the largest dimension of a positive subspace — a number defined without completing anything. The same argument with the signs reversed does the negative squares, and what is left over, the zero coefficients, is the dimension of the directions the form ignores altogether. The triple (positive, negative, zero) is called the form’s signature, and Sylvester’s name for its constancy, inertia, was borrowed from mechanics on the grounds that it is what stays put however the form is pushed.

That proof is short enough to fit on a card, and it explains the census completely. What it does not do is say how to find the signature without completing, and the answer to that turns out to be the most useful thing about the theorem.

Counting eigenvalues without finding them #

The eigenvalues of a symmetric matrix are a completion of its quadratic form — the one along perpendicular directions — so their signs are the form’s signature. That much is a corollary. The corollary run backwards is a method.

Take a symmetric matrix $A$ and a number $t$, and look at the matrix $A - tI$. Its eigenvalues are those of $A$, each lowered by $t$, so the number of negative eigenvalues of $A - tI$ is exactly the number of eigenvalues of $A$ that lie below $t$. By the law of inertia, that is also the number of negative coefficients in any completion of $A - tI$’s form — including the plain one-variable-at-a-time completion, which takes a few dozen arithmetic operations for a small matrix and never mentions an eigenvalue.

The staircase is a picture of a function that knows where the eigenvalues are without anyone having computed them. Below the smallest eigenvalue, about $-5.894$, every completion of $A - tI$ is entirely positive; above the largest, about $8.761$, entirely negative; in between, the count climbs by one each time $t$ crosses an eigenvalue. It is the same staircase that counting the eigenvalues directly would draw, and the figure checks that at every one of its 901 samples.

A count of eigenvalues below a number is enough to find them, by halving. Pick an interval known to contain the third smallest, say. Complete at its midpoint; if at least three coefficients come out negative, the third eigenvalue is to the left, and otherwise to the right. Keep the half it is in and repeat.

The first interval needs no computation of any eigenvalue either. Every eigenvalue lies within the sum of the off-diagonal entries’ sizes of some diagonal entry — the discs that fence in the eigenvalues — so for this matrix the whole spectrum is inside the interval from $-11$ to $12$, read off by adding up rows. From there, each completion halves the uncertainty, and fourteen of them pin the eigenvalue to three decimal places. Every step is guaranteed: the interval contains the eigenvalue at every stage, because the count at the midpoint is exact whatever rounding went into the coefficients’ sizes, as long as their signs are right.

This is not a classroom curiosity. It is how the eigenvalues of large symmetric tridiagonal matrices are computed to this day — the bisection method in numerical linear algebra libraries — and it has a property the faster methods lack: it can find the hundredth eigenvalue of a matrix with a million of them without touching the other 999,999. A method that only counts can be pointed at any part of the spectrum.

The surprising place the count turns up: a doughnut #

The law of inertia also classifies a kind of point every smooth landscape has, and when the landscape lives on a closed surface the classification produces a number that belongs to the surface and not to the landscape.

Near a point where a smooth function of two variables has zero slope, the function looks like its value plus a quadratic — the Taylor approximation stops at the second-order terms, whose coefficients form the Hessian matrix. Completing that quadratic’s square tells what kind of point it is. Two positive squares: the function rises in every direction, a pit. Two negative: it falls in every direction, a peak. One of each: it rises along one line and falls along another, a pass, or saddle. By inertia the classification does not depend on which completion is used, or on the coordinates the landscape was drawn in. The number of negative squares — 0, 1 or 2 — is called the point’s index.

The function in the figure was chosen to have no particular symmetry: $\cos x + 0.7\cos y + 0.5\sin(x + y) + 0.6\cos(2x - y)$, which repeats when $x$ or $y$ increases by $2\pi$ and so lives naturally on a square with opposite edges glued — a torus. Its critical points were found by searching, not by solving — Newton’s method run from a grid of starting guesses — and the search found eight: two pits, four passes and two peaks.

Count them with alternating signs, pits minus passes plus peaks: $2 - 4 + 2 = 0$. Change the function and the counts change — a different choice of coefficients can produce one pit, two passes and one peak, or three of each kind of extremum and six passes — but the alternating sum does not. It is always nought, and nought is the Euler characteristic of a torus. On a sphere the same sum is always $2$; on the surface of a two-holed doughnut it is $-2$. This is Morse’s theorem, from the 1920s and 1930s, and its engine is the index, which is to say the count of negative squares in a completed Hessian.

The connection is surprising in a specific way. The Euler characteristic is usually computed by cutting a surface into faces and counting vertices minus edges plus faces. Morse’s version never cuts anything. It fills the surface with water at rising levels and notes the moments the shoreline changes shape — a new pond appears at a pit, two ponds merge or a pond wraps round the hole at a pass, the last dry hill drowns at a peak — and the alternating count of those events is the same number. The same flooding, done on a random surface rather than a chosen one, is how pieces minus holes gets its formula. The negative squares of a completed quadratic are what decides which kind of event happens at each moment.

Two variables drawn, any number argued #

Every figure here draws a form in two variables or tabulates one in three. The proof of the law needs one fact about dimension — two subspaces whose dimensions add to more than $n$ meet — and in two dimensions that fact is the visible statement that a line cannot hide inside a wedge it is not in. In four or forty dimensions the same sentence is true and nothing can be drawn of it. The census is the stand-in: it shows that 36,844 completions of four-variable forms behave as the theorem says, which is evidence, and the dimension count is the proof.

The staircase’s samples avoid the eigenvalues themselves. Exactly at an eigenvalue, $A - tI$ is singular, one completion coefficient is zero, and the count is ambiguous between two steps. The figure skips samples within a millionth of an eigenvalue, which a reader cannot see, and the bisection never lands on one exactly. A practical implementation must decide what to do with a zero pivot — perturb it, or count it on one side by convention — and that decision is invisible in a picture where it never occurs.

The doughnut figure finds eight critical points; it does not prove there are no others. The search started Newton’s method from 576 points spread over the square and kept every distinct point it converged to. A critical point with a tiny basin could escape such a search. That the alternating count came out to nought is evidence that nothing was missed, since a missed pass or pit would break it — but that is using the theorem to check the search, and the theorem itself is not proved by any figure on this page.

Signs in the physics of space and time #

The law of inertia is the reason a well-known fact about space and time is a fact and not a choice of units. Distance in ordinary space is a quadratic form in three coordinates with three positive squares, $x^2 + y^2 + z^2$. The interval of special relativity is a form in four, $c^2t^2 - x^2 - y^2 - z^2$, with one positive square and three negative ones. Any change of coordinates — a moving observer, a rotated frame, a stretched scale — rewrites the coefficients, and by Sylvester’s law none can turn one plus and three minuses into two of each. The signature of spacetime is an invariant in exactly the sense this essay has been drawing, and it is why time is one direction and not two.

The same count classifies conic sections — ellipse, hyperbola, parabola — and the quadric surfaces one dimension up: ellipsoid, hyperboloid of one sheet or of two. Each is a signature, and each family is closed under every change of coordinates because the signature is. The eigenvalue at the highest point on a sphere is another reading of the same structure: the largest eigenvalue is the largest value of the form on unit vectors, and the count of eigenvalues above a level is the largest dimension of a subspace on which the form beats that level, which is the minimax principle and is the dimension argument above with a number in place of nought.

Still open: how much the count costs #

The signature is cheap to compute exactly for a matrix of whole numbers: complete in fractions, as the table did, and count signs. The fractions grow, but only polynomially, and the whole calculation is efficient. What is less settled is the cost of the bisection for a large dense matrix in floating point, where each completion is a full elimination and the method’s guarantee rests on a theorem about rounding: the signs computed in floating point are the exact signs of a slightly different matrix, and that matrix’s eigenvalues are close to the real ones. William Kahan proved that guarantee for tridiagonal matrices in 1966, and it is why the method is trusted there; for general matrices the guarantee is weaker, and the method is used only after reduction to tridiagonal form.

A sharper question lives in the doughnut figure. Morse’s alternating count says the numbers of pits, passes and peaks satisfy one equation; it does not say which triples occur, or how few critical points a function on a given surface can have. On a torus the answer is three if degenerate points are allowed and four if not — the Lusternik–Schnirelmann category against the Morse bound — and for surfaces and higher-dimensional spaces in general the gap between the two counts is a subject of its own, closely tied to the question of what a surface’s holes force. The law of inertia supplies the index at each point. How few points a shape can get away with is a question about the shape.

The next completion this subject owes is the one in the exponent of a bell in two variables, where completing in one variable and not the other is exactly the act of conditioning — and where the line the completion names turns out not to be the line anyone expects.