# Lagrange basis functions as bases of Polynomials Space

Suppose $L$ be a Vector Space of Polynomials of $x$ of degree $\leq n-1$ with coefficients in the field $K$.

Define $$g_i(x) := \prod _ {j=1}_{j\neq i}^n \frac{x-a_j}{a_i-a_j}.$$ Show that the polynomials $g_1(x), g_2(x),...,g_n(x)$ form a basis of L. Furthermore, show that coordinates of polynomial $f$ in this basis are $\{f(a_1),f(a_2),...,f(a_n)\}.$

To show that the polynomials are the bases, I need to show that they span $L$ and that they are linearly independent. I thought showing that any element in the set $\{1,x,x^2,...,x^{n-1}\}$ belongs to the span of $\{g_1(x), g_2(x),...,g_n(x)\}$ would be enough to show the $g_1(x), g_2(x),...,g_n(x)$ spans $L.$ But I don't know how to do this! Also, linear independence seems to be tougher!

-
What is $g_1$? You could use the fact that the size (cardinality) of any basis of $L$ is $n$. Then show that any function $x \mapsto x^k$ can be written in terms of $g_1,..,g_k$. Induction would work nicely here... –  copper.hat Sep 22 '13 at 17:06
The $a_j$ are fixed elements from $K$? Right? –  leo Oct 22 '13 at 2:20

Here is very easy method to show that they are linearly independent.

Suppose that $$b_1g_1(x)+b_2g_2(x)+...+b_ng_n(x)=0$$ To show linear independence, it suffices to show that $$b_1=b_2=...=b_n=0$$ Evaluate $$b_1g_1(x)+b_2g_2(x)+...+b_ng_n(x)=0$$ at $$x=a_i\;\;\;\;\forall i\le n$$

You can notice that $$g_i(a_j)=\begin{cases}0&i=j \\ 1 & i\neq j\end{cases}$$

It follows that $$b_1=b_2=b_3=...=b_n=0$$

To see that the coordinates are given as such, consider a general polynomial as above $$f(x)=c_1g_1(x)+c_2g_2(x)+...+c_ng_n(x)=0$$

Follow same thing as above, start substituting $x=a_i$, you will see that $$c_1=f(a_1)$$ and so on.

Best of luck. I hope I could help.

-
Why is it enough to show that $a_1g_1(x)+a_2g_2(x)+\ldots+a_ng_n(x)=0$ implies $a_1=\cdots=a_n=0$? I mean when proving linear independence we have to prove that for arbitrary scalars $c_1,\ldots,c_n\in K$, $$c_1g_1(x) + \cdots + c_ng_n(x)=0$$ implies $c_1=\cdots=c_n=0$. –  leo Oct 22 '13 at 2:39
I think @leo's objection is that you (inadvertently?) reused the $a_i$ to denote arbitrary scalars with $\sum a_ig_i=0$. –  Pedro Tamaroff Oct 22 '13 at 3:00

Choose arbitrary $f\in L$. Let be $$\tilde{f}(x) = \sum_{i = 1}^{n}f(a_i)g_i(x)\text{.}$$

For every $x\in \{a_1,\dots, a_n\}$ we have $f(x) = \tilde{f}(x)$, so the polynomial $p= f - \tilde{f}$ has $n$ zeros and $\deg p \leq n-1$, so $p(x) = 0$ for every $x\in \mathbb{R}$. So $g_i$ span $L$. We know that $\dim L = n$, so they must be linearly independendent.

-

You missed the hypothesis that the $a_i$ are pairwise distinct. Alternatively, consider the functionals $\eta_i$ with $P\mapsto P(a_i)$ in $V=(\Bbb R_{n-1}[X])^\ast$, and suppose $$\sum_{i=1}^n\lambda_i\eta_i=0$$

Evaluating at $1,X,X^2,\ldots,X^{n-1}$ we get $n$ equations $k=0,1,2,\ldots,n$.

$$\sum_{i=1}^n\lambda_ia_i^k=0$$

Or $$\begin{pmatrix}1&1&\cdots&1\\a_1&a_2& \cdots&a_n\\\vdots&\vdots &\ddots&\vdots\\a_1^{n-1}&a_2^{n-1}&\cdots&a_n^{n-1}\end{pmatrix}\begin{pmatrix}\lambda_1\\ \lambda_2\\\vdots\\ \lambda_n\end{pmatrix}=\begin{pmatrix}0\\ 0\\\vdots\\ 0\end{pmatrix}$$

But since the $a_i$ are pairwise distinct, the Vandermonde matrix is invertible, which means ${\bf \lambda} =\bf 0$ as desired.

The claim follows from the fact your polynomials are precisely the predual basis, call it $B$, of the evaluations above which form a basis $B'$ for $V$. This observation also means that $$(f)_B=(\eta_1f,\ldots,\eta_n f)=(f(a_1),\ldots,f(a_n))$$

This is a general property: if $B^*=\{\varphi_1,\ldots,\varphi_n\}$ is the dual basis of $B=\{v_1,\ldots,v_n\}$, and if $v\in V$, $\varphi\in V^\ast$, then $$(v)_B=(\varphi_1(v),\ldots,\varphi_n(v))$$ $$(\varphi)_{B^\ast}=(\varphi(v_1),\ldots,\varphi(v_n))$$ and the proof is just like that exhibited in the accepted answer: evaluate, and use $\varphi_i(v_j)=\delta_{ij}$.

-