Computing functions of roots without computing roots

Once in a while it's necessary to calculate some function of the roots of a polynomial, and it may be possible to do this without first calculating the roots.

Quadratics

The quadratic formula gives explicit solutions to the equation

The two solutions for x are

where

The awkward part is taking the square root of the discriminant . But that's not necessary if you only need to know the sum or the product of the roots.

The sum of the two roots is simply -b/a because the terms involving the discriminant cancel out.

The product of the roots works out to be c/a.

In my previous post, I needed the difference of two roots. This isn't quite as simple as the sum, but it works out to / a.

Higher-order polynomials

There are simple expressions for the sum and product of polynomial roots in general.

The sum of the roots is the negative of ratio of the second coefficient to the first. So for a cubic equation

the sum of the roots is again -b/a, just as in the quadratic case.

The product of the roots is the ratio of the last coefficient to the first, with a negative sign for odd degree polynomials. So in the cubic case, the product of the roots is -d/a.

More formal

To use symbols rather than words, let p(x) be the polynomial

and number the roots r₁ through r_n. Then

History

The theorem above goes back to Francois Viete (1540 - 1603) and is known as the first and last of Vieta's formulas. (There are others in between. We'll get to that shortly.) The formulas are called Vieta's formulas rather than Viete's formulas because the former is based on the Latinized form of his name, Franciscus Vieta.

As I wrote about here, Viete discovered the following infinite product for :

Generalization

I don't know whether Vieta's formulas in their full generality go back to Viete. Often a pioneer blazes the trail and someone else comes behind them to improve the trail.

The sum of the roots of a polynomial is the sum of all products of roots involving one term. The product is the sum of all products of roots involving n terms. One could ask for the sum of all roots involving an intermediate number of terms. For example, if the roots of the cubic

equation

are . , and , one could as for the sum of all products of two roots

and this turns out to be c/a.

If we number the roots of our polynomial r₁ through r_n then the sum of all distinct products of k roots is given by

The left-hand side of the equation above is complicated, but it amounts to the sum of all distinct products roots taken k at a time.

Proof

The proof is actually quite simple. Start by writing the polynomial in factored form.

Now imagine multiplying out the product. Each term in the product comes from selecting either an x or a -r from each term and adding up all the possibilities.

The coefficient of x^n-1 comes from summing all ways of selecting an x from all terms except one and selecting one negative root term. So the sum of the negatives of the roots is a_n-1 divided by the a_n term in front of the product. This proves the first Vieta formula.

The proof for the kth Vieta formula comes from applying the analogous combinatorial argument to the coefficient of x^n-k.

Discussion

Vieta's formulas are very clever even though they're simple to prove.

The quadratic case can be proved by brute force: find the roots, the compute their sum and product. It would be possible, but difficult, to do the same for the cubic case, though I don't know whether Viete ever saw the formula for the roots of a cubic equation because he and Cardano were contemporaries. The case for fourth degree polynomials would be even harder, and the case for higher degree polynomials would be impossible even in principle.

It would be an understandable mistake to believe you have to generalize the quadratic formula to generalize the theorem about sums and product of roots. But you don't. It's common in mathematics to have a flash of insight, realizing that you don't have to calculate something that it seems you have to calculate. Maybe the lack of convenient formulas for higher roots led Vieta to look at the problem more abstractly.

Vieta's result is more impressive when you realize how awkward mathematical notation was in his day. Algebra didn't even use parentheses until Vieta introduced them.

The post Computing functions of roots without computing roots first appeared on John D. Cook.