# Making a matrix invertible

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$?)

• @flawr The OP wrote distinct. – Amitai Yuval Sep 17 '14 at 11:02
• 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$? – flawr Sep 17 '14 at 11:05
• The first one to the two. – Amitai Yuval Sep 17 '14 at 11:06
• @flawr I think the right thing to do is delete your comments, now that you know they're irrelevant in this context. – 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.
• 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? – angryavian Sep 17 '14 at 14:00
• 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. – Kelenner Sep 17 '14 at 14:03
• 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. – angryavian Sep 17 '14 at 14:18
• 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}$. – Kelenner Sep 17 '14 at 14:40
• [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. – angryavian Sep 17 '14 at 14:58