Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I believe the following is true, but I do not know how to prove it.

Given two sets of distinct non-zero complex numbers $z_1, \dots , z_n$ and $w_1, \dots , w_n$, if

$$ \begin{bmatrix} z_{1} & \cdots & z_{n} \\ z_{1}^{2} & \cdots & z_{n}^{2} \\ \vdots & \ddots & \vdots \\ z_{1}^n & \cdots & z_{n}^n \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \begin{bmatrix} w_{1} & \cdots & w_{n} \\ w_{1}^{2} & \cdots & w_{n}^{2} \\ \vdots & \ddots & \vdots \\ w_{1}^n & \cdots & w_{n}^n \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} $$

then $w_1, \dots , w_n$ is a permutation of $z_1, \dots , z_n$.

Any ideas?


Background

Again given distinct non-zero complex numbers $z_1, \dots , z_n$, consider the matrix equation:

$$ \begin{bmatrix} 1 & z_{1} & z_{1}^2 & \cdots & z_{1}^{n-1} \\ 1 & z_{2} & z_{2}^2 & \cdots & z_{2}^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_{n} & z_{n}^2 & \cdots & z_{n}^{n-1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix} $$

By the fundamental theorem of algebra, this equation can only be satisfied when the $a_1, \dots , a_n$'s are all zero, and so the matrix is non-singular. Since the complex numbers $z_1, \dots , z_n$ are non-zero, the matrix

$$ \begin{bmatrix} z_{1} & z_{1}^2 & \cdots & z_{1}^{n} \\ z_{2} & z_{2}^2 & \cdots & z_{2}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ z_{n} & z_{n}^2 & \cdots & z_{n}^{n} \end{bmatrix} $$

is also non-singular, and so its columns form a linearly independent basis for $\mathbb{C}^n$. Considered in this light, the claim above compares two bases formed in this way and says, in effect, if the dot-products of each member of the bases with $[ 1,1, \dots ,1]$ are the same, then the two bases are the same.

share|improve this question
    
Induction?...... –  user17762 Feb 20 '11 at 0:38
    
I played around with induction and got stumped by the inductive step. With the insight provided by the answers below, I now see where the inductive step was headed. –  Eric Nitardy Feb 20 '11 at 1:46

2 Answers 2

up vote 3 down vote accepted

The result is true. Look at http://en.wikipedia.org/wiki/Symmetric_polynomial and http://en.wikipedia.org/wiki/Newton%27s_identities

A symmetric polynomial in $n$ variables $p(x_1,\dots,x_n)$ is one that does not change under any permutation of the variables.

As explained in the first Wikipedia page linked to above, any symmetric polynomial in $x_1,\dots, x_n$ can be expressed as a polynomial expression with rational coefficients in the power sum symmetric polynomials $p_i(x_1, \dots, x_n)$ for $i=1,\dots,n$, where $$p_i(x_1,\dots,x_n)=x_1^i+x_2^i+\dots+x_n^i. $$

The point is then that the coefficients of $$q(x)=(x-z_1)(x-z_2)\dots(x-z_n)$$ are symmetric polynomials of $z_1,\dots,z_n$ and therefore expressible in terms of the $p_i(z_1,\dots,z_n)$. Since these coefficients completely determine $q(x)$, we have the result you are after.

share|improve this answer

Yes, this is true. It follows from Newton's identities, which show that the first $n$ symmetric sums of $n$ numbers determine the coefficients of a polynomial with those numbers as its roots (in characteristic $0$).

A non-recursive formula follows from the exponential formula in combinatorics, which shows that the identity

$$\prod_{i=1}^n (1 + tz_i) = \exp \left( p_1 - \frac{p_2 t^2}{2} + \frac{p_3 t^3}{3} \mp ... \right)$$

is equivalent to the identity

$$e_k = \frac{1}{k!} \sum_{\pi \in S_k} \text{sgn}(\pi) p_{\pi}$$

where

  • $p_k = \sum_{i=1}^n z_i^k$,
  • $e_k$ is the $k^{th}$ coefficient of $\prod (1 + tz_i)$,
  • $\text{sgn}(\pi)$ is the sign of the permutation $\pi$, and
  • $p_{\pi} = p_{\lambda_1} ... p_{\lambda_m}$ where the permutation $\pi$ has cycle type $(\lambda_1, ... \lambda_n)$.

A short proof of the first identity is as follows: let $M$ be a matrix whose eigenvalues are $z_1, ... z_n$. Then the LHS is $\det (I + tM)$ and the RHS is $\exp \text{tr } \log (1 + tM)$. But the identity $\det \exp N = \exp \text{tr } N$ where $N$ is a matrix is straightforward to prove (e.g. by proving it for $N$ diagonalizable and extending by continuity).

share|improve this answer

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.