Linear Independent Vectors

Definition 1: Vectors X₁, …, X_k of the same size and shape are independent if for any scalar values b₁, … b_k, if b₁ X₁ +⋯+ b_k X_k = 0, then b₁ = … = b_k  = 0.

Vectors X₁, …, X_k are dependent if they are not independent, i.e. there are scalars b₁, … b_k, at least one of which is non-zero, such that b₁ X₁ +⋯+ b_k X_k = 0.

Observation: If X₁, …, X_k  are independent, then X_j ≠ 0 for all j.

Property 1: X₁, …, X_k are dependent if and only if at least one of the vectors can be expressed as a linear combination of the others.

Proof: Suppose X₁, …, X_k are dependent. Then there are scalars b₁, … b_k, at least one of which is non-zero such that b₁ X₁ +⋯+ b_k X_k = 0. Say b_i ≠ 0. Then

Now suppose that X_i = . Then b₁ X₁ +⋯+ b_k X_k = 0, where b_i = -1, and so X₁, …, X_k  are dependent.

Definition 2: The span of independent vectors X₁, …, X_k consists of all the vectors which are a linear combination of these vectors. If W is any set of vectors, then the vectors X₁, …, X_k are said to be a basis of W if they are independent and their span equals W. We call a set of vectors W closed if W is the span of some set of vectors. Since we will only consider finite sets of vectors, henceforth we will assume that any closet set is finite.

Property 2: If X₁, …, X_k is a basis of W, then every element in W has a unique representation as a linear combination of X₁, …, X_k.

Proof: That one such representation exists follows from the definition of span. We now show uniqueness. Suppose there are two such representations, as follows:

 = 

Then  = 0. But since X₁, …, X_k are independent, b_j – c_j = 0 for all j, i.e. b_j = c_j for all j, and so the two representations are equal.

Property 3: If B is a set of independent vectors such that the span of B is a subset of a closed (finite) set of vectors W, then B can be expanded to be a (finite) basis for W.

Proof: Let W = {X₁, …, X_n}. We now build a finite set of vectors recursively as follows. Start with B₀ = B. For each k from 0 to n–1, define B_k+1 = B_k ∪ {X_k} if X_k is not already in the span of B_k and B_k+1 = B_k otherwise. Clearly, each B_k is an independent set of vectors and the span of B_n is W.

Corollary 1: Every closed set of vectors W has a (finite) basis.

Proof: The corollary is Property 3 with B = Ø.

Property 4: If Y₁,…,Y_n is a basis for W and X₁, …, X_m is a set of independent vectors in W, then m ≤ n.

Proof: We now show by induction that for each k, 1 ≤ k ≤ m, there are vectors Z1,…,Zk such that {Z1,…,Zk} ⊆ {Y1,…,Yn} and Z1, …, Zk, Xk+1, …, Xm are independent.

We now assume the assertion is true for all values less than k and show it is true for k, where k ≤ m, i.e. we need to prove that for at least one j, Z1,…,Zk-1, Yj, Xk+1,…, Xm are independent. If there is no such j then by Property 1, each Yj can be expressed as a linear combination of Z1,…,Zk-1, Xk+1,…, Xm. But since Xk is in W and Y1,…,Yn, is a basis for W, we can express Xk as a linear combination of the Y1,…,Yn and therefore as a linear combination of Z1, …, Zk-1, Xk+1,…, Xm. Thus by Property 1, Z1,…,Zk-1, Xk, Xk+1,…, Xm are not independent, a violation of the induction hypothesis.

Thus, there is some j for which Z1,…,Zk-1, Yj, Xk+1,…, Xm are independent. We set Zk equal to any such Yj, which yields the desired result, namely that Z1, …, Zk, Xk+1,…, Xm are independent.

Where k = m, we conclude that {Z1, …, Zm} ⊆ {Y1, …, Yn} and that Z1, …, Zm are independent. Since Z1, …, Zm are independent, they are all distinct, but since {Z1, …, Zm} ⊆ {Y1, …, Yn}, it follows that m ≤ n.

Corollary 2: Any two bases for a finite set of vectors have the same number of elements.

Proof: Suppose X1, …, Xm  and Y1, …, Yn are bases for W. By Property 4, m ≤ n and also n ≤ m, and so m = n.

Corollary 3: Let Y1, …, Ym be a basis for W and let X1, …, Xm be a set of independent vectors in W. Then X1, …, Xm is also basis for W.

Proof: Suppose X1, …, Xm is not a basis for W. By Property 3, it can be expanded to become a basis for W. This basis has n elements for some n > m, but this contradicts Property 4 since Y1, …, Ym is a basis for W. Thus X1, …, Xm must also be a basis for W.

Corollary 4: Any set of n linearly independent n × 1 column vectors is a basis for the set of n × 1 column vectors. Similarly, any set of n linearly independent 1 × n row vectors is a basis for the set of 1 × n row vectors.

Proof: Let C_j be the jth column of the identity matrix I_n. It is easy to see that for any n, C₁, …, C_n forms a basis for the set of all n × 1 column vectors. The result for column vectors now follows by Corollary 3. The proof for row vectors is similar.

Definition 3: The dimension of a closed set of vectors W is the size of any basis of W.

Observation: This definition makes sense since, as we have seen from the above, any closed set of vectors has a basis, and any two bases have the same number of elements. Further, note that any element in W can be expressed uniquely as a linear combination of the elements in any basis.