Often a given vector space has a standard basis, but the particular problem we wish to solve requires a basis satisfying different properties, a basis of eigenvectors (if they exist) is a prime example. Other examples include extending a known basis for a proper subspace to the entire space. Here we focus both on building up from an independent set of vectors and paring down from a dependent spanning set of vectors.
For now we will restrict our attention to \(V=F^m;\) we can deal with arbitrary vector spaces once we know about coordinates. You might ask why use \(F^m\) and not \(F^n\text{.}\) The choice of notation is very important in mathematics. Well-chosen notation gives intuition to (or at least does not distract) the reader. Our construction of vectors in \(F^m\) will be used to construct an \(m\times n\) matrix. If we built them in \(F^n,\) the matrix we would construct would be \(n\times
m\) or \(n\times p\text{,}\) notation which would force much more concentration on the part of the reader. Hmmm. Might not be a bad idea …, but we shall stick with \(F^m.\)
Subsection 3.2.1 An algorithmic approach
As we begin, suppose we start with one nonzero vector \(v_1 \in
F^m\text{,}\) and since it is nonzero, the set \(S = \{v_1\}\) is linearly independent. Since we know that the dimension of \(F^m\) is \(m,\) we shall need \(m\) linearly independent vectors in \(S\) to form a basis. So as not to be trivial, we assume that \(m\gt 1.\) To add a second vector to \(S\text{,}\) independent from the first, all we must do is choose a vector \(v_2 \ne \lambda v_1\) for any scalar \(\lambda.\) Great, now \(S=\{v_1, v_2\}\) has two linearly independent vectors, so if \(m=2,\) we are done and have a basis for \(V.\)
Now supposing that \(m \ge 3,\) we begin to have to be more careful since adding a third vector independent from the other two means adding a vector which is not in their span, and here what we know about matrices helps a great deal.
Recall our
Observation 1.3.2 that if a matrix is given by
\(A = [a_1 \ a_2\ \cdots\ a_n]\) where
\(a_j\) is the
\(j\)th column of
\(A,\) and if
\(x\) is the column vector
\(x=[x_1, \dots,
x_n]\text{,}\) then the matrix product
\(Ax\) is a linear combination of the columns of
\(A.\) More precisely,
\begin{equation*}
Ax = x_1 a_1 + \cdots + x_na_n.
\end{equation*}
We describe how to use this observation in two ways: inductively and “just feeling lucky.” Starting from the lucky perspective, suppose that we have \(n\) vectors in \(F^m,\) \(v_1, \dots,
v_n\) and we want to know whether they are linearly independent. Create an \(m\times n\) matrix \(A\) whose columns are the \(v_i.\) Then the observation says that the columns are linearly dependent if and only if the system \(Ax=0\) has a nontrivial solution, but we know how to determine this by looking at the reduced row-echelon form of \(A:\) namely are there any free variables? So if the RREF form \(R\) of \(A\) has \(r\) nonzero rows (pivots, constrained variables) and \(r \lt n\text{,}\) there is a nontrivial solution, and the columns are linearly dependent.
Having dismissed the dependent vectors, those that remain are linearly independent, so this puts us in the inductive case where say we have acquired a linearly independent subset \(S = \{v_1,
\dots, v_r\}\) of vectors in \(F^m\text{,}\) and we wish to extend this independent set by one member (presuming of course \(r \lt m\)).
Suppose we wish to examine a new vector \(b\text{.}\) We can ask either "Is \(b\) in the span of \(S = \{v_1, \dots, v_r\}\text{,}\) or reverse the perspective and ask if \(S\cup \{b\}\) is linearly independent. Either way, we form the \(m\times (r+1)\) matrix, augmenting \(A\) with the column vector \(b.\)
To answer the question of is \(b\in \Span(S)\text{,}\) we consider the augmented matrix \([A|b]\) and row reduce to echelon form. If there is a pivot in the last column, the system \(Ax=b\) is not solvable, meaning that \(b\) is not in the column space of \(A,\) and hence \(S\cup \{b\}\) is linearly independent. If there is no pivot in the last column, the system is solvable meaning \(b\in \Span(S)\text{,}\) so we toss it out.
Subsection 3.2.2 Recovering familiar results
With the concepts of determining whether a set of vectors is linearly independent, we recover a familiar result: Any collection of more than \(m\) vectors in \(F^m\) is linearly dependent.
To remind us why this is true, let \(A\) be an \(m\times n\) matrix with entries in a field \(F,\) and assume that \(m \lt
n,\) so there are fewer rows than columns. Think of \(A\) as the coefficient matrix of a linear system.
Presumably we know that
\(A\) has a nontrivial
nullspace (since the number of constrained variables equals the number of pivots and there can be only one pivot per row, so there are free variables). By the observation, this means the columns of
\(A\) are linearly dependent.
