# Linear independence of element-wise powers of positive vectors

Consider a vector $$x$$ with $$0 < x_1 < \cdots < x_n < \infty$$, and let $$0 < \gamma_1 < \cdots < \gamma_n < \infty$$.

I would like to show that $$x^{\gamma_1}, \ldots, x^{\gamma_n}$$ are linearly independent, where $$x^{\gamma_i}$$ is defined as the vector $$(x_1^{\gamma_i}, \ldots, x_n^{\gamma_i})$$.

It is clear that $$x^{\gamma_1}$$ and $$x^{\gamma_2}$$ are linearly independent, and I might have an overly complicated argument for the case $$x^{\gamma_1}$$, $$x^{\gamma_2}$$, and $$x^{\gamma_3}$$, but I'm really at a loss about how to tackle the general case.

The following proposition shows that $$x^{\gamma_1}, \dots x^{\gamma_n}$$ are indeed always linearly independent if $$x \in \mathbb{R}^n$$ has $$n$$ mutually distinct strictly positive entries.

Proposition. For all real numbers $$\gamma_1 < \dots < \gamma_n$$ (be they positive or not) and each tuple $$0 \not= (\alpha_1, \dots, \alpha_n) \in \mathbb{R}^n$$ the function $$f_n: (0,\infty) \ni t \mapsto \alpha_1 t^{\gamma_1} + \dots + \alpha_n t^{\gamma_n} \in \mathbb{R}$$ has at most $$n-1$$ distinct zeros (by "distinct" I mean that we do not count multiplicities of zeros).

Proof. We show the proposition by induction. The assertion is obvious for $$n = 1$$, so assume that the claim has been proved for some $$n \in \mathbb{N}$$ and consider $$n+1$$ terms now.

Assume that $$f_{n+1}$$ has at least $$n+1$$ distinct zeros in $$(0,\infty)$$. Then all the coefficients $$\alpha_1, \dots, \alpha_{n+1}$$ are non-zero (otherwise $$f_{n+1}$$ would be a non-trivial linear combination of $$n$$ terms with at least $$n+1$$ zeros).

The function $$t^{-\gamma_1}f_{n+1}(t)$$ also has at least $$n+1$$ distinct zeros, and hence, its derivative $$(t^{-\gamma_1}f_{n+1}(t))'$$ has at least $$n$$ distinct zeros (as a consequence of Rolle's theorem). This is a contradiction since $$(t^{-\gamma_1}f_{n+1}(t))'$$ is a non-trivial linear combination of the $$n$$ terms $$t^{\gamma_2-\gamma_1-1}, \dots, t^{\gamma_{n+1}-\gamma_1 - 1}$$.

Remark. It is important in the above proof that we show the result for all real numbers $$\gamma_k$$ (and not only for positive ones), since even if all $$\gamma_k$$ are positive we need the induction hypotheses for negative exponents, too. So this is a nice example where strengthening the hypothesis is needed to make induction work..

• Apparently you mean distinct positive zeros in your proposition. Also, a reference to Rolle's theorem would be appropriate. – Max Alekseyev Sep 18 '19 at 14:30
• @MaxAlekseyev: Thank you for your comment! As you suggested, I added a reference to Rolle's theorem. The domain of $f_n$ is defined to be the set $(0,\infty)$ in the proposition, so all zeros of $f_n$ are automatically positive. – Jochen Glueck Sep 18 '19 at 15:18
• So now, you might want to note that if the OP's proposition was true, it would produce a polynomial of the form you discussed with n distinct zeros. It isn't a hard argument, but it directly ties your proposition to the problem. :) But I guess that depends on the expected audience. – Yakk Sep 18 '19 at 20:41
• @Yakk: Well, the first sentence in my post mentions that the subsequent proposition gives a positive answer to the OP's question, right? – Jochen Glueck Sep 18 '19 at 20:47
• No, I mean, explain how the number of zeros of a polynomial (where you reuse variables in the OP's question with different meaning) relate to the linear dependence of of the OP's elements. Specifically: if the OP's set of vectors is linearly dependent, then the $\alpha_i$ coefficients can be used to generate a a polynomial of the form $f_n$, and each of the distinct $x_i$ in the OP's question correspond to a distinct root of that $f_n$, and thus prove $n-1 >= n$. Or flip it around and do it without a contradiction. – Yakk Sep 18 '19 at 21:04

In the case of integer $$\gamma_i$$, the determinant is nonzero (in fact, strictly positive). This is proved in Gantmacher, The Theory of Matrices, Vol 2, p99. Gantmacher calls it a "generalized Vandermonde matrix", though that name is also used for a different class of matrices.

Gantmacher's proof uses the properties of polynomials like Rolle's Theorem, so I don't think it will work for non-integer $$\gamma_i$$. But I bet that case is out there somewhere.

• For integer $\gamma_i$, the vectors $x^\gamma_i$ are a subset of the columns of a (square invertible) Vandermonde matrix. Isn't this enough to conclude that they are linearly independent? – Federico Poloni Sep 18 '19 at 13:04
• The determinant must also be strictly positive when the $\gamma_i$ are positive reals. This follows from the fact that the $x^{\gamma_i}$ form a `Descartes system' and is given in Borwein and Erdelyi, Polynomials and Polynomial Inequalities as a guided exercise; see E.2 here – MKR Sep 18 '19 at 13:27
• @FedericoPoloni It is a minor of a Vandermonde matrix and there is a formula for the determinant: math.unipd.it/~demarchi/papers/res-math1.ps – Brendan McKay Sep 18 '19 at 13:31
• @BrendanMcKay Not simply a minor, but a subset of its columns (or rows, depending on how you define Vandermonde matrices). Minors of an invertible matrix are not guaranteed to have full rank, but subsets of the columns are. – Federico Poloni Sep 18 '19 at 13:34
• @FedericoPoloni Usually a Vandermonde matrix is defined to be square, and this smaller matrix is square too so it isn't a subset of the columns. It's a minor. You are right that minors aren't nonsingular in general but in this case they are. – Brendan McKay Sep 18 '19 at 13:37

When $$\gamma_i$$ are rational, let $$L$$ be the LCM of their denominators. Then a linear dependency would imply that $$x_1^{1/L},\dots,x_n^{1/L}$$ are zeros of a certain polynomial with at most $$n$$ nonzero coefficients. However, this contradicts Descartes' rule of signs.