---
jupytext:
  formats: md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: '0.8'
    jupytext_version: 1.4.1+dev
kernelspec:
  display_name: Python 3
  language: python
  name: python3
---

+++

(section:uge6S-extra)=
# 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?

```{admonition} Answer
:class: dropdown
$$ 
\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]
$$
```

+++

### Question b

+++

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

$$ 
\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]
$$

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}
:class: dropdown
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}
:class: dropdown
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}
:class: dropdown
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. 
```