1
$\begingroup$

I am thinking about this problem:

Let $\sum_{i=1}^N a_ix_i^k = b_k,\ k = 0,1,2,\dots,$ be an equation system. If I only know all the values of $b_k$'s, is there any way to find out the values of $a_i$'s and $x_i$'s for $i=1,2,\dots,N$? And how many equations do I need to use to solve $a_i$'s and $x_i$'s?

In the case that all the $a_i = 1$, I know that I can use Newton's equality and then solve the roots of a polynomial to find out $x_i$'s. But in the case that $a_i\neq 1$, I have no idea.

Thanks in advance for any advice you can offer.

  • 1
    However many equations we have, we cannot distinguish between $a_1=0$ and $x_1=0$.2012-06-28

1 Answers 1

2

André Nicolas' comment shows that we need to assume that the $a_i$ and the $x_i$ are all nonzero. We of course also need to assume that the $x_i$ are distinct.

Given this, let $p(t) = \prod (t - x_i) = t^n - e_1 t^{n-1} + e_2 t^{n-2} \mp ... + (-1)^n e_n$ be the polynomial whose roots are the $x_i$. Then $b_k$ satisfies the linear recurrence with characteristic polynomial $p$, or $b_{k+n} = e_1 b_{k+n-1} - e_2 b_{k+n-2} \pm ....$

Setting $k = 0, 1, 2, ... n-1$ gives a system of $n$ linear equations in the $n$ variables $e_1, ... e_n$. I have not actually thought about whether the conditions we've already specified are enough to ensure that this system always has a solution, but the determinant of the corresponding matrix looks vaguely like a Vandermonde matrix so let's guess that we're okay.

Once we have the $e_i$, we can determine the $x_i$ (in principle), and once we have the $x_i$, inverting the Vandermonde matrix gives us the $a_i$ from $b_0, ... b_{n-1}$.

  • 0
    @JSH: the set of all sequences satisfying the linear recurrence is a vector space of dimension $n$ (since such a sequence is determined freely by its first $n$ terms). Moreover the sequences $x_i^k$ all clearly lie in this vector space. So any linear combination does as well (and they span since they are linearly independent).2012-06-28