Monday, May 14, 2007

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 (x1, ..., xt) be a family of vectors in a vector space V. We call u in V a linear combination of (x1, ..., xt) if and only if there exists scalars α1, ..., αt such that:

u = α1x1 + ... + αtxt = ∑ (i=1,t) αixi.

Definition 2: [[ X ]]

Let X = (x1, ..., xn) 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 = (x1, ..., xt) be a family of vectors in V. Let W be a subspace of V that contains each xi.

Then, [[X]] ⊆ W.

Proof:

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

(2) So α1x1, ..., αtxt ∈ W by the closure of scalar multiplication.

(3) α1x1 + ... + αtxt ∈ W by the closure of addition.

(4) Thus, it is clear that every linear combination of (x1, ..., xt) is contained in W.

QED

Corollary 1.1:

Let V be a vector space and let X = (x1, ..., xt) and Y = (y1, ..., yu) be families of vectors in V.

If each xi is a linear combination of (y1, ..., yu), then [[X]] ⊆ [[Y]]

Proof:

(1) Assume that for each i, xi ∈ [[y1, ..., yu]].

(2) Then [[y1, ..., yu]] is a subspace of V. [See Theorem 2, here]

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

[[x1, ..., xt]] ⊆ [[y1, ..., yu]]

QED

Corollary 1.2:

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

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

Proof:

(1) Let X = (x1, ..., xt).

(2) Each xi is a member of (X,Y)

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

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

QED

Definition 3: ai,*

Let this designate a row such that: ai,* = [ ai,1 ai,2 ... ai,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:

ci,j = ∑ (k=1,n) bi,kak,j

(4) So,

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

= [ ∑(k=1,n) bi,kak,1 ∑(k=1,n) bi,kak,2 ... ∑(k=1,n) bi,kak,p ] =

= [ bi,1a1,1 bi,1a1,2 ... bi,1a1,p ] +
[ bi,2a2,1 bi,2a2,2 ... bi,2a2,p ] + ... +
[ bi,nan,1 bi,nan,2 ... bi,nan,p ] =

= bi,1[ a1,1 a1,2 ... a1,p] +
bi,2[ a2,1 a2,2 ... a2,p] + ... +
bi,n[ an,1 an,2 ... an,p] =

= bi,1(a1,*) +
bi,2( a2,* ) + ... +
bi,n( an,* )

= bi,*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:

ci,j = ∑ (k=1,m) ai,kbk,j

(4) So,

c*,j = [ c1,j c2,j ... cp,j ] =

= [ ∑(k=1,m) a1,kbk,j ∑(k=1,m) a2,kbk,j ... ∑(k=1,m) ap,kbk,j ] =

= [ a1,1b1,j a2,1b1,j ... ap,1b1,j ] +
[ a1,2b2,j a2,2b2,j ... ap,2b2,j ] + ... +
[ a1,nbn,j a2,nbn,j ... ap,nbn,j ] =

= b1,j[ a1,1 a2,1 ... ap,1] +
b2,j[ a1,2 a2,2 ... ap,2] + ... +
bn,j[ a1,n a2,n ... ap,n] =

= b1,j(a*,1) +
b2,j( a*,2 ) + ... +
bn,j( a*,n )

= b*,jA

QED


References

Sunday, May 13, 2007

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 (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/αi1x1 + ... + (-1/αii-1xi-1 + (-1/αii+1xi+1 + ... + (-1/αitxt

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