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.



When does a Vandermonde-like matrix have full rank
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.


