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.
Best Answer
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.