Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
See en.wikipedia.org/wiki/Cramer%27s_rule –  David Speyer Dec 13 '10 at 12:49
5  
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). –  darij grinberg Dec 13 '10 at 12:54
add comment

1 Answer

up vote 8 down vote accepted

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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