Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers 2

I guess I should stop being so cryptic. Here is the full solution. Using Newton's sums it is possible to compute the coefficients of the polynomial

$$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.

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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