Proof. The idea is to exchange the \(v\)’s into the spanning set one at a time, throwing out a \(u\) at each step, and to observe that we can never run out of \(u\)’s before we run out of \(v\)’s.

Since \(B\) spans \(V\) and \(v_1\in V\), we may write \[v_1=c_1u_1+c_2u_2+\cdots +c_nu_n.\] Not every \(c_i\) is zero, since \(v_1\neq 0\) (a set containing \(0\) is never linearly independent). Renumbering the \(u\)’s if necessary, suppose \(c_1\neq 0\). Then \(u_1\) can be solved for in terms of \(v_1\) and \(u_2,\dots ,u_n\), so \[\{v_1,u_2,u_3,\dots ,u_n\}\] still spans \(V\): anything expressible using \(u_1\) can be re-expressed without it.

Suppose that after \(k\) steps (\(k<m\)) we have arranged, again renumbering, that \[\{v_1,\dots ,v_k,u_{k+1},\dots ,u_n\}\] spans \(V\). Write \(v_{k+1}\) in terms of this spanning set: \[v_{k+1}=d_1v_1+\cdots +d_kv_k+e_{k+1}u_{k+1}+\cdots +e_nu_n.\] Some \(e_j\) must be non-zero. For if every \(e_j\) were zero, \(v_{k+1}\) would be a linear combination of \(v_1,\dots ,v_k\), contradicting the linear independence of \(B'\). In particular there must still be at least one \(u\) left — which is the crux of the argument. Renumbering so that \(e_{k+1}\neq 0\), we may solve for \(u_{k+1}\) and conclude that \[\{v_1,\dots ,v_{k+1},u_{k+2},\dots ,u_n\}\] spans \(V\).

If \(m>n\) we could carry out this exchange \(n\) times, arriving at a spanning set \(\{v_1,\dots ,v_n\}\) with no \(u\)’s remaining. But then \(v_{n+1}\), which exists because \(m>n\), would be a linear combination of \(v_1,\dots ,v_n\), contradicting the independence of \(B'\). Hence \(m\leq n\). □

Proof. Let \(B=\{u_1, u_2,\dots , u_n\}\) and \(B'=\{v_1, v_2,\dots , v_m\}\) be two bases for the vector space \(V\). Since \(B'\) is a linearly independent subset of \(V\) and \(V\) is spanned by \(B\), Lemma 5.4.3 implies that \(m\leq n\). Similarly, since \(B\) is a linearly independent subset of \(V\) and \(V\) is spanned by \(B'\), Lemma 5.4.3 implies that \(n\leq m\). Combining the two, we get,\(m=n\). □

Solution. We determine which of the vectors \(v_1,v_2,v_3,v_4\) are linearly independent. Let \(\alpha _1,\alpha _2, \alpha _3,\alpha _4\in \mathbb {R}\) such that \(\alpha _1v_1+\alpha _2v_2+\alpha _3v_3+\alpha _4v_4=0\). This leads to the system: \begin {align*} \alpha _1+\alpha _2+\alpha _4 &=0\\ \alpha _2 &=0\\ \alpha _1+\alpha _3 &=0\\ \alpha _3+\alpha _4 &=0 \end {align*}

The coefficient matrix is \( \begin {pmatrix} 1&1&0&1\\0&1&0&0\\1&0&1&0\\0&0&1&1 \end {pmatrix} \) Thus,

\begin {align*} \begin {pmatrix} 1&1&0&1\\0&1&0&0\\1&0&1&0\\0&0&1&1\\ \end {pmatrix} & \hspace {0.3cm} \begin {matrix} r_1\rightarrow r_1-r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&1\\0&1&0&0\\1&0&1&0\\0&0&1&1\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_2\rightarrow r_3-r_1\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&1\\0&1&0&0\\0&0&1&-1\\0&0&1&1\\ \end {pmatrix}\\\\ & \hspace {0.3cm} \begin {matrix} r_3\rightarrow r_3+r_4\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&1\\0&1&0&0\\0&0&2&0\\0&0&1&1\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_3\rightarrow \frac {1}{2}r_1\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&1\\0&1&0&0\\0&0&1&0\\0&0&1&1\\ \end {pmatrix}\\\\ & \hspace {0.3cm} \begin {matrix} r_4\rightarrow r_4-r_3\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\rightarrow r_1-r_4\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\ \end {pmatrix} \end {align*}

Thus the trivial solution \(\alpha _1=\alpha _2=\alpha _3=\alpha _4=0\) is the unique solution. Therefore, the vectors \(v_1,v_2,v_3\) and \(v_4\) are linearly independent. This means that \(B=\{v_1,v_2,v_3,v_4\}\) is a basis for \(\mathbb {R}^4\). Hence \(\dim (\)Span\(B)=\dim (\mathbb {R}^4)=4\).

The basis theorem implies that if \(\dim V=n\), then any set \(B\) of \(m\) linearly independent vectors in \(V\) with \(m<n\) cannot span \(V\). However, \(B\) can be extended to a basis for \(V\). This is the next theorem.

Proof. Let \(B=\{x_1,x_2,\dots ,x_m\}\) be a linearly independent set in \(V\) and let \(B'=\{y_1,y_2,\dots ,y_n\}\) be a spanning set for \(V\). Then \(\dim (V)<n\).

Let \(B^*=\{x_1,x_2,\dots ,x_m,y_1,y_2,\dots ,y_n\}\). Then \(B^*\) spans \(V\) and since \(m+n>\dim V\), then \(B^*\) is linearly dependent. Let \(z_j\) be a vector in \(B^*\) which is a linear combination of vectors in \(B^*\). Then \(B^*/\{z_j\}\) spans \(V\). If \(B^*/\{z_j\}\) is linearly independent, then it is a basis for \(V\) and we are done.

If \(B^*/\{z_j\}\) is linearly dependent, we repeat the process of eliminating the vectors that make it linearly dependent until we get a linearly independent set. Then we obtain a basis for \(V\). □

Solution. Let \(B=\{(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)\}\) be the standard basis for \(\mathbb {R}^4\) and consider the set \(B^*=\{(1,1,0,0), (1,0,1,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)\}\).

We form the matrix \( \begin {pmatrix} 1&1&0&0\\1&0&1&0\\1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\ \end {pmatrix} \) Applying elementary row operations to get the linearly independent vectors we have. \begin {align*} \begin {pmatrix} 1&1&0&0\\1&0&1&0\\1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1 \end {pmatrix} & \begin {matrix} r_1\rightarrow r_1-r_4\\\longrightarrow \\ r_2\rightarrow r_2-r_3\\ \end {matrix} \begin {pmatrix} 1&0&0&0\\ 0&0&1&0\\1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\ \end {pmatrix} \begin {matrix} r_3\rightarrow r_3-r_1\\ \longrightarrow \\ r_5\rightarrow r_5-r_2\\ \end {matrix} \begin {pmatrix} 1&0&0&0\\0&0&1&0\\0&0&0&0\\0&1&0&0\\0&0&0&0\\0&0&0&1\\ \end {pmatrix} \end {align*}

Thus \(\{(1,1,0,0), (1,0,1,0), (0,1,0,0), (0,0,0,1)\}\) is a basis for \(\mathbb {R}^4\) containing \((1,1,0,0)\) and \((1,0,1,0)\).