Suppose we are given an -tuple of (not necessarily distinct) complex numbers and we construct a monic univariate polynomial of degree over field whose roots are the elements of
where is the coefficient of monomial of degree in polynomial of degree . This double-indexing might seem a bit confusing, but its usefulness will be made evident later on.
Usually, we take a univariate polynomial and try to find its roots. Now we are interested in the reverse operation, i.e., we would like to find the values of the coefficients of polynomial in terms of the roots . Note that every permutation of the -tuple results in the same monic polynomial of degree .
Say we know the coefficients of polynomial of degree . Then we can write the coefficients of polynomial in terms of the coefficients and the -th element of -tuple . On my previous post on this topic, I derived the recursion
Let us start with a monic polynomial of degree zero, , whose only coefficient is . We take the first element of the -tuple and construct the monic polynomial of degree using the recursion above. Then we take the 2nd root and construct the monic polynomial of degree whose roots are
Iterating successively, we obtain a monic polynomial of degree whose roots are .
A graphical approach
Consider the following set of 15 nodes arranged in 5 columns and 5 rows. Each node is labelled with an ordered pair , where is the row index and is the column index.
We now attach a complex number to each node . The coefficient of monomial in polynomial can be thought of as the number attached to node . For example, the coefficients of polynomial are the numbers attached to the nodes of the 3rd column (note that we count rows and columns starting at the zero index, like in the C programming language). The double-indexing now makes some sense ;-)
Finally, we add directed edges linking nodes in adjacent columns, and obtain the following directed graph (which reminds me of the trellis diagrams used in convolutional coding)
Recall the recursion formula which allows us to write the coefficients of polynomial in terms of the coefficients of polynomial
Since the coefficients are attached to the nodes of the directed graph depicted above, we can use the recursion formula to compute the values attached to the nodes of a given column as a function of the values attached to the nodes in the column to the left.
This graphical approach is (most likely) of no practical use. Nonetheless, this approach does reveal the “structure” of the process of constructing a polynomial from its roots, and such structure is of much greater beauty than cumbersome algebraic manipulation.
Suppose we want to compute the coefficients of the monic polynomial , which has a root of multiplicity at . In this case we have . From the well-known binomial theorem, we know that
Let us now construct this polynomial one step at a time using the graphical approach described above. We start with monic polynomial , whose only coefficient is
where the directed edges now have weights. For example, the edge linking nodes and has weight , while the edge linking and has weight . If the weight of an edge is equal to , then we do not label the edge in order to avoid cluttering the diagram.
From the coefficients of and the second root, , we can compute the coefficients of using the recursion again, i.e., the values of the nodes in the 3rd column can be computed from the values in the nodes in the 2nd column, as follows
The values of the nodes in the 3rd column are known, and since the 3rd root is we can now obtain the coefficients of
and since , we can finally obtain the coefficients of the monic polynomial , which are the values of the nodes in the 5th column
In this example the roots I chose have zero imaginary parts, but this approach still works if the roots have nonzero imaginary parts. This method could be used to compute the coefficients of polynomials of degrees larger than , of course.