# When does a Vandermonde-like matrix have full rank

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.

• In what terms do you expect the answer? (It is related to the superabundance of a certain linear system, but I doubt that this fact makes the problem easier.) E.g., think about the case $d=2$ and $n=6$: $6$ points in the plane lie in a conic; how do you want this restated? – Alex Degtyarev Nov 11 '14 at 14:31
• @AlexDegtyarev, would you mind elaborating a little on the "superabundance of a certain linear system?" I'm happy to do some reading if you can point me in the right direction. My algebra/topology background is not terribly profound. Thanks. – TravisJ Nov 11 '14 at 16:04
• @AlexDegtyarev, Is it sufficient to say that the sampled points must not be contained in any $d$ lines? In the counter-example you gave, the data points are contained in 2 (looking at a degree 2 polynomial). – TravisJ Nov 11 '14 at 16:29

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.

• Thank you. This definitely gets me pointed in the right direction. The problem I'm working on is modeling a surface and sampling is expensive... so I want to sample enough points that $X^{T}X$ is non-singular. In practice though, what happens is that because of numerical issues, the computer calculates something (wrong frequently) for $(X^{T}X)^{-1}$. I was hoping to get some kind of "relatively easy" certificate that my matrix did in fact have an inverse. – TravisJ Nov 11 '14 at 19:41
• I've added one more to my answer. – Alex Degtyarev Nov 11 '14 at 22:52

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.)

• Thanks for the reference--I will go do some reading. I am slightly confused by the idea to set $y_{i}=x_{i}^{t}$ with $t>n$ because the $x_{i}$'s and $y_{i}$'s are sampled points. There would be a $t$ such that $y_{i}=x_{i}^{t}$ but (at least in my case) it will not be the case that $t>n$... unless the superscript $t$ is just another index (not a power). The other issue is that I understand why I could re-order the entries of column $X_{i}$, but then I'd have to re-order all the columns in the same manner which is unlikely to preserve the increasing nature on the other rows. – TravisJ Nov 12 '14 at 14:21

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.