The next theorem is called the exchange theorem. It is very important that you understand this
theorem. It is so important that I have given several proofs of it. Some amount to the same thing,
just worded differently.
Theorem 7.2.4Let
{x1,⋅⋅⋅,xr}
be a linearly independent set of vectors such that eachx_{i}is in the span
{y1,⋅⋅⋅,ys}
. Then r ≤ s.
Proof 1:Define span
{y1,⋅⋅⋅,ys}
≡ V, it follows there exist scalars c_{1},
⋅⋅⋅
,c_{s} such
that
s
x1 = ∑ ciyi. (7.5)
i=1
(7.5)
Not all of these scalars can equal zero because if this were the case, it would follow
that x_{1} = 0 and so
{x1,⋅⋅⋅,xr}
would not be linearly independent. Indeed, if x_{1} = 0,
1x_{1} + ∑_{i=2}^{r}0x_{i} = x_{1} = 0 and so there would exist a nontrivial linear combination of the vectors
( s- 1 vectors here )
y ∈ span (x ,◜y-,⋅⋅⋅,y-◞◟,y---,⋅⋅⋅,y◝) .
k 1 1 k−1 k+1 s
Define
{z1,⋅⋅⋅,zs−1}
by
{z1,⋅⋅⋅,zs− 1} ≡ {y1,⋅⋅⋅,yk−1,yk+1,⋅⋅⋅,ys}
Therefore, span
{x1,z1,⋅⋅⋅,zs−1}
= V because if v ∈ V, there exist constants c_{1},
⋅⋅⋅
,c_{s} such
that
s∑−1
v = cizi + csyk.
i=1
Now replace the y_{k} in the above with a linear combination of the vectors,
{x1,z1,⋅⋅⋅,zs−1}
to
obtain v ∈span
{x1,z1,⋅⋅⋅,zs−1}
. The vector y_{k}, in the list
{y1,⋅⋅⋅,ys}
, has now been replaced
with the vector x_{1} and the resulting modified list of vectors has the same span as the original list
of vectors,
{y1,⋅⋅⋅,ys}
.
Now suppose that r > s and that span
{x1,⋅⋅⋅,xl,z1,⋅⋅⋅,zp}
= V where the vectors,
z_{1},
⋅⋅⋅
,z_{p} are each taken from the set,
{y1,⋅⋅⋅,ys}
and l + p = s. This has now been done for
l = 1 above. Then since r > s, it follows that l ≤ s < r and so l + 1 ≤ r. Therefore, x_{l+1} is a vector
not in the list,
{x1,⋅⋅⋅,xl}
and since span
{x1,⋅⋅⋅,xl,z1,⋅⋅⋅,zp}
= V there exist scalars c_{i} and
d_{j} such that
∑l ∑p
xl+1 = cixi + djzj. (7.6)
i=1 j=1
(7.6)
Now not all the d_{j} can equal zero because if this were so, it would follow that
{x1,⋅⋅⋅,xr}
would
be a linearly dependent set because one of the vectors would equal a linear combination of the
others. Therefore, (7.6) can be solved for one of the z_{i}, say z_{k}, in terms of x_{l+1} and the other z_{i}
and just as in the above argument, replace that z_{i} with x_{l+1} to obtain
( )
----p- 1 vectors here-
span (x1,⋅⋅⋅xl,xl+1,◜z1,⋅⋅⋅zk−1◞,◟zk+1,⋅⋅⋅,z◝p) = V.
Continue this way, eventually obtaining
span (x1,⋅⋅⋅,xs) = V.
But then x_{r}∈span
{x1,⋅⋅⋅,xs}
contrary to the assumption that
{x1,⋅⋅⋅,xr}
is linearly
independent. Therefore, r ≤ s as claimed.
Proof 2: Let
∑s
xk = ajkyj
j=1
If r > s, then the matrix A =
(ajk)
has more columns than rows. By Corollary 4.3.9 one of these
columns is a linear combination of the others. This implies there exist scalars c_{1},
Definition 7.2.6A vector space V is of dimension n if ithas a basis consisting of nvectors. This is well defined thanks to Corollary 7.2.5. It is always assumed here that n < ∞and in this case, such a vector space is said to be finite dimensional.
Example 7.2.7Consider the polynomials defined on ℝ of degree no more than 3, denotedhere as P_{3}. Then show that a basis for P_{3}is
{1,x,x2,x3}
. Here x^{k}symbolizes the functionx
↦→
x^{k}.
It is obvious that the span of the given vectors yields P_{3}. Why is this set of vectors linearly
independent? Suppose
2 3
c0 + c1x + c2x + c3x = 0
where 0 is the zero function which maps everything to 0. Then you could differentiate three times
and obtain the following equations
c1 + 2c2x+ 3c3x2 = 0
2c + 6c x = 0
2 3
6c3 = 0
Now this implies c_{3} = 0. Then from the equations above the bottom one, you find in succession
that c_{2} = 0,c_{1} = 0,c_{0} = 0.
There is a somewhat interesting theorem about linear independence of smooth functions (those
having plenty of derivatives) which I will show now. It is often used in differential
equations.
Definition 7.2.8Let f_{1},
⋅⋅⋅
,f_{n}be smooth functions defined on an interval
[a,b]
. TheWronskian of these functions is defined as follows.
Note that to get from one row to the next, you just differentiate everything in that row. Thenotation f^{}
(k)
(x)
denotes the k^{th}derivative.
With this definition, the following is the theorem. The interesting theorem involving the
Wronskian has to do with the situation where the functions are solutions of a differential
equation. Then much more can be said and it is much more interesting than the following
theorem.
Theorem 7.2.9Let
{f1,⋅⋅⋅,fn}
be smooth functions defined on
[a,b]
. Then they arelinearly independent if there exists some point t ∈
[a,b]
where W
(f1,⋅⋅⋅,fn)
(t)
≠0.
Proof: Form the linear combination of these vectors (functions) and suppose it equals 0.
Thus
a1f1 + a2f2 + ⋅⋅⋅+ anfn = 0
The question you must answer is whether this requires each a_{j} to equal zero. If they all must equal
0, then this means these vectors (functions) are independent. This is what it means to be linearly
independent.
Differentiate the above equation n − 1 times yielding the equations
Since the determinant of the matrix on the left is assumed to be nonzero, it follows this matrix has
an inverse and so the only solution to the above system of equations is to have each a_{k} = 0.■
Here is a useful lemma.
Lemma 7.2.10Suppose v
∕∈
span
(u1,⋅⋅⋅,uk )
and
{u1,⋅⋅⋅,uk }
is linearly independent.Then
{u1,⋅⋅⋅,uk,v}
is also linearly independent.
Proof:Suppose ∑_{i=1}^{k}c_{i}u_{i} + dv = 0. It is required to verify that each c_{i} = 0 and
that d = 0. But if d≠0, then you can solve for v as a linear combination of the vectors,
{u1,⋅⋅⋅,uk}
,
∑k (ci)
v = − d- ui
i=1
contrary to assumption. Therefore, d = 0. But then ∑_{i=1}^{k}c_{i}u_{i} = 0 and the linear independence of
{u1,⋅⋅⋅,uk}
implies each c_{i} = 0 also. ■
Given a spanning set, you can delete vectors till you end up with a basis. Given a linearly
independent set, you can add vectors till you get a basis. This is what the following theorem is
about, weeding and planting.
Theorem 7.2.11If V = span
(u1,⋅⋅⋅,un)
then some subset of {u_{1},
⋅⋅⋅
,u_{n}} is a basisfor V. Also, if {u_{1},
⋅⋅⋅
,u_{k}} ⊆ V is linearly independent and the vector space is finitedimensional, then the set, {u_{1},
⋅⋅⋅
,u_{k}}, can be enlarged to obtain a basis of V.
Proof:Let
S = {E ⊆ {u1,⋅⋅⋅,un} such that span (E) = V }.
For E ∈ S, let
|E |
denote the number of elements of E. Let
m ≡ min {|E | such that E ∈ S }.
Thus there exist vectors
{v1,⋅⋅⋅,vm } ⊆ {u1,⋅⋅⋅,un }
such that
span (v1,⋅⋅⋅,vm) = V
and m is as small as possible for this to happen. If this set is linearly independent, it follows it is a
basis for V and the theorem is proved. On the other hand, if the set is not linearly independent,
then there exist scalars
c1,⋅⋅⋅,cm
such that
∑m
0 = civi
i=1
and not all the c_{i} are equal to zero. Suppose c_{k}≠0. Then the vector, v_{k} may be solved for in terms
of the other vectors. Consequently,
V = span (v1,⋅⋅⋅,vk−1,vk+1,⋅⋅⋅,vm )
contradicting the definition of m. This proves the first part of the theorem.