Building a polynomial from its roots II

Suppose we are given an $n$ -tuple of (not necessarily distinct) complex numbers $(w_1, w_2, \ldots, w_n)$ and we construct a monic univariate polynomial of degree $n$ over field $\mathbb{C}$ whose $n$ roots are the elements of $(w_1, w_2, \ldots, w_n)$

$p_n(z) = \displaystyle\prod_{i=1}^n (z - w_i) = \displaystyle\sum_{m=0}^n a(m,n) z^m$ ,

where $a(m,n) \in \mathbb{C}$ is the coefficient of monomial $z^m$ of degree $m$ in polynomial $p_n(z)$ of degree $n$ . 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 $\{a(m,n)\}_{m=0}^{n}$ of polynomial $p_n(z)$ in terms of the roots $(w_1, w_2, \ldots, w_n)$ . Note that every permutation of the $n$ -tuple $(w_1, w_2, \ldots, w_n)$ results in the same monic polynomial of degree $n$ .

_____

Constructing polynomials

Say we know the coefficients of polynomial $p_k(z)$ of degree $k$ . Then we can write the coefficients $\{a(m, k+1)\}_{m=0}^{k+1}$ of polynomial $p_{k+1}(z)$ in terms of the coefficients $\{a(m, k)\}_{m=0}^{k}$ and the $(k+1)$ -th element of $n$ -tuple $(w_1, w_2, \ldots, w_n)$ . On my previous post on this topic, I derived the recursion

$a(m,k+1) = \displaystyle\left\{\begin{array}{rl} - w_{k+1} a(0,k) & \text{if} \quad{} m = 0\\ a(m-1,k) - w_{k+1} a(m,k) & \text{if} \quad{} 1 \leq m \leq k\\ a(k,k) & \text{if} \quad{} m=k+1\\ \end{array}\right.$

Let us start with a monic polynomial of degree zero, $p_0(z) = 1$ , whose only coefficient is $a(0,0) = 1$ . We take the first element of the $n$ -tuple $(w_1, w_2, \ldots, w_n)$ and construct the monic polynomial $p_1(z) = z - w_1$ of degree $1$ using the recursion above. Then we take the 2nd root $w_2$ and construct the monic polynomial of degree $2$ whose roots are $w_1, w_2$

$p_2(z) = z^2 - (w_1 + w_2) z + w_1 w_2$ .

Iterating successively, we obtain a monic polynomial $p_n(z)$ of degree $n$ whose roots are $w_1, w_2, \ldots, w_n$ .

_____

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 $(i,j)$ , where $i$ is the row index and $j$ is the column index.

We now attach a complex number $a(i,j)$ to each node $(i,j)$ . The coefficient of monomial $z^m$ in polynomial $p_n(z)$ can be thought of as the number attached to node $(m,n)$ . For example, the coefficients of polynomial $p_2(z)$ 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 $p_{k+1}(z)$ in terms of the coefficients of polynomial $p_{k}(z)$

Since the coefficients $a(\cdot, \cdot)$ 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.

_____

An example

Suppose we want to compute the coefficients of the monic polynomial $p_4(z) = (z - 1)^4$ , which has a root of multiplicity $4$ at $z = 1$ . In this case we have $w_1 = w_2 = w_3 = w_4 = 1$ . From the well-known binomial theorem, we know that

$p_4(z) = z^4 - 4 z^3 + 6 z^2 - 4 z + 1$ ,

and therefore, the coefficients are $a(0,4) = 1$ , $a(1,4) = -4$ , $a(2,4) = 6$ , $a(3,4) = -4$ , and $a(4,4) = 1$ . Note that the absolute values of these coefficients are the binomial coefficients and can be found in the 5th row of Pascal’s triangle.

Let us now construct this polynomial one step at a time using the graphical approach described above. We start with monic polynomial $p_0(z) = 1$ , whose only coefficient is $a(0,0) = 1$

and then we compute the coefficients of the monic polynomial $p_1(z) = z-1$ using the recursion formula. Graphically, this means that the values of the 2 nodes in the 2nd column can be computed from $a(0,0)$ , as follows

where the directed edges now have weights. For example, the edge linking nodes $(0,0)$ and $(0,1)$ has weight $-1$ , while the edge linking $(0,0)$ and $(1,1)$ has weight $1$ . If the weight of an edge is equal to $1$ , then we do not label the edge in order to avoid cluttering the diagram.

From the coefficients of $p_1(z)$ and the second root, $w_2 = 1$ , we can compute the coefficients of $p_2(z)$ 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 $w_3 = 1$ we can now obtain the coefficients of $p_3(z)$

and since $w_4 = 1$ , we can finally obtain the coefficients of the monic polynomial $p_4(z)$ , 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 $4$ , of course.

About these ads

Tags: Mathematics, Polynomials

This entry was posted on December 10, 2008 at 05:58 and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Building a polynomial from its roots II”

Gene Chase Says:
December 31, 2008 at 14:23 | Reply
This sounds like Newton’s Forward Difference Formula, or equivalently Newton’s Backward Difference Formula, by which we can reconstruct an nth degree polynomial given its difference table.
Nate Says:
October 2, 2009 at 13:58 | Reply
Any thoughts of using this type of constructive algorithm to build bivariate (or multivariate) polynomials? I’d be interested to see the issues surrounding that problem worked out.

The technique you have laid out here has some nice applications in constructing polynomials that are constrained to have certain properties. For instance, you could use this technique to construct strictly positive polynomial by making sure that the polynomial has no real roots (the $w_i$ all appear in conjugate pairs). This polynomial can be integrated to make a polynomial that is guaranteed to be monotonic. And so on.

Very nice post. Thanks!
Federico Poloni Says:
February 10, 2010 at 09:13 | Reply
I think you can do it in $O(n \log^2 n)$ operations using discrete Fourier transforms: split the roots in two sets $I$ and $J$ of the same cardinality (plus or minus $1$ if $n$ is odd); then, given the two polynomials $\prod_{a\in I} (x-a)$ and $\prod_{a\in J} (x-a)$ (which you compute by applying this algorithm recursively), multiply them via a DFT. ;)

Rod Carvalho

Building a polynomial from its roots II

Like this:

3 Responses to “Building a polynomial from its roots II”

Leave a Reply Cancel reply

Follow “Rod Carvalho”