# Proof that linearly independent lists extend to a basis

In Axler's Linear Algebra Done Right there is the posit that every linearly independent list of vectors in a finite-dimensional vector space can be extended to a basis of the vector space. This seems fine, intuitively, but I don't understand his proof. He states:

Suppose a linear independent list, $u_1$ , ... , $u_m$ exists in vector space V. V also has a basis $w_1$ , ... , $w_m$.

1) If one creates a list $u_1$ , ... , $u_m$ , $w_1$ , ... , $w_m$, that means you now have another list that spans V.

2) Further, he says that if you remove any $w_j$ elements within the new list, you're able to create a basis as long as you don't remove any $u_j$ elements, as that original list of $u_j$ elements is linearly independent.

My questions are regarding 1) and 2). For 1): How is this new list a span of V? And for 2): Why does he emphasize that you need to remove $w_j$ elements and not $u_j$? Since the $w_j$ elements were originally from a basis, aren't they linearly independent, also?*

Consider the list $u_1,\dots,u_m,w_1,\dots,w_n$ (I'll call it the big list), where $u_1,\dots,u_m$ is linearly independent (I'll call it the $u$-list) and $w_1,\dots,w_n$ is a basis.

Clearly the big list is a spanning set. If it is already linearly independent, then you're done (actually the $u$-list would be empty, but it's irrelevant).

Otherwise the big list is linearly dependent, so we can write $$\alpha_1u_1+\dots+\alpha_mu_m+\beta_1w_1+\dots+\beta_nw_n=0$$ where not all the coefficients are zero. Actually one among $\beta_1,\dots,\beta_n$ must be non zero, otherwise we'd have $\alpha_1u_1+\dots+\alpha_mu_m=0$ and linear independence of the $u$-list would imply also $\alpha_1=\dots=\alpha_m=0$.

Without loss of generality, we can assume $\beta_n\ne0$ (reordering a basis still gives a basis). Hence also the list $u_1,\dots,u_m,w_1,\dots,w_{n-1}$ is a spanning set.

Proceed in the same way until the set you have is linearly independent, which must happen in at most $n$ steps. Since at every stage the list after the removal is still a spanning set, the final list will be linearly independent and a spanning set, hence a basis.

1. Why is the big list a spanning set? Because every list containing a spanning set is a spanning set as well.

2. Why emphasizing that elements of the $w$-list are removed? Because if we remove items from the $u$-list we won't get a list that extends the $u$-list.

Note that in the context of your second question, you cannot remove any item in the $w$-list, but you have to choose one in a suitable way, as outlined above.

• Perfect answer. Thanks. – Shocked Jul 12 '17 at 15:07
• @Shocked If you are satisfied with this answer, then don't forget to accept it. – Our Jul 12 '17 at 15:26

For the question $1-)$: Let $x\in V$, so $x= \sum_v \lambda_v w_v$ and also $x= \sum_v \lambda_v w_v + \sum_k 0 \cdot u_k$, so the list spans $V.$

For the question $2-)$: Since you want to create a basis containing the vectors $u_1, ..., u_m$, you don't remove them basically.

Actually, the author kind of using Steinitz exchange theorem, so you might want to check it out.

• so it's not that the list with $w_j$ elements automatically becomes linearly dependent or anything, right? It just seemed that way from his wording. – Shocked Jul 12 '17 at 14:24