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.

  • $\begingroup$ 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? $\endgroup$ – Alex Degtyarev Nov 11 '14 at 14:31
  • $\begingroup$ @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. $\endgroup$ – TravisJ Nov 11 '14 at 16:04
  • $\begingroup$ @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). $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – TravisJ Nov 11 '14 at 19:41
  • $\begingroup$ I've added one more to my answer. $\endgroup$ – 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.)

  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.