There are many situations in mathematics where we want to describe an infinite set in a concise manner. We saw this at work already in Section 1.3, where infinite sets of solutions to linear systems were neatly described with parametric expressions.
A similar issue arises when describing vector spaces and their subspaces. As we know, any vector space is either the zero space or infinite (Exercise 15). If we happen to be dealing with a subspace of \(\R^n\text{,}\) then there is the possibility of giving a parametric description; but how do we proceed when working in one of our more exotic vector spaces like \(C^1(\R)\text{?}\)
As we will see in Section 3.6 the relevant linear algebraic tool for this purpose is the concept of a basis. Loosely speaking, a basis for a vector space \(V\) is a set of vectors that is large enough to generate the entire space, and small enough to contain no redundancies. What exactly we mean by “generate” is captured by the rigorous notion of span; and what we mean by “no redundancies” is captured by linear independence.
Let \(V\) be a vector space, and let \(S\subseteq V\) be any subset of \(V\text{.}\) The span of \(S\), denoted \(\Span S\text{,}\) is the subset of \(V\) defined as follows:
If \(S=\emptyset\text{,}\) then \(\Span S=\{\boldzero_V\}\text{.}\)
Otherwise we define \(\Span S\) to be the set of all linear combinations of elements of \(S\text{:}\) i.e.,
\begin{equation*}
\Span S=\{\boldv\in V\colon \boldv=c_1\boldv_1+c_2\boldv_2\cdots +c_n\boldv_n \text{ for some } \boldv_i\in S \text{ and } c_i\in \R\}\text{.}
\end{equation*}
Let \(S\) be a subset of \(V\text{.}\) Some simple observations:
The zero vector is always an element of \(\Span S\text{.}\) Indeed, if \(S=\emptyset\text{,}\) then \(\Span S=\{\boldzero\}\) by definition. Otherwise, given any \(\boldv\in S\text{,}\) the linear combination \(0\boldv=\boldzero\) is an element of \(\Span S\text{.}\)
We have \(S\subseteq \Span S\text{:}\) i.e., \(\Span S\) includes \(S\) itself. Indeed, given any \(\boldv\in S\text{,}\) the linear combination \(1\boldv=\boldv\) is an element of \(\Span S\text{.}\)
If \(S=\{\boldv\}\) contains exactly one element, then \(\Span S=\{c\boldv\colon c\in \R\}\) is simply the set of all scalar multiples of \(\boldv\text{.}\)
If \(\boldv\ne \boldzero\text{,}\) then we know that this set is infinite (Exercise 15). Thus even when \(S\) is finite, \(\Span S\) will be infinite, as long as \(S\) contains nonzero vectors.
\(\Span S\) is the set of all scalar multiples of the nonzero vector \((a,b)\text{.}\) Geometrically, this is the line that passes through the the origin and the point \((a,b)\text{.}\)
By Remark 3.5.2, we have \(S\subseteq \Span S\text{.}\) Thus \(\R^2\subseteq \Span \R^2\text{.}\) Since \(\Span \R^2\subseteq \R^2\) by definition, we conclude that \(\Span S=\R^2\text{.}\)
Let \(W\subseteq V\) be a subspace that contains all elements of \(S\text{.}\) Since \(W\) is closed under arbitrary linear combinations, it must contain any linear combination of elements of \(S\text{,}\) and thus \(\Span S\subseteq W\text{.}\)
Let \(S\) be a subset of the vector space \(V\text{.}\) We call \(W=\Span S\) the subspace of \(V\) generated by S, and we call \(S\) a spanning set for \(W\text{.}\)
For most of the vector spaces we’ve met a natural spanning set springs to mind. We will refer to these loosely as standard spanning sets. Some examples:
Zero space.
Let \(V=\{\boldzero\}\text{.}\) By definition the empty set \(S=\emptyset=\{ \}\) is a spanning set of \(V\text{.}\)
Let \(V=\R^n\text{.}\) For \(1\leq i\leq n\text{,}\) define \(\bolde_i\) to be the \(n\)-tuple with a one in the \(i\)-th entry, and zeros elsewhere. Then \(S=\{\bolde_1, \bolde_2,\dots, \bolde_n\}\) is a spanning set for \(\R^n\text{.}\)
Let \(V=M_{mn}\text{.}\) For each \((i,j)\) with \(1\leq i\leq m\) and \(1\leq j\leq n\text{,}\) define \(E_{ij}\) to be the \(m\times n\) matrix with a one in the \(ij\)-th entry, and zeros elsewhere. Then \(S=\{E_{ij}\colon 1\leq i\leq m, 1\leq j\leq n\}\) is a spanning set for \(M_{mn}\text{.}\)
Let \(V=P_n\text{.}\) The set \(S=\{x^n, x^{n-1}, \dots, x, 1\}\) clearly spans \(P_n\text{.}\) This is just another way of saying that the monomials of degree at most \(n\) generate the polynomials of degree at most \(n\text{.}\)
Note the glaring difference between the first three examples, and the last: our standard spanning set for \(P\) is infinite, whereas the previous examples are all finite spanning sets. You suspect, no doubt, that there is no finite spanning set for \(P\text{.}\) We will be able to prove this shortly.
It is important to observe that spanning sets for vector spaces are not unique. Far from it! In general, for any nonzero vector space there are infinitely many choices of spanning sets.
Since the last column will never contain a leading one, we conclude that the system is consistent for any choice of \(a,b,c,d\text{,}\) and thus that \(\Span S=M_{22}\text{,}\) as claimed.
As in the examples above, our reasoning implies \(\Span S=P_2\) if and only if this system is consistent for any choice of \(a,b,c\text{.}\) Thus usual Gaussian elimination procedure tells us that this is indeed so. We leave the details to you.
As mentioned at the top, the notion of linear independence is precisely what we need to guarantee that a given spanning set has no “redundancies”. We first define linear independence of a finite set of vectors (Definition 3.5.9) and later generalize to an arbitrary set of vectors (Definition 3.5.14).
Let \(V\) be a vector space, let \(S\) be a finite subset, and let \(\boldv_1, \boldv_2, \dots, \boldv_n\) be the distinct elements of \(S\text{:}\) i.e., \(\boldv_i\ne \boldv_j\) for all \(i\ne j\text{.}\) We say \(S\) is linearly independent if the following condition holds:
\begin{equation*}
\text{if } c_1\boldv_1+c_2\boldv_2+\cdots +c_n\boldv_n=\boldzero \text{ for some } c_i\in \R , \text{ then } c_i=0 \text{ for all } i\text{.}
\end{equation*}
We say \(S\)is linearly dependent if it is not linearly independent; i.e., if we can find scalars \(c_1, c_2,\dots, c_n\) with \(c_i\ne 0\) for some \(i\) and
We call a linear combination \(c_1\boldv_1+c_2\boldv_2+\cdots c_n\boldv_n\) trivial if \(c_i=0\) for all \(i\text{,}\) and nontrivial if \(c_i\ne 0\) for some \(i\text{.}\) Using this terminology, a set \(S\) is linearly independent if the only linear combination of distinct elements of \(S\) yielding the zero vector is the trivial one.
More often than not you will do so in the direct manner: i.e., assume you have a linear combination equal to the zero vector, then show that all coefficients must be zero.
It is easy to see that \(S\) is linearly dependent if and only if some element of \(S\) can be written as a linear combination of other elements of \(S\text{:}\) just take the nontrivial linear combination yielding the zero vector, and solve for the vector in this combination with the nonzero coefficient.
This makes precise what it means for a spanning set \(S\) to have redundancies or not. If \(S\) is linearly dependent, then one of its vectors can be written as a linear combination of the others, and thus can be “thrown out” when computing \(\Span S\text{,}\) the set of all linear combinations of \(S\text{.}\) Conversely, if \(S\) is linearly independent, then no element of \(S\) can be written as a linear combination of the others; throwing any element out would thus result in \(\Span S\) being strictly smaller.
If \(S=\{\boldv\}\text{,}\) then \(S\) is linearly independent if and only if \(\boldv\ne \boldzero\text{.}\) The previous comment shows why \(\boldv\ne \boldzero\) is a necessary condition. Let’s see why it is sufficient.
Suppose \(\boldv\ne\boldzero\text{,}\) and suppose we have \(c\boldv=\boldzero\text{.}\) By Theorem 3.1.16 we have \(c=0\) or \(\boldv=\boldzero\) (Theorem 3.1.16). Since \(\boldv\ne 0\text{,}\) we conclude \(c=0\text{.}\) This shows that the only linear combination of \(S\) yielding \(\boldzero\) is the trivial one.
Suppose \(S=\{\boldv, \boldw\}\text{,}\) where \(\boldv\ne\boldw\text{.}\) From the last remark, it follows that \(S\) is linearly independent if and only if one of its elements is a scalar multiple of the other.
This makes it very easy to decide whether a two-element set is linearly independent. Note however, that the same observation does not apply to larger sets: e.g., \(S=\{(1,1),(1,0), (0,1)\}\) can be shown to be linearly dependent, and yet no element of \(S\) is a scalar multiple of any other element.
Deciding whether a subset \(S\) of a vector space \(V\) is linearly independent usually boils down to a question about the solutions to a certain system of linear equations. The procedure below outlines the steps necessary to extract the relevant linear system and draw the relevant conclusions.
Translate this vector equation into a homogeneous linear system in the unknowns \(c_1,c_2,\dots, c_n \text{,}\) using the definition of equality for your vector space.
This is a fitting point to recall our Gaussian elimination mantra. As you can see, even as we move into more and more abstract realms of linear algebra (linear independence, span, etc.), Gaussian elimination remains our most important tool.
Row reduction reveals that this last linear system has a free variable, and hence that there are infinitely many solutions to this system: e.g., \((a,b,c)=(2,1,3)\text{.}\) We conclude that \(S\) is linearly dependent.
So far we have only defined linead independence for finite subsets of a vector space. The notion is easily extended to arbitrary (potentially infinite) subsets.
Let \(V\) be a vector space. A subset \(S\subseteq V\) is linearly independent if and only if every finite subset of \(S\) is lineary independent in the sense of Definition 3.5.9.
A subtle question arises here: namely, whether our definition of linear independence for arbitrary sets is consistent with our definition for finite ones. In other words, given a set \(S=\{\boldv_1, \boldv_2, \dots, \boldv_n\}\) of \(n\) distinct vectors, is it true that \(S\) is linearly independent (in the sense of 3.5.9) if and only if every subset \(\{\boldv_{i_1}, \boldv_{i_2}, \dots, \boldv_{i_k}\}\) is linearly independent (in the sense of 3.5.9)? The answer of course is yes. One direction is easy: since \(S\) is a subset of itself, clearly if every subset is linearly independent, then \(S\) is linearly independent. The other direction is left as an exercise (Exercise 19).
is linearly independent. Given a finite subset \(T\subseteq S\text{,}\) we can write \(T=\{x^{n_1}, x^{n_2}, \dots, x^{n_r}\}\text{,}\)where \(n_1< n_2 < \cdots < n_r\text{.}\) By Corollary 0.7.4, we have
This proves \(T\) is linearly independent. We have thus shown that any finite subset of \(S\) is linearly independent, and thus conclude that \(S\) is linearly independent by Definition 3.5.14.
In each computation of Example 3.5.13 it was easy to derive a relevant linear system since the notion of equality in each of these spaces amounts to checking a finite number of numeric equalities: e.g., between the entries of two triples, the coefficients of two polynomials, or the entries of two \(2\times 2\) matrices.
Things are slightly more complicated when working in function spaces on an interval \(X\) (e.g. \(C(X), C^\infty(X)\text{,}\) etc.), since by definition functions \(f\) and \(g\) are equal if and only if \(f(x)=g(x)\) for all \(x\in X\text{.}\) Thus, in principle verifying two functions are equal amounts to showing infinitely many equalities hold: one for each \(x\in X\text{.}\) Despite this added complexity, we can still investigate linear independence of functions with certain linear systems, as described in the procedure below.
Since (3.17) is true for all \(x\in X\text{,}\) we can produce a homogeneous system of linear equations in the unknowns \(c_j\) by picking elements \(x_1,x_2,\dots \) of \(X\text{,}\) and evaluating(3.17) at \(x_i\text{.}\) The \(i\)-th equation of the resulting system is thus
If you can find elements \(x_1, x_2, \dots, x_t\in X\) so that the resulting homogeneous system in the unknowns \(c_j\) has the unique solution \(c_1=c_2=\dots=c_n=0\text{,}\) then we conclude that \(S\) is linearly independent.
A nontrivial linear combination of the \(f_i\) equal to the zero function amounts to a function identity. Either cite a well-known function identity involving the \(f_i\text{,}\) or else prove an identity of your own.
When using Procedure 3.5.17 to show \(S=\{f_1, f_2, \dots, f_n\}\) is linearly independent, you want to produce enough linear equations to force the unknowns \(c_i\) to all be equal to 0. Note that since you you have \(n\) unknowns, you need at at least\(n\) equations, and so must pick at least \(n\) elements \(x_i\in X\text{.}\) Do so judiciously in order to (a) force the \(c_i\) to all be equal to 0, and (b) make the necessary computations palatable.
for all \(x\in (-2\pi, 2\pi)\text{.}\) In particular, the equality is true when evaluated at \(x=0, \pi/2, \pi\text{,}\) yielding the following linear system:
This system can be now be solved essentially by inspection: the first equation implies \(c_2=0\text{;}\) setting \(c_2=0\text{,}\) in the third equation, we conclude \(c_1=0\text{;}\) the second equation now implies \(c_3=0\text{.}\) We conclude that \(c_1=c_2=c_3=0\text{.}\) Thus the only linear combination of \(f, g, h\) yielding the zero function is the trivial one, showing that \(S\) is linearly independent.
We claim \(S\) is linearly dependent. As discussed in Procedure 3.5.17, to prove this we have to produce an identity involving these functions. The double-angle formula from trigonometry tells us that
We only know that \(\mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3 \rbrace\subseteq \mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3, \mathbf{u}_4\rbrace\) .
\(\mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3 \rbrace= \mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3, \mathbf{u}_4\rbrace\) when \(\mathbf{u}_4\) is a scalar multiple of one of \(\lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3 \rbrace\text{.}\)
There is no obvious relationship between \(\mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3 \rbrace\) and \(\mathrm{span} \lbrace\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3, \mathbf{u}_4 \rbrace\) .
We only know that span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4\right\rbrace\subseteq\) span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3\right\rbrace\) .
There is no obvious relationship between span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3\right\rbrace\) and span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4\right\rbrace\) .
span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3\right\rbrace\) is a proper subset of span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4\right\rbrace\text{.}\)
span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3\right\rbrace=\) span\(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4\right\rbrace\) when none of \(\left\lbrace{\bf u}_1,{\bf u}_2,{\bf u}_3,\right\rbrace\) is a linear combination of the others.
\(\lbrace{{\bf u}_1, {\bf u}_2, {\bf u}_3, {\bf u}_4}\rbrace\) could be a linearly independent or linearly dependent set of vectors depending on the vectors chosen.
\(\lbrace{{\bf u}_1, {\bf u}_2, {\bf u}_3, {\bf u}_4}\rbrace\) is also a linearly independent set of vectors unless \({\bf u}_4\) is a scalar multiple another vector in the set.
\(\lbrace{{\bf u}_1, {\bf u}_2, {\bf u}_3, {\bf u}_4}\rbrace\) is a linearly independent set of vectors unless \({\bf u}_4\) is a linear combination of other vectors in the set.
\(\lbrace{{\bf u}_1, {\bf u}_2, {\bf u}_3, {\bf u}_4}\rbrace\) could be a linearly independent or linearly dependent set of vectors depending on the vectors chosen.
Determine whether each set \(\left\{ p_{1},p_{2} \right\}\) is a linearly independent set in \({\mathbb P}_{3}\text{.}\) Type "yes" or "no" for each answer.
If they are linearly dependent, find scalars that are not all zero such that the equation below is true. If they are linearly independent, find the only scalars that will make the equation below true.
A subset \(S\) of a vector space is given in each exercise below. Determine whether the given elements are elements of \(\Span S\text{.}\) Justify your answer by either providing a linear combination of \(S\) yielding the given element, or else showing that no such linear combination exists.
Let \(V\) be a vector space, and let \(S=\{\boldv_1, \boldv_2, \dots, \boldv_n\}\) be a subset of distinct vectors. Assume \(S\) is linearly independent. Show that any subset \(T\subseteq S\) is linearly independent.
The empty set \(T=\{\, \}\) is trivially linearly independent. Let \(T=\{\boldv_{i_1}, \boldv_{i_2}, \dots, \boldv_{i_k}\}\) represent an arbitrary nonempty set of distinct elements of \(S\text{.}\) You can show \(T\) is linearly independent by extending linear combinations of the elements of \(T\) to a linear combination of the elements of \(S\) in a certain way.
Let \(S=\{\boldv_1,\boldv_2,\dots, \boldv_n\}\) be a subset of \(\R^n\text{,}\) and let \(A\) be the \(n\times n\) matrix whose \(j\)-th column is \(\boldv_j\text{:}\) i.e.,
21.Linear transformations, span, and independence.
Suppose \(T\colon V\rightarrow W\) is a linear transformation. Let \(S=\{\boldv_1,\boldv_2,\dots ,\boldv_r\}\) be a subset of \(V\text{,}\) and let \(S'\) be the image of \(S\) under \(T\text{:}\) i.e.,
Answer true or false: if true, provide a proof; if false, provide an explicit counterexample. Note: for a complete counterexample you need to specify \(T\colon V\rightarrow W\text{,}\) and \(S\text{.}\)
