Extra (optional) exercises – Long Day

These exercises are optional extra material for students who have finished the exercises of the day and have the time and interest for more.

Extra exercise 1: Row operations and solution set of a system of linear equations

Theorem 6.2.1 in the textbook is central to the theory of systems of linear equations: it tells that we can carry out elementary row operations without altering the solution set.

Question a

Read the theorem and its proof once more and convince yourself that the proof holds.

Question b

Actually, the proof only covers the effect of row operations of the type \(R_i \leftarrow R_i+dR_j\). Finish the proof by checking that the theorem also holds for row operations of the types \(R_i \leftrightarrow R_j\) and \(R_j \leftarrow c\cdot R_j\).

Extra exercise 2: The interpolation problem

In this exercise we will let \(n\) be a natural number and \(p(Z)=a_0+a_1Z+\cdots +a_{n-1}Z^{n-1}\) a polynomial with real coefficients. Let \(c_1,c_2,\dots,c_{n}\) denote distinct (not equal) real numbers.

Question a

Let \(b_1,b_2,\dots,b_{n}\) be real numbers (not necessarily distinct). With \(b_1,b_2,\dots,b_{n}\) and \(c_1,c_2,\dots,c_{n}\) given as before, the \(n\) equations that are given by \(p(c_1)=b_1, p(c_2)=b_2, \dots, p(c_{n})=b_n\) are called the interpolation problem.

Show that the \(n\) equations in the interpolation problem can be written as \(n\) linear equations in the unknowns \(a_0,a_1,\dots,a_{n-1}.\) What is the coefficient matrix of these linear equations?

Answer

\[\begin{split} \left[ \begin{array}{rrrrr} 1 & c_1 & \dots & c_1^{n-1}\\ 1 & c_2 & \dots & c_2^{n-1}\\ \vdots & \vdots & & \vdots\\ 1 & c_n & \dots & c_n^{n-1}\\ \end{array} \right] \end{split}\]

Question b

As before, let \(c_1,\dots,c_n\) be different real numbers. A matrix of the form

\[\begin{split} \left[ \begin{array}{ccccc} 1 & c_1 & \dots & c_1^{n-1}\\ 1 & c_2 & \dots & c_2^{n-1}\\ \vdots & \vdots & & \vdots\\ 1 & c_n & \dots & c_n^{n-1}\\ \end{array} \right] \end{split}\]

is called a Vandermonde matrix. We will denote the matrix by \(\mathbf V(c_1,\dots,c_n)\). Use elementary row operations to show for \(n=1\), \(n=2\) and \(n=3\) that the reduced row-echelon form of a Vandermonde matrix \(\mathbf V(c_1,\dots,c_n)\) has \(n\) pivot elements.

Question c

Let \(b_1,b_2,\dots,b_{n}\) and \(c_1,c_2,\dots,c_{n}\) be given as before. Show that there exists at most one polynomial \(p(Z)\) of degree no higher than \(n-1\) that solves the corresponding interpolation problem \(p(c_1)=b_1, p(c_2)=b_2, \dots, p(c_{n})=b_n\).

Hint

If there are two different solutions \(p_1(Z)\) and \(p_2(Z)\), to which interpolation problem is \(p_1(Z)-p_2(Z)\) then a solution?

Hint

How many roots can a polynomial of degree \(n-1\) that is not the zero polynomial have?

Question d

For a given \(i\) between \(1\) and \(n\), consider the polynomial

\[L_i(x)=\dfrac{(x-c_1) \cdot \cdots \cdot (x-c_{i-1}) \cdot (x-c_{i+1})\cdot \cdots \cdot (x-c_{n})}{(c_i-c_1) \cdot \cdots \cdot (c_i-c_{i-1}) \cdot (c_i-c_{i+1})\cdot \cdots \cdot (c_i-c_{n})}.\]

Show that \(L_i(x)\) is a polynomial of degree \(n-1\) solving the interpolation problem, if \(b_1=\dots=b_{i-1}=0\), \(b_i=1\) og \(b_{i+1}=\dots=b_n=0.\)

Question e

Let \(b_1,b_2,\dots,b_{n}\) and \(c_1,c_2,\dots,c_{n}\) be given as before. Show that there exists precisely one polynomial \(p(Z)\) of degree no higher than \(n-1\) that solves the corresponding interpolation problem \(p(c_1)=b_1, p(c_2)=b_2, \dots, p(c_{n})=b_n\). Conclude that the Vandermonde matrix \(V(c_1,\dots,c_n)\) has rank \(n\).

Hint

In light of Question c, it is enough to show that the interpolation problem has at least one solution. Show this using the polynomials \(L_1(x),\dots,L_n(x)\) from Question d.