Linear Combinations

Today's blog is taken straight from Matrices and Linear Algebra by Hans Schneider and George Philip Barker.

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

Definition 1: linear combination

Let (x¹, ..., x^t) be a family of vectors in a vector space V. We call u in V a linear combination of (x¹, ..., x^t) if and only if there exists scalars α₁, ..., α_t such that:

u = α₁x¹ + ... + α_tx^t = ∑ (i=1,t) α_ixⁱ.

Definition 2: [[ X ]]

Let X = (x¹, ..., xⁿ) is a family of vectors.

Then [[X]] is the set of all vectors that are a linear combination from X.

Note: This is not the standard notation but I am using it because of limitations with the blogging software that I use.

Definition 3: spanning a vector space

The set of linear combinations of a family of vectors [[X]] is said to span a vector space V if all vectors v that are elements of V are also elements of [[X]].

Lemma 1:

Let V be a vector space and let X = (x¹, ..., x^t) be a family of vectors in V. Let W be a subspace of V that contains each xⁱ.

Then, [[X]] ⊆ W.

Proof:

(1) Since W is a subspace, it closed under addition and scalar multiplication. [See Definition 2, here]

(2) So α₁x¹, ..., α_tx^t ∈ W by the closure of scalar multiplication.

(3) α₁x¹ + ... + α_tx^t ∈ W by the closure of addition.

(4) Thus, it is clear that every linear combination of (x¹, ..., x^t) is contained in W.

QED

Corollary 1.1:

Let V be a vector space and let X = (x¹, ..., x^t) and Y = (y¹, ..., y^u) be families of vectors in V.

If each xⁱ is a linear combination of (y¹, ..., y^u), then [[X]] ⊆ [[Y]]

Proof:

(1) Assume that for each i, xⁱ ∈ [[y¹, ..., y^u]].

(2) Then [[y¹, ..., y^u]] is a subspace of V. [See Theorem 2, here]

(3) Using Lemma 1 above, we can conclude that:

[[x¹, ..., x^t]] ⊆ [[y¹, ..., y^u]]

QED

Corollary 1.2:

Let X and Y be two families of vectors in V.

Then [[X]] ⊆ [[X,Y]]

Proof:

(1) Let X = (x¹, ..., x^t).

(2) Each xⁱ is a member of (X,Y)

(3) Hence, each xⁱ is a linear combination of (X,Y).

(4) Using Corollary 1.1 above, we can conclude that [[X]] ⊆ [[X,Y]]

QED

Definition 3: a_i,*

Let this designate a row such that: a_i,* = [ a_i,1 a_i,2 ... a_i,p ]

Now, I will use this notation in the following lemma.

Lemma 2:

If C = BA, then the ith row of C is a linear combination of the rows A with coefficients from the ith row of B.

Proof:

(1) Let B be an m x n matrix

(2) Let A be an n x p matrix

(3) Let C = BA so that:

C is an m x p matrix [see Definition 1, here for review of matrix multiplication]

such that:

c_i,j = ∑ (k=1,n) b_i,ka_k,j

(4) So,

c_i,* = [ c_i,1 c_i,2 ... c_i,p ] =

= [ ∑(k=1,n) b_i,ka_k,1 ∑(k=1,n) b_i,ka_k,2 ... ∑(k=1,n) b_i,ka_k,p ] =

= [ b_i,1a_1,1 b_i,1a_1,2 ... b_i,1a_1,p ] +
[ b_i,2a_2,1 b_i,2a_2,2 ... b_i,2a_2,p ] + ... +
[ b_i,na_n,1 b_i,na_n,2 ... b_i,na_n,p ] =

= b_i,1[ a_1,1 a_1,2 ... a_1,p] +
b_i,2[ a_2,1 a_2,2 ... a_2,p] + ... +
b_i,n[ a_n,1 a_n,2 ... a_n,p] =

= b_i,1(a_1,*) +
b_i,2( a_2,* ) + ... +
b_i,n( a_n,* )

= b_i,*A

QED

Lemma 3:

If C = AB, then the ith row of C is a linear combination of the columns A with coefficients from the jth row of B.

Proof:

(1) Let B be an m x n matrix

(2) Let A be an p x m matrix

(3) Let C = AB so that:

C is an p x n matrix [see Definition 1, here for review of matrix multiplication]

such that:

c_i,j = ∑ (k=1,m) a_i,kb_k,j

(4) So,

c_*,j = [ c_1,j c_2,j ... c_p,j ] =

= [ ∑(k=1,m) a_1,kb_k,j ∑(k=1,m) a_2,kb_k,j ... ∑(k=1,m) a_p,kb_k,j ] =

= [ a_1,1b_1,j a_2,1b_1,j ... a_p,1b_1,j ] +
[ a_1,2b_2,j a_2,2b_2,j ... a_p,2b_2,j ] + ... +
[ a_1,nb_n,j a_2,nb_n,j ... a_p,nb_n,j ] =

= b_1,j[ a_1,1 a_2,1 ... a_p,1] +
b_2,j[ a_1,2 a_2,2 ... a_p,2] + ... +
b_n,j[ a_1,n a_2,n ... a_p,n] =

= b_1,j(a_*,1) +
b_2,j( a_*,2 ) + ... +
b_n,j( a_*,n )

= b_*,jA

QED


References

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

Linear Independence

The content in today's blog is taken from Schneider and Barker's Matrices and Linear Algebra.

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¹, ..., x^t) be a family of vectors in a vector space V. The family (x¹, ..., x^t) is called linearly dependent if and only if there are scalars α_i, not all zero, such that α₁x¹ + ... + α_tx^t = 0.

If (x¹, ..., x^t) is not linearly dependent, we call (x¹, ..., 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¹, ..., xⁿ) be a family of vectors. We call (x¹, ..., xⁿ) a basis for V if and only if:
(1) (x¹, ..., xⁿ) is linearly independent
(2) (x¹, ..., xⁿ) spans V.

Lemma 1:

Let V be a vector space and let (x¹, ..., xⁿ) be a family of vectors in V. Then (x¹, ..., xⁿ) is a basis for V if and only if for each y ∈ V there are unique scalars α₁, ..., α_n such that y = ∑ (i=1,n) α_ixⁱ.

Proof:

(1) Assume that (x¹, ..., xⁿ) is a basis for a vector space V.

(2) Assume that y ∈ V

(3) From definition 2 above, there exists scalars α₁, ..., α_n such that y = ∑(i=1,n) α_ixⁱ.

(4) Assume that there exists scalars β₁, ..., β_n such that y = ∑(i=1,n) β_ixⁱ.

(5) Then:

0 = ∑ (i=1,n) α_ixⁱ - ∑ (i=1,n) β_ixⁱ = ∑ (i=1,n) (α_i - β_i)xⁱ

(6) Since (x¹, ..., xⁿ) is a basis, (x¹, ..., xⁿ) 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 α₁, ..., α_n such that y = ∑ (i=1,n) α_ixⁱ.

(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¹, ..., xⁿ) spans V.

(12) Now, it follows that 0 = 0x¹ + ... + 0xⁿ 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¹, ..., xⁿ) is not linearly independent.

(14) Since (x¹, ..., xⁿ) is not linear independent, then there exists α₁, ..., α_n such that 0 = α₁x¹ + ... + α_nxⁿ 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¹, ..., xⁿ) is linearly independent.

(17) Thus (x¹, ..., xⁿ) 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¹, ..., x^t) and Y = (x¹, ..., x^t, y¹, ..., 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 α₁, ..., α_t such that 0 = ∑ (i=1,t) α_ixⁱ. [From Definition 1 above]

(3) Then, 0 = ∑(i=1,t) α_ixⁱ + ∑(i=1,u) 0*yⁱ.

(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 α₁, ..., α_t such that 0 = ∑ (i=1,t) α_ixⁱ. [From Definition 1 above]

(8) Then, 0 = ∑(i=1,t) α_ixⁱ + ∑(i=1,u) 0*yⁱ.

(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¹, ..., zⁿ) be linearly independent. Then each zⁱ is nonzero.

Proof:

(1) Assume that Z = (z¹, ..., zⁿ) is linearly independent.

(2) Assume that there exists zⁱ such that zⁱ = 0.

(3) Then for all α, αzⁱ = 0.

(4) Let X = (zⁱ)

(5) Let Y = (z¹, ..., zⁿ)

(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ⁱ ≠ 0.

QED

Lemma 3:

Let V be a vector space, let (x¹, ..., x^t) be a family of vectors in V and suppose x¹ ≠ 0.

Then (x¹, ..., x^t) is linearly dependent if and only if for each integer j, 2 ≤j ≤ t, x^j is in [[x¹, .., x^j-1 ]].

Proof:

(1) Assume x^j is a linear combination of (x¹, ..., x^j-1).

(2) Then, there exists a set β_i such that: x^j = β₁x¹ + ... + β_j-1x^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 = α₁x¹ + ... + α_tx^t

where α_j ≠ 0.

(5) So that, (x¹, ..., x^t) is linear dependent [see Definition 1 above]

(6) Assume that (x¹, ..., x^t) is linear dependent

(7) So, that there exists α_i ≠ 0 such that:

0 = ∑ (i=1,t) α_ixⁱ

(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:

α₁x¹ + ... + α_jx^j = 0

(11) We know that j ≥ 2 since:

(a) Assume j = 1

(b) Since α_j ≠ 0, we can conclude that x¹ = 0. [from step #10 above]

(c) But this is impossible from the given since we assume that x¹ ≠ 0.

(12) From j ≥ 2, we have:

α₁x¹ + ... + α_jx^j = 0

which means that:

α₁x¹ + ... + α_jx^j-1 = -α_jx^j

(13) We now put β_i = -α_j^-1α_i for i is less than j.

(14) We now obtain that:

β₁x¹ + ... + β_j-1x^j-1 =
([-α_j]^-1)[α₁x¹ + ... + α_jx^j-1] = ([-α_j]^-1)(-α_jx^j) =
x^j

(15) Thus, we have shown that:

x^j = β₁x¹ + ... + β_j-1x^j-1

QED

Corollary 3.1:

Let V be a vector space, let (x¹, ..., x^t) be a family of vectors in V and suppose x¹ ≠ 0.

Then (x¹, ..., x^t) is linearly independent if and only if for each integer j, j =2, ..., s, x^j is not in [[x¹, .., x^j-1 ]].

Proof:

(1) Assume (x¹, ..., x^t) is linearly independent

(2) Assume that there exists x^j is in [[x¹, .., x^j-1 ]].

(3) But then (x¹, ..., 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¹, .., x^j-1 ]].

(5) Assume for each integer j, j =2, ..., s, such that x^j is not in [[x¹, .., x^j-1 ]].

(6) Assume that (x¹, ..., x^t) is linearly dependent

(7) But then by Lemma 3 above there exists x^j is in [[x¹, .., x^j-1 ]].

(8) But this contradictions our assumption in step #5 so we reject our assumption in step #6 and conclude that (x¹, ..., x^t) is linearly independent.

QED

Lemma 4: The family (x¹, ..., x^t) is linearly dependent if and only if there is some index j such that x^j is a linear combination of (x¹, ..., x^j-1, x^j+1, ..., x^t)

Proof:

(1) Assume the family (x¹, ..., x^t) is linearly dependent.

(2) Then, there exists there are scalars α_i, not all zero, such that α₁x¹ + ... + α_tx^t = 0. [See Definition 1 above]

(3) Let α_i be a scalar that is not 0.

(4) Then -α_ixⁱ = α₁x¹ + ... + α_i-1x^i-1 + α_i+1xⁱ⁺¹ + ... + α_tx^t.

(5) So that:

xⁱ = (-1/α_i)α₁x¹ + ... + (-1/α_i)α_i-1x^i-1 + (-1/α_i)α_i+1xⁱ⁺¹ + ... + (-1/α_i)α_tx^t

(6) Thus, we have shown that xⁱ is a linear combination of (x¹, ..., x^i-1, xⁱ⁺¹, ..., x^t). [See Definition 1, here]

(7) Assume that x^j is a linear combination of (x¹, ..., x^j-1, x^j+1, ..., x^t)

(8) Then there exists α_i such that:

x^j = α₁x¹ + ... + α_j-1x^j-1 + α_j+1x^j+1 + ... + α_tx^t

(9) But then

0 = α₁x¹ + ... + α_j-1x^j-1 + α_j+1x^j+1 + ... + α_tx^t + (-1)x^j

(10) This gives us that (x¹, ..., x^t) is linearly dependent. [See Definition 1 above]

QED

References:

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