Given a Vandermonde matrix $ V= \begin{bmatrix} 1 & 1 & 1 & \ldots & 1 \\\\ x_1 & x_2 & x_3 & \ldots & x_n \\\\ x_1^2 & x_2^2 & x_3^2 & \ldots & x_n^2 \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ x_1^{m-1} & x_2^{m-1} & x_3^{m-1} & \ldots & x_n^{m-1} \end{bmatrix}, $ when $m=n-1$, $x_i \neq x_j$, what is the kernel of V? I mean when $m=n-1$, the kernel is one-dimensional. Can we present the analytical form for the kernel.
-
$\begingroup$ See en.wikipedia.org/wiki/Cramer%27s_rule $\endgroup$– David E SpeyerDec 13, 2010 at 12:49
-
5$\begingroup$ So basically you are looking for the inverse of the (complete) Vandermonde matrix. There is a formula for that: proofwiki.org/wiki/Inverse_of_Vandermonde%27s_Matrix (and the proof is simple Lagrange interpolation). $\endgroup$– darij grinbergDec 13, 2010 at 12:54
1 Answer
The answer is pretty much given by darij but it is nice enough (in final form) to spell out a bit further. The short story is that for $n=4$ one vector in (right) kernel is the column vector
$[\frac{1}{(x_1-x_2)(x_1-x_3)(x_1-x_4)},\frac{1}{(x_2-x_1)(x_2-x_3)(x_2-x_4)},\frac{1}{(x_3-x_1)(x_3-x_2)(x_3-x_4)},\frac{1}{(x_4-x_1)(x_4-x_2)(x_4-x_3)}]^t$
and in general one has the vector whose $jth$ entry is $\frac{1}{\prod_{i \ne j}x_j-x_i}$. Dividing through by the last entry gives
$[\frac{(x_2-x_4)(x_3-x_4)}{(x_1-x_2)(x_1-x_3)},\frac{(x_1-x_4)(x_3-x_4)}{(x_2-x_1)(x_2-x_3)},\frac{(x_1-x_4)(x_2-x_4)}{(x_3-x_1)(x_3-x_2)},1]^t$
and in general one has the vector whose $j$th entry is $1$ for $j=n$ and otherwise is is $\prod_{i \ne j,n}\frac{x_i-x_n}{x_j-x_i}$.
The longer story is still fairly compact. Consider the $m \times n$ matrices $V=V_m=V_m(x_1,x_2,\cdots x_n)=$ $$\begin{bmatrix} 1 & 1 & 1 & \ldots & 1 \\ x_1 & x_2 & x_3 & \ldots & x_n \\ x_1^2 & x_2^2 & x_3^2 & \ldots & x_n^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_1^{m-1} & x_2^{m-1} & x_3^{m-1} & \ldots & x_n^{m-1} \end{bmatrix}$$ The question posed was how to find a vector in the (dimension 1, right) kernel of $V_{n-1}$. If we add any $nth$ row to make an (invertible) matrix $M$, then the last column of $M^{-1}$ will work. The first answer above comes from putting in the final row which makes $V_{n-1}$ into $V_n$. The second comes from using $[0,0,\cdots,0,1]$ as the final row. A related, useful and easier problem is to find an $n$-entry row vector in the (left) kernel of the $n \times (n-1)$ matrix $V_n(x_1,x_2,\cdots,x_{n-1}).$ Try it before reading further.
If $f(x)=\sum_0^{m-1}a_jX^j$ is a polynomial and $\mathbf{a}=[a_0,a_1,\cdots,a_{m-1}]$ then $\mathbf{a}V =[f(x_1),f(x_2),\cdots,f(x_n)]$. If we want to find the inverse of the square matrix $V_n$ then from $V^{-1}V=I$ we see that the $j$th row of $V^{-1}$ should be the coefficients of the degree $n-1$ polynomial $F$ with $F(x_j)=1$ but $F(x_i)=0$ for $i \ne j$. Evidently, $F(X)=\prod_{i\ne j}\frac{X-x_i}{x_j-x_i}$ since the degree and values are correct. We know how to use the elementary symmetric functions to find the coefficients of $F$ but do not need that knowledge to see that coefficient of $X^{n-1}$ is $1$. Then using $VV^{-1}=I$ we see that the first vector described above is the final column of $V^{-1}$ and is in the kernel of $V_{n-1}$.