= Solution
For $I\subseteq[m]$, the independent <vectors> $\{v_i:i\in I\}$ lie in the coordinate subspace supported on
$$
S_I=\bigcup_{i\in I}\operatorname{supp}(v_i),
$$
which has dimension $|S_I|$. Hence $|I|\leq|S_I|$, and the stated form of <Hall marriage theorem> gives an injection $f$ with $f(i)\in\operatorname{supp}(v_i)$.
Let $V$ be the $n\times m$ <matrix> whose $i$th column is $v_i$. Its column rank is $m$. By equality of row and column rank, it has $m$ linearly independent rows. Let $B$ be their indices. The $m\times m$ submatrix $V_B$ is invertible, so its columns are independent. Those columns are exactly the nonzero coordinates of $Bv_1,\ldots,Bv_m$, and therefore these truncated <vectors> are linearly independent.
Expanding $\det V_B$ gives a permutation $f:[m]\to B$ for which
$$
\prod_{i=1}^m (v_i)_{f(i)}\ne0.
$$
Thus $f(i)\in\operatorname{supp}(v_i)$. Finally, order the coordinates with $B$ first. The <matrix> whose columns are the $v_i$ together with the $e_j$ for $j\notin B$ is block triangular, with diagonal blocks $V_B$ and an identity <matrix>. Its <determinant> is nonzero. Consequently
$$
\boxed{
\bigl(\{e_j:j\in[n]\}\setminus\{e_{f(i)}:i\in[m]\}\bigr)
\cup\{v_i:i\in[m]\}
}
$$
is a <basis> of $\mathbb C^n$. This is the <simultaneous basis exchange from a nonzero minor>.
Back to article page
