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 (x1, ..., xt) be a family of vectors in a vector space V. The family (x1, ..., xt) is called linearly dependent if and only if there are scalars αi, not all zero, such that α1x1 + ... + αtxt = 0.
If (x1, ..., xt) is not linearly dependent, we call (x1, ..., xt) 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 (x1, ..., xn) be a family of vectors. We call (x1, ..., xn) a basis for V if and only if:
(1) (x1, ..., xn) is linearly independent
(2) (x1, ..., xn) spans V.
Lemma 1:
Let V be a vector space and let (x1, ..., xn) be a family of vectors in V. Then (x1, ..., xn) 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) αixi.
Proof:
(1) Assume that (x1, ..., xn) 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) αixi.
(4) Assume that there exists scalars β1, ..., βn such that y = ∑(i=1,n) βixi.
(5) Then:
0 = ∑ (i=1,n) αixi - ∑ (i=1,n) βixi = ∑ (i=1,n) (αi - βi)xi
(6) Since (x1, ..., xn) is a basis, (x1, ..., xn) 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) αixi.
(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 (x1, ..., xn) spans V.
(12) Now, it follows that 0 = 0x1 + ... + 0xn and further that 0 ∈ V since V is a vector space (See Definition 2, here for more details on vector spaces)
(13) Assume that (x1, ..., xn) is not linearly independent.
(14) Since (x1, ..., xn) is not linear independent, then there exists α1, ..., αn such that 0 = α1x1 + ... + αnxn 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 (x1, ..., xn) is linearly independent.
(17) Thus (x1, ..., xn) 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 = (x1, ..., xt) and Y = (x1, ..., xt, y1, ..., yu) 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) αixi. [From Definition 1 above]
(3) Then, 0 = ∑(i=1,t) αixi + ∑(i=1,u) 0*yi.
(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) αixi. [From Definition 1 above]
(8) Then, 0 = ∑(i=1,t) αixi + ∑(i=1,u) 0*yi.
(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 = (z1, ..., zn) be linearly independent. Then each zi is nonzero.
Proof:
(1) Assume that Z = (z1, ..., zn) is linearly independent.
(2) Assume that there exists zi such that zi = 0.
(3) Then for all α, αzi = 0.
(4) Let X = (zi)
(5) Let Y = (z1, ..., zn)
(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 zi ≠ 0.
QED
Lemma 3:
Let V be a vector space, let (x1, ..., xt) be a family of vectors in V and suppose x1 ≠ 0.
Then (x1, ..., xt) is linearly dependent if and only if for each integer j, 2 ≤j ≤ t, xj is in [[x1, .., xj-1 ]].
Proof:
(1) Assume xj is a linear combination of (x1, ..., xj-1).
(2) Then, there exists a set βi such that: xj = β1x1 + ... + βj-1xj-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 = α1x1 + ... + αtxt
where αj ≠ 0.
(5) So that, (x1, ..., xt) is linear dependent [see Definition 1 above]
(6) Assume that (x1, ..., xt) is linear dependent
(7) So, that there exists αi ≠ 0 such that:
0 = ∑ (i=1,t) αixi
(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:
α1x1 + ... + αjxj = 0
(11) We know that j ≥ 2 since:
(a) Assume j = 1
(b) Since αj ≠ 0, we can conclude that x1 = 0. [from step #10 above]
(c) But this is impossible from the given since we assume that x1 ≠ 0.
(12) From j ≥ 2, we have:
α1x1 + ... + αjxj = 0
which means that:
α1x1 + ... + αjxj-1 = -αjxj
(13) We now put βi = -αj-1αi for i is less than j.
(14) We now obtain that:
β1x1 + ... + βj-1xj-1 =
([-αj]-1)[α1x1 + ... + αjxj-1] = ([-αj]-1)(-αjxj) =
xj
(15) Thus, we have shown that:
xj = β1x1 + ... + βj-1xj-1
QED
Corollary 3.1:
Let V be a vector space, let (x1, ..., xt) be a family of vectors in V and suppose x1 ≠ 0.
Then (x1, ..., xt) is linearly independent if and only if for each integer j, j =2, ..., s, xj is not in [[x1, .., xj-1 ]].
Proof:
(1) Assume (x1, ..., xt) is linearly independent
(2) Assume that there exists xj is in [[x1, .., xj-1 ]].
(3) But then (x1, ..., xt) 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, xj is not in [[x1, .., xj-1 ]].
(5) Assume for each integer j, j =2, ..., s, such that xj is not in [[x1, .., xj-1 ]].
(6) Assume that (x1, ..., xt) is linearly dependent
(7) But then by Lemma 3 above there exists xj is in [[x1, .., xj-1 ]].
(8) But this contradictions our assumption in step #5 so we reject our assumption in step #6 and conclude that (x1, ..., xt) is linearly independent.
QED
Lemma 4: The family (x1, ..., xt) is linearly dependent if and only if there is some index j such that xj is a linear combination of (x1, ..., xj-1, xj+1, ..., xt)
Proof:
(1) Assume the family (x1, ..., xt) is linearly dependent.
(2) Then, there exists there are scalars αi, not all zero, such that α1x1 + ... + αtxt = 0. [See Definition 1 above]
(3) Let αi be a scalar that is not 0.
(4) Then -αixi = α1x1 + ... + αi-1xi-1 + αi+1xi+1 + ... + αtxt.
(5) So that:
xi = (-1/αi)α1x1 + ... + (-1/αi)αi-1xi-1 + (-1/αi)αi+1xi+1 + ... + (-1/αi)αtxt
(6) Thus, we have shown that xi is a linear combination of (x1, ..., xi-1, xi+1, ..., xt). [See Definition 1, here]
(7) Assume that xj is a linear combination of (x1, ..., xj-1, xj+1, ..., xt)
(8) Then there exists αi such that:
xj = α1x1 + ... + αj-1xj-1 + αj+1xj+1 + ... + αtxt
(9) But then
0 = α1x1 + ... + αj-1xj-1 + αj+1xj+1 + ... + αtxt + (-1)xj
(10) This gives us that (x1, ..., xt) is linearly dependent. [See Definition 1 above]
QED
References:
- Hans Schneider, George Philip Barker, Matrices and Linear Algebra
, 1989.
