**Definition 1**: Vectors X_{1}, …, X_{k} of the same size and shape are **independent** if for any scalar values *b*_{1}, … *b _{k}*, if

*b*

_{1}

*X*

_{1}

*+⋯+ b*= 0, then

_{k }X_{k}*b*

_{1}= … =

*b*= 0.

_{k}Vectors *X*_{1}, …, *X _{k}*

_{ }are

**dependent**if they are not independent, i.e. there are scalars

*b*

_{1}, …

*b*, at least one of which is non-zero, such that

_{k}*b*

_{1}

*X*

_{1}

*+⋯+ b*= 0.

_{k}X_{k}**Observation**: If *X*_{1}, …, *X _{k}* are independent, then

*X*≠ 0 for all

_{j}*j*.

**Property 1**: *X*_{1}, …, *X _{k}* are dependent if and only if at least one of the vectors can be expressed as a linear combination of the others.

Proof: Suppose *X*_{1}, …, *X _{k}* are dependent. Then there are scalars

*b*

_{1}, …

*b*, at least one of which is non-zero such that

_{k}*b*

_{1}

*X*

_{1}

*+⋯+ b*= 0. Say

_{k}X_{k}*b*≠ 0. Then

_{i}Now suppose that *X _{i}* = . Then

*b*

_{1}

_{ }X_{1}

*+⋯+ b*= 0, where

_{k}X_{k}*b*= -1, and so

_{i }*X*

_{1}, …,

*X*are dependent.

_{k}**Definition 2**: The **span** of independent vectors *X*_{1}, …, *X _{k}* consists of all the vectors which are a linear combination of these vectors. If

*W*is any set of vectors, then the vectors

*X*

_{1}, …,

*X*are said to be a

_{k}**basis**of

*W*if they are independent and their span equals

*W*. We call a set of vectors

*W*closed if

*W*is the span of some set of vectors. Since we will only consider finite sets of vectors, henceforth we will assume that any closet set is finite.

**Property 2**: If *X*_{1}, …, *X _{k}* is a basis of

*W*, then every element in

*W*has a unique representation as a linear combination of

*X*

_{1}, …,

*X*.

_{k}Proof: That one such representation exists follows from the definition of span. We now show uniqueness. Suppose there are two such representations, as follows:

=

Then = 0. But since *X*_{1}, …, *X _{k}* are independent,

*b*

_{j}–

*c*= 0 for all

_{j}*j*, i.e.

*b*

_{j}=

*c*for all

_{j}*j*, and so the two representations are equal.

**Property 3**: If *B* is a set of independent vectors such that the span of *B* is a subset of a closed (finite) set of vectors *W*, then *B* can be expanded to be a (finite) basis for *W*.

Proof: Let *W* = {*X*_{1}, …, *X _{n}*}. We now build a finite set of vectors recursively as follows. Start with

*B*

_{0}=

*B*. For each

*k*from 0 to

*n–*1, define

*B*

_{k+1 }=

*B*

_{k}∪ {

*X*} if

_{k}*X*is not already in the span of

_{k}*B*and

_{k}*B*

_{k+1}=

*B*otherwise. Clearly each

_{k}*B*is an independent set of vectors and the span of

_{k}*B*is

_{n}*W*.

**Corollary 1**: Every closed set of vectors *W* has a (finite) basis.

Proof: The corollary is Property 3 with *B* = Ø.

**Property 4**: If *Y*_{1},…,*Y _{n}* is a basis for

*W*and

*X*

_{1}, …,

*X*is a set of independent vectors in

_{m}*W*, then

*m ≤ n*.

Proof: We now show by induction that for each *k*, 1 ≤ *k* ≤ *m*, there are vectors *Z*1,…,*Zk* such that {*Z*1,…,*Zk*} ⊆ {*Y*1,…,*Yn*} and *Z*1, …, *Zk*, *X*_{k+}1, …, *Xm* are independent.

We now assume the assertion is true for all values less than *k* and show it is true for *k*, where *k* ≤ *m, *i.e. we need to prove that for at least one* j*, *Z*1,…,*Z*, *Y _{j}*,

*X*

*k*+1,…,

*Xm*are independent. If there is no such

*j*then by Property 1, each

*Y*can be expressed as a linear combination of

_{j}*Z*1,…,

*Z*,

*X*

*k*+1,…,

*Xm.*But since

*Xk*is in

*W*and

*Y*1,…,

*Yn,*is a basis for

*W*, we can express

*Xk*as a linear combination of the

*Y*1,…,

*Yn*and therefore as a linear combination of

*Z*1,…,

*Z*,

*X*

*k*+1,…,

*Xm.*Thus by Property 1,

*Z*1,…,

*Z*,

*X*

_{k},

*X*

*k*+1,…,

*Xm*are not independent, a violation of the induction hypothesis.

We conclude there is some *j* for which *Z*1, …, *Z*, *Yj*, *X**k*+1,…, *Xm* are independent. We set *Z**k *equal to any such *Yj*, which yields the desired result, namely that *Z*1, …, *Z*, *X**k*+1,…, *Xm* are independent.

Where *k* = *m*, we conclude that {*Z*1, …, *Z*_{m}} ⊆ {*Y*1, …, *Yn*} and that *Z*1, …, *Z*_{m} are independent. Since *Z*1, …, *Z**m *are independent, they are all distinct, but since {*Z*1, …, *Z*_{m}} ⊆ {*Y*1, …, *Yn*}, it follows that *m **≤ n*.

**Corollary 2**: Any two bases for a finite set of vectors have the same number of elements.

Proof: Suppose *X*1, …, *Xm* and *Y*1, …, *Yn* are bases for *W*. By Property 4, *m ≤ n* and also *n* ≤ *m*, and so *m = n*.

**Corollary 3**: Let *Y*1, …, *Ym* be a basis for *W* and let *X*1, …, *Xm* be a set of independent vectors in *W*. Then *X*1, …, *Xm* is also basis for *W*.

Proof: Suppose *X*1, …, *Xm* is not a basis for *W*. By Property 3, it can be expanded to become a basis for *W*. This basis has *n* elements for some *n* > *m*, but this contradicts Property 4 since *Y*1, …, *Ym* is a basis for *W*. Thus *X*1, …, *Xm* must also be a basis for *W*.

**Corollary 4**: Any set of n linearly independent *n* × 1 column vectors is a basis for the set of *n* × 1 column vectors. Similarly, any set of *n* linearly independent 1 × *n* row vectors is a basis for the set of 1 × *n* row vectors.

Proof: Let *C _{j}* be the

*j*th column of the identity matrix

*I*. It is easy to see that for any

_{n}*n*,

*C*

_{1}, …,

*C*forms a basis for the set of all

_{n}*n*× 1 column vectors. The result for column vectors now follows by Corollary 3. The proof for row vectors is similar.

**Definition 3**: The **dimension** of a closed set of vectors *W* is the size of any basis of *W*.

**Observation**: This definition makes sense since, as we have seen from the above, any closed set of vectors has a basis, and any two bases have the same number of elements. Further, note that any element in *W* can be expressed uniquely as a linear combination of the elements in any basis.

I just discovered your site. It is very instructive!

Quick question: in the summation as part of the first proof on this page, should the b(j) term be -b(j)?

Michael,

Yes, you are right. Thanks for catching this error. I have now updated the referenced webpage.

Charles