Chapter 2, Problem 11SE

Let x₁, …, 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{array}{ccccc}1& x_1& x_1^2& \cdots & x_1^{n-1}\\ 1& x_2& x_2^2& \cdots & x_2^{n-1}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^{n-1}\end{array}\right]$

Given y = (y₁,…, y_n) in ℝⁿ, suppose c = (c₀, …, c_n−1) in ℝⁿ satisfies Vc = y, and define the polynomial p(t) = c₀ +c₁t + c₂t² + … + c_n−1tⁿ⁻¹.

1. a. Show that p(x₁) = y₁,…, p(x_n) = y_n. We call p(t) an interpolating polynomial for the points (x₁, y₁), …, (x_n, y_n) because the graph of p(t) passes through the points.
2. b. Suppose x₁,…, 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?]
3. c. Prove:”If x₁,…, x_n are distinct numbers, and y₁,…,y_n are arbitrary numbers, then there is an interpolating polynomial of degree ≤ n − 1 for (x₁, y₁),…, (x_n, y_n)”.