[proofplan] We start with a linearly independent list $(u_1, \ldots, u_m)$ and a fixed basis $(w_1, \ldots, w_n)$ of $V$. We iteratively attempt to append each $w_j$ to the current list: if adjoining $w_j$ preserves linear independence, we keep it; if not, we discard it. The resulting list is linearly independent by construction. It is a basis because it spans $V$: every $w_j$ that was discarded was already in the span of the current list, so by induction the entire basis $(w_1, \ldots, w_n)$ lies in the span of the final list. [/proofplan] [step:Fix a basis and define the extension algorithm] Since $V$ is finite-dimensional, there exists a basis $(w_1, \ldots, w_n)$ of $V$. We construct a sequence of lists $B_0, B_1, \ldots, B_n$ as follows: - $B_0 := (u_1, \ldots, u_m)$, the given linearly independent list. - For $j = 1, \ldots, n$: if the list $B_{j-1}$ concatenated with $(w_j)$ is linearly independent, set $B_j := B_{j-1} \cup (w_j)$. Otherwise, set $B_j := B_{j-1}$. - The final list is $B := B_n$. [/step] [step:Verify that $B$ is linearly independent] At stage $j = 0$, the list $B_0 = (u_1, \ldots, u_m)$ is linearly independent by hypothesis. At each subsequent stage, we adjoin $w_j$ to $B_{j-1}$ only if the resulting list remains linearly independent. If we do not adjoin $w_j$, then $B_j = B_{j-1}$, and independence is inherited. By induction on $j$, the list $B_j$ is linearly independent for every $j = 0, 1, \ldots, n$. In particular, $B = B_n$ is linearly independent. [/step] [step:Show that $B$ spans $V$ by tracing each discarded $w_j$] We show that $w_j \in \operatorname{span}(B)$ for every $j = 1, \ldots, n$. Since $(w_1, \ldots, w_n)$ is a basis of $V$, this implies $V = \operatorname{span}(w_1, \ldots, w_n) \subset \operatorname{span}(B)$, and therefore $\operatorname{span}(B) = V$. There are two cases for each $j$: **Case 1:** $w_j$ was adjoined (i.e., $w_j$ is an element of $B_j$ and hence of $B$). Then $w_j \in \operatorname{span}(B)$. **Case 2:** $w_j$ was not adjoined. This means that $B_{j-1}$ concatenated with $(w_j)$ is linearly dependent. Since $B_{j-1}$ is itself linearly independent (established in the previous step), the [Equivalent Characterization of Dependence](/theorems/3260) (implication $(1) \implies (2)$) guarantees that some vector in the concatenated list lies in the span of the others. We claim that $w_j$ itself must be the redundant vector, i.e., $w_j \in \operatorname{span}(B_{j-1})$. Indeed, by the implication $(1) \implies (2)$ in the [Equivalent Characterization of Dependence](/theorems/3260), there is a nontrivial dependence relation $\sum a_i v_i + c \, w_j = 0$ (summing over the entries $v_i$ of $B_{j-1}$). If $c = 0$, then $\sum a_i v_i = 0$ is a nontrivial relation among the entries of $B_{j-1}$, contradicting the linear independence of $B_{j-1}$. Therefore $c \neq 0$, and solving for $w_j$ gives $w_j = -c^{-1} \sum a_i v_i \in \operatorname{span}(B_{j-1})$. Since $B_{j-1} \subset B$, we have $\operatorname{span}(B_{j-1}) \subset \operatorname{span}(B)$, so $w_j \in \operatorname{span}(B)$. In both cases, $w_j \in \operatorname{span}(B)$. [guided] We need to verify that the final list $B$ spans all of $V$. Since $(w_1, \ldots, w_n)$ is a basis, it suffices to show each $w_j$ is in $\operatorname{span}(B)$. If $w_j$ was kept (adjoined to the list), it is literally in $B$, so it is in $\operatorname{span}(B)$. The interesting case is when $w_j$ was discarded. This happened because $B_{j-1} \cup (w_j)$ was linearly dependent while $B_{j-1}$ was linearly independent. What can we conclude? A key subtlety: the [Equivalent Characterization of Dependence](/theorems/3260) says that in a dependent list, some vector is in the span of the others. But which vector? Could it be one of the vectors from $B_{j-1}$ rather than $w_j$? No. If the redundant vector were some $v_p \in B_{j-1}$, then removing $v_p$ from $B_{j-1} \cup (w_j)$ would not change the span. But more directly: a dependence relation $\sum a_i v_i + c \, w_j = 0$ with $c = 0$ would give $\sum a_i v_i = 0$ as a nontrivial relation among the entries of $B_{j-1}$, contradicting the independence of $B_{j-1}$. So $c \neq 0$, and we can solve: $w_j = -c^{-1} \sum a_i v_i \in \operatorname{span}(B_{j-1}) \subset \operatorname{span}(B)$. This is the heart of the argument: every $w_j$ that fails the independence test is already expressible in terms of vectors we have kept. So by the time we finish processing all $n$ basis vectors, every $w_j$ is in $\operatorname{span}(B)$, and therefore $\operatorname{span}(B) = V$. [/guided] [/step] [step:Conclude that $B$ is a basis extending the original list] The list $B = B_n$ is linearly independent (by the second step) and spans $V$ (by the third step), so $B$ is a basis of $V$. By construction, $B$ begins with the original list $(u_1, \ldots, u_m)$ and appends some subset of $(w_1, \ldots, w_n)$. Therefore $B$ is an extension of $(u_1, \ldots, u_m)$ to a basis of $V$. Note that by the [Independent Lists Cannot Exceed Spanning Lists in Size](/theorems/3262), the length of $B$ equals $\dim V$, and $m \le \dim V$, confirming that the extension is always possible. [/step]