# Show that there are vectors to get a basis

#### mathmari

##### Well-known member
MHB Site Helper
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?

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey mathmari !!

If $k=m$ then we are done, aren't we?
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?

#### mathmari

##### Well-known member
MHB Site Helper
If $k=m$ then we are done, aren't we?
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?
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

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.

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$.

#### mathmari

##### Well-known member
MHB Site Helper
Yep.

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

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$.
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)$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

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)$?

#### mathmari

##### Well-known member
MHB Site Helper
Is this a strong induction on $\ell$ ?

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)$?
So we add just one extra vector, right?

Staff member

#### mathmari

##### Well-known member
MHB Site Helper
Not really.
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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?
I was thinking of the following proof by induction.

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.

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.