# Find Vandermonde data to satisfy V*1=p

I would like to state something about the existence of solutions $x_1,x_2,\dots,x_n \in \mathbb{R}$ to the set of equations

$\sum_{j=1}^n x_j^k = np_k$, $k=1,2,\dots,m$

for suitable constants $p_k$. By "suitable", I mean that there are some basic requirements that the $p_k$ clearly need to satisfy for there to be any solutions at all ($p_{2k} \ge p_k^2$, e.g.).

There are many ways to view this question: find the coordinates $(x_1,\dots,x_n)$ in $n$-space where all these geometric structures (hyperplane, hypersphere, etc.) intersect. Or, one can see this as determining the $x_j$ necessary to generate the truncated Vandermonde matrix $V$ (without the row of 1's) such that $V{\bf 1} = np$ where ${\bf 1} = (1,1,\dots,1)^T$ and $p = (p_1,\dots,p_m)^T$.

I'm not convinced one way or the other that there has to be a solution when one has $m$ degrees of freedom $x_1,\dots,x_m$ (same as number of equations). In fact, it would be interesting to even be able to prove that for finite number $m$ equations $k=1,2,\dots,m$ that one could find $x_1,\dots,x_n$ for bounded $n$ (that is, the number of data points required does not blow up).

A follow on question would be to ask if requiring ordered solutions, i.e. $x_1 \le x_2 \le \dots \le x_n$, makes the solution unique for the cases when there is a solution.

Note: $m=2$ is easy. There is at least one solution = the point(s) where a line intersects a circle given that $p_2 \ge p_1^2$.

Any pointers on this topic would be helpful -- especially names of problems resembling it.

-
The solution is unique if it exists for m \ge n. This is a basic exercise in symmetric functions. –  Qiaochu Yuan Feb 20 '10 at 5:10
Up to permutation, that is. –  Qiaochu Yuan Feb 20 '10 at 5:11
Anyway, the keyword here is Newton's sums: artofproblemsolving.com/Wiki/index.php/Newton%27s_sums –  Qiaochu Yuan Feb 20 '10 at 5:40

$$P(x) = (x - x_1)...(x - x_n)$$
provided that $m \ge n$, and this determines the $x_i$ up to permutation. This is essentially a generalization of the technique for $m = 2$, where we compute $(x_1 + ... + x_n)^2 - (x_1^2 + ... + x_n^2)$. So the question is whether this polynomial has all real roots. To answer that question, there is Sturm's theorem. Newton's inequalities give necessary conditions that generalize the ones you give.
A relevant result is the Corollary on page 203 of Gantmacher, Matrix Theory, vol. 2. In particular (if I am interpreting this Corollary correctly) when $n=m$ there exist distinct real solutions if and only if the $n\times n$ matrix $A$ is positive definite, where $A_{ij}=np_{i+j-2}$ (setting $p_0=1$). The condition is clearly necessary, since $A=VV^t$, where $V$ is the Vandermonde matrix $V_{ij}=x_j^{i-1}$.