A collection of vectors spans a set if every vector in the set can be expressed as a linear combination of the vectors in the collection. The set of rows or columns of a matrix are spanning sets for the row and column space of the matrix.

If is a (finite) collection of vectors in a vector space , then the span of is the set of all linear combinations of the vectors in . That is
Show that for any (non-empty) set of vectors , is a subset of (in other words, it is closed under the addition and scalar multiplication operations coming from ). Your argument should work for general sets without any assumptions on cardinality.

In fact, something stronger is true.

Proof
Assume first that is finite; then for some collection of vectors , . To show that is a subspace, it suffices to show three things: i) it contains the zero vector, ii) it is closed under vector addition, and iii) it is closed under scalar multiplication.
  • , so . In other words, the zero vector can be written as a linear “combination” of a single vector in (a linear combination of one vector amounts to a scalar multiple of that vector).
  • C1 Suppose . Then there must exist scalars such that then implying is closed under vector addition.
  • C2 For as above and , Hence is closed under scalar multiplication.

Suppose now that is an infinite set. The first property is verified the same way, by choosing any vector and taking the scalar product with . For the second property, for any , there must be some finite set satisfying the property that . But then by the above argument we have that , verifying the closure axiom (C1). Finally, for the same and finite set with , and scalar , the above argument shows that , verifying the second closure axiom (C2). So the necessary properties have been verified, and we may conclude that is a subspace for any non-empty subset , as claimed.

Proof
Because we allow spanning sets to be arbitrarily large, we can take and observe that for trivial reasons.

The lemma above suggests that spanning sets are not only not unique, they can have vastly different sizes. For example, is spanned by . It is also spanned by the set itself, which is much larger. It is natural to ask how small a spanning set can be. This leads to

Proof
As we have seen, spans , so it is a spanning set for . However, if we form the subset by removing from the set, then any vector in the span of contains zero in its ith coordinate. So , and must be minimal.

Recall that for a matrix we write for the ith row, and for the jth column. If is an matrix, then each row is a row vector in the vector space , while each column is a vector in the vector space . This leads to the following definition

Note that the row and column spaces of a matrix are different vector spaces, unless . If then and can be naturally identified via the transpose operation, but they are not the same space.

Finding spanning sets for or is not a problem; they are just the set of rows and columns of . However if one wants to find a minimal spanning set then some work needs to be done. The main tool we will use is the following theorem.

We also have the following useful lemma, which is relatively straightforward to prove.

This theorem and lemma provide an efficient algorithm for determining minimal spanning sets, as well as determining linear relations among vectors.

Given a matrix , a minimal spanning set for is found by

  • computing ;
  • identifying the set of pivot columns;
  • choosing as your minimal spanning set for to be the subset of column vectors

Moreover, in the reduced row echelon form the columns that are not pivot columns are easily computed as linear combinations of the pivot columns. And since the row space remains unchanged under row operations, a minimal spanning set for is found by

  • computing ;
  • identifying the set of indices corresponding to the non-zero rows of ;
  • choosing as your minimal spanning set for the subset of row vectors where .

Note that, unlike the column case, these rows typically won’t be among the original set of rows of ; they will simply have the same span.

Suppose is a matrix with
  • Find a minimal spanning set for from the original set of columns of (expressed simply in terms of the original set of column vectors);
  • For each remaining column of , write it explicitly as a linear combination of the minimal spanning set you have just constructed.
  • Write down a minimal spanning set for the row space (here you can give explicit numerical vectors).

The above Theorem and Lemma have additional implications, which we summarize in the following corollary.