Chapter 2 - Finite Dimensional Vector Spaces

The span of a list of vectors is the smallest subspace of V containing all of those vectors.

Let $(v_1, \ldots, v_n)$ be a list of vectors in $V.$ 1) To show that the span is a subspace, we check that $\vec{0}$ is in the span by making all the scalars 0. To show that it is closed under vector addition, consider the vectors $c_1 v_1+ \cdots +c_n v_n$ and $d_1 v_1+ \cdots +d_n v_n$ in their span. Then their sum is $(c_1+d_1 ) v_1+ \cdots +(c_n+d_n ) v_n,$ which is also in the span. Finally, if a vector $c_1 v_1+ \cdots +c_n v_n$ in the span is scaled by a scalar $\lambda,$ then the result is $\lambda c_1 v_1 + \cdots + \lambda c_n v_n,$ which is also a linear combination.

2) To show that every other subspace contains the span, suppose $U$ is a subspace of $V$ with $v_1, …, v_n \in U$ and let $v_1 + \cdots + v_n$ be an arbitrary vector in the span. Then $c_1 v_1, …, c_n v_n \in U$ because $U$ is closed under scalar multiplication. Furthermore, their sum $c_1 v_1 + \cdots + c_n v_n$ is also in the span because $U$ is closed under vector addition.

Suppose $\left(v_{1},\ \ldots ,\ v_{n}\right)$ is a linearly independent list of vectors in $V.$ Then every sublist $\left(v_{i_{1}},\ \ldots ,\ v_{i_{k}}\right)$ is also linearly independent.

Let $(v_{i_{1}},\ \ldots ,\ v_{i_{k}})$ be a linearly dependent sublist of $\left(v_{1},\ \ldots ,\ v_{n}\right)$, and let $d_{i_{1}}v_{i_{1}}+\ldots +d_{i_{k}}v_{i_{k}}=0$ be its linear dependence relation, with at least one coefficient $d_{i_{j}}$ being non-zero. Let $c_{i_{j}}=d_{i_{j}}$ for every $i_{j}$ used in the sublist and the others all $0.$ Then $c_{1}v_{1}+\ldots +c_{n}v_{n}=0$ with at least one non-zero scalar.

Let $v_{1},\ \ldots ,\ v_{n}$ be a list of vectors in $V.$ The following are equivalent (TFAE):

1) $v_{1},\ \ldots ,\ v_n$ is linearly independent. 2) Every vector in $\text{span}\left(v_{1},\ \ldots ,\ v_n\right)$ has a unique scalar representation. 3) No vector $v_i$ is in the span of the other vectors. 4) No vector $v_i$ is in the span of the vectors before it.

(1)$⇔$(2): For the forward direction, suppose $\left(c_{1},\ \ldots ,\ c_{n}\right)$ and $(d_{1},\ \ldots ,\ d_{n})$ are two scalar representations of $v\in \text{span}(v_{1},\ \ldots ,\ v_{n}).$ Then $c_{1}v_{1}+\ldots +c_{n}v_{n}=d_{1}v_{1}+\ldots +d_{n}v_{n}$ because they are both $v.$ Subtracting, we get $\left(c_{1}-d_{1}\right)v_{1}+\ldots +\left(c_{n}-d_{n}\right)v_{n}$, which means $c_{i}-d_{i}=0$ for every $i$, i.e. they are all equal. The backward direction follows automatically because $c_i=0$ for every $i$ would be the unique representation for the zero vector.

(1)$⇔$(3): We prove the forward direction by contrapositive, if $v_i$ is in the span of the other vectors, i.e. $c_{1}v_{1}+\ldots +c_{i-1}v_{i-1}+c_{i+1}v_{i+1}+\ldots c_nv_n$, then we have a linear dependence relation $c_{1}v_{1}+\ldots +c_{i-1}v_{i-1}+\left(-1\right)v_i+c_{i+1}v_{i+1}+\ldots c_nv_n=v_i-v_i=0.$ Note that not every scalar is $0$ because $(-1)$ is used. For the backward direction, we use a very similar argument, also by contrapositive. If $c_{1}v_{1}+\ldots +c_nv_n=0$ with some $c_i\neq 0$, then subtracting the other terms gives us $c_iv_i=-c_{1}v_{1}-\ldots -c_{i-1}v_{i-1}-c_{i+1}v_{i+1}-\ldots -c_nv_n.$ Dividing both sides by $c_i$ (which is non-zero) shows us that $v_i$ is in the span of the other vectors.

(1)$⇔$(4): We have already proved the forward direction with the previous proof (1)$⇔$(3), since a vector being a linear combination of the vectors before it is a linear combination of the other vectors (just use $0$'s for the other vectors). For the backward direction, we use a very similar argument to the previous backwards direction, only the non-zero scalar we pick will be the last non-zero scalar: Start with our linear dependence relation

with not every scalar equal to $0.$ Let $c_i$ be the last non-zero scalar so that $c_i\neq 0$ and $c_{1}v_{1}+\ldots +c_iv_i=0.$ Subtract the other terms from both sides and divide by $c_i$ to get the desired conclusion:

Let $(v_{1},\ \ldots ,\ v_{n})$ be a list of linearly dependent vectors in $V.$ Then there exists a $k \in {1, …, n}$ such that $v_{k}\in \text{span}(v_{1},\ldots ,\ v_{k-1})$ and the list $(v_{1},\ldots ,\ v_{k-1},\ v_{k+1},\ \ldots ,\ v_{n})$ has the same span as $v_1,\ldots v_m.$ That is, removing $v_k$ from the list does not change its span.

Suppose $v_{1},\ \ldots ,\ v_{n}$ is a linearly dependent list of vectors in $V.$ Then from our last result, one of the vectors is in the span of the vectors before it, i.e. $v_{i}=c_{1}v_{1}+\ldots +c_{i-1}v_{i-1}.$ To show that the span does not change after removing $v_i$, we just express the term $d_iv_i$ as $d_i\left(c_{1}v_{1}+\ldots +c_{i-1}v_{i-1}\right).$ Here is how we implement that. Suppose $v\in \text{span}\left(v_{1},\ \ldots ,\ v_n\right)$, i.e. $v=d_{1}v_{1}+\ldots +d_nv_n.$ Then $v=d_{1}v_{1}+\ldots +d_{i-1}v_{i-1}+d_i\left(c_{1}v_{1}+\ldots +c_{i-1}v_{i-1}\right)+d_{i+1}v_{i+1}+\ldots +d_nv_n$, which is a linear combination of the other vectors:

Suppose $\left(u_{1},\ \ldots ,\ u_{n}\right)$ be a linearly independent list of vectors in $V$ with $n≥1$, let $\left(u_{1},\ldots ,\ u_{k}\right)$ be a sublist with $k<n$, possibly empty, shorter than the original list (but still linearly independent). Suppose further that $\left(u_{1},\ldots ,\ u_k,\ v_{1},\ldots ,\ v_m\right)$ is any extension of our sublist to a spanning list of $V.$ Then

1) The augmented list $\left(u_{1},\ldots ,\ u_{k},\ u_{k+1},\ v_{1},\ldots ,\ v_{m}\right)$ is linearly dependent, and

2) One of the $v_{i}$'s can be ejected so that $\left(u_{1},\ldots ,\ u_k,\ u_{k+1},\ v_{1},\ldots ,\ v_{i-1},\ v_{i+1},\ \ldots ,\ v_m\right)$ is still a spanning list.

The augmented list $\left(u_{1},\ldots ,\ u_{k},\ u_{k+1},\ v_{1},\ldots ,\ v_{m}\right)$ is linearly dependent because $u_{k}$ is in the span of the other vectors $\left(u_{1},\ldots ,\ u_{k},\ v_{1},\ldots ,\ v_{m}\right)$, which is a spanning list for all of $V$ by hypothesis. By the redundancy lemma, one of these vectors is in the span of the vectors before it. This vector cannot be one of the $u_i$'s because those vectors are linearly independent, so it must be a $v_i.$ Use the redundancy lemma again to remove that vector, keeping the span the same.

Suppose $\left(u_{1},\ \ldots ,\ u_{n}\right)$ is a linearly independent list and $\left(v_{1},\ \ldots ,\ v_{m}\right)$ is a spanning list of vectors in $V.$ Then

1) (Extension) The list $\left(u_{1},\ \ldots ,\ u_n\right)$ can be extended to a spanning list $\left(u_{1},\ \ldots ,\ u_n,\ v_{i_{1}},\ldots ,\ v_{i_k}\right)$ of length $n$ using coming from $\left(v_{1},\ \ldots ,\ v_m\right).$

2) (Comparison) Subsequently, $n≤m.$

(by induction on $n$)

Base case ($n=0$): If $n=0$, then $\left(u_{1},\ \ldots ,\ u_{n}\right)=\left(\ \right)$ is the empty list. The proof follows immediately because the list $\left(v_{1},\ \ldots ,\ v_{m}\right)$ is the extension in question. Induction step: Let $n∈N.$ Suppose $\left(u_{1},\ \ldots ,\ u_{n},\ u_{n+1}\right)$ is a linearly independent list of vectors in $V$ and $\left(v_{1},\ldots ,\ v_{m}\right)$ is a spanning list of vectors in $V.$ The induction hypothesis tells us that for the linearly independent list $\left(u_{1},\ldots ,\ u_{n}\right)$ of vectors in $V$ and the spanning list $\left(v_{1},\ldots ,\ v_{m}\right)$ for $V$, there exists a spanning list $\left(u_{1},\ \ldots ,\ u_{n},\ v_{i_{1}},\ \ldots ,\ v_{i_{k}}\right)$ for $V$, where $v_{i_{1}},\ldots ,\ v_{i_{k}}\in V$ and $k=m-n.$ Applying the insertion lemma, the list $\left(u_{1},\ldots ,\ u_k,\ u_{k+1},\ v_n,\ \ldots ,\ v_m\right)$ is linearly dependent (because the other vectors span $V$, so $u_{k+1}$ is in their span), and we can remove a $v_{i_j}$ without changing the span. Note that this forces there to be at least one $v_{i_j}$ still in the list that can be removed so that the list $\left(u_{1},\ \ldots ,\ u_k,\ u_{k+1},\ v_{i_{1}},\ \ldots ,\ v_{i_j-1},\ v_{i_j+1},\ v_{i_k}\right)$ of the same length also spans $V$, subsequently making $n≤m.$ Remark: The comment that a $v_{i_j}$ must still be present is the key idea for why we cannot run out of vectors in the list of $v$'s, making this the key check for the list lengths.

Any two bases of a finite dimensional vector space have the same length.

For any two bases are, by definition, linearly independent spanning lists. So the length of each (linearly independent) list is bounded above by the length of the other (spanning) list.

A list $v_{1},\ \ldots ,\ v_{n}\in V$ of vectors is a basis of $V$ if and only if every $v∈V$ can be written uniquely in the form

where $c_{1},\ldots ,\ c_n\in \mathbb{F}.$

$\Rightarrow$: The existence part comes from the fact that our list is a spanning list. The uniqueness part comes from linear independence.

$\Leftarrow$: The existence part implies we have a spanning list. Furthermore, the uniqueness of a linear combination to obtain $0$ means they are linearly independent.

Every subspace of every finite-dimensional vector space is finite-dimensional.

Consider the largest linearly independent list of the given subspace. Such a list must exist, because for any spanning list of our vector space of size $n,$ linearly independent lists in our vector space are bounded above by $n.$

Claim: A maximal linearly independent list in our subspace must be a spanning list. Proof: If not, then there is a vector outside its span in the subspace, and adding it to the list would also be linearly independent, violating the maximality of our linearly independent list's size.

Every spanning list contains a basis.

(Proof idea)

Use the redundancy lemma to remove redundant vectors without changing the span. Do this until no more can be removed in this way, i.e. the remaining list is linearly independent.

Every finite-dimensional vector space has a basis.

Apply the previous lemma to a spanning list of the space in question.

For every F.D.V.S. $V$ and every subspace $U⊆V$, $\dim\left( U \right) \leq \dim⁡(V).$

A basis for $U$ is a linearly independent list (by definition) in $U.$ This is the same as linear independence in $V,$ so it is bounded by every basis of $V.$

If $\dim \left( V \right)=n$, then any list of linearly independent vectors of length $n$ in $V$ is a basis for $V.$

Let $\dim \left( V \right)=n$ and $v_{1},\ldots ,\ v_{n}$ linearly independent vectors in $V.$ It remains to prove that this list is also a spanning list. So by contrapositive, suppose there is a vector not in the span of these vectors, call it $v_{n+1}.$ We argue that the list $v_{1},\ldots ,\ v_{n},\ v_{n+1}$ is also linearly independent. For if it weren't, then the linear independence lemma tells us one of the vectors is in the span of the ones before it. And if that vector is one of the first $n$ vectors then the original list would not be linearly independent. But that just leaves the last vector and we just supposed that it was not in the span of the vectors before it. Now, since this longer list is linearly independent, we must have a linearly independent list longer than the dimension of $V$, which contradicts the comparison lemma.

If $U$ is a subspace of $V$ and $\dim \left( U \right)=\dim⁡(V)$ then $U=V.$

If $B=(u_{1},\ \ldots ,\ u_{n})$ is a basis for $U$ and $V$ has dimension $n$, then $B$ is a linearly independent list with the "right length", so it is a basis. Thus, $U=\text{span}\left(B\right)=V.$

If $V$ is a F.D.V.S. then every spanning list of $V$ of length $dim⁡(V)$ is a basis.

If any spanning list of length $n=dim⁡(V)$ were not a linearly independent list, then one of the vectors in the list could be dicarded without changing the span (by the linear dependence lemma). Thus, we would have a smaller spanning list than $n$, which is a contradiction.

If $U$ and $W$ are subspaces of a finite-dimensional vector space, then

Suppose $U, W$ are subspaces of a F.D.V.S. $V.$ Let $\left(v_{1},\ldots ,\ v_\ell \right)$ be a basis for $U \cup W.$ Extend to a basis $\left(u_{1},\ \ldots ,\ u_{k},\ v_{1},\ldots ,\ v_\ell \right)$ for $U$ and extend also to a basis $\left(v_{1},\ldots ,\ v_\ell ,\ w_{1},\ldots ,\ w_{m}\right)$ for $W.$ It suffices to show that the list $\beta =\left(u_{1},\ldots ,\ u_{k},\ v_{1},\ldots ,\ v_\ell ,\ w_{1},\ldots ,\ w_{m}\right)$ is a basis for $U+W$, since $\dim \left(U+W \right)=k+\ell +m$ while $\dim \left( U \right) + \dim \left( W\right) - \dim \left( U\cup W \right) = \left(k+\ell \right)+\left(\ell +m\right)-\ell =k+\ell +m$ would follow.

Claim 1: $β$ is a spanning set. Proof: Let $v=u+w∈U+W$, where $u∈U$ and $w∈W$ and express each as linear combinations of their bases: $U=c_{1}u_{1}+\ldots +c_ku_k+d_{1}v_{1}+\ldots +d_\ell v_\ell$ and $w=f_{1}v_{1}+\ldots +f_\ell v_\ell +g_{1}w_{1}+\ldots +g_mw_m.$ Then

is a linear combination of $β.$