# Is there any algorithm can solve the following equations efficiently?

$$x_1 + x_2 + \cdots +x_n = c_1$$ $$\frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2$$
$$\cdots$$ $$\frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n$$

$c_1,\cdots,c_n$ are known constants. $x_1 \cdots x_n$ are the unknown variables to solve.

• What have you tried ? BTW, using the word algorithm does not make it Computer Science. Solving such equations seems straight math to me. – babou Nov 24 '14 at 1:30
• I am wondering some iteration techniques, but have no experience. Please let me known what kind of mathematics approaciate, I am not sure if numerical mathematics is suitable for math exchange. If necessary i will post it there. – user26143 Nov 24 '14 at 1:34
• Cross-posted on math.se: math.stackexchange.com/questions/1036219/…. – Yuval Filmus Nov 24 '14 at 6:33

One way, which is numerically probably a bad idea, is to use Newton's identities. They give the value of the elementary symmetric functions given the power sums, and from the elementary symmetric functions you can construct a polynomial whose roots are the answers to your problem. Let $$p_k = k! c_k$$, and let $$e_k$$ be the sum of all $$\binom{n}{k}$$ products of $$k$$ variables out of $$x_1,\ldots,x_n$$. Newton's identities state that $$ke_k = (-1)^{k-1} p_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_{k-i} p_i.$$ Using these identities, you can compute $$e_1,\ldots,e_n$$. Now consider the polynomial $$P = x^n + \sum_{i=1}^n (-1)^i e_i x^{n-i}.$$ The unique solution to your equations are the $$n$$ roots of $$P$$.
As an example, let's do the case $$n = 2$$. We have $$e_1 = p_1$$ and $$2e_2 = -p_2 + e_1 p_1 = p_1^2 - p_2.$$ The polynomial $$P$$ is therefore $$x^2 - p_1 x + \frac{p_1^2-p_2}{2}.$$
For $$n=3$$ we calculate additionally $$3e_3 = p_3 - e_1 p_2 + e_2 p_1 = p_3 - p_1 p_2 + \frac{p_1^2-p_2}{2} p_1 = \frac{2p_3 - 3p_1p_2 + p_1^3}{2}.$$ The polynomial $$P$$ is therefore $$x^3 - p_1 x^2 + \frac{p_1^2-p_2}{2}x - \frac{2p_3 - 3p_1p_2 + p_1^3}{6}.$$
• Sorry for late response, excuse me, why the roots of $P$ give the solutions to the eqns above, i.e. $\sum_i^n x_i^k /k!= c_k, k=1,2,\cdots, n$? – user26143 Jan 10 '15 at 13:54
• If we write $P = (x-x_1)(x-x_2)\cdots(x-x_n)$ then we can read off the coefficients of $x^m$ to deduce that $e_1=x_1+\cdots+x_n$, $e_2=x_1x_2+\cdots+x_{n-1}x_n$, and so on. Therefore the roots $x_1,\ldots,x_n$ of $P$ satisfy these equations on $e_1,\ldots,e_n$. We conclude that the roots of $P$ are solutions of the system of equations $e_1=x_1+\cdots+x_n$, $e_2=x_1x_2+\cdots+x_{n-1}x_n$, ..., $e_n = x_1x_2\cdots x_n$. A priori there could be other solutions, but this is not the case here. – Yuval Filmus Jan 10 '15 at 17:25