Matrix of powers of pairwise differences

Question

Let $\underline{c}:=\left(c_1,\dots,c_n\right)$ be pairwise distinct complex numbers, and let $k$ be a non-negative integer. Define the matrix $A_{n,k}(\underline{c})$ to contain the $k$-th powers of the pairwise differences, i.e. $$ A_{n,k}\left(\underline{c}\right):=\left[ (c_i-c_j)^k \right]_{1\leq i,j \leq n}, $$ where $0^0\equiv 1$.

Direct calculation suggests that $$ rank\left(A_{n,k}\left(\underline{c}\right)\right) = \min\left(k+1,n\right) $$ for all choices of $\underline{c}$.

Is there a well-known/simple proof of this fact?

Answer 1

$$(c_i-c_j)^k = \sum_{h=0}^k \binom{k}{h} (-1)^{k-h}c_i^h c_j^{k-h}$$

and each summand is a rank-1 matrix (since it's a function of $i$ times a function of $j$). To prove that the rank is not lower than that, consider that the vectors $\mathbf{v}_h = (c_i^h)_{i=1}^n$ are independent because they form a Vandermonde matrix, and so are the $\mathbf{w}_h = (c_j^h)_{j=1}^n$.

Sometimes these concepts appears in tensor / matrix approximation problems as "separability" of a two-variable function; in your case, we just showed that the polynomial $(x-y)^k$ has separation rank $k+1$, i.e., it can be written as the sum of $k+1$ terms of the form $f(x)g(y)$.