How to elegantly prove these vectors are linearly independent?

Question

I have the vector made up of geometric sequences:

${A_n} = \left[ {\begin{array}{*{20}{c}} 1&{{a_n}}&{...}&{a_n^{K - 1}} \end{array}} \right]$

Then, how to give a elegent proof that :

$A_1, A_2,...A_N$ is linearly independent? (N << K)

Answer 1

To be linearly independent, clearly, we require $a_i$ to be all distinct.

Pick any $K$ distinct value of $a_i$'s, where we let $A_i$'s be the rows of the matrix $A$. Consider the vector $Ac=0$ where $c \in \mathbb{R}^K$, then we have

$$\sum_{i=0}^{K-1}c_ia_n^{i}=0$$

That is we have $c_i$ are the coefficients of the polynomial $\sum_{i=0}^{K-1}c_ix^{i}$ and the $a_i$'s are the roots.

A degree $K-1$ polynomials have at most $K-1$ distinct roots but we have $k$ roots, hence all the $c_i$ must be equal to $0$.

Hence $\{A_1, \ldots, A_K\}$ are linearly independent. Hence $\{A_1, \ldots, A_N\}$ is linearly independent as well.