Let \({x_1},...,{x_n}\) be fixed numbers. The matrix below called a Vandermonde matrix, occurs in applications such as signal processing, error-correcting codes, and polynomial interpolation.

\(V = \left( {\begin{aligned}{*{20}{c}}1&{{x_1}}&{x_1^2}& \ldots &{x_1^{n - 1}}\\1&{{x_2}}&{x_2^2}& \ldots &{x_2^{n - 1}}\\ \vdots & \vdots & \vdots &{}& \vdots \\1&{{x_n}}&{x_n^2}& \ldots &{x_n^{n - 1}}\end{aligned}} \right)\)

Given \(y = \left( {{y_1},...,{y_n}} \right)\) in \({\mathbb{R}^n}\), suppose \({\mathop{\rm c}\nolimits} = \left( {{c_0},...,{c_{n - 1}}} \right)\) in \({\mathbb{R}^n}\) satisfies \(V{\mathop{\rm c}\nolimits} = {\mathop{\rm y}\nolimits} \), and define the polynomial.

\(p\left( t \right) = {c_0} + {c_1}t + {c_2}{t^2} + .... + {c_{n - 1}}{t^{n - 1}}\).

a. Show that \(p\left( {{x_1}} \right) = {{\mathop{\rm y}\nolimits} _1},...,p\left( {{x_n}} \right) = {{\mathop{\rm y}\nolimits} _n}\). We call \(p\left( t \right)\) an interpolating polynomial for the points \(\left( {{x_1},{y_1}} \right),...,\left( {{x_n},{y_n}} \right)\) because the graph of \(p\left( t \right)\) passes through the points.

b. Suppose \({x_1},...,{x_n}\) are distinct numbers. Show that the columns of V are linearly independent. (Hint: How many zeros can a polynomial of degree \(n - 1\) have?)

c. Prove: “If \({x_1},...,{x_n}\) are distinct numbers, and \({y_1},...,{y_n}\) are arbitrary numbers, then there is an interpolating polynomial of degree \( \le n - 1\) for \(\left( {{x_1},{y_1}} \right),...,\left( {{x_n},{y_n}} \right)\).”

It is given that \(y = \left( {{y_1},...,{y_n}} \right)\) in \({\mathbb{R}^n}\). Suppose \({\mathop{\rm c}\nolimits} = \left( {{c_0},...,{c_{n - 1}}} \right)\)in \({\mathbb{R}^n}\) satisfies \(V{\mathop{\rm c}\nolimits} = {\mathop{\rm y}\nolimits} \).

The case of \(i = 1,..,n\)is shown below.

\(\begin{aligned}{c}p\left( {{x_i}} \right) = {c_0} + {c_1}{x_i} + ... + {c_{n - 1}}x_i^{n - 1}\\ = {{\mathop{\rm row}\nolimits} _i}\left( V \right) \cdot \left( {\begin{aligned}{*{20}{c}}{{c_0}}\\ \vdots \\{{c_{n - 1}}}\end{aligned}} \right)\\ = {{\mathop{\rm row}\nolimits} _i}\left( V \right){\mathop{\rm c}\nolimits} \end{aligned}\)

According to the property of matrix multiplication, the fact that c was chosen to satisfy \(V{\mathop{\rm c}\nolimits} = {\mathop{\rm y}\nolimits} \)is shown below.

\(\begin{aligned}{c}{{\mathop{\rm row}\nolimits} _i}\left( V \right){\mathop{\rm c}\nolimits} = {{\mathop{\rm row}\nolimits} _i}\left( {V{\mathop{\rm c}\nolimits} } \right)\\ = {{\mathop{\rm row}\nolimits} _i}\left( y \right)\\ = {y_i}\end{aligned}\)

Therefore\(p\left( {{x_i}} \right) = {y_i}\). To conclude, the entries in \(V{\mathop{\rm c}\nolimits} \) represent the values of the polynomial \(p\left( x \right)\) at \({x_1},...,{x_n}\).

Hence, it is proved that \(p\left( {{x_1}} \right) = {{\mathop{\rm y}\nolimits} _1},...,p\left( {{x_n}} \right) = {{\mathop{\rm y}\nolimits} _n}\).

Let \({x_1},...,{x_n}\) be distinct vectors and let \(Vc = 0\) for some vector c. Therefore, the entries in c represent the polynomial whose coefficients are zero at the distinct points\({x_1},...,{x_n}\). In addition, the polynomial must be identically zero since a non-zero polynomial of degree \(n - 1\) cannot have \(n\) zeros. This means that the entries in \(c\) must all be zero. It demonstrates that the columns of V are linearly independent.

Thus, it is proved that the columns of V are linearly independent.

If \({x_1},...,{x_n}\) are distinct vectors, then the columns of V are linearly independent by part (b). V is invertible, and the columns of V span \({\mathbb{R}^n}\) according to the invertible matrix theorem. Therefore, for every \(y = \left( {{y_1},...,{y_n}} \right)\) in \({\mathbb{R}^n}\), there exists a vector c such that \(Vc = y\). Suppose p be the polynomial whose coefficients are contained in c. According to part (a), \(p\) is an interpolating polynomial for \(\left( {{x_1},{y_1}} \right),...,\left( {{x_n},{y_n}} \right)\).

Thus, it is proved that \(p\) is an interpolating polynomial for \(\left( {{x_1},{y_1}} \right),...,\left( {{x_n},{y_n}} \right)\).