6
$\begingroup$

Given some roots : $r_1,r_2,\ldots,r_n$, how can we reconstruct polynomial coefficients?

I know the Horner scheme and that we can just go backwards receiving those coefficients.

But I'm curious if there's some other nice solution to this problem.

$\endgroup$
  • 7
    $\begingroup$ I'm not sure I'm answering your question, but to get the coefficients from the roots, just expand $(X-r_1) (X-r_2) \ldots (X-r_n)$. You get $$(X-r_1) (X-r_2) \ldots (X-r_n) = X^n - (r_1 + r_2 + \cdots + r_n) X^{n-1}+ \cdots + (-1)^n r_1 r_2 \ldots r_n X^0$$ The expressions you find are called symmetric polynomials. $\endgroup$ – Joel Cohen Oct 3 '11 at 15:21
  • 3
    $\begingroup$ This is relevant: elementary symmetric polynomials. $\endgroup$ – Srivatsan Oct 3 '11 at 15:22
  • 2
    $\begingroup$ It's not clear to me how you can take the Horner scheme "backwards" to get the coefficients. $\endgroup$ – Thomas Andrews Oct 3 '11 at 15:27
  • $\begingroup$ Joel could you elaborate hows this equation goes further? I can't get it $\endgroup$ – Krzysztof Lewko Oct 3 '11 at 15:52
  • 2
    $\begingroup$ @Chris : The $X^{n-2}$ coefficient is $\sum_{1 \le i, j \le n} r_i r_j$ (sum of products of $2$ roots), then the $X^{n-3}$ coefficient $-\sum_{1 \le i, j, k \le n} r_i r_j r_k$ (sum of products of $3$ roots), the $X^{n-4}$ coefficient $\sum_{1 \le i, j, k, l \le n} r_i r_j r_k r_k$ (sum of products of $4$ roots) and so on. The $X^{n-k}$ coefficient is $(-1)^k\sum_{1 \le i_1, i_2, \ldots, i_k \le n} r_{i_1} r_{i_2} \ldots r_{i_k}$ (sum of products of $k$ roots). $\endgroup$ – Joel Cohen Oct 3 '11 at 16:37
10
$\begingroup$

Knowing the location of roots really only pins down a family of polynomials, which vary by multiplicative constants. If you know the roots of $P(x)$ are $r_1, r_2, \dots, r_n $ then you can write the polynomial as $$ P(x) = a (x-r_1)(x-r_2) \cdots (x-r_n) $$

where $a$ is some non-zero constant. However, we can not be more precise than that. We can pin down $a$ if we know the value of $P$ are any other point. If we knew $a$, then simply expanding the right hand side would produce the polynomial in a form where you could read off the constants.

$\endgroup$
  • 1
    $\begingroup$ As a tiny note: the requirement of an $a$ along with the $n$ roots is very much consistent with the fact that one requires $n+1$ conditions to uniquely determine a polynomial. $\endgroup$ – J. M. is a poor mathematician Oct 4 '11 at 0:42
4
$\begingroup$

The polynomial is $P(z) = a_0 (z-r_1)\times (z-r_2) \times \cdots \times (z-r_n)$. Now labeling coefficients as $P(z) = a_0 z^n + a_1 z^{n-1} + \ldots + a_n$ we have $$ a_1 = -a_0 ( r_1 + r_2 + \ldots + r_n) \qquad a_n = (-1)^n a_0 r_1 \times r_2 \times \cdots \times r_n $$ In general: $$ a_k = \frac{(-1)^k}{k!} a_0 \sum_\pi r_{\pi(1)} \times \cdots \times r_{\pi(k)} $$ where the sum is over permutations $ \pi \in \mathfrak{S}_n$.

$\endgroup$
  • $\begingroup$ Thanks for the to-the-point answer, Sasha. Do I understand correctly that $\mathfrak{S}_n$ is set of all $k$-permutations of the set $\{1,...,n\}$? $\endgroup$ – Garrett Jul 1 '16 at 22:28
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Sasha Jul 2 '16 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.