1

In this video lecture, time stamp 19:20 - 24:30. Professor show proof of following claim: (Extend to basis) Every linearly independent list of vectors in a finite dimensional vector space can be extended to a basis of the vector space.

I known one approach to prove this claim. Here is my attempt, but I still feel confuse on my proof. I would really appreciate if you give some feedback.

Apparently professor proved this claim using different approach (from I known). Professor Proof: Let $\{v_1,…,v_m\}$ be linearly independent. Let $\{w_1,…,w_n\}$ is basis of $V$. If $w_1\in \mathrm{span}(v_1,…,v_m)$, set $B_1=\{v_1,…,v_m\}$. If $w_1\notin \mathrm{span}(v_1,…,v_m)$, set $B_1=\{v_1,…,v_m,w_1\}$. $w_j\in \mathrm{span}(B_{j-1})$, do nothing. If $w_j\notin \mathrm{span}(B_{j-1})$, set $B_j=B_{j-1}\cup \{w_j\}$. At step $n$, $V=\mathrm{span}(B_n)$, $B_n$ is linearly independent, so basis.

I don’t know what professor did. You can check video(I have given time stamp) for complete context surrounding the proof. Proof seems extremely handwavy. In my proof, I constructed basis without any help of other(existing) basis, unlike $\{w_1,…,w_n\}$. Of course I proved it for subspace, but proof is essentially same for any vector space, so no modification required. Please help me in completing details of professor proof. I will have two approach in my arsenal to prove this claim(extend to basis).

user264745
  • 4,143
  • It's not handwavy, it's an argument in the style of mathematical induction. Doesn't it pretty plainly say that any l.i. set can be completed to one with $n$ elements? – rschwieb Jun 24 '22 at 17:13
  • @rschwieb you have hindsight 2020. You know the complete proof. – user264745 Jun 24 '22 at 17:15
  • Do you already understand that all bases (of a finite-dimensional vector space) have the same dimension? And that every vector space has a basis? – Brian Tung Jun 24 '22 at 17:19
  • I do think it's a little weird to start with that basis of $w_i$'s. You probably did it the way of just plucking new basis elements out of what wasn't generated. Either way gets the job done I suppose. – rschwieb Jun 24 '22 at 17:21
  • @BrianTung yup. I know in finite dimensional vector space any two bases have same cardinality(finite). I don’t know the proof of every vector space have basis. – user264745 Jun 24 '22 at 17:21
  • You don't need it for every vector space, though, just for finite-dimensional vector spaces, right? The full version needs the axiom of choice (possibly countable if the vector space has countable dimension). – Brian Tung Jun 24 '22 at 17:24
  • @BrianTung yes. Actually I have seen it’s proof, that proof uses axiom of choice. I haven’t studied axiom of choice. So I didn’t read complete proof. – user264745 Jun 24 '22 at 17:27
  • @rschwieb First of all, I don’t why we want $w_1\in \mathrm{span}(v_1,…,v_m)$? If you can show your version of complete proof. It will help me a lot! – user264745 Jun 24 '22 at 17:29
  • @rschwieb if you see my this post, we’ll see where I’m having difficulty with and that is the reason why I said Professor proof is handwavy, even using mathematical induction. – user264745 Jun 24 '22 at 17:32
  • @user264745 Hm? If you include $w_i\in span(v_j\mid 1\leq j\leq m)$ then your $B_j$'s will no longer be linearly independent. – rschwieb Jun 24 '22 at 18:37
  • @rschwieb I wrote it without any context or follow up, my bad. My point is that I don’t know what’s going on. – user264745 Jun 24 '22 at 18:39
  • @user264745 He's literally just checking to see which of the $w_i$'s the $v_i$'s don't span. There have to be at least $n-m$ that aren't in the span. Then those $v_i$'s, plus those extra ones of $w$ not in the span make an entire basis. – rschwieb Jun 24 '22 at 18:40
  • @rschwieb Ahhh! I think now I vaguely understand what’s going on. let $v=a_1\cdot w_1+…+a_n\cdot w_n \in V$. Define $A={i\in J_n|w_i\in \mathrm{span}(B_{i-1})}$ and $B={j\in J_n |w_i\notin \mathrm{span}(B_{i-1})}$. If $w_i$ for some $i\in A$, then $w_i=\sum_{i=1}^pb_i\cdot u_i$ ; $u_i \in B_{i-1}$. Basically we want each $w_i$ to be in $B_n$ so that $v\in \mathrm{span}(B_n)$. Thus $V=\mathrm{span} (B_n)$ and $B_n$ is linearly independent by construction. Still I think, in term of “proof based mathematics”, this proof is extremely vague. – user264745 Jun 25 '22 at 08:56

2 Answers2

1

An explicit construction of a list of sequences $B_0,B_1,\ldots,B_n$ is given (while it is not written, $B_0=[v_1,\ldots,v_m]$ is the initial sequence. (Also sequences are written as sets, which they are not; this is just sloppy.) The crux of the proof is to show by induction on $j$ that one has two properties: (1) $B_j$ is an independent sequence of vectors, and (2) $\def\Sp{\operatorname{Span}} \forall i\leq j:w_i\in\Sp(B_j)$. The passage from $j-1$ to $j$ is quite easy when $w_j\in\Sp(B_{j-1})$, and therefore (by construction) $B_j=B_{j-i}$: all you need is distinguish for (2) the cases $i<j$ and $i=j$. The other case ($w_j\notin\Sp(B_{j-1})$ so $B_j=\text{append}(B_{j-1},w_j)$) is only harder for statement (1), where one needs to use that appending to a linearly independent sequence of vectors not in their span always gives another linearly independent sequence of vectors, but that is an important fact that can be proved directly from the definition.

So if one accepts that these properties holds, one obtains for $B_n$ that it is a linearly independent sequence of vectors whose span contains as element each of the $w_i$. But since the span of those $w_i$ is the whole vector space$~V$, the span of $B_n$ must be at least as large, and therefore also all of$~V$. Being both linearly independent and spanning$~V$, the sequence $B_n$ is a basis of$~V$.

Marc van Leeuwen
  • 115,048
  • In beginning I was trying to show $V=\mathrm{span}(B_n)$ by $x\in V=\mathrm{span}(w_1,…,w_n)$. $x=\sum_{i\in J_n}a_i\cdot w_i$ ; $w_i\in \mathrm{span}(B_n)$, $\forall i\in J_n$. So $x\in \mathrm{span}(\mathrm{span}(B_n))$. Why $B_j$ is sequence of vector not sets? If $B_j$ have two same element then $B_j$ is dependent, which is not what we want. Thank you so much for the answer. – user264745 Jun 26 '22 at 18:50
  • Can you please check my proof? – user264745 Jun 26 '22 at 23:16
  • @user264745 Yes, your proof seems OK. That the $B_j$ are finite is kind of obvious because they are elements of the set of finite sequences of vectors; the only operation applied to them is appending a vector at the end, which clearly remains inside this set. That the $B_j$ are defined to be sequences rather than sets is (not so much to make what I just said work, but) because in our context a basis (which is what we want) is a sequence, not a set. One wants coordinates for the basis to be a map $V\to K^n$, and for that the basis vectors must appear in a specific order, as in a sequence. – Marc van Leeuwen Jun 27 '22 at 05:20
  • Ohhh! You’re using sequence definition of basis. I have not yet studied ordered basis and coordinate section in Hoffman’s book. Till section 2.3 independent, dependent and span is defined on sets. From context, I assume $K$ is a field, precisely $V$ is a vector space over field $K$. – user264745 Jun 27 '22 at 08:36
0

In this post, I’m just rewriting Professor Marc Van Leeuwen proof.

Claim: $\exists B_0,B_1,…,B_n\subseteq V$ such that each $B_j$ have following three properties: $(1)$ $B_j$ is linearly independent, $(2)$ $w_i\in \mathrm{span}(B_j)$, $\forall 1\leq i\leq j$, and $(3)$ $B_j$ is finite.

Proof: We use mathematical induction approach. Base case: $j=0$. Define $B_0=\{v_1,…,v_m\}$. $B_0$ is independent and finite by our assumption. So $(1)$ & $(3)$ property holds. Since $1\leq i\leq 0$ is false, $(2)$ property holds vacuously. Inductive step: Assume $\exists B_{j-1}$ for $1\leq j\leq n$ such that property $(1)$, $(2)$ & $(3)$ holds. We need to construct $B_j$ such that $(1)$, $(2)$ & $(3)$ property holds. Case$(1)$: If $w_j\in \mathrm{span}(B_{j-1})$, then define $B_j:=B_{j-1}$.By inductive hypothesis, $B_j=B_{j-1}$ is independent and finite. Since $w_j\in \mathrm{span}(B_{j-1})$ and $B_{j-1}$ satisfy $(2)$ property, we have $\forall 1\leq i\leq j$, $w_i\in \mathrm{span}(B_{j-1})$$=\mathrm{span}(B_j)$. Case$(2)$: If $w_j\notin \mathrm{span}(B_{j-1})$, then define $B_j:=B_{j-1}\cup \{w_j\}$. By lemma, $B_j$ is independent. Since $|B_{j-1}|\in \Bbb{N}$, $|B_{j}|=|B_{j-1}|+1\in \Bbb{N}$. So $B_j$ is finite. Since $B_{j-1}$ satisfy $(2)$ property, we have $\forall i\lt j$, $w_i\in \mathrm{span}(B_{j-1})\subseteq \mathrm{span}(B_{j-1}\cup \{w_j\})$$=\mathrm{span}(B_j)$. It’s easy to check, $w_j\in \mathrm{span}(B_{j-1}\cup \{w_j\})$$=\mathrm{span}(B_j)$. Thus $\exists B_j$ such that property $(1)$, $(2)$ & $(3)$ holds in case$(1)$ & case$(2)$. By principle of mathematical induction, $\forall 0\leq j\leq n$, $\exists B_j$ such that property $(1)$, $(2)$ & $(3)$ holds.

So $B_n$ is independent, $\{w_1,…,w_n\}\subseteq \mathrm{span}(B_n)$ and $B_n$ is finite. span$(B_n)$ is a subspace containing $\{w_1,…,w_n\}$. By Hoffman’s definition of subspace, $V=\mathrm{span}(w_1,…,w_n)\subseteq \mathrm{span}(B_n)$. Conversely, $\mathrm{span}(B_n)\subseteq V$ holds trivially. Thus $\mathrm{span}(B_n)=V$. Hence $B_n$ is finite basis of $V$.

One can also start with $B_1$, instead of $B_0$. Base case: $j=1$. If $w_1\in \mathrm{span}(v_1,…,v_m)$, then define $B_1:=\{v_1,…,v_n\}$. If $w_1\notin \mathrm{span}(v_1,…,v_m)$, then define $B_1:=\{v_1,…,v_n\}\cup \{w_1\}$. It’s easy to check, $B_1$ satisfy $(1)$, $(2)$ & $(3)$ property. We can rephrase claim, $\forall j\in J_n$, $P(j)$: $\exists B_j$ such that property $(1)$, $(2)$ & $(3)$ holds.

user264745
  • 4,143
  • 1
    Just a nitpick: as always if you push your base case further up, your induction proof will actually fail to prove the lower cases (which is a pity, especially because they are usually quite trivial). Concretely, if you make $j=1$ your base case, then your proof won't work for $n=0$, that is in $0$-dimensional vector spaces. The "extend basis" statement for such spaces is rather trivial (the only independent sequence or basis possible is empty) so it is a shame to not have proved it. – Marc van Leeuwen Jun 27 '22 at 05:27
  • @MarcvanLeeuwen Yes. You’re right. Before writing my answer, I was thinking the same thing for $0$-dimensional vector space. As you said, only independent sequence or basis possible is empty. Which is kind of trivial. – user264745 Jun 27 '22 at 08:18