Linear Independence Theorem for Vectors 2

Given a finitely generated vector space V, if we consider a set of generators $$ \{ \vec{v}_1, \vec{v}_2, ...,\vec{v}_n \} $$ and a set of linearly independent vectors belonging to V $$ \{ \vec{w}_1, \vec{w}_2, ..., \vec{w}_p \} $$, then $$ p \le n $$.

Essentially, the number of linearly independent vectors in V is always less than or equal to the number of vectors in a set of generators for V.

The Proof

For a real vector space V, let's consider a set of generators for V

$$ \{ \vec{v}_1, \vec{v}_2, ...,\vec{v}_n \} $$

and a set of linearly independent vectors belonging to V

$$ \{ \vec{w}_1, \vec{w}_2, ..., \vec{w}_p \} $$

Any vector w ∈ V can be generated by the linear combination of the generators {v₁,v₂,...,v_n}

$$ \vec{w}_1 = \lambda_1 \vec{v}_1 + \lambda_2 \vec{v}_2 + ... + \lambda_n \vec{v}_n $$

By assumption, w₁ is linearly independent.

Therefore, at least one of the coefficients λ must be nonzero. Otherwise, it would be linearly dependent.

We consider the last coefficient λ_n≠0.

$$ \lambda_n \ne 0 $$

Since λ_n≠0 is nonzero, we divide both sides of the equation by λ_n

$$ \vec{w}_1 = \lambda_1 \vec{v}_1 + \lambda_2 \vec{v}_2 + ... + \lambda_{n-1} \vec{v}_{n-1} + \lambda_n \vec{v}_n $$

$$ \frac{1}{ \lambda_n} \vec{w}_1 = \frac{\lambda_1}{ \lambda_n} \vec{v}_1 + \frac{\lambda_2}{ \lambda_n} \vec{v}_2 + ... + \frac{\lambda_{n-1}}{\lambda_n} \vec{v}_{n-1} + \frac{\lambda_n}{ \lambda_n} \vec{v}_n $$

$$ \frac{1}{ \lambda_n} \vec{w}_1 = \frac{\lambda_1}{ \lambda_n} \vec{v}_1 + \frac{\lambda_2}{ \lambda_n} \vec{v}_2 + ... + \frac{\lambda_{n-1}}{\lambda_n} \vec{v}_{n-1} + \vec{v}_n $$

Next, we derive the vector v_n

$$ \vec{v}_n = \frac{1}{ \lambda_n} \vec{w}_1 - \frac{\lambda_1}{ \lambda_n} \vec{v}_1 - \frac{\lambda_2}{ \lambda_n} \vec{v}_2 - ... - \frac{\lambda_{n-1}}{\lambda_n} \vec{v}_{n-1} $$

We then replace the coefficients with another variable 1/λ_n=α₁, λ₁/λ_n=α₂, λ₂/λ_n=α₃,..., λ_n-1/λ_n=α_n,

$$ \vec{v}_n = \alpha_1 \vec{w}_1 - \alpha_2 \vec{v}_1 - \alpha_3 \vec{v}_2 - ... - \alpha_n \vec{v}_{n-1} $$

Thus, the set of vectors {w₁,v₁,v₂,...,v_n-1} is still a set of generators with the same number of vectors as before because if we replace v_n= α₁ w₁ + α₂ v₁ + α₃ v₂ +...+ α_nv_n-1 in the linear combination of a generic vector v of the vector space V, we get another set of generators for V.

$$ \vec{v} = \lambda_1 \vec{v}_1 + \lambda_2 \vec{v}_2 + ... + \lambda_n \vec{v}_n $$

Knowing that v_n= α₁ w₁ + α₂ v₁ + α₃ v₂ +...+ α_nv_n-1

$$ \vec{v} = \lambda_1 \vec{v}_1 + \lambda_2 \vec{v}_2 + ... + \lambda_n ( \alpha_1 \vec{w}_1 - \alpha_2 \vec{v}_1 - \alpha_3 \vec{v}_2 - ... - \alpha_n \vec{v}_{n-1} ) $$

$$ \vec{v} = \lambda_1 \vec{v}_1 + \lambda_2 \vec{v}_2 + ... + \lambda_n \alpha_1 \vec{w}_1 - \lambda_n \alpha_2 \vec{v}_1 - \lambda_n \alpha_3 \vec{v}_2 - ... - \lambda_n \alpha_n \vec{v}_{n-1} $$

$$ \vec{v} = ( \lambda_1 - \lambda_n \alpha_2 ) \vec{v}_1 + ( \lambda_2 - \lambda_n \alpha_3 ) \vec{v}_2 + ... + (\lambda_{n-1} - \lambda_n \alpha_n ) \vec{v}_{n-1} + ( \lambda_n \alpha_1) \vec{w}_1 $$

We then replace the coefficients with another variable λ₁-λ_nα₂=β₁, and so on.

$$ \vec{v} = \beta_1 \vec{v}_1 + \beta_2 \vec{v}_2 + ... + \beta_{n-1} \vec{v}_{n-1} + \beta_n \vec{w}_1 $$

Thus, the vector v is a combination of n vectors {w₁,v₁,v₂,...,v_n-1}

Next, we repeat the same process, hypothesizing that β_n-1≠0 and replacing v_n-1 with w₂

We continue by replacing v_n-2 with w₃, and so on... until we replace v₁ with w_n

Ultimately, once all the generator vectors are replaced, we obtain a set of generators {w₁,w₂,...,w_n}

$$ \vec{v} = \lambda_1 \vec{w}_1 + \lambda_2 \vec{w}_2 + ... + \lambda_{n-1} \lambda{w}_{n-1} + \lambda_n \vec{w}_n $$

Given that the initially hypothesized linearly independent vectors were p vectors

$$ \{ \vec{w}_1, \vec{w}_2, ...,\vec{w}_p \} $$

If p>n, there would be vectors w_n+1, w_n+2, ... , w_p that are not included in the set of generators {w₁,w₂,...,w_n}

$$ \{ \vec{w}_1, \vec{w}_2 , ... , \vec{w}_n, \color{red}{ \vec{w}_{n+1} }, \color{red}{ \vec{w}_{n+2} }, ..., \color{red}{ \vec{w}_{p} } \} $$

Hence, I could generate the vector w_n+1 using a linear combination of the generator vectors {w₁,w₂,...,w_n}

$$ \vec{w}_{n+1} = \lambda_1 \vec{w}_1 + \lambda_2 \vec{w}_2 + ... + \lambda_{n-1} \lambda{w}_{n-1} + \lambda_n \vec{w}_n $$

The vector w_n+1 is linearly dependent on {w₁,w₂,...,w_n}

However, this contradicts the initial assumption which states that the vectors {w₁,w₂,...,w_p} are linearly independent.

If p>n is not true, then the opposite must be true, i.e., p≤n.

In conclusion, if the vector space V has p linearly independent vectors, then the number n of vectors in any generator of V must be equal to or greater than p.

$$ n \le p $$

And so on.