0

If $W$ is a subspace of a finite dimensional vector space $V$, every linearly independent subset of $W$ is finite and is part of a (finite) basis for $W$.

Rephrasing Theorem to my taste:

If $W\leq V$, $\mathrm{dim}(V)=n\in \Bbb{N}$, $S_0\subseteq W$ is linearly independent, then $\exists B\subseteq W$ such that $B$ is a finite basis of $W$ and $S_0\subseteq B$.

Proof of first part: $S_0\subseteq W\subseteq V$ is linearly independent. By theorem 4 section 2.3, $|S_0|\leq n$. Thus $S_0$ is finite. Why Hoffman used set $S$ with $S_0\subseteq S\subseteq W$ and $S$ is independent? Is it necessary?

Proof of second part: Now we construct finite basis of $W$ from $S_0$. Let me known if I understand proof correctly, $\exists 1\leq m\leq \mathrm{dim}(V)=n$ such that $\mathrm{span}(S_m)=W$. Assume towards contradiction, $\exists m\gt n$ such that $\mathrm{span}(S_m)=W$. $S_m$ is independent by construction. By theorem 4 section 2.3, $m\leq|S_m|\leq \mathrm{dim}(V)= n$. So $m\leq n$. Which contradicts our initial assumption of $m\gt n$. Another slightly equivalent way to reach contradiction, $\exists m\gt n$ such that $\mathrm{span}(S_m)=W$. It’s easy to check $m\leq |S_m|$. So $n\lt m\leq |S_m|$. By contrapositive of theorem 4 section 2.3, $S_m$ is dependent. Thus we reach contradiction. Am I right?

Can we make argument more “concrete”? in a sense, we don’t use sentence like “if we continue in this way , then(in not more than dim$(V)$ steps) we reach a set $S_m=S_0\cup \{\beta_1,…,\beta_m\}$ which is a basis of $W$”. My Hypothesis: We claim, $\exists 1\leq m\leq \mathrm{dim}(V)$ such that $S_m=S_0\cup \{\beta_1,…,\beta_m\}$ is linearly independent and span $W$. But we haven’t defined $\{\beta_1,…,\beta_m\}$ and existence of each $\beta_i$ depends on $\beta_{i-1}$, i.e. if $\mathrm{span}(S_{i-1})\neq W$.

Edit: In hindsight, I would prove second part in following way, claim: $\exists 1\leq m\leq \mathrm{dim}(V)=n$ such that $\mathrm{span}(S_m)=W$. Proof: Assume towards contradiction, $\nexists 1\leq m\leq \mathrm{dim}(V)=n$ such that $\mathrm{span}(S_m)=W$, or equivalently $\forall 1\leq m\leq \mathrm{dim}(V)=n$ we have $\mathrm{span}(S_m)\neq W$. In particular, $\mathrm{span}(S_n)\neq W$. So $\exists \beta_{n+1}\in W$ such that $\beta_{n+1}\notin \mathrm{span}(S_n)$. $S_n=S_0 \cup \{\beta_1,…,\beta_n\}$ is linearly independent by construction. By lemma, $S_{n+1}=S_n\cup \{\beta_{n+1}\}$ is linearly independent.By theorem 4 section 2.3, $|S_{n+1}| \leq n$. But $|S_{n+1}|\geq n+1 \gt n$ by construction . Thus we reach contradiction. I think nature of both proof is different, unedited version of proof, assume $\exists m\in \Bbb{N}$ with $m\gt n$ such that $\mathrm{span}(S_m)=W$. Such $m$ may not exist, if $W$ is countable or uncountable. Edited version of proof, don’t depends on any existence. So I think is more precise.

We can make an observation, if $S_0\geq 1$, then $m\lt \mathrm{dim}(V)=n$, instead of $m\leq \mathrm{dim}(V)=n$.

user264745
  • 4,143
  • Your rephrasing of the result uses the notion of dimension (as opposed to the more basic "finite dimensional"), but I think this result is usually proved before that notion is defined (because some facts like the one considered here are necessary in order to define dimension in the first place). So I think this might not be a valid approach. – Marc van Leeuwen Jun 26 '22 at 14:43
  • @MarcvanLeeuwen In Hoffman’s linear algebra, dimension is defined for finite dimensional vector space and is denoted by dim$(V)\in \Bbb{N}$. In this book, theorem 5 is given after defining dimension of a finite dimensional vector space. – user264745 Jun 26 '22 at 15:05

2 Answers2

0

The first paragraph is more than just proving that $S_0$ is finite. The authors are setting up the second paragraph by showing that in extending $S_0$ to a basis $S_m$ (which is an $S$) for $W$, set $S_m$ is finite and therefore can be obtained in not more than $\dim V$ steps. That is why the authors' "If we continue in this way, . . ." actually is concrete.

I read through your edited version of the proof of the second part. Your proof looks OK to me. I, however, prefer direct proofs, like the one given in the text, over proofs by contradiction.

user0
  • 3,247
  • Thank you for answer. Existence of $S$ such that $S_0\subseteq S\subseteq W$ is a thing, that need to be prove, it’s not automatic. One take simply $S=S_0$, that works out fine. I agree, $S_m$ is finite. But that don’t show span$(S_m)=W$. And I use contradiction to show indeed, in not more than dim$(V)$ steps, span$(S_m)=W$. We are having essentially similar conversation as in this post. For you claim is so ”obvious” that it don’t need proof but to prove a claim I use contradiction (what if $S_m$ don’t span $W$ even after dim$(V)$ steps). – user264745 Jun 26 '22 at 19:23
  • @user264745 In the second paragraph of the authors' proof, whether or not $S_0,S_1,\dots,S_m$ span $W$ is needed only to determine whether to invoke the lemma. The final result that $S_m$ is a basis for $W$ does not directly require knowledge that $S_m$ spans $W$. To prove that $S_m$ is a basis for $W$, it is sufficient to know that $S_m$ is linearly independent (by the lemma) and that any basis for $W$ is finite by (Corollary 1 to Theorem 4). – user0 Jun 27 '22 at 14:51
  • Why is it sufficient to know $S_m$ is independent and any basis of $W$ is finite? Also we don’t know yet $W$ is finite dimensional. That’s what we are trying to prove, don’t we? – user264745 Jun 27 '22 at 15:18
  • @user264745 The authors are not trying to prove that $W$ is finite dimensional (that is Corollary 1). They are trying to prove that $S_0$ is part of a basis for $W$. If any basis of $W$ is finite, which the authors prove in the first paragraph because $S$ contains no more than $\dim V$ elements, then the authors' step-by-step construction of a basis $S_m$ for $W$ stops after $m$ steps. The lemma guarantees that $S_m$ is linearly independent. By construction, $S_0\subseteq S_m$. Thus, $S_0$ is part of a basis for $W$. The bottom line is that both the authors' and your proofs are good. – user0 Jun 28 '22 at 17:40
  • Thank you for saying my proof is good . I want to rebuttal your comment. You said, “If any basis of $W$ is finite…..”. Well we don’t know the existence of any basis of $W$. Even if we use arbitrary finite basis $B$ of $W$(assuming finite basis exists), that don’t guarantee $S_0\subseteq B$. So we have to construct basis using only $S_0$ information. And to show something is basis, we have to show it span $V$ and it is independent. – user264745 Jun 28 '22 at 18:21
0

In past few days I have made some progress. I will try to show why it is not possible to write “concrete” proof.

Theorem 5 Corollary 2 Section 2.3: If $V$ is a finite-dimensional vector space with $\mathrm{dim}(V)=n\in \Bbb{N}$, $S_0\subseteq V$ is linearly independent, then $\exists B\subseteq V$ such that $B$ is finite basis of $V$ and $S_0\subseteq B$.

My attempt: By theorem 4 section 2.3, $|S_0|\leq \mathrm{dim}(V)=n$. Let $|S_0|=k$ and $m=n-k\geq 0$. Claim: $\forall 0\leq j\leq m$, $P(j)$: $\exists S_j\subseteq V$ such that $S_j$ is independent and $|S_j|=k+j$. Proof: We use mathematical induction approach. Base case: $j=0$. By our assumption, $S_0$ is independent and $|S_0|=k+0=k$. Inductive case: Assume $\exists S_{j-1}$ for some $1\leq j\leq m$ such that $S_{j-1}$ is independent and $|S_{j-1}|=k+j-1$. Since $j\leq m$, we have $k+j-1\leq k+ m-1$. So $|S_{j-1}|\leq k+m-1=n-1\lt n$. Since $|S_{j-1}|\lt n$, we have $\mathrm{span}(S_{j-1})\neq V$, by theorem 4 corollary 2 section 2.3. So $\exists \beta_j\in V$ such that $\beta_j \notin \mathrm{span}(S_{j-1})$. Define $S_j:=S_{j-1}\cup \{\beta_{j}\}$. By inductive hypothesis, $S_{j-1}$ is independent. By lemma, $S_j$ is independent. $|S_j|=|S_{j-1}|+1=k+j$. By principle of mathematical induction, $\forall 0\leq j\leq m$, $\exists S_j\subseteq V$ such that $S_j$ is independent and $|S_j|=k+j$.

So $S_m$ is independent and $|S_m|=k+m=k+(n-k)=n$. By theorem 4 corollary 2 section 2.3, $\mathrm{span}(S_m)=V$. By construction of $\{S_j\}$, it’s easy to check $S_{j-1}\subseteq S_j$, $\forall 1\leq j\leq m$. In particular, $S_0\subseteq S_m$. Thus $S_m$ is finite basis of $V$ and $S_0\subseteq S_m$. Our desired result.

IMO, the reason why proof of theorem 5 corollary 2 section 2.3, is “concrete” but proof of theorem 5 section 2.3 is not, because in former case we have $V$ is $n$-dimensional vector space. In latter case, we don’t even know if $W$ is finite-dimensional vector space. So taking about $\mathrm{dim}(W)$, don’t make sense.

user264745
  • 4,143