# How to show a certain determinant is non-zero

For any $n$ distinct points $x_1,x_2 , \ldots , x_n$ on the real line show that the matrix $M$ where $M(i,j) = e^{\lambda_j x_i}$ has non-zero determinant where $\lambda_1 \lt \lambda_2 \lt \ldots \lt \lambda_n \in \mathbb{R}$ are fixed constants.

I am able to show this for $n=1$(duh...) and $n=2$. Is this an inductive proof?

-
He did post there (math.stackexchange.com/questions/271791/…), and got an answer, but it seems to me that one of the steps in the answer is not valid (where $\Phi(\lambda_t) = 0$ implies $\Phi'(\lambda_t) = 0$ -- how does that follow? however, I am unable to leave a comment there). Are we absolutely sure this is homework? It doesn't look easy to me (van der Monde is a special case). –  Todd Trimble Jan 7 '13 at 16:12
Meta-discussion at tea.mathoverflow.net/discussion/1511/… –  András Bátkai Jan 7 '13 at 17:06
In any case the result follows from the fact that an "exponential polynomial" $A(x) = \sum_{j=1}^n a_j \exp(\lambda_j x)$ (each $\lambda_j \in {\bf R}$ and $a_j \in {\bf R}^*$) with $n$ nonzero terms can have at most $n-1$ real roots. See for instance my accepted answer to mathoverflow.net/questions/83999 (where $n=d+1$). –  Noam D. Elkies Jan 7 '13 at 17:14
See also this discussion: tea.mathoverflow.net/discussion/1501/… The wording of the question is not lucky, but is it not a language problem here as well? –  András Bátkai Jan 7 '13 at 17:29
The only things I saw in the question that might have prompted a "not for homework" response were the imperative "show that..." and "is this an inductive proof?". Yes, it could very well be a matter of less than perfect control of English... Elsewhere I have proposed that before you write, "not for homework", make sure you know how to do the homework yourself. :-) –  Todd Trimble Jan 7 '13 at 19:06

Just in case it helps: to see that the OP's matrix $M$ has nonzero determinant using the argument in Noam Elkies' argument above, consider

$$\begin{equation*} \mathrm{det}\; \begin{pmatrix} e^{\lambda_1 x_1} & e^{\lambda_2 x_1} & \cdots & e^{\lambda_n x_1}\\\\ e^{\lambda_1 x_2} & e^{\lambda_2 x_2} & \cdots & e^{\lambda_n x_2}\\\\ \vdots & \vdots & & \vdots\\\\ e^{\lambda_1 x} & e^{\lambda_2 x} & \cdots & e^{\lambda_n x} \end{pmatrix} \end{equation*}$$

as an exponential polynomial $f(x) = \sum_{k=1}^n a_k e^{\lambda_k x}$. This has roots at $x = x_1, x_2, \ldots, x_{n-1}$. On the other hand, Elkies argued (see mathoverflow.net/questions/83999) that an exponential polynomial with $n$ terms has at most $n-1$ real roots. (We actually need only the weaker claim that $f(x)$ has at most $n-1$ distinct real roots. This follows by induction, where the inductive step involves Rolle's theorem applied to the derivative of the exponential polynomial $e^{-\lambda_n x}f(x)$, which has $n-1$ terms.) Thus $f(x)$ must be nonzero at $x = x_n$, as desired.

-
Thanks. We also need that the coefficients of this exponential polynomial are not all zero; but each coefficient is an order $n-1$ determinant of the same type, so we can frame this as an argument by induction, and then at the $n-1$ step we showed that all of the coefficients are nonzero, so we're done. –  Noam D. Elkies Mar 27 '13 at 22:16
This proof can be made even simpler: If the determinant of the big matrix were $0$, then there would be a nontrivial $\mathbb{R}$-linear combination of its columns that would equal $0$. This immediately means that a nontrivial exponential polynomial with $n$ terms has at least $n$ distinct real roots; this completes the proof, with no induction needed. (Combined with the correct part of my answer, this yields that the determinant is positive.) –  darij grinberg Jul 28 at 16:28
@darijgrinberg Thanks for that! –  Todd Trimble Jul 28 at 17:14

EDIT: OOPS! The solution below is FALSE. My apologies for wasting everyone's time (particularly those among you who already were aware of Schur functions) with this scrible. I'll let it stay around because maybe this thread will one day be renamed "how not to show a certain determinant..." and maybe there is something to be learned from it.

For the record, the mistake is to claim that "multiplying $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ by their common denominator $p$ is easily compensated by replacing the positive reals $y_1$, $y_2$, ..., $y_n$ by the (equally positive) reals $y_1^{1/p}$, $y_2^{1/p}$, ..., $y_n^{1/p}$". This is true for the original question, but not for the more subtle (1). Sorry again!

For the sake of pushing algebraic combinatorics (specifically Schur polynomials), let me present a different proof of the nonvanishing of the determinant in question. The idea of this proof is taken from my Jan 7, 2013 comment on the original question, but it has been tweaked to work in the general case.

We want to prove that $\det\left(\left(e^{\lambda_j x_i}\right)_{1\leq i,j\leq n}\right)\neq 0$ for any $n$ distinct reals $x_1$, $x_2$, ..., $x_n$ and any $n$ distinct reals $\lambda_1$, $\lambda_2$, ..., $\lambda_n$.

Let us WLOG assume that $x_1 > x_2 > ... > x_n$ and $\lambda_1 > \lambda_2 > ... > \lambda_n$ (because interchanging the $x_i$ or the $\lambda_i$ boils down to row resp. column swaps on the matrix whose determinant we are concerned with).

Let us denote $y_i = e^{x_i}$ for every $i\in\left\lbrace 1,2,...,n\right\rbrace$. Then, $y_1$, $y_2$, ..., $y_n$ are $n$ positive reals satisfying $y_1 > y_2 > ... > y_n$, and we must prove that $\det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right)\neq 0$ (since $e^{\lambda_j x_i} = \left(e^{x_i}\right)^{\lambda_j} = y_i^{\lambda_j}$ for any $i$ and $j$).

We can WLOG assume that $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ are all nonnegative, since we could replace the whole $n$-tuple $\left(\lambda_1,\lambda_2,...,\lambda_n\right)$ by $\left(\lambda_1+m,\lambda_2+m,...,\lambda_n+m\right)$ for a sufficiently large real $m$ without changing much about our determinant (namely, the determinant would merely gain a multiplicative factor of $y_1^m y_2^m ... y_n^m$). So assume this.

We will actually prove that

(1) $\det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right) \geq \prod\limits_{1\leq i < j \leq n} \left(y_i-y_j\right) \cdot \prod\limits_{k=1}^n y_k^{\lambda_k - n + k}$.

Once this is proven, it will follow that $\det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right) > 0$ (because the right hand side of (1) is positive) and thus $\det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right) \neq 0$, which is exactly what we need to prove.

So it remains to prove (1) for any $n$ positive reals $y_1$, $y_2$, ..., $y_n$ satisfying $y_1 > y_2 > ... > y_n$, and any $n$ nonnegative reals $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ satisfying $\lambda_1 > \lambda_2 > ... > \lambda_n$.

Note that both sides of the inequality (1) are continuous as functions in $\lambda_1$, $\lambda_2$, ..., $\lambda_n$. Hence, we can WLOG assume that $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ are nonnegative rationals (because the inequality is non-strict, and the set of strictly increasing $n$-tuples of nonnegative rationals is dense in the set of strictly increasing $n$-tuples of nonnegative reals). Assuming this, we can go further and assume WLOG that $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ are nonnegative integers, because multiplying $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ by their common denominator $p$ is easily compensated by replacing the positive reals $y_1$, $y_2$, ..., $y_n$ by the (equally positive) reals $y_1^{1/p}$, $y_2^{1/p}$, ..., $y_n^{1/p}$. So assume this, and let $\mu$ denote the sequence $\left(\lambda_1+n-1, \lambda_2+n-2, ..., \lambda_n+n-n\right)$. This sequence $\mu$ is a partition (in the sense of algebraic combinatorics), i. e., a finite weakly decreasing sequence of nonnegative integers.

Now, for any sequence $\kappa = \left(\kappa_1,\kappa_2,...,\kappa_n\right)$ of nonnegative integers, let $a_{\kappa}$ denote the determinant $\det\left(\left(y_i^{\kappa_j}\right)_{1\leq i,j\leq n}\right)$. Let $\rho$ be the sequence $\left(n-1,n-2,...,0\right)$. Then, $a_{\rho} = \prod\limits_{1\leq i < j \leq n} \left(y_i-y_j\right)$ (by Vandermonde's determinant) while (using the notation $\mu+\rho$ for the termwise sum of the sequences $\mu$ and $\rho$) we have $a_{\mu+\rho} = \det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right)$ (since $\mu+\rho$ is the sequence $\left(\lambda_1,\lambda_2,...,\lambda_n\right)$). Hence, (1) rewrites as

$a_{\mu+\rho} \geq a_{\rho} \cdot \prod\limits_{k=1}^n y_k^{\lambda_k - n + k}$.

Since $a_{\rho} = \prod\limits_{1\leq i < j \leq n} \left(y_i-y_j\right) > 0$, this is equivalent to

(2) $\dfrac{a_{\mu+\rho}}{a_{\rho}} \geq \prod\limits_{k=1}^n y_k^{\lambda_k - n + k}$.

But it is known (e. g., Corollary 2.37 in Victor Reiner, Hopf algebras in combinatorics) that $\dfrac{a_{\mu+\rho}}{a_{\rho}}$ equals the Schur polynomial $s_{\mu}$ evaluated at $\left(y_1,y_2,...,y_n\right)$. Thus,

(3) $\dfrac{a_{\mu+\rho}}{a_{\rho}} = s_{\mu}\left(y_1,y_2,...,y_n\right) = \sum\limits_{T} \prod\limits_{k=1}^n y_k^{\text{number of }k\text{'s in }T}$,

where the $T$ on the right hand side runs over all semistandard (i. e., column-strict) Young tableaux of shape $\mu$ with entries in $\left\lbrace 1,2,...,n\right\rbrace$. One such tableau is obtained by filling each cell in row $k$ with the number $k$, for every $k \in \left\lbrace 1,2,...,n\right\rbrace$ (where the numbering of rows starts with $1$). This tableau contributes one addend to the sum on the right hand side of (3), and this addend is $\prod\limits_{k=1}^n y_k^{\lambda_k - n + k}$ (because the length of the $k$-th row is $\lambda_k - n + k$, and the $k$'s in the tableau are exactly the entries of the $k$-th row). Since all the other addends on the right hand side of (3) are nonnegative (being monomials in $y_1$, $y_2$, ..., $y_n$ with coefficient $1$), this yields

$\dfrac{a_{\mu+\rho}}{a_{\rho}} \geq \prod\limits_{k=1}^n y_k^{\lambda_k - n + k}$.

But this is exactly (2). Since we know that (2) is equivalent to (1), this completes the proof of (1), and thus solves the problem.

Remark: Why did we take the detour through (1) rather than confine ourselves to proving the (weaker but sufficient) inequality

(4) $\det\left(\left(y_i^{\lambda_j}\right)_{1\leq i,j\leq n}\right) > 0$ ?

Because (1) is a non-strict inequality, whereas (4) is strict. When proving a strict inequality, it is not enough to prove it on a dense subset of its domain, even if it is continuous; for example, Vasile Cîrtoaje's brainteaser $\left(x^2+y^2+z^2\right)^2\geq 3\left(x^3y+y^3z+z^3x\right)$ (an inequality holding for all $x,y,z\in \mathbb R$) attains its equality at $x=y=z$ but also at $x:y:z=\sin^2\dfrac{4\pi}{7}:\sin^2\dfrac{2\pi}{7}:\sin^2\dfrac{\pi}{7}$, an equality condition invisible when one restricts oneself to the dense subset of rationals.

-
This is very pretty. –  Abdelmalek Abdesselam Mar 28 '13 at 22:51
Too pretty for this world... –  darij grinberg May 26 at 0:36

First note that,

1. We show that $L$ and $X$ are full-rank matrices
2. Each set of $n$ columns of $L$ (similarly $X$) is linearly independent
3. $M=LX^T$ is elementwise strictly positive.

However, as Todd has pointed out, the gap in the argument is that: the above points (1-2; I haven't thought about 3 yet) do not suffice to conclude that $LX^T$ has full rank. Since the conclusion is true (using Noam's or Darij's proofs), maybe there is a way to "rescue" the proof outline below---and if not, then I'll still let this "answer" hang in here to show an example of "what type of proof does not work for this problem!"

Here is an attempt at a Vandermonde-based proof.

This proof below is an adaptation of (the proof of) Theorem 4.3.3 from this book by Bapat and Raghavan (their result is cast in terms of positive definite matrices).

Let $A=\lambda x^T$ (where $\lambda=(\lambda_1,\ldots,\lambda_n)$; likewise $x=(x_1,\ldots,x_n)$. and consider the Schur matrix $[e^{a_{ij}}]$. By direct expansion we have

\begin{equation*} [e^{a_{ij}}] = I + A + \frac{A^{(2)}}{2!} + \ldots + \frac{A^{(k)}}{k!} + \ldots \end{equation*} where $A^{(k)}$ is the Schur power of matrix $A$. We see that, \begin{equation*} A^{(2)} = (\lambda x^T) \circ (\lambda x^T) = (\lambda \circ \lambda)(x \circ x)^T. \end{equation*} Inductively, we obtain that $A^{(k)} = \lambda^{\circ (k)}x^{\circ (k)^T}$ (Schur powers), for $k=1,2,\ldots$.

Thus, it follows that \begin{equation*} [e^{a_{ij}}] = LX^T, \end{equation*} where $L$ and $X$ are infinite matrices with columns given by \begin{eqnarray*} L &=& \begin{pmatrix} \mathbf{1}, \lambda, \frac{\lambda^{\circ (2)}}{\sqrt{2!}},\ldots,\frac{\lambda^{\circ (k)}}{\sqrt{k!}},\ldots \end{pmatrix}\\\\ X &=& \begin{pmatrix} \mathbf{1}, x, \frac{x^{\circ (2)}}{\sqrt{2!}},\ldots,\frac{x^{\circ (k)}}{\sqrt{k!}},\ldots \end{pmatrix}, \end{eqnarray*} where $\mathbf{1}$ denotes the vector of all ones.

The desired invertibility of $[e^{a_{ij}}]$ will follow if we show that each of the matrices $L$ and $X$ has $n$ linearly independent columns. Since the $\lambda_i$ are distinct (given the ordering), as are the $x_i$, as per assumption, the Vandermonde matrix \begin{equation*} V = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\\\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1}\\\\ \vdots & \vdots & \vdots & \vdots\\\\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{pmatrix} \end{equation*} is nonsingular, which shows already that the first $n$ columns of $X$ are linearly independent. A similar argument applies to $L$. Thus, their product $LX^T$ also has full rank, and its determinant is nonzero as desired.

-
Sorry, I'm having trouble understanding your argument. It looks like all that is being said is that the matrix $M$ of the OP is a limit of matrices of full rank $n$. (I don't know how to interpret the product $L X^T$, which involves infinite sums, unless I interpret it as a limit.) But of course, that doesn't prove $M$ itself is of full rank. –  Todd Trimble Mar 27 '13 at 18:54
@Todd: I added a short note of clarification; but I see your worries if we view $M = \lim_{k \to \infty) L_kX_k^T$, because rank is not closed. I just viewed $(LX^T)_{ij}$ as a power series (which converges everywhere, and thus is ok. But maybe this needs to be made slightly more rigorous.... –  Suvrit Mar 27 '13 at 19:35
Thanks. I had already understood what you put in the note; my worry (which I think you understood) is elsewhere. –  Todd Trimble Mar 27 '13 at 19:55
except perhaps if one could use the fact that every set of $n$ columns of $L$ (and $X$) is linearly ID---maybe that could rescue the proof... –  Suvrit Mar 28 '13 at 0:17
Hate to be such a spoil-sport (and I'd welcome a variation on your idea that gets the job done), but let me give a simple example of the type of thing I think needs to be addressed. Take $n=1$, and suppose $A$ is the $1 \times \infty$ matrix $(1, 1, 1, \ldots)$, and $B$ is the $1 \times \infty$ matrix $(1, -1/2, -1/4, -1/8, \ldots)$. Then every set of $n$ columns of $A$ and of $B$ is linearly independent. But $A B^T = 0$. –  Todd Trimble Mar 28 '13 at 16:41