Welcome to our community

Be a part of something great, join today!

Show that there are vectors to get a basis

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,036

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
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)