A shared root, found without finding it

What the coefficients already know ended by naming a rung it did not climb: the resultant of two polynomials, which decides whether they share a root without finding one. This is that rung, and the decision is a determinant.

The array is Sylvester’s, and the striking part of it is what it does not contain. There is no root anywhere in the computation, exact or approximate. There is no factoring, no iteration, no tolerance. The input is a list of integers and the output is an integer, and that integer is zero exactly when two numbers nobody has computed happen to coincide.

Why a determinant should know #

The argument is short and worth having, because otherwise the construction looks like a coincidence.

Two polynomials $f$ and $g$ share a root exactly when they share a common factor of positive degree. If they do share a factor $h$, then $f = h u$ and $g = h v$, and the polynomials $v f$ and $u g$ are the same thing — so there exist polynomials $u$ and $v$, of degrees below those of $g$ and $f$, with

$$v f - u g = 0.$$

If they share no factor, no such pair exists, because $vf = ug$ with $f$ and $g$ coprime forces $f$ to divide $u$, which the degree bound forbids.

So the question is whether a certain linear equation has a non-zero solution. The unknowns are the coefficients of $u$ and $v$ — there are $\deg f + \deg g$ of them — and the equations are the coefficients of $vf - ug$, of which there are the same number. A square system of linear equations has a non-zero solution exactly when its determinant vanishes, and that determinant is the array in the figure.

That is the whole of it. The Sylvester matrix is the matrix of the map $(u, v) \mapsto vf - ug$ in the obvious basis, and the resultant is the number that says how much room the map leaves: zero exactly when the map crushes something to nothing.

Elimination, which is what it is for #

Deciding whether two given polynomials share a root is a small question. The construction earns its keep on a larger one.

Take two curves in the plane, each given by a polynomial equation in $x$ and $y$. Where do they cross? Two equations, two unknowns, and no general method — except that each equation, read as a polynomial in $y$ alone, has coefficients that are polynomials in $x$. Their resultant is then a polynomial in $x$ alone, and it vanishes exactly at those $x$ for which the two share a $y$: which is to say, exactly at the abscissae of the crossings.

Two equations in two unknowns have become one equation in one unknown. That is elimination, and it is the oldest reason anybody cared about resultants; the machinery generalises to many variables and many equations, and it is the ancestor of everything in the subject that goes by the name of a Gröbner basis.

The figures check the claim rather than asserting it. The eliminated polynomial is compared against the resultant evaluated at twenty-five separate values of $x$, and the roots of that polynomial are found independently of the crossings, which are found by solving each curve. Neither computation feeds the other.

The product over roots, which explains the vanishing #

There is a second formula for the same number, and it is the one that makes the vanishing obvious rather than merely proved.

If $f$ has leading coefficient $a$ and roots $\alpha_1, \dots, \alpha_m$, and $g$ has degree $k$, then

$$\operatorname{Res}(f, g) = a^{k} \prod_{i=1}^{m} g(\alpha_i).$$

The resultant is the second polynomial evaluated at every root of the first, multiplied together. Now the theorem is a triviality: the product is zero exactly when one of the factors is, and a factor $g(\alpha_i)$ is zero exactly when a root of $f$ is also a root of $g$.

The two formulas describe the same number and could hardly be less alike. One is a determinant of integers and mentions no root; the other is a product over roots and mentions no determinant. That they agree is the content, and the hero figure checks it: the roots of the first polynomial are found numerically, the product is formed, and it is required to equal the determinant. It is the only place in the whole family where a root is computed at all, and it is computed to test the answer rather than to produce it.

The product formula also explains a fact about the determinant that is otherwise mysterious. Swap the two polynomials and the resultant changes by a sign of $(-1)^{mk}$ — which from the array is a statement about reordering rows, and from the product is a statement about which polynomial’s roots are being fed to which.

The discriminant is a resultant #

There is a special case everybody meets years before the general one, and it is usually presented as a formula to memorise.

A polynomial has a repeated root exactly when its graph touches the axis without crossing it — which is to say, at a point where both the polynomial and its slope vanish. So “does this have a repeated root” is “do these two share a root”, with the two being the polynomial and its derivative. The resultant of that pair is the discriminant, up to a factor depending on the degree and the leading coefficient.

For a quadratic the construction gives $b^2 - 4ac$, which is where the schoolroom formula comes from. For a cubic it gives an expression with five terms, which nobody memorises and everybody can now derive: build the four-by-four array, take the determinant.

The gain is not the formula. It is knowing what kind of object the discriminant is — a resultant, hence a determinant, hence something that vanishes when a linear map degenerates — and therefore knowing without checking that it is a polynomial in the coefficients with whole-number coefficients, that it changes in a predictable way when the variable is scaled, and that an analogue exists for every question of the same shape.

A determinant is a signed sum, and the sum is over orderings #

It is worth pausing on what taking the determinant of the coefficient array actually costs, because the answer is the reason the resultant is a polynomial in the coefficients rather than merely a number.

Each term of the expansion picks one coefficient from each row and column and multiplies them, with a sign attached. So the resultant of a quadratic and a cubic is a sum of products of five coefficients apiece, with integer signs — which is a polynomial identity in the coefficients, valid over any ring at all, not merely over the numbers the example happened to use.

That is what makes the construction robust. It works over the integers, over a field of finitely many elements, over polynomial rings — anywhere the coefficients live, the same array can be written and the same determinant taken, and the same theorem holds with “root” read in whatever setting is in play.

The determinant as a function #

A single resultant answers a yes-or-no question. Sliding one polynomial through a family turns it into a curve, and the curve says more.

Read this way the resultant is a function on the space of coefficient-tuples, and the set where it vanishes is a hypersurface: the discriminant locus, the place where the family degenerates. Almost every question in the subject about “what happens for generic parameters” is a statement that some resultant is non-zero, and almost every interesting phenomenon happens on the surface where it is.

The curve also settles a question the yes-or-no reading cannot even ask. Between two crossings the determinant has a sign, and the sign is not arbitrary: by the product formula it is the sign of a product of values of one polynomial at the roots of the other, so a change of sign records a root moving past a root rather than a root appearing. Watching an integer-valued quantity change sign is often the cheapest way to locate something that is otherwise expensive to find, and this is the algebraic instance of a habit the whole site keeps running into — a continuous quantity that is forced to be a whole number cannot change without something structural happening.

What it costs #

The numbers get large. The resultant of two degree-ten integer polynomials is a determinant of a twenty-by-twenty array of their coefficients, and its size grows roughly as the tenth power of the coefficients. Exact arithmetic is essential — the whole claim is that a certain number is exactly zero — and exact arithmetic on numbers that large is not free. Everything in the figures here stays in ordinary whole numbers because the degrees are small and the coefficients are small, and both facts are stated rather than assumed.

It says whether, not where. A zero resultant proves a common root exists and gives no hint what it is. That is a genuine limitation and it is also the point: the question is there is answered by a rational computation on the coefficients, and the question what is it is not a rational computation at all, since the answer need not be a rational number.

The product formula needs all the roots, including the complex ones. Written out over the real numbers it is false as often as not, because a real cubic may have one real root and two complex ones and the product over the real roots alone is the wrong number. The figure sidesteps this by checking the identity only when the polynomial’s real roots account for its whole degree, which is a restriction on the check rather than on the theorem.

And the degrees have to be honest. The array’s size is fixed by the two degrees, so a polynomial whose leading coefficient happens to vanish under a substitution changes the size of the problem underneath the computation. Elimination between curves runs into exactly this: at the values of $x$ where the leading coefficient in $y$ vanishes, the eliminated polynomial can pick up a spurious root, and the standard treatments carry a clause about it.

Where it fails, and what it needs #

Two polynomials can share a root at infinity. If both leading coefficients vanish, the resultant vanishes too, and the shared “root” is not a number. Projectively it is a perfectly good point and the theorem is improved by saying so; affinely it is a false positive and has to be excluded by hand.

Multiplicity is invisible. The resultant is zero for one shared root and zero for three, and nothing in the number distinguishes them. Recovering that requires the whole factorisation of the resultant, not merely its vanishing.

The curve version needs the curves to have no common component. If two plane curves share a whole branch — if the polynomials share a factor involving both variables — then the eliminated polynomial is identically zero and says nothing, correctly: there are infinitely many crossings and no finite list of abscissae describes them.

And the eliminated polynomial can have roots the picture does not show. A quartic with two real roots has two complex ones as well, and the figure draws the real crossings. Nothing is wrong; the eliminated polynomial is telling the truth about a larger set of solutions than the plane contains, which is the usual situation once complex roots are admitted.

Where it came from #

Euler and Bézout both wrote elimination methods in the middle of the eighteenth century, for the practical reason that solving simultaneous polynomial equations was a computation people needed and had no system for. Sylvester’s matrix and the name resultant are from the 1840s, in the middle of the burst of work on determinants and invariants that also produced the word matrix.

The subject then did something unusual: it was almost completely abandoned. Elimination theory was central to nineteenth-century algebraic geometry and was regarded by the middle of the twentieth as a mass of unreadable computation, superseded by methods that avoided coordinates entirely. Weil wrote of eliminating elimination theory from geometry.

It came back with computers, and for the reason the technique was invented: somebody has to actually solve the equations. Modern computer algebra runs on resultants and their descendants, and the determinant in the figure above is executed millions of times a day by software written for people who have never heard of Sylvester.

What the pictures cannot show #

The determinants drawn here are four-by-four at largest, because a six-by-six array of coefficients is a picture of a wall of digits. The construction has no size limit and the figure has one.

The curves are drawn where they cross in the plane, and the eliminated polynomial’s complex roots — which are just as much a part of what elimination found — have nowhere to go on the page. A reader who counts crossings and compares with the polynomial’s degree will find a shortfall, and the shortfall is the complex solutions.

And the vanishing of the determinant is drawn as a number reading zero, which is a report of an exact computation rather than a visible feature of the array. Nothing about the left-hand grid in the hero figure looks different from the right-hand one; the difference is the value, and the value is the whole content.

The ladder from here #

Below: what the coefficients already know, where the symmetric functions of the roots are read off without finding them, and the number that says how much room is left, which is the determinant this construction leans on. Sideways: one cone, four curves, where the discriminant decides which conic a quadratic equation draws, and the field with four elements, over which the same array can be written and the same theorem holds. Above: Newton’s identities, the multivariate resultant, and the elimination ideals a Gröbner basis computes.

What is worth carrying away #

Some questions about numbers can be answered without producing the numbers. That is not a trick of this particular construction; it is what happens whenever a property can be phrased as the degeneracy of a linear map, because degeneracy is a determinant and a determinant is arithmetic on the data.

The shape to look for is the one in the second section: a question of the form does there exist a thing satisfying these constraints, where the thing is determined by finitely many unknowns and the constraints are linear in them. Every such question is a determinant, and the answer arrives without the thing ever being built.