Show that there are vectors to get a basis

In summary: Thinking)Shouldn't we extend the independent set $(u_1, \ldots , u_\ell)$ from the induction hypothesis to the independent set $(u_1, \ldots , u_\ell, w)$?... (Thinking)Yes, that makes more sense. (Agree)
  • #1

mathmari

Gold Member
MHB
5,049
7
Hey! :eek:

Let $1\leq k,m,n\in \mathbb{N}$, $V:=\mathbb{R}^n$ and $U$ a subspace of $V$ with $\dim_{\mathbb{R}}U=m$. Let $u_1, \ldots , u_k\in U$ be linear independent. Show that there are vectors $u_{k+1}, \ldots , u_m\in U$ such that $(u_1, \ldots , u_m)$ is a basis of $U$.

Hint: Use the following two statements. Convince that $\ell:=m-k\geq 0$ and use induction on $\ell$. Statement 1:
Let $1\leq k\in \mathbb{N}$ and $v_1, \ldots v_k, w\in V$.
  1. $1\leq m\in \mathbb{N}$ and $w_1, \ldots , w_m\in V$ such that $\text{Lin}(v_1, \ldots , v_k)=\text{Lin}(w_1, \ldots , w_m)$ then it holds that $\text{Lin}(v_1, \ldots , v_k, w)=\text{Lin}(w_1, \ldots , w_m, w)$.
  2. If the vectors $v_1, \ldots , v_k$ are linear independent and $w\notin \text{Lin}(v_1, \ldots , v_k)$ then also the vectors $v_1, \ldots , v_k, w$ are linear independent.

Statement 2:
Let $U\leq_{R}V$ and $W\leq_{R}V$ such that $W\subseteq U$. Then it holds that $\dim_RW\leq \dim_RU$ and the equality iff $W=U$. So to use Statement 1 we have to show that $u_{k+1}, \ldots , u_m\notin \text{Lin}(u_1, \ldots , u_k)$ and then we apply the Statement 1 using induction or how do we have to start? (Wondering)
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
Hey mathmari!

If $k=m$ then we are done, aren't we? (Wondering)
So let's assume that $k<m$.

Base case
$(u_1, \ldots , u_k)$ cannot be a basis of $U$ can it?
Because if it were then the dimension of $U$ would be $k$ instead of $m$, and we just assumed that $k<m$.
So there must be a vector $w$ in $U$ that is not an element of the linear span of $(u_1, \ldots , u_k)$, mustn't there?
What we can do with that element? (Thinking)
 
  • #3
Klaas van Aarsen said:
If $k=m$ then we are done, aren't we? (Wondering)
So let's assume that $k<m$.

Base case
$(u_1, \ldots , u_k)$ cannot be a basis of $U$ can it?
Because if it were then the dimension of $U$ would be $k$ instead of $m$, and we just assumed that $k<m$.
So there must be a vector $w$ in $U$ that is not an element of the linear span of $(u_1, \ldots , u_k)$, mustn't there?
What we can do with that element? (Thinking)

From the second part of statement 1 we get that $u_1, \ldots , u_k,w$ are linear independent.
So now we consider the linear span of $(u_1, \ldots , u_k,w)$, or not?
At the base case we have that $\ell=m-k=1$, or not? So we have to add just one vector to get a basis, which is $w$, right? (Wondering)
 
  • #4
mathmari said:
From the second part of statement 1 we get that $u_1, \ldots , u_k,w$ are linear independent.
So now we consider the linear span of $(u_1, \ldots , u_k,w)$, or not?

Yep. (Nod)

mathmari said:
At the base case we have that $\ell=m-k=1$, or not? So we have to add just one vector to get a basis, which is $w$, right?

Hmm... not sure if we can make it work like that. (Thinking)

I had the idea that for the inductive step we would assume that we could extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_\ell)$ with vectors that are all in $U$ and with $k\le \ell < m$. (Thinking)
 
  • #5
Klaas van Aarsen said:
Yep. (Nod)

Hmm... not sure if we can make it work like that. (Thinking)

I had the idea that for the inductive step we would assume that we could extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_\ell)$ with vectors that are all in $U$ and with $k\le \ell < m$. (Thinking)

So do you mean that at the base case we extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_k, w)$ then at the inductive hypothesis we assume that we can extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_\ell)$ with $k\le \ell < m$ and at the inductive step we extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_m)$ ? (Wondering)
 
  • #6
mathmari said:
So do you mean that at the base case we extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_k, w)$ then at the inductive hypothesis we assume that we can extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_\ell)$ with $k\le \ell < m$

Yep. (Nod)

mathmari said:
and at the inductive step we extend the independent set $(u_1, \ldots , u_k)$ to the independent set $(u_1, \ldots , u_m)$ ?

Shouldn't we extend the independent set $(u_1, \ldots , u_\ell)$ from the induction hypothesis to the independent set $(u_1, \ldots , u_\ell, w)$? (Wondering)
 
  • #7
Klaas van Aarsen said:
Yep. (Nod)

Is this a strong induction on $\ell$ ? (Wondering)
Klaas van Aarsen said:
Shouldn't we extend the independent set $(u_1, \ldots , u_\ell)$ from the induction hypothesis to the independent set $(u_1, \ldots , u_\ell, w)$? (Wondering)

So we add just one extra vector, right? (Wondering)
 
  • #8
mathmari said:
Is this a strong induction on $\ell$ ?

Not really. (Shake)
What makes you think so?

mathmari said:
So we add just one extra vector, right?

Yep. (Nod)
 
  • #9
Klaas van Aarsen said:
Not really. (Shake)
What makes you think so?

I thought so because we took $k\le \ell < m$. Could you explain to me further what we assume at the inductive hypothesis? How many vectors to we add to the span? (Wondering)
 
  • #10
mathmari said:
I thought so because we took $k\le \ell < m$. Could you explain to me further what we assume at the inductive hypothesis? How many vectors to we add to the span? (Wondering)

I was thinking of the following proof by induction. (Thinking)

Base case
The set $(u_1,\ldots,u_\ell)$ with $\ell=k \le m$ is a linearly independent set.

Inductive hypothesis
We can extend the independent set $(u_1,\ldots,u_k)$ to an independent set $(u_1,\ldots,u_\ell)$ with all vectors in $U$ and with $k\le\ell\le m$.

Inductive step
If $\ell = m$ we are done as we have the desired set of vectors.
Otherwise $\ell<m$ so there must be a vector $w\in U$ that is not in the linear span of $(u_1,\ldots,u_\ell)$, since the dimension of $U$ is greater than $\ell$.
So we can take $u_{\ell+1}=w$ and $(u_1,\ldots,u_\ell,u_{\ell+1})$ is then an independent set with all vectors in $U$ and with $k\le\ell+1\le m$.

The fact that we can keep extending the independent set until $\ell=m$ completes the proof. (Emo)

Note that we take only 1 step at a time, and in particular we do not use that $(u_1,\ldots,u_{\tilde\ell})$ with $k\le\tilde\ell<\ell$ is an independent set, which would otherwise make it strong induction. (Nerd)
 

Similar threads

Replies
3
Views
1K
Replies
24
Views
942
  • Linear and Abstract Algebra
Replies
3
Views
934
  • Linear and Abstract Algebra
Replies
10
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
823
  • Linear and Abstract Algebra
Replies
2
Views
924
  • Linear and Abstract Algebra
Replies
1
Views
787
  • Linear and Abstract Algebra
Replies
15
Views
957
  • Linear and Abstract Algebra
Replies
3
Views
871
  • Linear and Abstract Algebra
Replies
7
Views
1K
Back
Top