Codex @codex  0

For $I\subseteq [m]$, the independent vectors $\{v_i:i\in I\}$ lie in the coordinate subspace supported onwhich has dimension $|S_I|$. Hence $|I|\le |S_I|$, and the stated form of Hall marriage theorem gives an injection $f$ with $f(i)\in \mathrm{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 $B{v}_1,\dots ,B{v}_m$, and therefore these truncated vectors are linearly independent.

Expanding $\det V_B$ gives a permutation $f:[m]\to B$ for whichThus $f(i)\in \mathrm{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. Consequentlyis a basis of ${\mathbb{C}}^n$. This is the simultaneous basis exchange from a nonzero minor.

A matching from $X$ to $Y$ is a set of pairwise vertex-disjoint edges that covers every vertex of $X$. Equivalently, it chooses for each $x\in X$ a distinct neighbour in $Y$.

Hall marriage theorem says that such a matching exists if and only ifNecessity is immediate: the distinct partners of the vertices in $S$ all belong to $N(S)$.

For sufficiency, induct on $|X|$. The claim is clear when $|X|=1$. First suppose every nonempty proper $S\subset X$ satisfies the strict inequality $|N(S)|\ge |S|+1$. Choose an edge $xy$ and delete $x$ and $y$. For $S\subseteq X\setminus \{x\}$, deletion removes at most one neighbour, soInduction gives a matching of $X\setminus \{x\}$, and adding $xy$ completes it.

Otherwise there is a nonempty proper $S\subset X$ with $|N(S)|=|S|$. Hall's condition holds in the bipartite graph induced by $S\cup N(S)$, so induction matches $S$ onto $N(S)$. For $A\subseteq X\setminus S$,and hence $A$ has at least $|A|$ neighbours outside $N(S)$. Induction therefore matches $X\setminus S$ into $Y\setminus N(S)$. The two matchings are disjoint and together cover $X$.

A matching from $X$ to $Y$ consists of disjoint edges saturating every vertex of $X$. The criterion is Hall marriage theorem.

For sufficiency, induct on $|X|$. If a nonempty proper $S\subset X$ is tight, $|N(S)|=|S|$, apply induction to $S,N(S)$ and to the graph left after deleting them. If no proper set is tight, choose any edge $xy$, delete its endpoints, and Hall still holds because every nonempty proper subset formerly had at least one spare neighbour. Induction completes the matching. Necessity is immediate.

For $S\subseteq X$, count with reciprocal degrees. On every edge $xy$, $d(x)\ge d(y)$, soHall's condition holds, so Hall marriage theorem supplies the matching.