# 09-240/Classnotes for Tuesday October 13

WARNING: The notes below, written for students and by students, are provided "as is", with absolutely no warranty. They can not be assumed to be complete, correct, reliable or relevant. If you don't like them, don't read them. It is a bad idea to stop taking your own notes thinking that these notes can be a total replacement - there's nothing like one's own handwriting! Visit this pages' history tab to see who added what and when.

## Replacement Theorem

...

1. dim(V) = n
1. If G generates V then ${\displaystyle |G|\geq n}$. If also ${\displaystyle \,\!|G|=n}$ then G is a basis.
2. If L is linearly dependent then ${\displaystyle |L|\leq n}$. If also ${\displaystyle \,\!|L|=n}$ then L is a basis. If also ${\displaystyle \,\!|L| then L can be extended to a basis. Proofs a1. If G has a subset which is a basis then that subset has n elements, so ${\displaystyle |G|\geq n}$.
a2. Let ${\displaystyle \beta }$ be a basis of V, then ${\displaystyle \,\!|B|=n}$. Now use replacement with G & L = ${\displaystyle \beta }$. Hence, ${\displaystyle |G|\geq |L|=|B|=n}$.
a. From a1 and a2, we know ${\displaystyle |G|\geq n}$. If ${\displaystyle \,\!|G|=n}$ then G contains a basis ${\displaystyle \beta }$. But ${\displaystyle \,\!|B|=n}$, so ${\displaystyle \,\!|G|=\beta }$, and hence G is a basis.

b. Use replacement with G' being some basis of V. |G| = n.

If ${\displaystyle |L|=|G|}$ then ${\displaystyle |R|=n=|G|}$, so ${\displaystyle R=G}$, so ${\displaystyle (G\backslash R)\cup L}$ generates, so L generates, so L is a basis since it is linearly independent.

We have that L is basis. If ${\displaystyle |L|<|G|}$ the nagain find ${\displaystyle R\subset G}$ such that ${\displaystyle |R|=|L|}$ and ${\displaystyle (G\backslash R)\cup L}$ generates.

1. ${\displaystyle \beta }$ generates V.
2. ${\displaystyle |B|\leq |G|-|R|+|L|=n}$. So by part a, ${\displaystyle \beta }$ is a basis.
3.
2. If V is finite-dimensional (f.d.) and ${\displaystyle \mathbf {W} \subset \mathbf {V} }$ is a subspace of V, then W is also finite, and ${\displaystyle \operatorname {dim} (\mathbf {W} )\leq \operatorname {dim} (\mathbf {V} )}$. If also dim(W) = dim(V) then W = V and if dim(W) < dim(V) then any basis of W can be extended to a basis of V.

Proof: Assuming W is finite-dimensional, pick a basis ${\displaystyle \beta }$ of W; ${\displaystyle \beta }$ is linearly independent in V so by Corollary 3 of part b, ${\displaystyle |B|\leq \operatorname {dim} (\mathbf {V} )\Rightarrow \operatorname {dim} (\mathbf {W} )=|B|\leq \operatorname {dim} (\mathbf {V} )}$. So span(${\displaystyle \beta }$) = V = W so V = W. ...

Assume W is not finite-dimensional. ${\displaystyle \mathbf {W} \neq \{0\}}$ so pick a ${\displaystyle x_{1}\in W}$ such that ${\displaystyle x_{1}\neq 0}$. So ${\displaystyle \{x_{1}\}}$ is linearly independent in W, and ${\displaystyle \operatorname {span} (\{x_{1}\})\subsetneq \mathbf {W} }$. Pick ${\displaystyle x_{2}\in W\backslash \operatorname {span} (\{x_{1}\})}$. So ${\displaystyle \{x_{1},x_{2}\}}$ is linearly dependent and ${\displaystyle \operatorname {span} (\{x_{1},x_{2}\})\subsetneq \mathbf {W} }$. Pick ${\displaystyle x_{3}\in W\backslash \operatorname {span} (\{x_{1},x_{2}\})}$ ... continue in this way to get a sequence ${\displaystyle x_{1},x_{2},\ldots ,x_{n+1}}$ where n = dim(V) and ${\displaystyle \{x_{1},\ldots ,x_{n+1}\}}$ is linearly independent. There is a contradiction by Corollary 3.b.

## The Lagrange Interpolation Formula

[Aside: ${\displaystyle (a-x)(b-x)\ldots (z-x)=0}$ because ${\displaystyle x-x=0}$]

Where ${\displaystyle 1\leq i

Let ${\displaystyle x_{i}}$ be distinct points in ${\displaystyle \Re }$.

Let ${\displaystyle y_{i}}$ be any points in ${\displaystyle \Re }$.

Can you find a polynomial ${\displaystyle P\in \mathbb {P} _{n}(\Re )}$ such that ${\displaystyle P(x_{i})=y_{i}}$? Is it unique?

Example:

${\displaystyle x_{i}=0,1,3}$
${\displaystyle y_{i}=5,2,2}$

Can we find a ${\displaystyle P\in \mathbb {P} _{2}}$ such that

${\displaystyle P(0)=5}$
${\displaystyle P(1)=2}$
${\displaystyle P(2)=2}$?

Solution: Let ${\displaystyle {\tilde {P}}_{i}(x)=\prod _{j=1,j\neq 1}^{n+1}(x-x_{j})\in \mathbb {P} _{n}(\Re )}$. (Remember capital pi notation.)

Then ${\displaystyle {\tilde {P}}_{i}(x_{k})={\begin{cases}0&i\neq k\\\prod _{i\neq j}(x_{i}-x_{j})&i=k\\\end{cases}}}$

${\displaystyle {\tilde {P}}_{1}=(x-x_{2})(x-x_{3})=(x-1)(x-3)=x^{2}-4x+3}$
${\displaystyle {\tilde {P}}_{2}=(x-0)(x-3)=x^{2}-3x}$
${\displaystyle {\tilde {P}}_{3}=(x-0)(x-1)=x^{2}-x}$

${\displaystyle {\begin{matrix}{\tilde {P}}_{1}(0)=3&{\tilde {P}}_{1}(1)=0&{\tilde {P}}_{1}(3)=0\\{\tilde {P}}_{2}(0)=0&{\tilde {P}}_{2}(1)=-2&{\tilde {P}}_{2}(3)=0\\{\tilde {P}}_{3}(0)=0&{\tilde {P}}_{3}(1)=0&{\tilde {P}}_{3}(3)=6\\\end{matrix}}}$

Set ${\displaystyle P_{i}(x)={\frac {1}{{\tilde {P}}_{i}(x)}}\cdot {\tilde {P}}_{i}=\prod _{j\neq i}{\frac {(x-x_{j})}{(x_{i}-x_{j})}}}$

Then ${\displaystyle P_{i}(x_{k})={\begin{cases}0&i\neq k\\1&i=k\\\end{cases}}}$

${\displaystyle P_{1}(x)={\frac {1}{3}}x^{2}-{\frac {4}{3}}x+1}$
${\displaystyle P_{2}(x)=-{\frac {1}{2}}x^{2}+{\frac {3}{2}}x}$
${\displaystyle P_{3}(x)={\frac {1}{6}}x^{2}-{\frac {1}{6}}x}$

Let ${\displaystyle P=\sum _{i=1}^{n+1}y_{i}P_{i}(x)\in \mathbb {P} _{n}(\Re )}$

${\displaystyle P=5\cdot \left({\frac {1}{3}}x^{2}-{\frac {4}{3}}x+1\right)+2\cdot \left(-{\frac {1}{2}}x^{2}+{\frac {3}{2}}x\right)+2\cdot \left({\frac {1}{6}}x^{2}-{\frac {1}{6}}x\right)}$
${\displaystyle \,\!=x^{2}-4x+5}$