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^{m1} & x_2^{m1} & x_3^{m1} & \ldots & x_n^{m1} \end{bmatrix}, $ when $m=n1$, $x_i \neq x_j$, what is the kernel of V? I mean when $m=n1$, the kernel is onedimensional. 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_1x_2)(x_1x_3)(x_1x_4)},\frac{1}{(x_2x_1)(x_2x_3)(x_2x_4)},\frac{1}{(x_3x_1)(x_3x_2)(x_3x_4)},\frac{1}{(x_4x_1)(x_4x_2)(x_4x_3)}]^t$
and in general one has the vector whose $jth$ entry is $\frac{1}{\prod_{i \ne j}x_jx_i}$. Dividing through by the last entry gives
$[\frac{(x_2x_4)(x_3x_4)}{(x_1x_2)(x_1x_3)},\frac{(x_1x_4)(x_3x_4)}{(x_2x_1)(x_2x_3)},\frac{(x_1x_4)(x_2x_4)}{(x_3x_1)(x_3x_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_ix_n}{x_jx_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^{m1} & x_2^{m1} & x_3^{m1} & \ldots & x_n^{m1} \end{bmatrix}$$ The question posed was how to find a vector in the (dimension 1, right) kernel of $V_{n1}$. 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_{n1}$ 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 (n1)$ matrix $V_n(x_1,x_2,\cdots,x_{n1}).$ Try it before reading further.
If $f(x)=\sum_0^{m1}a_jX^j$ is a polynomial and $\mathbf{a}=[a_0,a_1,\cdots,a_{m1}]$ 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 $n1$ polynomial $F$ with $F(x_j)=1$ but $F(x_i)=0$ for $i \ne j$. Evidently, $F(X)=\prod_{i\ne j}\frac{Xx_i}{x_jx_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^{n1}$ 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_{n1}$.