• Linear Algebra: #4 Linear Independence and Dimension

Definition
Let v₁, . . . , v_n ∈ V be finitely many vectors in the vector space V over the field F. We say that the vectors are linearly dependent if there exists an equation of the form

a₁· v₁ + · · · + a_n· v_n = 0, 

such that not all a_i ∈ F are simply zero. If no such non-trivial equation exists, then the set {v₁, . . . , v_n} ⊂ V is said to be linearly independent.

This definition is undoubtedly the most important idea that there is in the theory of linear algebra!

Examples 

• In ℜ² let v₁ = (1, 0), v₂ = (0, 1) and v₃ = (1, 1). Then the set {v₁, v₂, v₃} is linearly dependent, since we have
  
  
  v₁ + v₂ - v₁ = 0 
  
  On the other hand, the set {v₁, v₂} is linearly independent.


• In C₀([0, 1], ℜ), let f₁ : [0, 1] → ℜ be given by f₁(x) = 1 for all x ∈ [0, 1]. Similarly, let f₂ be given by f₂(x) = x, and f₃ is f₃(x) = 1 − x. Then the set {f₁, f₂, f₃} is linearly dependent. 

Now take some vector space V over a field F, and let S ⊂ V be some subset of V. (The set S can be finite or infinite here, although we will usually be dealing with finite sets.) Let v₁, . . . , v_n ⊂ S be some finite collection of vectors in S, and let a₁, . . . , a_n∈ F be some arbitrary collection of elements of the field. Then the sum

a₁· v₁ + · · · + a_n· v_n  

is a linear combination of the vectors v₁, . . . , v_n in S. The set of all possible linear combinations of vectors in S is denoted by span(S), and it is called the linear span of S. One also writes [S]. S is the generating set of [S]. Therefore if [S] = V, then we say that S is a generating set for V . If S is finite, and it generates V, then we say that the vector space V is finitely generated.


Theorem 5
Given S ⊂ V, then [S] is a subspace of V.

Proof
A simple consequence of theorem 2.

Examples

• For any n ∈ ℕ, let
  
  
  Then S = {e₁, e₂ ,. . . , e_n} is a generating set for ℜⁿ
  
• On the other hand, the vector space C₀([0, 1], ℜ) is clearly not finitely generated. (In general such function spaces — which play a big role in quantum field theory, and which are studied using the mathematical theory of functional analysis — are not finitely generated. However in this lecture, we will mostly be concerned with finitely generated vector spaces. )

So let S = {v₁, . . . , v_n} ⊂ V be a finite set. From now on in these discussions, we will assume that such sets are finite unless stated otherwise.


Theorem 6
Let w = a₁v₁ + · · · + a_nv_n be some vector in [S] ⊂ V, where a₁, . . . , a_n are arbitrarily given elements of the field F. We will say that this representation of w is unique if, given some other linear combination, w = b₁v₁ + · · · + b_nv_n , then we must have b_i = a_i for all i = 1, . . . , n. Given this, then we have that the set S is linearly independent ⇔ the representation of all vectors in the span of S as linear combinations of vectors in S is unique.

Proof.
‘⇐’ We certainly have 0v₁ + · · · + 0v_n= 0. Since this representation of the zero vector is unique, it follows S is linearly independent.

‘⇒’ Can it be that S is linearly independent, and yet there exists a vector in the span of S which is not uniquely represented as a linear combination of the vectors in S? Assume that there exist elements a₁, . . . , a_n and b₁, . . . , b_n of the field F, where a_j ≠ b_j , for at least one j between 1 and n, such that

shows that S cannot be a linearly independent set.


Definition
Assume that S ⊂ V is a finite, linearly independent subset with [S] = V. Then S is called a basis for V.


Lemma
Assume that S = {v₁, . . . , v_n} ⊂ V is linearly dependent. Then there exists some j ∈ {1, . . . , n}, and elements a_i ∈ F, for i ≠ j, such that

 

 Proof
Since S is linearly dependent, there exists some non-trivial linear combination of the elements of S, summing to the zero vector,

such that b_j ≠ 0, for at least one of the j. Take such a one. Then



Corollary
Let S = {v₁, . . . , v_n} ⊂ V be linearly dependent, and let v_j be as in the lemma above. Let S' = {v₁, . . . , v_j-1 ,v_j+1 , . . . ,v_n} be S, with the element v_j removed.



Theorem 7
Assume that the vector space V is finitely generated. Then there exists a basis for V.

Proof
Since V is finitely generated, there exists a finite generating set. Let S be such a finite generating set which has as few elements as possible. If S were linearly dependent, then we could remove some element, as in the lemma, leaving us with a still smaller generating set for V. This is a contradiction. Therefore S must be a basis for V.


Theorem 8
Let S = {v₁, . . . , v_n} be a basis for the vector space V, and take some arbitrary non-zero vector w ∈ V. Then there exists some j ∈ {1, . . . , n}, such that

S' = {v₁, . . . , v_j-1 , w, v_j+1 , . . . ,v_n}

is also a basis of V.

Proof
Writing w = a₁v₁ + · · · + a_nv_n, we see that since w ≠ 0, at least one  a_j ≠ 0. Taking that j, we write

We now prove that [S'] = V. For this, let u ∈ V be an arbitrary vector. Since S is a basis for V, there exists a linear combination u = b₁v₁ + · · · + b_nv_n. Then we have

This shows that [S'] = V.

In order to show that S' is linearly independent, assume that we have

for some c, and c_i ∈ F. Since the original set S was assumed to be linearly independent, we must have ca_i + c_i = 0, for all i. In particular, since c_j = 0, we have ca_j = 0. But the assumption was that a_j ≠ 0. Therefore we must conclude that c = 0. It follows that also c_i = 0. , for all i ≠ j. Therefore, S' must be linearly independent.


Theorem 9 (Steinitz Exchange Theorem)
Let S = {v₁, . . . , v_n} be a basis of V and let T = {w₁, . . . , w_m} ⊂ V be some linearly independent set of vectors in V. Then we have m ≤ n. By possibly re-ordering the elements of S, we may arrange things so that the set

U = {w₁, . . . , w_m , v_m+1 , . . . ,v_n} 

is a basis for V.

Proof
Use induction over the number m. If m = 0 then U = S and there is nothing to prove.

Therefore assume m ≥ 1 and furthermore, the theorem is true for the case m − 1. So consider the linearly independent set T' = {w₁, . . . , w_m-1}. After an appropriate re-ordering of S, we have U' = {w₁, . . . , w_m-1, v_m , . . . ,v_n} being a basis for V. Note that if we were to have n < m, then T' would itself be a basis for V. Thus we could express w_m as a linear combination of the vectors in T'. That would imply that T was not linearly independent, contradicting our assumption. Therefore, m ≤ n.

Now since U' is a basis for V, we can express w_mas a linear combination

w_m = a₁w₁ + · · · + a_m-1w_m-1 + a_mv_m + · · · + a_nv_n

If we had all the coefficients of the vectors from S being zero, namely
 

a_m = a_m+1 = · · · = a_n = 0,

then we would have w_m being expressed as a linear combination of the other vectors in T. Therefore T would be linearly dependent, which is not true. Thus one of the a_j ≠ 0, for j ≥ m. Using theorem 8, we may exchange w_m for the vector v_j in U', thus giving us the basis U.


Theorem 10 (Extension Theorem)
Assume that the vector space V is finitely generated and that we have a linearly independent subset S ⊂ V. Then there exists a basis B of V with S ⊂ B.

Proof
If [S] = V then we simply take B = S. Otherwise, start with some given basis A ⊂ V and apply theorem 9 successively.


Theorem 11
Let U be a subspace of the (finitely generated) vector space V. Then U is also finitely generated, and each possible basis for U has no more elements than any basis for V.

Proof
Assume there is a basis B of V containing n vectors. Then, according to theorem 9, there cannot exist more than n linearly independent vectors in U. Therefore U must be finitely generated, such that any basis for U has at most n elements.


Theorem 12
Assume the vector space V has a basis consisting of n elements. Then every basis of V also has precisely n elements.

Proof
This follows directly from theorem 11, since any basis generates V, which is a subspace of itself.


Definition
The number of vectors in a basis of the vector space V is called the dimension of V, written dim(V).

Definition
Let V be a vector space with subspaces X, Y ⊂ V. The subspace X + Y = [X ∪ Y ] is called the sum of X and Y. If X ∩ Y = {0}, then it is the direct sum, written X ⊕ Y.


Theorem 13 (A Dimension Formula)
Let V be a finite dimensional vector space with subspaces X, Y ⊂ V. Then we have

dim(X + Y) = dim(X) + dim(Y) − dim(X ∩ Y).

Corollary
dim(X ⊕ Y) = dim(X) + dim(Y).

Proof of Theorem 13
Let  S = {v₁, . . . , v_n} be a basis of X ∩ Y. According to theorem 10, there exist extensions  T = {x₁, . . . , x_m} and  U = {y₁, . . . , y_r}, such that S ∪ T is a basis for X and S ∪ U is a basis for Y. We will now show that, in fact, S ∪ T ∪ U is a basis for X + Y.

To begin with, it is clear that X+Y = [S ∪T ∪U]. Is the set S ∪T ∪U linearly independent? Let

Then we have y = −v − x. Thus y ∈ X. But clearly we also have, y ∈ Y. Therefore y ∈ X ∩ Y. Thus y can be expressed as a linear combination of vectors in S alone, and since S ∪ U is is a basis for Y , we must have c_k = 0 for k = 1, . . . , r. Similarly, looking at the vector x and applying the same argument, we conclude that all the b_j are zero. But then all the a_i must also be zero since the set S is linearly independent.

Putting this all together, we see that the dim(X) = n +m, dim(Y) = n +r and dim(X ∩ Y) = n. This gives the dimension formula.


Theorem 14
Let V be a finite dimensional vector space, and let X ⊂ V be a subspace. Then there exists another subspace Y ⊂ V, such that V = X ⊕ Y.

Proof
Take a basis S of X. If [S] = V then we are finished. Otherwise, use the extension theorem (theorem 10) to find a basis B of V, with S ⊂ B. Then Y = [B \ S] satisfies the condition of the theorem. (The notation B \ S denotes the set of elements of B which are not in S)