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?



Matrix of powers of pairwise differences
$$(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)$.


