I am confused about this proof of this statement in baby Rudin (Theorem 9.2 in third edition pp. 205).

If a vector space $X$ is spanned by r vectors, then dimension($X$)$\leq r$

The proof goes as follows:

If this is false, there is a vector space $X$ which has an independent set $Q=\{y_1,\dots ,y_{r+1} \}$ which is spanned by the set $S_0$ consisting of $r$ vectors. We construct $S_i$ from $S_0$ by replacing $i$ of its elements by members of $Q$, without altering the span.

I am unable to follow how can we ensure that the span of $S_i$'s remains the same after the replacement operation.


1 Answer 1


Any of the elements in $Q$ can be written as a linear combination of the elements in $S_0$. Let's say the elements in $S_0$ are $x_1,x_2,...x_r$. Thus, we have: $$y_i=\alpha_{i,1}x_1+\alpha_{i,2}x_2+...+\alpha_{i,r}x_r \text{ for some scalars } \alpha_{i,j}$$ Now, let's say for some $y_i$, $\alpha_{i,j}$ is non-zero. Then, in $S_0$, we can replace $x_j$ with $y_i$ and we will still have the same span because $x_j$ can be found by subtracting $y_i$ by the other vectors in $S_0$ and then dividing by $\alpha_{i,j}$: $$x_j=\frac{y_i-\alpha_{i,1}x_1-\alpha_{i,2}x_2-...-\alpha_{i,j-1}x_{j-1}-\alpha_{i,j+1}x_{j+1}-...-\alpha_{i,r}x_r}{\alpha{i,j}}$$ Thus, we replace $x_j$ with $y_i$ to get $S_1$.

Now, since $S_1$ spans $X$, we re-write all of the $Q$ as the following: $$y_l=\beta_{l,1}x_1+\beta_{l,2}x_2+...+\beta_{l,j}y_j+...+\beta_{l,r}x_r \text{ for some scalar } \beta_{l,k}$$ Thus, we have new coefficients because of the new set $S_1$. However, there still exists a $y_l$ such that some $\beta_{l,k}$ is non-zero for $k \neq j$ because otherwise, all of the $y_l$ would be a linear combination of $y_i$, which would make $Q$ linearly dependent. Therefore, we can replace another element in $S_1$ as we did in $S_0$ by replacing $x_k$ with $y_l$.

Then, we get $S_2$ and we re-write the coefficients again. However, there is still some non-zero coefficient of an $x_n$ in one of the $y_m$s because otherwise, all of the elements in $Q$ would be a linear combination of $y_i$ and $y_l$, which would make $Q$ linearly dependent, so we replace $x_n$ with $y_m$ to get $S_3$.

Thus, we keep going with this until we get to $S_r$, at which point there are no $x_i$ vectors left and the last $r+1^{\text{th}}$ has to be a linear combination of the other $r$ vectors, contradicting the linear independence of $Q$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .