Span, linear independence and bases are the building blocks of linear algebra. They describe vector spaces in terms of generating sets and coordinates. We define them both for finite lists of vectors , where order matters and repetitions are allowed (this is what coordinates and matrices need), and for arbitrary, possibly infinite, subsets .
4.6.1 Linear Combinations and Span
Definition 4.6.1 (Linear combination). A linear combination of vectors is a vector of the form with scalars . For the empty sum is .
Definition 4.6.2 (Span). The span of a subset is the set of all linear combinations of finitely many elements of : For a list we write . We say (or the list) spans , or is a spanning set for , if its span is .
Even when is infinite, only finite linear combinations are allowed; infinite sums have no meaning in a general vector space. Since the empty sum is , we have always, and .
Proposition 4.6.3 (The span is the smallest subspace containing ). For any subset , is a subspace of that contains , and it is contained in every subspace of that contains .
Proof. We have . A sum of two finite linear combinations of elements of is again one, and so is a scalar multiple of one: is a linear combination of the finitely many vectors . So is a subspace. Each equals . Finally, a subspace is closed under addition and scalar multiplication, hence (by induction on ) contains every linear combination with . ∎
Equivalently, is the intersection of all subspaces containing , which is a subspace by Proposition 4.5.11.
4.6.2 Linear Independence
Definition 4.6.4 (Linear independence). A list of vectors is linearly independent if the only way to write as a linear combination of them is the trivial way: A subset is linearly independent if every list of finitely many distinct elements of is linearly independent: for all , all distinct and all , A list or subset that is not linearly independent is linearly dependent: some nontrivial finite linear combination of its elements is .
Note. The word “distinct” matters. Without it, the relation would make every nonempty set dependent. A list with a repeated vector, such as , is linearly dependent, while the set is linearly independent whenever . For a list of distinct vectors, the list is independent exactly when the set is. The empty list and the empty set are linearly independent.
Note. Linear dependence means that some vector is a linear combination of the others. If with, say, , then so is redundant: it already lies in the span of the others.
Proposition 4.6.5 (Characterizations of linear independence). The following are equivalent for vectors :
- are linearly independent;
- no is a linear combination of the others;
- the linear map , , is injective.
Proof. (a) (c): If , then , so for all by independence.
(c) (a): If , then , so all by injectivity.
(a) (b): Suppose . Then is a nontrivial relation, since the coefficient of is , contradicting independence.
(b) (a): Suppose with some . Then , contradicting (b). ∎
Lemma 4.6.6 (Adjoining a vector outside the span). If are linearly independent and , then are linearly independent.
Proof. Suppose . If , then , a contradiction. So , and then by independence of the . ∎
Proposition 4.6.7 (Characterization of spanning). The following are equivalent for vectors :
- span ;
- every can be written as for some ;
- the linear map , , is surjective.
Proof. Statement (b) is the definition of (a), and (c) says that every is of the form , which is (b). ∎
4.6.3 Bases
Definition 4.6.8 (Basis). A basis of is a linearly independent subset that spans . Similarly, a list is a basis of if it is linearly independent and spans ; equivalently, the linear map , , is bijective.
When we speak of a finite basis we usually mean a list, so that its elements come in a definite order.
Proposition 4.6.9 (Unique representation). A subset is a basis if and only if every can be written uniquely as a linear combination of distinct elements of ; more precisely, there is a unique family of scalars , only finitely many of them nonzero, with . In particular, if is a basis of , then every can be written uniquely as with . The scalars are the coordinates of with respect to this basis.
Proof. Suppose is a basis. Existence of an expression is the spanning property. If , then , a finite linear combination of distinct elements of ; by independence, for all .
Conversely, suppose every vector has a unique expression. Then spans . If with distinct , this is an expression of ; comparing it with the expression in which all coefficients are , uniqueness gives for all . So is independent. The statement for a list is proved in the same way. ∎
Note. For an arbitrary subset , let be the space of functions with for only finitely many . The map , , is linear; spans if and only if it is surjective, is linearly independent if and only if it is injective, and is a basis if and only if it is bijective. For with distinct , this is the map above.
Example 4.6.10. Standard basis of : The vectors form the standard basis of : every vector , and this is the only way to write it as a linear combination of the .
Example 4.6.11. A non-standard basis of : If , the vectors and also form a basis of : every vector can be written as and if , then , so and . In characteristic this fails: there , so and the list is linearly dependent.
Example 4.6.12. Bases of polynomial spaces: The polynomials form a basis of , and the infinite set is a basis of . Indeed, every polynomial is a finite linear combination of monomials, and a linear combination of distinct monomials is the polynomial whose coefficients are the , which is only if every .
Example 4.6.13. In , let be the sequence with in position and elsewhere. The set is linearly independent, but it spans only the eventually zero sequences: a finite linear combination of the has only finitely many nonzero terms. So it is a basis of the subspace of eventually zero sequences, and not of .