Show that there are vectors to get a basis

[mathmari]

Hey!

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)

 

[I like Serena]

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)

 

[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)

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)

 

[I like Serena]

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)

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)

 

[mathmari]

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)

 

[I like Serena]

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)

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)

 

[mathmari]

Yep. (Nod)

Is this a strong induction on $\ell$ ? (Wondering)

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)

 

[I like Serena]

Is this a strong induction on $\ell$ ?

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

So we add just one extra vector, right?

Yep. (Nod)

 

[mathmari]

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)

 

[I like Serena]

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)