LEC ALG1 8

Recall

We showed in L7 that a spanning set in ${\mathbb{R}}^n$ must be of size at least $n$, and a linearly independent set in ${\mathbb{R}}^n$ cannot have more than $n$ elements. We defined a basis to be a linearly independent spanning set, and concluded that any basis of ${\mathbb{R}}^n$ must have cardinality $n$. Then, we asked the question “Does every vector space $V$ have a basis?“. We discussed two strategies to construct a basis for any arbitrary vector space:

1. Start with an empty set, and keep adding vectors (while preserving linear independence) till $V$ is spanned. However, we do not know if this process will ever terminate.
2. Start with any (finite) spanning set of $V$, and keep removing (redundant) vectors till you reach a basis. However, we do not know if $V$ has a spanning set of finite size to begin with.

We observed that both approaches hinge on $V$ having a finite spanning set. We turned this property into a definition, and called $V$ a finite dimensional vector space (fdvsp) if it has a finite spanning set.

In this lecture, we will prove that every fdvsp has a basis, and that the cardinality of a basis is an invariant of a fdvsp.

---

Every fdvsp has a basis

Theorem 74.1(Theorem).

Every fdvsp has a basis.

a005a3

Strategy 1: Augment a linearly independent (or empty) set

Let $V$ be a fdvsp. Any linearly independent set $I\in V$ can be extended to give a basis of $V$. The existence of a finite spanning set $S\in V$ is guaranteed by definition. Keep adding vectors from $S$ to $I$ that increase the span until you exhaust the spanning set.

Proof.

Define $I_0:=I$.
Let $S:=\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_k\}$ be a spanning set in $V$.
Define

$$I_j:=\{\begin{array}{ll}{I}_{j-1}\cup \{{\mathbf{u}}_j\}& {\mathbf{u}}_j\notin \text{Span }{I}_{j-1}\\ I_{j-1}& {\mathbf{u}}_j\in \text{Span }{I}_{j-1}\end{array}$$

Each $I_j$ is linearly independent, and $\text{Span }{I}_k=\text{Span }S=V$.
Thus, $I_k$ is a basis.□

You could also begin from an empty set, if you’d like. If using the “span” of an empty $I_0$ to define $I_1$ troubles you, just make $I_0$ have a single non zero vector.

Strategy 2: Prune a spanning set

Take a finite spanning set $S$ of $V$ and keep deleting unnecessary vectors till what remains is linearly independent. This process is guaranteed to terminate before we reach the empty set, since the empty set is not a spanning set, and we are preserving the spanning property on every deletion.

---

Cardinality of basis is invariant of an fdvsp

Theorem 74.2(Theorem).

Any two bases of an fdvsp have same cardinality, i.e, the cardinality of a basis is an invariant of an fdvsp.

d11967

Note

Theorem 2 does not say anything about the existence of bases, only that if bases exist, they must have the same cardinality. We proved Theorem 1 for a reason.

We have already shown that any basis of ${\mathbb{R}}^n$ has $n$ vectors. This is a result of pivot analysis. Now, we will show an analogue for a general fdvsp. Again, two strategies:

1. Use first principles of vector spaces to prove the result.
2. Show that every fdvsp is isomorphic to ${\mathbb{R}}^n$.

Strategy 1: First principles

Lemma 74.3(Steinitz Exchange).

Let $\mathbf{v}\in S\subset V$, where $V$ is a fdvsp and $S$ is of finite cardinality, and $\mathbf{u}\in V$ such that $\mathbf{u}\in \text{Span }S$. Suppose $\mathbf{u}\notin \text{Span }(S\setminus \{\mathbf{v}\})$, then $\mathbf{v}\in \text{Span }((S\setminus \{\mathbf{v}\})\cup \{\mathbf{u}\})$.

Proof.

Let $S=\{\mathbf{v},{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$
Since $\mathbf{u}\in \text{Span }S$,

$$\mathbf{u}=a\mathbf{v}+\sum _{i=2}^k{a}_i{\mathbf{v}}_i,$$

for some $a,a_i\in \mathbb{R}$.
Also, $a\ne 0$ because $\mathbf{u}\notin \text{Span }(S\setminus \{\mathbf{v}\})$.

$$⟹\frac{1}{a}\mathbf{u}-\sum _{i=2}^k\left(\frac{a_i}{a}\right){\mathbf{v}}_i=\mathbf{v}.$$ □

What this is essentially saying is that you can “exchange” or “replace” $\mathbf{v}$ with $\mathbf{u}$ while conserving the span of $S$ (We can express any linear combination of elements in $S$ as a linear combination of elements in $(S\setminus \{\mathbf{v}\})\cup \{\mathbf{u}\}$ by replacing $\mathbf{v}$ in the linear combination with the expression for $\mathbf{v}$ in terms of $\mathbf{u}$ obtained in the proof above).

Embedding a linearly independent set in a spanning set

Lemma 74.4(Lemma).

If $I:=\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots {\mathbf{u}}_m\}\subset V$ is a finite linearly independent set and $S:=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots {\mathbf{v}}_n\}\subset V$ is a finite spanning set in a fdvsp $V$, and $m\le n$, then, after rearranging $v_j$ if necessary, $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_m,{\mathbf{v}}_{m+1},\dots ,{\mathbf{v}}_n\}$ spans $V$.

Proof.

By induction on$|I|$.
Holds for $|I|=0$, as there are no ${\mathbf{u}}_i$‘s, and $S$ spans $V$.
Assume the result holds for $|I|=m^{\prime }-1$, where $m^{\prime }-1<n$.
$S^{\prime }=\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_{m^{\prime }-1},{\mathbf{v}}_{m^{\prime }},{\mathbf{v}}_{m^{\prime }+1},\dots ,{\mathbf{v}}_n\}$ spans $V$.
Then, ${\mathbf{u}}_{m^{\prime }}={\sum }_{i=1}^{m^{\prime }-1}{c}_i{\mathbf{u}}_i+{\sum }_{j=m^{\prime }}^n{d}_j{\mathbf{v}}_j$. Observe that, since $I$ is linearly independent, some $d_j$ must be non zero, say $d_{m^{\prime }}$, after possibly rearranging the ${\mathbf{v}}_j$‘s. Note that more than one of the $d$‘s may be non zero.

Now, two things can happen:

1. ${\mathbf{u}}_{m^{\prime }}\notin \text{Span }(S^{\prime }\setminus \{{\mathbf{v}}_{m^{\prime }}\})$. We can exchange ${\mathbf{v}}_{m^{\prime }}$ with ${\mathbf{u}}_{m^{\prime }}$ in $S^{\prime }$ while keeping its span unchanged courtesy the Steinitz Exchange Lemma.
2. ${\mathbf{u}}_{m^{\prime }}\in \text{Span }(S^{\prime }\setminus \{{\mathbf{v}}_{m^{\prime }}\})$. This means ${\mathbf{u}}_{m^{\prime }}$ can be expressed as a linear combination of the vectors in $S^{\prime }\setminus \{{\mathbf{v}}_{m^{\prime }}\}$, i.e, $S^{\prime }\setminus \{{\mathbf{v}}_{m^{\prime }}\}$ spans $V$. Obviously, tacking on ${\mathbf{u}}_{m^{\prime }}$ isn’t going to change that.

Thus, either way, we can swap ${\mathbf{v}}_{m^{\prime }}$ with ${\mathbf{u}}_{m^{\prime }}$ in $S^{\prime }$ while maintaining the spanning property of $S^{\prime }$. We have shown that $S^{\prime \prime }=\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_{m^{\prime }-1},{\mathbf{u}}_{m^{\prime }},{\mathbf{v}}_{m^{\prime }+1},\dots ,{\mathbf{v}}_n\}$ spans $V$.□

Linearly independent sets cannot be larger than spanning sets

Lemma 74.5(Lemma).

If $I:=\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots {\mathbf{u}}_m\}\subset V$ is a finite linearly independent set and $S:=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots {\mathbf{v}}_n\}\subset V$ is a finite spanning set in a fdvsp $V$, then $|I|\le |S|$.

Proof.

Assume$m=n+k$ for some $k>0$. From the previous lemma, $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_n\}$ must be a spanning set (a subset of a linearly independent set is linearly independent). This implies that ${\mathbf{u}}_{n+1},\dots ,{\mathbf{u}}_k$ can be expressed as a linear combination of ${\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_n$, which implies $I$ cannot be linearly independent (contradiction!). Consequently, we must have $m\le n$.□

Finally, Thm 2

Let $B_1$ and $B_2$ be bases of cardinality $n$ and $m$ respectively.
Since $B_1$ is linearly independent, and $B_2$ is a spanning set, $n\le m$.
Since $B_2$ is linearly independent, and $B_1$ is a spanning set, $m\le n$.
Thus, $m=n$.

Strategy 2: Exploit previous work on ${\mathbb{R}}^n$

Isomorphisms

Observe: A basis “defines” a “coordinate system” on the fdvsp $V$. How? Any $\mathbf{v}\in V$ can be written uniquely as a linear combination of basis vectors.

Thus, if we fix the order in which the elements of a basis $B=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\}$ are listed, then $(c_1,c_2,\dots ,c_n{)}^T\in {\mathbb{R}}^n$ is the coordinate vector of $\mathbf{u}={\sum }_{i=1}^n{c}_i{\mathbf{v}}_i$ in $V$.

Definition 74.6(Definition).

Suppose $V$ and $W$ are vector spaces. A function $f:V\to W$ is called an isomorphism is

1. $f$ is a bijection
2. $f({\mathbf{v}}_1+{\mathbf{v}}_2)=f({\mathbf{v}}_1)+f({\mathbf{v}}_2),f(\lambda \mathbf{v})=\lambda f(\mathbf{v})$ for all $\lambda \in \mathbb{R}$, $\mathbf{v},{\mathbf{v}}_1,{\mathbf{v}}_2\in V$, i.e, $f$ is a linear map.

Remark 74.7(Remark).

If $f$ is an isomorphism, so is $f^{-1}$. (If $f$ is bijective, $f^{-1}$ exists, and is a bijection. Property 2 can be easily proved.)

If there is an isomorphism from $V$ to $W$, we say that $V$ and $W$ are isomorphic ($V\cong W$).

Also, if $f:V\to W$ is an isomorphism, then any true assertion in $V$ about its vector space structure remains true after transport by $f$ to $W$ and vice versa.

Let $f$ be a linear map from ${\mathbb{R}}^c$ to ${\mathbb{R}}^r$. We know that $f$ can be represented as an $r\times c$ matrix $A$. If $f$ is an isomorphism, $f$ must be bijective, and it must be the case that $c=r$ (cuz pivots).
Thus, ${\mathbb{R}}^n\cong {\mathbb{R}}^k⟺n=k$.

Proof of Thm 2

Let $V$ be a fdvsp.
Let $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\}$ and $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_k\}$ be bases of $V$.
Now, there exist isomorphisms $f:{\mathbb{R}}^n\to V$, defined by $f\left((c_1,c_2,\dots ,c_n{)}^T\right)=\sum c_i{\mathbf{v}}_i$ and $g:{\mathbb{R}}^k\to V$ defined by $g((d_1,d_2,\dots ,d_k{)}^T)=\sum d_i{\mathbf{u}}_i$.
It follows that $g^{-1}f:{\mathbb{R}}^n\to {\mathbb{R}}^k$ is an isomorphism.
Thus, $n=k$.