0

The Replacement theorem states the following :

Let $V$ be a vector space that is generated by as set $G$ containing exactly $n$ vectors and let $L$ be a linearly independent subset of $V$ containing exactly $m$ vectors. Then $m \leq n$ and there exists a subset $H$ of $G$ containing exactly $n-m$ vectors such that $L \cup H$ generates V.

Understanding the proof is one thing, I am not able to 'digest' the first statement or should I say visualize the first statement.

My question is, Why can't be the $Length$($Linearly\:Independent\: Set$) greater than that of $Length$($Spanning\: Set$) ? ( I am not aware of dimensions yet.)

I understand that $Length$($Basis$) $\leq$ $Length$($Spanning\: Set$), but we are talking about 'any' linearly independent set, how is 'any' linearly independent set dependent on the spanning set ?

In its proof the induction approach is taken which doesn't answer my question.

Can anyone help ?

User9523
  • 2,094

1 Answers1

3

My question is, Why can't be the $Length$($Linearly\:Independent\: Set$) greater than that of $Length$($Spanning\: Set$) ?

(Finite) spanning sets can be as large as you like (well, unless $V$ is finite, in which case the upper limit is all of $V$). If you have a spanning set $S$ and a vector $\mathbf x$ not in $S$, then $S \cup \{\mathbf x\}$ is also a spanning set.

So your question is the same as: $\hphantom{X}$ "Why can't a linearly independent set be as large as I like?"

That's really what the replacement theorem is trying to tell us. Hopefully the discussion below helps.

I understand that $\mathit{Length}(\mathit{Basis}) \leq \mathit{Length}(\mathit{Spanning Set})$ ...

At this stage in your study (before you've encountered dimension and before we've proved the Replacement Theorem), we don't yet know that the statement above is true. A basis $B$ is defined to be a minimal spanning set, i.e. if you remove any vector from $B$, what's left is not a spanning set. For all we know, $V$ might have a basis consisting of $3$ vectors and another basis consisting of $4$ vectors. 'Minimal spanning set' doesn't mean a spanning set whose size is $\le$ any other spanning set.

Revision: stuff you hopefully already understand

Linear independence. The technical definition is a set $L=\{\mathbf v_1,\mathbf v_2,\dots,\mathbf v_n\}$ is linearly independent if the equation $k_1\mathbf v_1 + k_2\mathbf v_2 + \dots + k_n\mathbf v_n=\mathbf 0$ only has the single solution $k_1=k_2=\dots=k_n=0$. The equivalent practical definition is $L$ is linearly independent if you can't write any of its vectors as a linear combination of the others.

This means that any basis has to be linearly independent. Proof follows: a basis is a spanning set that is minimal, i.e. if you toss out any vector it stops being a spanning set. Suppose a spanning set $S=\{\mathbf s_1,\mathbf s_2, \dots, \mathbf s_n\}$ is not linearly independent (i.e. linearly dependent), i.e. you can write one of its vectors $\mathbf s_j$ in terms of the others. Then we don't need to use $\mathbf s_j$ to span all of $V$: every time we write $\mathbf v\in V$ as $\mathbf v= k_1\mathbf s_1+k_2\mathbf s_2+\dots+k_j\mathbf s_j+\dots +k_n\mathbf s_n$ we can replace $\mathbf s_j$ with the LC of the others, so $S \setminus \{\mathbf s_j\}$ is a still spanning set. This means $S$ cannot be not a basis (since we just removed one of its vectors and it still spans $V$). This process of removing vectors keeps going while the set is linearly dependent; it only stops (giving us a basis) when we reach a set that's linearly independent.

The main ideas and a sketch of the proof Replacement Theorem, hopefully easier to understand than your course / text proof.

Setup: We have a vector space $V$ with some basis $G=\{\mathbf g_1,\mathbf g_2,\dots,\mathbf g_n\}$ and any linearly independent set $L=\{\mathbf w_1,\dots,\mathbf w_m\}$.

Exciting conclusion: $m\le n$, and we can find a basis $H=\{\mathbf w_1,\dots,\mathbf w_m, \mathbf h_{m+1}, \dots \mathbf h_n\}$ where the $\mathbf h$'s are enough of the $\mathbf g$'s to fill the basis up to have $n$ elements.

Proof summary:

  • We make a basis $G_0$ with $n$ elements (all $n$ vectors from $G$)
  • We make a basis $G_1$ with $n$ elements ($\mathbf w_1$ and $n-1$ vectors from $G$)
  • We make a basis $G_2$ with $n$ elements ($\mathbf w_1$, $\mathbf w_2$ and $n-2$ vectors from $G$)
  • We make a basis $G_3$ with $n$ elements ($\mathbf w_1$, $\mathbf w_2$, $\mathbf w_3$ and $n-3$ vectors from $G$)
  • ...

This process can stop in two ways:

  1. We run out of elements in $L$, i.e. $m<n$, and we're left with a basis $G_m$ with $n$ elements $(\mathbf w_1, \dots, \mathbf w_m$ and $n-m$ vectors from $G)$
  2. We fill the basis completely with elements of $L$ when we get to $G_n=\{\mathbf w_1,\dots,\mathbf w_n\}$. At this point, there cannot be any other elements in $L$. If there was a vector $\mathbf w_{n+1}$ then we could write $\mathbf w_{n+1} = k_1\mathbf w_1+\dots+k_n\mathbf w_n$ since $G_n$ (like all the other $G$'s) is a basis. But this can't happen because $L$ is linearly independent - we can't write one of its vectors as a LC of the others.

Putting the two stopping cases together means, regardless of what linearly independent set $L$ we started with, $m$ must be $\le n$.

Additional boring detail of getting from basis $G_i$ to basis $G_{i+1}$

$G_0$ is just the original basis we started with, all of $G$.

We make $G_1$ by writing first $\mathbf w_1=k_1\mathbf g_1+\dots +k_n\mathbf g_n$, which we can do since $G_0$ is a basis. We pick some $\mathbf g_i$ where $k_i\ne0$ (Not all of the $k$'s are $0$, otherwise $\mathbf w_1=\mathbf 0$, which can't happen in a linearly independent set.) Then we rearrange to get $\mathbf g_i = $ LC of other $\mathbf g$'s and $\mathbf w_1$. So whenever we write a vector $v$ as a LC of stuff in $G_0$, we would replace $\mathbf g_i$ with other $\mathbf g$'s plus $\mathbf w_1$. This means $\mathbf w_1$ plus the other $n-1$ $\mathbf g$'s form a basis - this is $G_1$.

$G_2$ is similarly made from $G_1$.

Frentos
  • 3,041