Given $N$ distinct real numbers $x_1,\ldots, x_N$, how can I show that there exist real numbers $a_1,\ldots, a_N$ so that the following matrix is invertible?

$$\begin{bmatrix} \exp(ia_1 x_1) & \exp(i a_2 x_1) & \cdots & \exp(i a_N x_1)\\ \exp(ia_1 x_2) & \exp(i a_2 x_2) & \cdots & \exp(i a_N x_2)\\ \vdots & \vdots & \ddots & \vdots\\ \exp(ia_1 x_N) & \exp(i a_2 x_N) & \cdots & \exp(i a_N x_N)\\ \end{bmatrix}$$

Coming up with the $a_n$ explicitly seems hard. Would a proof by contradiction work? (Suppose it is not invertible for any choice of the $a_n$. Then we must have some $x_i=x_j$ for $i \ne j$?)

  • 1
    $\begingroup$ @flawr The OP wrote distinct. $\endgroup$ – Amitai Yuval Sep 17 '14 at 11:02
  • $\begingroup$ Does that mean $x_i \neq x_j \forall i \neq j$ or just that $\exists i,j$ s.t. $x_i \neq x_j$? $\endgroup$ – flawr Sep 17 '14 at 11:05
  • $\begingroup$ The first one to the two. $\endgroup$ – Amitai Yuval Sep 17 '14 at 11:06
  • 1
    $\begingroup$ @flawr I think the right thing to do is delete your comments, now that you know they're irrelevant in this context. $\endgroup$ – Amitai Yuval Sep 17 '14 at 11:10

a) First note that if we have a sum $$f(a)=\sum_{k=1}^N \lambda_k \exp(iax_k)$$ with the $x_k\in \mathbb{R}$ distincts, then this function is zero on $\mathbb{R}$ if and only if all $\lambda_k$ are zero. To see this, use induction on $N$, and if $f(a)=0$ for all $a$, compute the derivative of $g(a)=f(a)\exp(-iax_N)$.

b) Now prove your assertion by induction on $N$. I leave to you the case $N=1,N=2$. Now to show that the assertion is true for $N$ if it is true for $N-1$, you have by the induction hypothesis that there exists $a_1,\cdots,a_{N-1}$ such that the $(N-1)\times (N-1)$ determinant is non zero, that we fix. If we put $a=a_N$ in the $N\times N$ determinant, and developping it with respect to the last column, we get an expression of the form $f(a)$ of a). In addition, the coefficient of $\exp(iax_N)$ is the non zero determinant $(N-1)\times (N-1)$. Hence by a) $f(a)$ is not the zero function, and there exists $a=a_N$ such that$f(a_N)$ is not zero, and we are done.

  • $\begingroup$ I am getting $g'(a) = i \sum_k \lambda_k (x_k-x_N) \exp(ia(x_k-x_N))=0$; where is the contradiction? $\endgroup$ – angryavian Sep 17 '14 at 14:00
  • $\begingroup$ For $k=N$ your last term is zero. Hence you can use the induction hypothesis (as the $x_k-x_N$, $1\leq k\leq N-1$ are all distincts); this gives to you $\lambda_k=0$ for $k=1,\cdots,N-1$. Now $\lambda_N =0$ is easy. $\endgroup$ – Kelenner Sep 17 '14 at 14:03
  • $\begingroup$ I see, thank you. Is there any intuition for where the definition of $g$ comes from? I don't think I could have come up with it myself. $\endgroup$ – angryavian Sep 17 '14 at 14:18
  • $\begingroup$ This trick is used in several questions. For example, show using this trick and Rolle's Theorem that if $x_k$ are distincts $\in \mathbb{R}$, a (real valued...) function $f(y)=\sum_{k=1}^n \lambda_k \exp(y x_k)$ has at most $n-1$ zeros $\in \mathbb{R}$. $\endgroup$ – Kelenner Sep 17 '14 at 14:40
  • $\begingroup$ [We also should assume WLOG that $\lambda_k \ne 0$ for any $k$.] If $n=1$, the statement is clear. For $n \ge 2$, assume the statement holds for $n-1$ and consider the case of $n$. Suppose for sake of contradiction that $f$ has $n$ zeros. Then $g$ (defined as before) has $n$ zeros in the same places. Rolle's theorem shows that $g'$ has $n-1$ zeros, but because $g'(y) = \sum_{k=1}^{n-1} \lambda'_k \exp(y(x_k-x_n))$, this is a contradiction by the inductive hypothesis. $\endgroup$ – angryavian Sep 17 '14 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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