If you need to review vectors (see Definition 1 here), vector spaces (see Definition 2, here), linear combinations (see Definition 1, here), or family of vectors (see Definition 4, here), start here.

Definition 1: Linear Dependent and Linear Independent

Let V be a vector space and let (x

^{1}, ..., x

^{t}) be a family of vectors in a vector space V. The family (x

^{1}, ..., x

^{t}) is called linearly dependent if and only if there are scalars α

_{i}, not all zero, such that α

_{1}x

^{1}+ ... + α

_{t}x

^{t}= 0.

If (x

^{1}, ..., x

^{t}) is not linearly dependent, we call (x

^{1}, ..., x

^{t}) linearly independent.

We can now use this idea to establish the concept of the basis.

Definition 2: Basis

Let V be a vector space and let (x

^{1}, ..., x

^{n}) be a family of vectors. We call (x

^{1}, ..., x

^{n}) a basis for V if and only if:

(1) (x

^{1}, ..., x

^{n}) is linearly independent

(2) (x

^{1}, ..., x

^{n}) spans V.

Lemma 1:

Let V be a vector space and let (x

^{1}, ..., x

^{n}) be a family of vectors in V. Then (x

^{1}, ..., x

^{n}) is a basis for V if and only if for each y ∈ V there are unique scalars α

_{1}, ..., α

_{n}such that y = ∑ (i=1,n) α

_{i}x

^{i}.

Proof:

(1) Assume that (x

^{1}, ..., x

^{n}) is a basis for a vector space V.

(2) Assume that y ∈ V

(3) From definition 2 above, there exists scalars α

_{1}, ..., α

_{n}such that y = ∑(i=1,n) α

_{i}x

^{i}.

(4) Assume that there exists scalars β

_{1}, ..., β

_{n}such that y = ∑(i=1,n) β

_{i}x

^{i}.

(5) Then:

0 = ∑ (i=1,n) α

_{i}x

^{i}- ∑ (i=1,n) β

_{i}x

^{i}= ∑ (i=1,n) (α

_{i}- β

_{i})x

^{i}

(6) Since (x

^{1}, ..., x

^{n}) is a basis, (x

^{1}, ..., x

^{n}) is linearly independent. [See Definition 2 above]

(7) Therefore, in order for step #5 to be true, all values (α

_{i}- β

_{i}) must be 0 [See Definition 1 above]

Note: the definition of linear independence tells us that the only way a linear combination is 0 is if all the coefficients are 0. If there is a linear combination that results in 0 where 1 coefficient is not 0, then that family is linear dependent.

(8) So, we have for each i, α

_{i}- β

_{i}= 0 which gives us that α

_{i}= β

_{i}.

(9) This proves the first half of the lemma.

(10) Assume that for each y ∈ V, there are unique scalars α

_{1}, ..., α

_{n}such that y = ∑ (i=1,n) α

_{i}x

^{i}.

(11) Since by assumption each element of V has such a linear combination, we can see that the set of linear combination includes all the elements of V. We can thus say (x

^{1}, ..., x

^{n}) spans V.

(12) Now, it follows that 0 = 0x

^{1}+ ... + 0x

^{n}and further that 0 ∈ V since V is a vector space (See Definition 2, here for more details on vector spaces)

(13) Assume that (x

^{1}, ..., x

^{n}) is not linearly independent.

(14) Since (x

^{1}, ..., x

^{n}) is not linear independent, then there exists α

_{1}, ..., α

_{n}such that 0 = α

_{1}x

^{1}+ ... + α

_{n}x

^{n}where there exists some α

_{i}≠ 0.

(15) But this is a contradiction since in step #10, we assumed that each y ∈ V, there are unique scalars and yet 0 ∈ V (step #12) and we have listed two different scalars for 0 (step #12 and step #14).

(16) Therefore, we reject our assumption in step #13 and conclude that (x

^{1}, ..., x

^{n}) is linearly independent.

(17) Thus (x

^{1}, ..., x

^{n}) is a basis since it is linearly independent (step #13) and since it spans V (step #11). [See Definition 2 above]

QED

Lemma 2:

Let X = (x

^{1}, ..., x

^{t}) and Y = (x

^{1}, ..., x

^{t}, y

^{1}, ..., y

^{u}) be two families of vectors.

If X is linearly dependent, then so is Y. If Y is linearly independent, then so is X.

Proof:

(1) Assume X is linearly dependent.

(2) Then there exists α

_{1}, ..., α

_{t}such that 0 = ∑ (i=1,t) α

_{i}x

^{i}. [From Definition 1 above]

(3) Then, 0 = ∑(i=1,t) α

_{i}x

^{i}+ ∑(i=1,u) 0*y

^{i}.

(4) This gives us that Y is linearly depedent since there exists at least one α

_{i}≠ 0 since X is linearly dependent by assumption. [See Definition 1 above]

(5) Assume Y is linearly independent.

(6) Assume that X is linearly dependent.

(7) Then there exists α

_{1}, ..., α

_{t}such that 0 = ∑ (i=1,t) α

_{i}x

^{i}. [From Definition 1 above]

(8) Then, 0 = ∑(i=1,t) α

_{i}x

^{i}+ ∑(i=1,u) 0*y

^{i}.

(9) But this is impossible since it implies that Y is linearly dependent (see Definition 1 above) but we assumed that Y is linearly independent.

(10) So, we reject our assumption in step #6 and conclude that X is linearly independent.

QED

Corollary 2.1:

Let Z = (z

^{1}, ..., z

^{n}) be linearly independent. Then each z

^{i}is nonzero.

Proof:

(1) Assume that Z = (z

^{1}, ..., z

^{n}) is linearly independent.

(2) Assume that there exists z

^{i}such that z

^{i}= 0.

(3) Then for all α, αz

^{i}= 0.

(4) Let X = (z

^{i})

(5) Let Y = (z

^{1}, ..., z

^{n})

(6) It is clear that X is linearly dependent from step #2.

(7) From Lemma 2 above, we can conclude that Y is also linearly dependent.

(8) But this impossible since Z = Y and Z is linearly independent.

(9) So we need to reject our assumption in #2 and conclude that z

^{i}≠ 0.

QED

Lemma 3:

Let V be a vector space, let (x

^{1}, ..., x

^{t}) be a family of vectors in V and suppose x

^{1}≠ 0.

Then (x

^{1}, ..., x

^{t}) is linearly dependent if and only if for each integer j, 2 ≤j ≤ t, x

^{j}is in [[x

^{1}, .., x

^{j-1}]].

Proof:

(1) Assume x

^{j}is a linear combination of (x

^{1}, ..., x

^{j-1}).

(2) Then, there exists a set β

_{i}such that: x

^{j}= β

_{1}x

^{1}+ ... + β

_{j-1}x

^{j-1}. [See Definition 5, here for details if needed]

(3) Let us define the following coefficients:

if i is less than j, let α

_{i}= -β

_{i}

if i = j, then let α

_{i}= 1

if i is greater than j, then let α

_{i}= 0

(4) From step #3, it is clear that:

0 = α

_{1}x

^{1}+ ... + α

_{t}x

^{t}

where α

_{j}≠ 0.

(5) So that, (x

^{1}, ..., x

^{t}) is linear dependent [see Definition 1 above]

(6) Assume that (x

^{1}, ..., x

^{t}) is linear dependent

(7) So, that there exists α

_{i}≠ 0 such that:

0 = ∑ (i=1,t) α

_{i}x

^{i}

(8) Let j be the biggest integer for which α

_{i}≠ 0.

(9) So that if i is greater than j, α

_{i}= 0.

(10) Then, we know that:

α

_{1}x

^{1}+ ... + α

_{j}x

^{j}= 0

(11) We know that j ≥ 2 since:

(a) Assume j = 1

(b) Since α

_{j}≠ 0, we can conclude that x

^{1}= 0. [from step #10 above]

(c) But this is impossible from the given since we assume that x

^{1}≠ 0.

(12) From j ≥ 2, we have:

α

_{1}x

^{1}+ ... + α

_{j}x

^{j}= 0

which means that:

α

_{1}x

^{1}+ ... + α

_{j}x

^{j-1}= -α

_{j}x

^{j}

(13) We now put β

_{i}= -α

_{j}

^{-1}α

_{i}for i is less than j.

(14) We now obtain that:

β

_{1}x

^{1}+ ... + β

_{j-1}x

^{j-1}=

([-α

_{j}]

^{-1})[α

_{1}x

^{1}+ ... + α

_{j}x

^{j-1}] = ([-α

_{j}]

^{-1})(-α

_{j}x

^{j}) =

x

^{j}

(15) Thus, we have shown that:

x

^{j}= β

_{1}x

^{1}+ ... + β

_{j-1}x

^{j-1}

QED

Corollary 3.1:

Let V be a vector space, let (x

^{1}, ..., x

^{t}) be a family of vectors in V and suppose x

^{1}≠ 0.

Then (x

^{1}, ..., x

^{t}) is linearly independent if and only if for each integer j, j =2, ..., s, x

^{j}is not in [[x

^{1}, .., x

^{j-1}]].

Proof:

(1) Assume (x

^{1}, ..., x

^{t}) is linearly independent

(2) Assume that there exists x

^{j}is in [[x

^{1}, .., x

^{j-1}]].

(3) But then (x

^{1}, ..., x

^{t}) is linearly dependent by Lemma 3.

(4) This contradicts our assumption in step #1, so we reject our the assumption in step #2 and conclude that for each integer j, j =2, ..., s, x

^{j}is not in [[x

^{1}, .., x

^{j-1}]].

(5) Assume for each integer j, j =2, ..., s, such that x

^{j}is not in [[x

^{1}, .., x

^{j-1}]].

(6) Assume that (x

^{1}, ..., x

^{t}) is linearly dependent

(7) But then by Lemma 3 above there exists x

^{j}is in [[x

^{1}, .., x

^{j-1}]].

(8) But this contradictions our assumption in step #5 so we reject our assumption in step #6 and conclude that (x

^{1}, ..., x

^{t}) is linearly independent.

QED

Lemma 4: The family (x

^{1}, ..., x

^{t}) is linearly dependent if and only if there is some index j such that x

^{j}is a linear combination of (x

^{1}, ..., x

^{j-1}, x

^{j+1}, ..., x

^{t})

Proof:

(1) Assume the family (x

^{1}, ..., x

^{t}) is linearly dependent.

(2) Then, there exists there are scalars α

_{i}, not all zero, such that α

_{1}x

^{1}+ ... + α

_{t}x

^{t}= 0. [See Definition 1 above]

(3) Let α

_{i}be a scalar that is not 0.

(4) Then -α

_{i}x

^{i}= α

_{1}x

^{1}+ ... + α

_{i-1}x

^{i-1}+ α

_{i+1}x

^{i+1}+ ... + α

_{t}x

^{t}.

(5) So that:

x

^{i}= (-1/α

_{i})α

_{1}x

^{1}+ ... + (-1/α

_{i})α

_{i-1}x

^{i-1}+ (-1/α

_{i})α

_{i+1}x

^{i+1}+ ... + (-1/α

_{i})α

_{t}x

^{t}

(6) Thus, we have shown that x

^{i}is a linear combination of (x

^{1}, ..., x

^{i-1}, x

^{i+1}, ..., x

^{t}). [See Definition 1, here]

(7) Assume that x

^{j}is a linear combination of (x

^{1}, ..., x

^{j-1}, x

^{j+1}, ..., x

^{t})

(8) Then there exists α

_{i}such that:

x

^{j}= α

_{1}x

^{1}+ ... + α

_{j-1}x

^{j-1}+ α

_{j+1}x

^{j+1}+ ... + α

_{t}x

^{t}

(9) But then

0 = α

_{1}x

^{1}+ ... + α

_{j-1}x

^{j-1}+ α

_{j+1}x

^{j+1}+ ... + α

_{t}x

^{t}+ (-1)x

^{j}

(10) This gives us that (x

^{1}, ..., x

^{t}) is linearly dependent. [See Definition 1 above]

QED

References:

- Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.