09-240/Classnotes for Tuesday October 13

09-240/Navigation Panel   Additions to the MAT 240 web site no longer count towards good deed points # Week of... Notes and Links 1 Sep 7 Tue, About, Thu 2 Sep 14 Tue, HW1, HW1 Solution, Thu 3 Sep 21 Tue, HW2, HW2 Solution, Thu, Photo 4 Sep 28 Tue, HW3, HW3 Solution, Thu 5 Oct 5 Tue, HW4, HW4 Solution, Thu, 6 Oct 12 Tue, Thu 7 Oct 19 Tue, HW5, HW5 Solution, Term Test on Thu 8 Oct 26 Tue, Why LinAlg?, HW6, HW6 Solution, Thu 9 Nov 2 Tue, MIT LinAlg, Thu 10 Nov 9 Tue, HW7, HW7 Solution Thu 11 Nov 16 Tue, HW8, HW8 Solution, Thu 12 Nov 23 Tue, HW9, HW9 Solution, Thu 13 Nov 30 Tue, On the final, Thu S Dec 7 Office Hours F Dec 14 Final on Dec 16 To Do List The Algebra Song! Register of Good Deeds Misplaced Material Add your name / see who's in!

• 

  Bright - 1

• 

  2

• 

  3

• 

  4

Replacement Theorem

...

3. dim(V) = n
   1. If G generates V then $|G| \ge n$. If also $\,\! |G| = n$ then G is a basis.
   2. If L is linearly dependent then $|L| \le n$. If also $\,\! |L| = n$ then L is a basis. If also $\,\! |L| < n$ 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 $|G| \ge n$.
      a2. Let $\beta$ be a basis of V, then $\,\! |B| = n$. Now use replacement with G & L = $\beta$. Hence, $|G| \ge |L| = |B| = n$.
      a. From a1 and a2, we know $|G| \ge n$. If $\,\! |G| = n$ then G contains a basis $\beta$. But $\,\! |B| = n$, so $\,\! |G| = \beta$, and hence G is a basis.
      
      b. Use replacement with G' being some basis of V. |G| = n.
      
      If $|L| = |G|$ then $|R| = n = |G|$, so $R = G$, so $(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 $|L| < |G|$ the nagain find $R \subset G$ such that $|R| = |L|$ and $(G \backslash R) \cup L$ generates.
      
      1. $\beta$ generates V.
      2. $|B| \le |G| - |R| + |L| = n$. So by part a, $\beta$ is a basis.
      3.
4. If V is finite-dimensional (f.d.) and $\mathbf W \subset \mathbf V$ is a subspace of V, then W is also finite, and $\operatorname{dim}(\mathbf W) \le \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 $\beta$ of W; $\beta$ is linearly independent in V so by Corollary 3 of part b, $|B| \le \operatorname{dim}(\mathbf V) \Rightarrow \operatorname{dim}(\mathbf W) = |B| \le \operatorname{dim}(\mathbf V)$. So span($\beta$) = V = W so V = W. ...
   
   Assume W is not finite-dimensional. $\mathbf W \ne \{0\}$ so pick a $x_1 \in W$ such that $x_1 \ne 0$. So $\{x_1\}$ is linearly independent in W, and $\operatorname{span}(\{x_1\}) \subsetneq \mathbf W$. Pick $x_2 \in W \backslash \operatorname{span}(\{x_1\})$. So $\{x_1, x_2\}$ is linearly dependent and $\operatorname{span}(\{x_1, x_2\}) \subsetneq \mathbf W$. Pick $x_3 \in W \backslash \operatorname{span}(\{x_1, x_2\})$ ... continue in this way to get a sequence $x_1, x_2, \ldots, x_{n+1}$ where n = dim(V) and $\{x_1, \ldots, x_{n+1}\}$ is linearly independent. There is a contradiction by Corollary 3.b.

The Lagrange Interpolation Formula

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

Where $1 \le i < n,$

Let $x_i$ be distinct points in $\real$.

Let $y_i$ be any points in $\real$.

Can you find a polynomial $P \in \mathbb P_n(\real)$ such that $P(x_i) = y_i$? Is it unique?

Example:

$x_i = 0, 1, 3$

$y_i = 5, 2, 2$

Can we find a $P \in \mathbb P_2$ such that

$P(0) = 5$

$P(1) = 2$

$P(2) = 2$?

Solution: Let $\tilde P_i(x) = \prod_{j=1, j \ne 1}^{n+1} (x - x_j) \in \mathbb P_n(\real)$. (Remember capital pi notation.)

Then $\tilde P_i(x_k) = \begin{cases} 0 & i \ne k \\ \prod_{i \ne j} (x_i - x_j) & i = k \\ \end{cases}$

$\tilde P_1 = (x - x_2)(x - x_3) = (x - 1)(x - 3) = x^2 - 4x + 3$

$\tilde P_2 = (x - 0)(x - 3) = x^2 - 3x$

$\tilde P_3 = (x - 0)(x - 1) = x^2 - x$

$\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 $P_i(x) = \frac1{\tilde P_i(x)} \cdot \tilde P_i = \prod_{j \ne i} \frac{(x - x_j)}{(x_i - x_j)}$

Then $P_i(x_k) = \begin{cases} 0 & i \ne k \\ 1 & i = k \\ \end{cases}$

$P_1(x) = \frac13 x^2 - \frac43 x + 1$

$P_2(x) = -\frac12 x^2 + \frac32 x$

$P_3(x) = \frac16 x^2 - \frac16 x$

Let $P = \sum_{i=1}^{n+1} y_i P_i(x) \in \mathbb P_n(\real)$

$P = 5 \cdot \left( \frac13 x^2 - \frac43 x + 1 \right) + 2 \cdot \left( -\frac12 x^2 + \frac32 x \right) + 2 \cdot \left( \frac16 x^2 - \frac16 x \right)$

$\,\! = x^2 - 4x + 5$