When does a Vandermonde-like matrix have full rank

Question

I have a matrix which is similar to Vandermonde matrix except that the entries are monomials of degree $d$ polynomial in 2 variables. Each row has the following form:

$X_{i}= [1, x_{i}, y_{i}, x_{i}^2, x_{i}y_{i}, y_{i}^2, x_{i}^3, x_{i}^2y_{i},...,x_{i}y_{i}^{d-1}, y_{i}^{d}]$

so that the matrix $X$ contains $n$ rows, $X_{1},...,X_{n}$ where $n$ is large enough that I have more rows than columns.

My question is: when does the matrix $X$ have full rank?

What I'm looking for is necessary/sufficient conditions for when the columns are linearly independent. If this were a Vandermonde matrix (drop all columns that include a $y$ term for example), then the columns would be independent provided that I had enough distinct $x$ values (where enough is the number of columns in the Vandermonde matrix -1). Is there a similar condition here? How many distinct $x$ and $y$ values might guarantee such a result?

For information, the matrix arises in polynomial linear regression. We have a bunch of data points $(x_{i}, y_{i}, z_{i})$ and we want to build a best-fit polynomial surface. The coefficients of the polynomial come from $(X^T X)^{-1}X^T Z$ and so we want to be certain that $X^T X$ is invertible.

Answer 1

This is not an answer but rather a very week sufficient condition. (The true condition is that the points in question should not lie on a degree $d$ curve, but that would be merely a restatement.) So, it suffices to assume that the set of points $\{(x_i,y_i)\}$ contains a product $X\times Y=\{x_0,\ldots,x_d\}\times\{y_0,\ldots,y_d\}$ with $|X|=|Y|=d+1$.

There are lots of ways to prove the sufficiency: Kronecker of two Vandermonde's or just Bezout's theorem.

Obviously, one cannot make it smaller: if, say, $|X|=d$, then all points in $X\times Y$ lie in $d$ lines. (On the other hand, the set containing $X\times Y$ with $|X|=d$ and $|Y|=d+1$ and one more point not in this union of $d$ lines would also do.) One can probably play more with Bezout's theorem and vertical/horizontal lines. (But, as an answer to one of the comments, in general, it is certainly not sufficient to require that the points are not contained in $d$ lines: the curve containing them may be more complicated!) Also, sets like that are quite an overkill: asymptotically, they contain twice as many points as needed.

Remark: As an answer to another comment, in the modern language, "superabundance" is merely $\dim H^1$ of a certain invertible sheaf. But I really do not recommend to dig in this direction: unless the configuration of points is of some very special nature (coming from some geometric problems), that would be just another restatement without useful consequences.

A minimal construction: If the sampling is expensive but, on the other hand, you can choose where to sample, you can just pick distinct $x_0,\ldots,x_d$ and $y_0,\ldots,y_d$ and consider the $(d+1)(d+2)/2$ (the minimal possible number) of points of the form $(x_i,y_j)$, $0\le i\le d$, $i\le j\le d$. Indeed, should these points lie in a degree $d$ curve, applying Bezout's theorem inductively to the vertical lines $x=x_0$, $x=x_1$, etc. (and splitting these lines off), one concludes that all $(d+1)$ lines would have to be components of the curve.

Answer 2

The matrix is called interpolation matrix, the question is when it is invertible or full-rank.

Some relevant results are summarized in part 2 "Haar spaces and multivariate polynomials" of the "Scattered Data Approximation" by Holger Wendland:

• Theorem 2.5 proves that the multivariate monomials are linearly independent.
• Definition 2.6. gives conditions for the points that guarantee unique interpolation: they need to be unisolvent with respect to the polynomial space.
• Discussion of unisolvent configuration follow, e.g., if the points are on a set of lines, or a grid.

"If the data sites are part of a mildly disturbed grid, however, interpolation with polynomials is always possible." So, you may want to simply sample on a regular grid with the number of nodes at least $\dim \pi_m(\mathbb{R}^d)={m+d\choose d}$. But then you could as well use a tensor-product spline interpolation (or LS fitting) which is preferred over polynomial interpolation.

Answer 3

Let $s$ be the number of entries in $X_i$, set $y_i = x_i^t$, where $t > n$, and reorder the entries of $X_i$ into strictly ascending powers of $x_i$. Then, when the number of $x_i$ is $s$, you get a square matrix whose determinant is $\Pi(x_i - x_j)$ times the Schur function of $x_1, \dots , x_s$ corresponding to some partition, a determinant which is nonzero. (See p. 40 of Symmetric Functions and Hall Polynomials, Second Edition, by I. G. Macdonald.)