[proofplan] We first choose an ordered basis of the subspace $U$. Then we extend this linearly independent list to a basis of the whole finite-dimensional space $V$ by adjoining vectors outside its span until the span becomes all of $V$. Ordering the extended basis so that the vectors from $U$ occur first gives an ordered basis whose initial segment is exactly a basis of $U$, which is the definition of being adapted to $U$. [/proofplan]

[step:Choose an ordered basis of the subspace $U$] Let $m=\dim U$. Since $U$ is a finite-dimensional [vector space](/page/Vector%20Space) over $k$, there exists an ordered basis \begin{align*}\mathcal U=(u_1,\ldots,u_m)\end{align*} of $U$. If $m=0$, this means $\mathcal U$ is the empty ordered list, and its span is the zero subspace $U=\{0\}$. Thus the list $(u_1,\ldots,u_m)$ is linearly independent in $U$. Since $U\subset V$, the same list is also linearly independent in $V$: any relation \begin{align*}a_1u_1+\cdots+a_mu_m=0\end{align*} with scalars $a_1,\ldots,a_m\in k$ is a relation in $U$, so $a_1=\cdots=a_m=0$ because $\mathcal U$ is a basis of $U$. [/step]

[step:Extend the basis of $U$ to a basis of $V$]We extend the linearly independent list $(u_1,\ldots,u_m)$ in $V$ to a basis of $V$. [claim:Any finite linearly independent list in $V$ extends to a basis of $V$] Let $(w_1,\ldots,w_r)$ be a linearly independent list in the finite-dimensional vector space $V$. Then there exist vectors $z_1,\ldots,z_s\in V$ such that \begin{align*} (w_1,\ldots,w_r,z_1,\ldots,z_s) \end{align*} is a basis of $V$. [/claim] [proof] Let $L_0=(w_1,\ldots,w_r)$, and let $W_0=\operatorname{span}(L_0)$ denote the subspace of $V$ spanned by this list. If $W_0=V$, then $L_0$ already spans $V$, and since it is linearly independent, it is a basis of $V$. Suppose instead that $W_0\neq V$. Choose $z_1\in V\setminus W_0$. Then the list \begin{align*} L_1=(w_1,\ldots,w_r,z_1) \end{align*} is linearly independent. Indeed, if \begin{align*}a_1w_1+\cdots+a_rw_r+b_1z_1=0\end{align*} with $a_1,\ldots,a_r,b_1\in k$, then $b_1\neq 0$ would imply \begin{align*}z_1=-b_1^{-1}(a_1w_1+\cdots+a_rw_r)\in W_0,\end{align*} contrary to the choice of $z_1$. Hence $b_1=0$, and then $a_1=\cdots=a_r=0$ by [linear independence](/page/Linear%20Independence) of $(w_1,\ldots,w_r)$. Repeat this construction: after choosing $z_1,\ldots,z_j$, let \begin{align*}L_j=(w_1,\ldots,w_r,z_1,\ldots,z_j)\end{align*} and let $W_j=\operatorname{span}(L_j)$. If $W_j\neq V$, choose $z_{j+1}\in V\setminus W_j$, and the same argument shows that $L_{j+1}$ remains linearly independent. Because $V$ is finite-dimensional, no linearly independent list in $V$ can have length greater than $\dim V$. Therefore this process must stop after finitely many steps. Thus for some $s\geq 0$, the list \begin{align*} (w_1,\ldots,w_r,z_1,\ldots,z_s) \end{align*} is linearly independent and spans $V$. Hence it is a basis of $V$. [/proof] Applying the claim to the linearly independent list $(u_1,\ldots,u_m)$ in $V$, we obtain vectors $v_{m+1},\ldots,v_n\in V$ such that \begin{align*} (u_1,\ldots,u_m,v_{m+1},\ldots,v_n) \end{align*} is a basis of $V$.[/step]

[guided]The goal of this step is to keep the basis vectors already chosen inside $U$ and add only as many new vectors as are needed to span $V$. We start with the list $(u_1,\ldots,u_m)$, which is linearly independent in $V$ by the previous step. Let $W_0=\operatorname{span}(u_1,\ldots,u_m)\subset V$. If $W_0=V$, then the list $(u_1,\ldots,u_m)$ is already both linearly independent and spanning in $V$, so it is a basis of $V$. In that case no new vectors are needed. If $W_0\neq V$, choose a vector $v_{m+1}\in V\setminus W_0$. This choice is precisely what preserves linear independence. Indeed, if \begin{align*}a_1u_1+\cdots+a_mu_m+bv_{m+1}=0\end{align*} with $a_1,\ldots,a_m,b\in k$, then $b\neq 0$ would force \begin{align*}v_{m+1}=-b^{-1}(a_1u_1+\cdots+a_mu_m)\in W_0,\end{align*} contradicting $v_{m+1}\notin W_0$. Therefore $b=0$, and then $a_1=\cdots=a_m=0$ because $(u_1,\ldots,u_m)$ is linearly independent. Now repeat the same construction. After vectors $v_{m+1},\ldots,v_{m+j}$ have been chosen, define \begin{align*} W_j=\operatorname{span}(u_1,\ldots,u_m,v_{m+1},\ldots,v_{m+j}). \end{align*} If $W_j\neq V$, choose $v_{m+j+1}\in V\setminus W_j$. The same coefficient argument proves that adjoining $v_{m+j+1}$ preserves linear independence. Why must this stop? Because $V$ is finite-dimensional. A linearly independent list in $V$ cannot have more than $\dim V$ vectors, so the process cannot continue indefinitely. When it stops, the current list is still linearly independent and its span is all of $V$. Thus for some $n\geq m$, \begin{align*} (u_1,\ldots,u_m,v_{m+1},\ldots,v_n) \end{align*} is a basis of $V$.[/guided]

[step:Order the extended basis so that the initial segment spans $U$] Define the ordered list \begin{align*} \mathcal B=(v_1,\ldots,v_n) \end{align*} by setting $v_i=u_i$ for each $i\in\{1,\ldots,m\}$ and using the vectors $v_{m+1},\ldots,v_n$ obtained in the previous step for the remaining entries. By construction, $\mathcal B$ is an ordered basis of $V$. Its initial segment is \begin{align*} (v_1,\ldots,v_m)=(u_1,\ldots,u_m), \end{align*} which is an ordered basis of $U$. Therefore $\mathcal B$ is adapted to $U$. This proves the existence of an ordered basis of $V$ adapted to $U$. [/step]