09-240/Classnotes for Tuesday October 13
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bright - 1
2
3
4
Replacement Theorem
...
-
dim(V) = n
- If G generates V then [math]\displaystyle{ |G| \ge n }[/math]. If also [math]\displaystyle{ \,\! |G| = n }[/math] then G is a basis.
- If L is linearly dependent then [math]\displaystyle{ |L| \le n }[/math]. If also [math]\displaystyle{ \,\! |L| = n }[/math] then L is a basis. If also [math]\displaystyle{ \,\! |L| \lt n }[/math] 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 [math]\displaystyle{ |G| \ge n }[/math].
a2. Let [math]\displaystyle{ \beta }[/math] be a basis of V, then [math]\displaystyle{ \,\! |B| = n }[/math]. Now use replacement with G & L = [math]\displaystyle{ \beta }[/math]. Hence, [math]\displaystyle{ |G| \ge |L| = |B| = n }[/math].
a. From a1 and a2, we know [math]\displaystyle{ |G| \ge n }[/math]. If [math]\displaystyle{ \,\! |G| = n }[/math] then G contains a basis [math]\displaystyle{ \beta }[/math]. But [math]\displaystyle{ \,\! |B| = n }[/math], so [math]\displaystyle{ \,\! |G| = \beta }[/math], and hence G is a basis.
b. Use replacement with G' being some basis of V. |G| = n.
If [math]\displaystyle{ |L| = |G| }[/math] then [math]\displaystyle{ |R| = n = |G| }[/math], so [math]\displaystyle{ R = G }[/math], so [math]\displaystyle{ (G \backslash R) \cup L }[/math] generates, so L generates, so L is a basis since it is linearly independent.
We have that L is basis. If [math]\displaystyle{ |L| \lt |G| }[/math] the nagain find [math]\displaystyle{ R \subset G }[/math] such that [math]\displaystyle{ |R| = |L| }[/math] and [math]\displaystyle{ (G \backslash R) \cup L }[/math] generates.
1. [math]\displaystyle{ \beta }[/math] generates V.
2. [math]\displaystyle{ |B| \le |G| - |R| + |L| = n }[/math]. So by part a, [math]\displaystyle{ \beta }[/math] is a basis.
3.
-
If V is finite-dimensional (f.d.) and [math]\displaystyle{ \mathbf W \subset \mathbf V }[/math] is a subspace of V, then W is also finite, and [math]\displaystyle{ \operatorname{dim}(\mathbf W) \le \operatorname{dim}(\mathbf V) }[/math]. 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 [math]\displaystyle{ \beta }[/math] of W; [math]\displaystyle{ \beta }[/math] is linearly independent in V so by Corollary 3 of part b, [math]\displaystyle{ |B| \le \operatorname{dim}(\mathbf V) \Rightarrow \operatorname{dim}(\mathbf W) = |B| \le \operatorname{dim}(\mathbf V) }[/math]. So span([math]\displaystyle{ \beta }[/math]) = V = W so V = W. ...
Assume W is not finite-dimensional. [math]\displaystyle{ \mathbf W \ne \{0\} }[/math] so pick a [math]\displaystyle{ x_1 \in W }[/math] such that [math]\displaystyle{ x_1 \ne 0 }[/math]. So [math]\displaystyle{ \{x_1\} }[/math] is linearly independent in W, and [math]\displaystyle{ \operatorname{span}(\{x_1\}) \subsetneq \mathbf W }[/math]. Pick [math]\displaystyle{ x_2 \in W \backslash \operatorname{span}(\{x_1\}) }[/math]. So [math]\displaystyle{ \{x_1, x_2\} }[/math] is linearly dependent and [math]\displaystyle{ \operatorname{span}(\{x_1, x_2\}) \subsetneq \mathbf W }[/math]. Pick [math]\displaystyle{ x_3 \in W \backslash \operatorname{span}(\{x_1, x_2\}) }[/math] ... continue in this way to get a sequence [math]\displaystyle{ x_1, x_2, \ldots, x_{n+1} }[/math] where n = dim(V) and [math]\displaystyle{ \{x_1, \ldots, x_{n+1}\} }[/math] is linearly independent. There is a contradiction by Corollary 3.b.
The Lagrange Interpolation Formula
[Aside: [math]\displaystyle{ (a - x)(b - x) \ldots (z - x) = 0 }[/math] because [math]\displaystyle{ x - x = 0 }[/math]]
Where [math]\displaystyle{ 1 \le i \lt n, }[/math]
Let [math]\displaystyle{ x_i }[/math] be distinct points in [math]\displaystyle{ \real }[/math].
Let [math]\displaystyle{ y_i }[/math] be any points in [math]\displaystyle{ \real }[/math].
Can you find a polynomial [math]\displaystyle{ P \in \mathbb P_n(\real) }[/math] such that [math]\displaystyle{ P(x_i) = y_i }[/math]? Is it unique?
Example:
- [math]\displaystyle{ x_i = 0, 1, 3 }[/math]
- [math]\displaystyle{ y_i = 5, 2, 2 }[/math]
Can we find a [math]\displaystyle{ P \in \mathbb P_2 }[/math] such that
- [math]\displaystyle{ P(0) = 5 }[/math]
- [math]\displaystyle{ P(1) = 2 }[/math]
- [math]\displaystyle{ P(2) = 2 }[/math]?
Solution: Let [math]\displaystyle{ \tilde P_i(x) = \prod_{j=1, j \ne 1}^{n+1} (x - x_j) \in \mathbb P_n(\real) }[/math]. (Remember capital pi notation.)
Then [math]\displaystyle{ \tilde P_i(x_k) = \begin{cases} 0 & i \ne k \\ \prod_{i \ne j} (x_i - x_j) & i = k \\ \end{cases} }[/math]
- [math]\displaystyle{ \tilde P_1 = (x - x_2)(x - x_3) = (x - 1)(x - 3) = x^2 - 4x + 3 }[/math]
- [math]\displaystyle{ \tilde P_2 = (x - 0)(x - 3) = x^2 - 3x }[/math]
- [math]\displaystyle{ \tilde P_3 = (x - 0)(x - 1) = x^2 - x }[/math]
[math]\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} }[/math]
Set [math]\displaystyle{ P_i(x) = \frac1{\tilde P_i(x)} \cdot \tilde P_i = \prod_{j \ne i} \frac{(x - x_j)}{(x_i - x_j)} }[/math]
Then [math]\displaystyle{ P_i(x_k) = \begin{cases} 0 & i \ne k \\ 1 & i = k \\ \end{cases} }[/math]
- [math]\displaystyle{ P_1(x) = \frac13 x^2 - \frac43 x + 1 }[/math]
- [math]\displaystyle{ P_2(x) = -\frac12 x^2 + \frac32 x }[/math]
- [math]\displaystyle{ P_3(x) = \frac16 x^2 - \frac16 x }[/math]
Let [math]\displaystyle{ P = \sum_{i=1}^{n+1} y_i P_i(x) \in \mathbb P_n(\real) }[/math]
- [math]\displaystyle{ 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) }[/math]
- [math]\displaystyle{ \,\! = x^2 - 4x + 5 }[/math]
