be vectors in F^{p}. They are independentifand only if the only solution to the system of equations
( )
u1 ⋅⋅⋅ ur x = 0
isx = 0.In other words the vectors are independent means that whenever
r
∑ xiui = 0
i=1
it follows that each x_{i} = 0. The set of vectors is dependentif it is not independent.
Note that any list of vectors containing the zero vector is automatically linearly
dependent. Indeed, you could multiply this vector by 1 and all the others by 0. Then
adding these together, you would have a linear combination of the vectors in your list
which equals 0 although not all of the scalars used are 0. With this preparation, here is a
major theorem.
Theorem 18.10.2Suppose you have vectors
{u1,⋅⋅⋅,ur}
and that thisset of vectors is independent. Suppose also that there are vectors
{v1,⋅⋅⋅,vs}
andthat each u_{j}is a linear combination of the vectors
{v1,⋅⋅⋅,vs}
. Then r ≤ s. Alittle less precisely, spanning sets are at least as long as linearly independent sets.
Proof: Suppose to the contrary that r > s. The vector u_{1} is a linear combination of
vectors of
{v1,⋅⋅⋅,vs}
. Since
{u1,⋅⋅⋅,ur}
is linearly independent, not all of the scalars
in this linear combination are 0 since otherwise, you would have u_{1} would be
the zero vector. Solve for some v_{k} having a non zero coefficient in terms of u_{1}
and the other vectors in in the linear combination. Then replace v_{k} with the
linear combination involving u_{1} and the other vectors v_{i} for i≠k. Thus you
have
{u1,v1,⋅⋅⋅,vk−1,vk+1,⋅⋅⋅,vs} (18.29)
(18.29)
has the same span as the original vectors in the spanning set. Indeed, any linear
combination involving v_{k} can be changed into a linear combination of the above vectors
by replacing every occurrance of v_{k} with a suitable linear combination of the vectors of
18.29. Now let these vectors play the same role as the original vectors
{v ,⋅⋅⋅,v }
1 s
.
It is a spanning set. Thus u_{2} is a linear combination of the vectors of 18.29.
Say
∑
u2 = cu1 + xivi
i⁄=k
You can’t have each x_{i} = 0 because then u_{2}− cu_{1} = 0 which is impossible due to the
linear independence of these vectors. Thus you can replace another v_{l} with a linear
combination involving u_{1},u_{2}, and v_{j} for j≠k,l. Continue doing this till you have
replaced all of the v_{j} with u_{1},u_{2},
⋅⋅⋅
,u_{s} such that the span of these vectors is the
same as the span of
{v1,⋅⋅⋅,vs}
. Then this is a contradiction if s < r because
you would then have u_{r} in span
(u1,u2,⋅⋅⋅,us)
so the u_{i} vectors won’t be
independent. Since you can’t have s < r, it must be the case that s ≥ r as claimed.
■
There is a fundamental result in the case where m < n. In this case, the matrix A of
the linear transformation looks like the following.
PICT
Theorem 18.10.3Let A be an m × n matrix where m < n. Then N
(A)
contains nonzero vectors.
Proof:There is a spanning set for ℝ^{m}, namely
{e1,⋅⋅⋅,em}
. Therefore, any linearly
independent set in ℝ^{m} has no more than m vectors. However, there are n > m columns of
A so these columns can’t be independent. In other words, there is a nonzero vector x
such that Ax = 0. That is, N
(A)
≠
{0}
. ■
Now is the very important idea of a basis and dimension.
Definition 18.10.4Let V be a subspace of F^{n}. Then
{u1,⋅⋅⋅,ur}
iscalled a basisfor V if each u_{i}∈ V andspan
(u1,⋅⋅⋅,ur)
= V and
{u1,⋅⋅⋅,ur}
islinearly independent. In words,
{u1,⋅⋅⋅,ur}
spans and is independent.
Theorem 18.10.5Let
{u1,⋅⋅⋅,ur}
and
{v1,⋅⋅⋅,vs}
be bases for V .Then s = r.
Proof:From Theorem 18.10.2, r ≤ s since u_{i} is in the span of
{v1,⋅⋅⋅,vs}
and
{u1,⋅⋅⋅,ur}
is independent. Then also r ≥ s by the same reasoning. ■
Definition 18.10.6Let V be a subspace of F^{n}. Then the dimensionof Vis the number of vectors in a basis. This is well defined by Theorem 18.10.5.
Observation 18.10.7The dimension of F^{n}is n. This is obvious because ifx ∈ F^{n}, where x =
( )
x1 ⋅⋅⋅ xn
^{T}, thenx =∑_{i=1}^{n}x_{i}e_{i}which shows that
{e1,⋅⋅⋅,en}
is a spanning set. However, these vectors are clearly independentbecause if∑_{i}x_{i}e_{i} = 0,then0 =
( )
x1 ⋅⋅⋅ xn
^{T}and so each x_{i} = 0. Thus
{e1,⋅⋅⋅,en}
is also linearly independent.
The next lemma says that if you have a vector not in the span of a linearly
independent set, then you can add it in and the resulting longer list of vectors will still be
linearly independent.
Lemma 18.10.8Suppose v
∕∈
span
(u1,⋅⋅⋅,uk)
and
{u1,⋅⋅⋅,uk}
is linearlyindependent. 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. ■
It turns out that every nonzero subspace equals the span of linearly independent
vectors. This is the content of the next theorem.
Theorem 18.10.9V is a nonzero subspace of F^{n}if and only if it has abasis.
Proof: Pick a nonzero vector of V,u_{1}. If V = span
{u1}
, then stop. You have found
your basis. If V≠span
(u1)
, then there exists u_{2} a vector of V which is not
a vector in span
, stop. You have found a basis.
Otherwise, pick u_{3}
∈∕
span
(u1,u2)
. Continue this way until you obtain a basis.
The process must stop after fewer than n + 1 iterations because if it didn’t,
then there would be a linearly independent set of more than n vectors which is
impossible because there is a spanning set of n vectors from the above observation.
■
The following is a fundamental result. It includes the idea that you can enlarge a
linearly independent set of vectors to obtain a basis.
Theorem 18.10.10If V is a subspace of F^{n}and the dimension of V ism, then m ≤ n and also if
{u1,⋅⋅⋅,um }
is an independent set of vectors of V , thenthis set of vectors is a basis for V . Also, if you have a linearly independent set ofvectors of V,
{u1,⋅⋅⋅,uk }
for k ≤ m = dim
(V)
, there is a linearly independent setof vectors
{u1,⋅⋅⋅,uk,vk+1,⋅⋅⋅vm}
which is a basis for V .
Proof:If the dimension of V is m, then it has a basis of m vectors. It follows m ≤ n
because if not, you would have an independent set of vectors which is longer than a
spanning set of vectors
is an independent set of vectors of V , then if it fails to span V,
it must be there is a vector w which is not in this span. But then by Lemma 18.10.8, you
could add w to the list of vectors and get an independent set of m + 1 vectors. However,
the fact that V is of dimension m means there is a spanning set having only m vectors
and so this contradicts Lemma 18.10.8. Thus
{u1,⋅⋅⋅,um }
must be a spanning
set.
Finally, if k = m, the vectors
{u ,⋅⋅⋅,u }
1 k
must span V since if not, you could add
another vector which is not in this list to the list and get an independent set which is
longer than a spanning set contrary to Theorem 18.10.2. Thus assume k < m. The set of
vectors
{u ,⋅⋅⋅,u }
1 k
cannot span V because if it did, the dimension of V would be k
not m. Thus there is a vector v_{k+1} not in this span. Then by Lemma 18.10.8,
{u ,⋅⋅⋅,u ,v }
1 k k+1
is independent. If it spans V , stop. You have your basis.
Otherwise, there is a v_{k+2} not in the span and so you can add it in and get an
independent set
{u ,⋅⋅⋅,u ,v ,v }
1 k k+1 k+2
. Continue this process till it stops.
It must stop since otherwise, you would be able to get an independent set of
vectors larger than m which is the dimension of V, contrary to Theorem 18.10.2.
■
Definition 18.10.11The rankof a matrix A is the dimension ofIm
(A)
which is the same as the column space of A.
Theorem 18.10.12Let A be an n × n matrix. Then A^{−1}exists if andonly if the rank of A equals n.
Proof:If the rank of A is n, then if Ax = 0, it follows that x = 0. Also for any
y ∈ ℝ^{n}, there exists x such that Ax = y. This is because, by the above theory, the
columns of A are a basis for ℝ^{n}. The solution x such that Ax = y can be denoted as
T^{−1}
(y)
and T^{−1}
(y )
is well defined because if Ax = A
xˆ
, then A
(x− ˆx)
= 0 so x =
ˆx
as
just noted. Thus T^{−1} : ℝ^{n}→ ℝ^{n} is well defined function. It is also linear because for a,b
scalars,
( ) ( ) ( )
A aT−1 (y )+ bT −1(ˆy) = aA T−1 (y ) + bA T− 1(ˆy ) ≡ ay+ bˆy
and
A (T−1(ay + byˆ)) ≡ ay+ bˆy
Thus
aT −1(y)+ bT− 1(ˆy ) = T−1 (ay + bˆy)
which shows that T^{−1} is a linear transformation. Letting B be the matrix of this linear
transformation, it follows that for all y,
A (B (y)) = AB (y) ≡ A (T −1(y)) ≡ y
and so AB = I. On the other hand, T^{−1}
(Ax )
= x because A
( −1 )
T (Ax)
≡ Ax and so
T^{−1}
(Ax)
= x as claimed. Thus it is also the case that BA
(x)
= B
(A (x))
= T^{−1}
(Ax )
= x
showing that BA = I. It follows that A is invertible and its inverse is the matrix of the
linear transformation T^{−1} just defined.
Next, if A is invertible, the colums must be independent because if Ax = 0, Then
x = A^{−1}
(Ax )
= A^{−1}
(0)
= 0. ■
Note that this shows that right and left inverses are the same. Indeed, if A,B are
n × n and AB = I, then the columns of A are linearly independent because there
are n of them and the above equation shows that the span of these columns
equals all of ℝ^{n}. Thus they must be independent and so A is invertible. Then
AA^{−1} = AB and so, multiplying both sides on the left by A^{−1} yields A^{−1} = B.
If BA = I, then the columns of A are independent because if Ax = 0, then
x = BA
(x)
= B
(0)
= 0. Thus A is invertible and so BA = A^{−1}A and now
multiplying on the right and using the associative law again, you get B = A^{−1}.
Thus left inverses, right inverses and inverses are all the same for an n × n
matrix.